References: <4EA7DB88.7020906@residenset.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
User-Agent: Mutt/1.5.21 (2010-09-15)
Message-ID:  <20111026105033.GA8500@csmvddesktop>
Date:         Wed, 26 Oct 2011 11:50:33 +0100
Reply-To: Mailing list for the LaTeX3 project
              <LATEX-L@listserv.uni-heidelberg.de>
Sender: Mailing list for the LaTeX3 project <LATEX-L@listserv.uni-heidelberg.de>
From: dongen <dongen@CS.UCC.IE>
Subject: Re: S combinator and such
To: LATEX-L@listserv.uni-heidelberg.de
In-Reply-To:  <4EA7DB88.7020906@residenset.net>
Precedence: list
Status: R

* Lars Hellström <Lars.Hellstrom@RESIDENSET.NET> [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