[Richard Suchenwirth] 2002-11-30 - An innocent question in the [Tcl
chatroom] from me, after reading
[http://openmap.bbn.com/~kanderso/building/closure],
brought [DKF] to produce the following amazing Tcl code. The
background is functional programming, and the discovery of M.
Schoenfinkel in 1924 that all functions can be composed from the
elementary combinators S and K, which can be written in Tcl as:
 proc S {f g x} {$f $x [$g $x]}
 proc K {x y} {set x}
However, to reproduce the various derivations, some work was
necessary, because function "calls" might have more or less than their
defined arguments. At toplevel, Donal creates a function ''curry'' that
is called like [proc], but prepares for cases where the argument count
differs from the one specified:}
 proc curry {name arglist body} {
    proc ${name}_impl $arglist $body ;# the "real thing"
    interp alias {} $name {} _curry_impl $name [llength $arglist]
 }
if 0 {The generic curry implementation calls the "real thing" if the
number of arguments matches, else does some pretty dense voodoo (means:
I at least do look at it, but don't understand the details), mostly
due to the fact that [eval] runs best with a single pure list:}
 proc _curry_impl {name len args} {
    set nArgs [llength $args]
    set L_1 [expr {$len-1}]
    if {$nArgs > $len} {
        eval [linsert [lrange $args $len end] 0 \
           [eval [linsert [lrange $args 0 $L_1] 0 ${name}_impl]]]
    } elseif {$nArgs < $len} {
        linsert $args 0 $name
    } else {
        eval [linsert $args 0 ${name}_impl]
    }
 }
 curry S {f g x} {$f $x [$g $x]}
 curry K {x y} {set x}
if 0 {Donal also required the following enhancement to the [unknown]
handler, which flattens list-like commands, e.g. ''{a b c} d'' gets
turned into ''a b c d'':}
  proc unknown args [string map [list @ [info body unknown]] {
    set arg0 [lindex $args 0]
    if {[llength $arg0] > 1} {
        return [uplevel 1 $arg0 [lrange $args 1 end]]
    }
 @}]
if 0 {With these parts in place, we can start experimenting. The first
claim is that the identity function I (which in Tcl would be just
 proc I x {set x}
) is the composition of ''S K K''. Let's try: 
 % [S K K] x
 x
 % [S K K] 4711
 4711
 % curry I x {S K K $x} ;# let's commit that derivation
Looks right. Next to try a "warbler" W, that applies a function
to its duplicated argument. For this we need a workhorse function: just
extract multiplication from [expr], and try whether [[W f x]] is indeed
[[S f I x]], as the tutorial says:
 proc * {x y} {expr $x*$y}
 % S * I 5
 25
 % curry W {f x} {S $f I $x} ;# committed too
 % W * 6 ;# multiply 6 with itself
 36
Currying itself is the B ("bluebird") combinator,
''B f g x'' == ''f ( g x)''. So let's curry B, and another single argument
function that just increments:
 % curry B {f g x} {$f [$g $x]}
 % curry +1 x      {incr x}
 % B +1 +1 40
 42
C is "cardinal", curry second arg first:
 % curry C {f g x} {$f $x $g}
 % C I 5 +1 ;# T ("thrush"), T x f == f x, T == C I
 6
 % curry T {x f} {C I $x $f}
 T
What I could not get to work is M ("mocking bird"), which just returns
its argument doubled: ''M x == x x == S I I x'':
 % S I I x
 invalid command name "x"
Trouble seems to be that evaluation in Tcl does not stop at constants,
but "everything is a command", which x does not satisfy.
}

[KBK] 2002-12-02 No, Richard, you're fine so far!  M x == x x == the result of x applied as a function to itself.
Consider:
 % S I I puts
 puts
 % proc x y { return "x($y)" }
 % S I I x
 x(x)

Everything looks fine for M.

Also, S and K are fundamental, all the others really, really should be defined in terms of them.  How about:

    I x = x = S K K x
    B f g x = f [g x] = S [K [S [S [K S] K]]] K f g x
    C f g x = f x g = S [S [K S] [S [K K] S]] [K K] f g x
    T x f = f x = C I x f
    W f x = f x x = S f I x = S S [K I] f x