Hot curry

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 Combinatory Logic and 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} {
   # We're going to implement the curried command using a pair of helper procedures
   interp alias {} $name {} _curry_impl $name [llength $arglist]
   # Create the command-specific helper
   proc ${name}_impl $arglist $body ;# the "real thing"
   # Arrange for the helper to go away when the front-end vanishes.
   trace add command $name delete [list _curry_nuke $name]
}

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:
}

Lars H: Sorry to interrupt, but isn't it simply as follows: the function does not evaluate unless the necessary number of arguments are available (i.e., the command evaluates to itself), whereas if there are are more arguments available than necessary, then the function leaves the extra arguments up ahead as arguments for some other function?


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]
    }
}
proc _curry_nuke {name args} {
    catch {
        rename ${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

Lars H: The following should make x act like a constant (anything beginning with x expands to itself)

 interp alias {} x {} list x

but perhaps a more useful behaviour would be to evaluate everything following the x, like

 proc x {args} {linsert [eval $args] 0 x}

According to the claim at the top, though, both of these should be possible to define using only curry, S, and K. I wonder how.

Also, if one is to analyse these things properly (determine how much can be implemented using them) then one must probably be clear about what kinds of grouping are allowed. Can {} and [] behave differently here?

KBK Without answering Lars's questions fully, let's observe that the implementation shown does eager evaluation, where all arguments to a combinator are evaluated prior to evaluating the combinator itself. This method gets us into trouble as we get into more advanced combinator theory.

In particular, I tried to implement the factorial function with the fixed-point combinator Y:

    A = B [S I] [S I I]
    Y = A A
    f = K {S {{S zero?} {K 1}}}} {S {K {S *}} {S {S {K S} K} {K {{S -} {K 1}}}}
    factorial = Y f

for an appropriate definiton of [zero?]. The eager evaluation made it infinitely recursive. I wasted entirely too much time changing things to do lazy evaluation instead, and wound up with a different Combinator Engine.


DKF - When defining the derived combinators, it's easier if you do it like this:

  proc define {symbol = args} {
     curry $symbol {} [string map "\\\{ \[ \\\} \]" $args]
  }
  define I = S K K
  define B = S {K {S {S {K S} K}}} K
  define C = S {S {K S} {S {K K} S}} {K K}
  define T = C I
  define W = S S {K I}