Version 1 of Hot curry

Updated 2002-12-02 09:07:51

Richard Suchenwirth 2002-11-30 - An innocent question in the Tcl chatroom from me, after reading [L1 ], 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. }