Church numerals: Difference between revisions

Line 695:

<pre>(funcall f ...)</pre>

(<code>Funcall</code> is also needed when the function is the value of a more complex expression, rather than just a variable.)

<code>Funcall</code> is also needed when the function is the value of a more complex expression, rather than just a variable.

Suppose ''n'' is a Church numeral and we want to use it to call a function, ''g'', ''n'' times on a value, ''v''. Here's how that would be written:

<pre>

(funcall n g v) ; uncurried n

(funcall (funcall n g) v) ; curried n

</pre>

===Uncurried Church numerals===

Line 783:

Line 790:

</syntaxhighlight>

The remaining definitions, the calls to <code>show</code>, and the resulting output are the same as the version that uses uncurried numerals.

The remaining definitions, the calls to <code>show</code>, and the resulting output are the same as in the version that uses uncurried numerals.

===Further Church ~~numerals~~===

===Further Church functions===

The predecessor of a Church numeral ''n'' has to call the function it's given one fewer times than ''n'' would. How can that be arranged? The trick used here is that the predecessor doesn't call ''f'' directly; instead ''f'' is given to a ''container function'' that can call ''f'' or not.

<code>Value</code> returns a container that calls the function; <code>const</code> is a container that doesn't. <code>Inc</code>, given a container, calls the container on ''f'' and returns the result in a calling container. The predecessor uses ''n'' to call <code>inc</code> ''n'' times but gives it a non-calling container (<code>const</code>) initially. So ''f'' isn't called the first time ''n'' calls <code>inc</code> but is called each time thereafter. This process therefore calls ''f'' ''n-1'' times.

<code>Extract</code> gets the value out of a container by giving the container the identity function and is used only at the end.

Line 799:

Line 812:

(funcall n #'pred m))

</syntaxhighlight>

<code>Minus</code> returns <code>zero</code> for ''m-n'' if ''n > m''.

For boolean values, we'll use functions of two functional arguments. <code>True</code> calls its first argument; <code>false</code> calls its second. This lets us write conditional expressions and a <code>church-if</code> macro.

Line 807:

Line 824:

(defvar false (lambda (f g) (funcall g)))

</syntaxhighlight>

Division of ''m'' by ''n'' can now be defined by counting the number of times ''n'' can be subtracted from ''m+1'' while leaving a non-zero result.

Line 820:

Line 839:

zero

(succ (divide1 d n)))))

</syntaxhighlight>

Examples:

(show '(pred four))

(show '(minus (church 11) three))

Line 838:

Line 860:

===Further, curried===

Again, the remaining definitions, the calls to <code>show</code>, and the resulting output are the same as in uncurried version.

Again, the remaining definitions, the calls to <code>show</code>, and the resulting output are the same as in the uncurried version.