* 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