Anonymous user
Church numerals: Difference between revisions
→{{header|Common Lisp}}
imported>Rowsety Moid |
imported>Rowsety Moid |
||
Line 695:
<pre>(funcall f ...)</pre>
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 ⟶ 790:
</syntaxhighlight>
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
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.
<syntaxhighlight lang="lisp">
Line 799 ⟶ 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.
<syntaxhighlight lang="lisp">
Line 807 ⟶ 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.
<syntaxhighlight lang="lisp">
Line 820 ⟶ 839:
zero
(succ (divide1 d n)))))
</syntaxhighlight>
Examples:
<syntaxhighlight lang="lisp">
(show '(pred four))
(show '(minus (church 11) three))
Line 838 ⟶ 860:
===Further, curried===
Again, the remaining definitions, the calls to <code>show</code>, and the resulting output are the same as in the uncurried version.
<syntaxhighlight lang="lisp">
| |||