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 xLars H: The following should make x act like a constant (anything beginning with x expands to itself) interp alias {} x {} list xbut 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 ffor 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}