* Lars Hellström <[log in to unmask]> [2011-10-26 12:06:00 +0200]:
: Continuing my reading up on Lambda calculus and related matters,
: I've now gotten to the Combinatory logic
: (http://en.wikipedia.org/wiki/Combinatory_logic), which also turns
: out to be much easier to understand when one transcribes the whole
: thing into LaTeX macros. :-) In particular, there are
:
: \cs_new:Npn \combinator_I:n #1 { #1 } % AKA \use_i:n
: \cs_new:Npn \combinator_K:nn #1 #2 { #1 } % AKA \use_i:nn
: \cs_new:Npn \combinator_S:nnn #1 #2 #3 { #1{#3}{ #2{#3} } }
: \cs_new:Npn \combinator_B:nnn #1 #2 #3 { #1{ #2{#3} } }
: \cs_new:Npn \combinator_C:nnn #1 #2 #3 { #1{#3}{#2} }
:
: My thought with this mail is mainly to ask whether there are any
: more of these (or other standard combinators) that are defined in
: LaTeX3 already. I seem to recall some discussion to the effect that
: the C combinator might be named \use_i_biii_bii:nnn, but I haven't
: seen any occurrence in the source of such _bii_ names (then again,
: maybe I'm not looking close enough). Continuing such a naming
: scheme, one would arrive at maybe
:
: \use_i_biibiii:nnn for the B combinator
: \use_i_biii_biibiii:nnn for the S combinator
:
: which does not seem entirely practical...
I've been reading this thread for a while and I've used these combinators
to implement some simple arithmetic. (IIRC it uses Church Numerals and
the arithmetic is called Church Arithmetic.) For example, I could write
something like the following (rewritten for readability):
<numeral> X to get <numeral> copies of X, so <2> a -> aa.
<numeral> + <numeral> to get <numeral + numeral>, so (<1> + <2>)a -> aaa,
<numeral> - <numeral> to get <numeral - numeral>, and so on. This is
all well understood.
You can define any lambda expression (and therefore LaTeX) in terms of
the S and K you mention. See for example [Curry:Feys:Craig:68], which
also mentions some other names for commonly used combinators.
These combinators are __hopelessly__ inefficient. For example, the
following definitions are from ``LaTeX and Friends:''
\newcommand\K[2]{#1}
\newcommand\S[3]{#1#3{#2#3}}
\newcommand\I{\S\K\K}
\newcommand\X{\S{\K{\S\I}}{\S{\K\K}\I}}
The combinator \X is defined in terms of \S and \K. All it does is swop
its (two) arguments, so ``\X ab'' gives ``ba.'' Using ``\Xab'' requires
17 reductions, which is sad because X is pretty simple.
@BOOK{Curry:Feys:Craig:68,
title = {Combinatory Logic},
author = {Curry, H.\,B. and
Feys, R. and
Craig W.},
editor = {Heyting, A. and
Robinson, A. and
Suppes, P. and
Motowski, A.},
publisher = {North-Holland},
series = {Studies in Logic {and the Foundations of Mathematics}},
year = {1968},
volume = {I}}
Regards,
Marc van Dongen
|
