## Tcl Lambda Abstractionwritten 25 February 2002 being revised May 2006 |

Tcl distinguishes functions (procedures or commands) from variables. They occupy different namespaces. In particular all Tcl procedures have global scope even if declared within another procedure which means that their proliferation has to be managed. Tcl variables on the other hand have local scope within procedures.

$\lambda $-calculus and functional language recognise only functions. Within the context of Tcl, lambda abstractions are assigned to variables. Assigning $\lambda $-abstractions to procedures would acheive no useful result by definition and is a pointless exercise. $\lambda $-abstractions are procedures masquerading as variables and as such they have local scope.

Variables in Tcl have a functional representaion in the form of the command 'set var' or the phrase [set var]. There is an important difference between these and the $var convention in that they are substituted in Tcl by different processes, command and variable substitution respectively. This can be controlled by the Tcl **[subst]** command (substitute).

The way the **[lambda]** procedure works is illustrated by example. The example chosen is the classic lambda constructor, head and tail expressions though we will only use cons and head. The cons expression glues two objects together like the node of a binary tree and is defined as follows :

set cons {lambda { x y f } {$f $x $y}}The head expression returns the left node and is defined:

set head {lambda c {$c {lambda {x y} {$x}}}}Similarly for tail:

set tail {lambda c {$c {lambda {x y} {$y}}}}

This is not the usual notation for lambda abstraction. Because we dont have a $\lambda $ sign we use the word "lambda" instead. This is then followed by the parameter list for **bound variables**, and then followed by the **body**. The parentheses are replaced by braces to mimic Tcl convention. So a lambda abstraction can be read as a kind of proc command where the proc name has been left out. It can also be read statically as an object consisting of an ordered pair, namely a paramter list and a body, prescribed with the type of *lambda* and with an associated method, the lambda procedure, which "normalises" a lambda object.

Within lambda abstractions the $var convention is used in the usual way. [lambda] acts like other control structure commands such as [foreach] and prefixes the body with a [set] command to effect variable substitution. In theory this should be done "in situ", but in order to avoid name clash problems **set** commands are inserted at the head of the body instead. This makes use of Tcl's local variable scope to avoid parameter name clashes in nested lambda expressions. The "in situ" method would require the parsing of the expression and its subexpressions to determine the scope of bound variables, and also a name substitution operator for when name clashes occur. Tcl already takes care of these details for us.

Either technique is valid if the notion is upheld that the parameter's value remains unchanged within the lambda expression. It is a corruption of lambda abstraction to define a function such as

lambda x { set x [ expr 3 + $x]; puts $x}which changes the value of an argument. There is no simple way of precluding such abuse of the construct and neither "in situ" substitution nor [set ...] prefixes get round this kind of abuse. While "in situ" substitution gives the correct theoretical result, if a programmer does modify the value of an argument, the result will be different from what is expected, though perhaps not obviously so. Using the [set ...] prefix is theoretically incorrect, but is intuitively correct if a programmer does happen to modify the value of an argument. It is also the way that some functional languages implement the construct.

After setting argument values a null statement is executed to ensure that the result of the previous set command is not returned. Lambda functions can also have null bodies, so {} is declared as a valid procedure.

proc {} args {}

According to the definition of cons and head we have that *head ( cons p q ) -> p*. That is if we glue two things p and q together and then take the head ( left ) one we get p. The following calculation works this out symbolically, after which it will be reworked in Tcl so that the features of the lambda procedure itself are made clear.

head { cons p q } | |

= lambda c {$c {lambda {x y} {$x}} } { cons p q } |
by variable substitution and list reduction of the first element |

-> cons p q {lambda {x y} {$x}} |
by currying and lambda reduction and list reduction of the first element |

= lambda {a b f} {$f $a $b} p q {lambda {x y} {$x}} |
by variable substitution and list reduction of the first element |

-> lambda {b f } { $f p $b } q {lambda {x y} {$x}} |
by currying |

-> lambda f {$f p q} {lambda {x y} {$x}} |
by currying |

-> lambda {x y} {$x} p q |
by currying and lambda reduction and list reduction of the first element |

-> lambda {y} {p} q |
by currying |

-> p |
by currying and lambda reduction and list reduction of the first element |

In this instance p and q would typically be commands (functions) such as *set p*, so that an evaluated command is returned.

As can be seen from the example above there are three normalisation processes. Simple currying , lambda reduction with list reduction, and variable substitution with list reduction. The Tcl version will expand the detail of each operation, but will batch the curry operations. In Tcl, substitution of all variables in a command takes place at once. Lambda abstraction defers variable substitution until it is necessary. *cons* and *head* are global to the scope of the lambda abstraction and any other known Tcl variables could be referenced within a lambda abstraction.

lambda {} $head {$cons {set p} {set q}} |
This would be a typical way of invoking the evaluation of a body with arguments which contained lambda abstractions. |

-> $head {$cons {set p} {set q}} |
Lambda reduction because the argument list is empty. Reduce first list element, though in this case the operation is redundant |

-> {lambda c {$c {lambda {x y} {$x}}}} {$cons {set p} {set q}} |
Variable substitution of first list element |

-> lambda c {$c {lambda {x y} {$x}}} {$cons {set p} {set q}} |
List reduction of the first element after variable substitution. |

-> lambda {} {{$cons {set p} {set q}} {lambda {x y} {$x}}} |
By currying. |

-> {$cons {set p} {set q}} {lambda {x y} {$x}} |
Lambda reduction |

-> $cons {set p} {set q} {lambda {x y} {$x}} |
First element list reduction after lambda reduction |

-> {lambda {a b f} {$f $a $b}} {set p} {set q} {lambda {x y} {$x}} |
Variable substitution of first element |

-> lambda {a b f} {$f $a $b} {set p} {set q} {lambda {x y} {$x}} |
First element list reduction after variable substitution |

-> lambda {} {{lambda {x y} {$x}} {set p} {set q}} |
by currying |

-> {lambda {x y} {$x}} {set p} {set q} |
Lambda reduction |

-> lambda {x y} {$x} {set p} {set q} |
First element list reduction after lambda reduction |

-> lambda {} {{set p}} |
By currying |

->{set p} |
Lambda reduction |

->set p |
First element list reduction after lambda reduction. This is not a lambda command so return eval {set p} |

The operations are performed in the following order:

Currying arguments until the parameter list is exhausted. If parameters remain, return a lambda expression. Lambda reduction and first list element reduction. Variable substitution and first list element reduction until a procedure name is encountered which is then evaluated in its own scope.

The reader may wonder why the Tcl command *$head { $cons {set p} {set q}}* cannot be used directly. This is because *$head* is substituted by Tcl not as *lambda c {$c {lambda {x y} {$x}}}....*, but as *{lambda c {$c {lambda {x y} {$x}}}}* which is not a known procedure name. This quirk applies to any use of partial commands in Tcl anywhere regardless of the use of lambda abstractions. It is in evidence in the design of commands like *string* and *list* for which two different paradigms have been employed in the language, making Tcl appear to be an inconsistent language. In the case of *{list range}* the offending space was omitted and the result abbreviated to *lrange* while in the case of *{string range}* an intuitive reduction was used. A third paradigm is *sting_range* and *list_range*. *string range...* is the best of these paradigms because Tcl appears to have been designed with the convention that command names are simple strings, though the language does not admit this limitation.

% proc { expr $x + $y } { x y } { expr $x + $y } % { expr $x + $y } 3 4 7 % proc {} {} { puts "null proc"} % {} null proc

**A Challenge** -
Can anyone find a theoretical basis for the use of procedure names that are more than simple strings in Tcl. There are of course good reasons for not using procedure names containing spaces or braces as they need to be constantly quoted.

Assuming that there is no use for list structured procedure names, and noting that they have been assiduously avoided in the language design it would be appropriate to alter the interpreter so that is reduced "command names" that are nontrivial lists until a simple procedure name is reached. This would allow variables with partial commands to be readily used in Tcl without resorting to the *eval [ concat $partcommand [list $restofcommand]]* construct, which although complicated enough does not do the job for nested partial commands, or for a command sequence.

It is conceivable that existing programs which use non-simple list structured procedure names could be invalidated by such a change. Therefore the reduction process could be added to the *unknown* procedure. This would not invalidate existing programs and it would make partial commands accessable to the language, whereas at present they are impossibly difficult to use. This one change is the key which Tcl needs to equip itself with object and/or functional programming constructs. Tcl itself is already being confronted by this issue as can be seen in such commands as *namespace inscope*.

The following code addresses this issue, although it does not embed the command name reduction in the best place within [unknown].

rename unknown __curry__unknown proc unknown {base args} { set split 0 while {[set first [lindex $base 0]] !=$base} { set split 1 regsub -all \\$ $first {\\$} pfirst regsub $pfirst $base {} rest set args [concat $rest $args] set base $first } if {!$split} {return [uplevel [list __curry__unknown $base] $args]} uplevel $base $args } |

The *while* loop reduces *base* to an initial simple string. Usually this requires only one pass, but *base* could be a deeply nested list. The second *regsub*command is used to get the trail end of the base string without exposing it to the side effects of list processing. Tcl list commands work fine on a single command but "protect" semi-colons and newlines embedded in the function spec, and cannot be used where a string may contain several commands. This is particularly important as *lambda* prepends statements to the body. The first
*regsub* protects $ signs in the match.

This change to *unknown* is useful whether *lambda* is being used or not. It allows the programmer to store partial function references in variables and use them in commands. In the parlance of lambda calculus it is the eta-reduction form of a lambda expression; the special case where *lambda {x} {F x}* <=> *F*. It is used in many places in Tcl and Tk where commands are constructed where the programmer provides the command and Tcl provides the arguments as in Tk -command options or *client -server* option. The reverse, where Tcl/Tk creates commands for which the programmer provides additional arguments, is a fundamental part of the language process but has had one foot nailed to the floor, so to speak.

With this version of *unknown* in place, the lambda procedure simplifies considerably.

$head {$cons {set p} {set q}} |
This is now the way one would invoke a lambda expression |

-> {lambda c {$c {lambda {x y} {$x}}}} {$cons {set p} {set q}} |
Tcl interpreter does variable substitution |

-> lambda c {$c {lambda {x y} {$x}}} {$cons {set p} {set q}} |
unknown pops the first list item |

-> {$cons {set p} {set q}} {lambda {x y} {$x}} |
lambda proc curries and reduces |

-> $cons {set p} {set q} {lambda {x y} {$x}} |
(Tcl evaluation and) popping by the unknown proc |

-> lambda {a b f} {$f $a $b} {set p} {set q} {lambda {x y} {$x}} |
Tcl substitution and pop by unknown |

-> {lambda {x y} {$x}} {set p} {set q} |
lambda proc curries and reduces |

-> lambda {x y} {$x} {set p} {set q} |
(Tcl evaluation and) pop by unknown proc |

->{set p} |
lambda proc curries and reduces |

->p |
(Tcl evaluation,) pop by unkown and evaluation of set (p has value p) |

Here is the code for the *lambda* procedure:

proc {} args {} ; proc lambda {params body args} { set pre "" while { [llength $params ] > 0 && [llength $args] > 0} { if { [llength $params] == 1 && [lindex $params 0] == "args" } { append pre "set args [list $args] ; {} ; " set params {} set args {} } else { append pre "set [lindex $params 0] [list [lindex $args 0]] ; " set params [lrange $params 1 end] set args [lrange $args 1 end] } } set body [concat $pre $body] if { [llength $params] > 0 } { return [list lambda $params $body ] } uplevel $body $args } |

The procedure accommodates the Tcl convention of *args* as a final argument. This is a somewhat dubious extension in regard to the theory of lambda calculus. But more objectionable because the variable name *incr* cannot be rewritten as a simple lambda expression.

One improvement that could be made to the procedure is to check for eta-reduction. As an example, the expr *set sum {lambda {x y} {expr $x + $y}}* could be partially specified as:

% set sum {lambda {x y} {expr $x + $y}} lambda {x y} {expr $x + $y} % set add1 [$sum 1] lambda y {set x 1 ; expr $x + $y} %Here the expression can be simplified by eliminating the reference to y and using Tcl's own currying. The rule is reasonably simple: if the parameter appears as a variable, once only, at the end of the body, then the expression can be reduced. In addition the remainder of the body must represent a function. This is difficult to check in Tcl except perhaps by evaluating and getting an error.

**Exercise** - write the eta-reduction code.

However the primary purpose of the *lambda* proc is to make the lambda abstraction mechanism available. Creating a lambda calculus engine is another task.

A second aspect is whether the lambda parameters should be *unset* after use. There is always the chance that these parameter names clash with other variables in the local scope. Such variable name management is always the responsibility of the programmer so by leaving the variable names in the namespace there is a sense of saying that these parameter names exist in the local scope as persistently as any other variable name. Lambda expressions are not executed in their own scope and this may be a good enough reason not to give the impression that they are executed in a private subscope by attempting to imitate a private subscope for the lambda parameter variables. This convention conforms to the convention used by the control commands, [for], [foreach] etc. How many wizened old programmers are still capable of scrunching their loop control variables?

% set sum {lambda {x y} {expr $x + $y}}is worked through above. If only the value of x is given, then the x assignment is put inside the lambda. Now if we use x for something else later in this procedure and invoke $add1 then the assignment to the variable x will be made in the lambda and the other value of x will be overwritten. This kind of error is difficult to spot.

A second similar kind of bug can occur. If instead we define sum as

% set sum {lambda x {lambda y {expr $x + $y}}} lambda x {lambda y {expr $x + $y}} % set add1 [$sum 1] lambda y {expr $x + $y} % set x 1You can see that the x variable assigbnment is not included in the value of add1. This is because it has already occurred. Now if you reuse x later for something else and then invoke $add1, the later value of x will be used rather than this value (1).

These two traps mean that you should be very careful about using uniue parameter names in the context. Just using x, y, z and evaluating any lambda expression any where can cause problems, just as using i, j, k improperly causes trouble.

One way to avoid this is to test that the variable is NOT being used already, and [unset]ting as soon as the lambda is evaluated.

proc {} args {} ; proc lambda {params body args} { set pre "" ; set suf "" while { [llength $params ] > 0 && [llength $args] > 0} { if { [llength $params] == 1 && [lindex $params 0] == "args" } { append pre "set args [list $args] ; {} ; " set params {} set args {} } else { # append pre "if { \[ info exists [lindex $params 0]\] } { # bgerror \"lambda argument [lindex $params 0] is being used as a variable\" # }" append pre "set [lindex $params 0] [list [lindex $args 0]] ; " append suf "unset [lindex $params 0];" set params [lrange $params 1 end] set args [lrange $args 1 end] } } set body [concat $pre $body ] if { [llength $params] > 0 } { return [list lambda $params $body ] } [uplevel $body $args] } |

% set x 100 100 % set sum {lambda {x y} {expr $x + $y}} lambda {x y} {expr $x + $y} % set add1 [$sum 1] lambda y {if {[info exists x]} {bgerror "lambda argument x is being used as a variable" } set x 1 ; expr $x + $y ; unset x} % $add1 5This raises the error "lambda argument x is being used as a variable". This is as it should be because the variable x is about to be overwritten by the argument x as a postponed side effect.

% set x 100 100 % set sum2 {lambda x {lambda y {expr {$x + $y}}}} lambda x {lambda y {expr {$x + $y}}} % set add2 [$sum2 1]This raises the error "lambda argument x is being used as a variable". This is as it should be because the variable x would have been set to 1, probably inadvertantly.

However the code does not work because the [unset] occurs before the evaluation of the next lower lambda. HOW TO FIX THIS????

% set fac {lambda n {if { $n == 0 } { expr 1 } else { expr $n * [$fac [expr $n-1]]}}} lambda n {if { $n == 0 } { expr 1 } else { expr $n * [$fac [expr $n-1]]}} % $fac 0 1 % $fac 6 720 %This example is little different from a procedure declaration and invocation. The lambda expression has to be assigned to a variable ( effectively a local procedure name ) in order to be invoked by name from within the procedure.

Lambda calculus provides its own recusion abstraction usually called Y which can be applied to the original function with its recursive call parameterised.

set Y {lambda h { {lambda x {$h {$x $x}}} {lambda x {$h {$x $x}}}}} set yfac {lambda {fac n} {if { $n == 0 } { expr 1 } else { expr $n * [$fac [expr $n-1]]}}} set fac {$Y $yfac}The resulting raw lambda expression computes the factorial:

{lambda h { {lambda x {$h {$x $x}}} {lambda x {$h {$x $x}}}}} {lambda {fac n} {if { $n == 0 } { expr 1 } else { expr $n * [$fac [expr $n-1]]}}}This recursion exercise uses an interesting theoretical aspect of lambda calculus to test the robustness of the implementation.

A special thanks to Alexandre Ferrieux

Finally, I have not proved that the code is correct and there may be rare combinations of Tcl and lambda expressions which may not be properly handled. I suspect there are 2 bugs in the code - but have not come across them in practice. Can you find them ?

One particular bug relates to namespaces:

% namespace eval ::y { variable a 1} % lambda x {set ::y x} can't create procedure "lambda x {set ::y x}": unknown namespace % lambda x {set ::y::a x} can't create procedure "lambda x {set ::y::a x}": unknown namespace

It is important to remember that these functions are intended to act on functions such as lambdas.

I is the identity. I is λ x . x

lambda x x => I I x -> x proc I x { set x}This is theoretically redundant as SKK = I, but I is basic to implementation.

S K K x -> K x (K x) -> xI is useful in that it avoids the renaming problem. It represents an implicit refence to the object rather than a reference via a nametag. This is ultimately more immediate. I is effectively [set] in Tcl.

I is not that interesting but K, though simple, has uses. K is the true function.

K c x -> c lambda x {c} => K c where c != x proc K { x y } {set x}K is useful in Tcl for returning a result which produces side effects.

proc pop1 {} { set top [lindex $::Stack end] set ::Stack [lrange $::Stack 0 end-1] return $top }or, implemented with K:

proc pop2 {} { K [lindex $::Stack end] [set ::Stack [lrange $::Stack 0 end-1]] }This can produce efficiencies in list or string handling, and would be even better if K was used in the bytecode compiler.

S is a complex beast.

S f g x -> f x (g x) lambda x { expression1 expression2} => S ( lambda x expression1) ( lambda x expression2) proc S { f g x } { ???????????? }S looks like it performs a distributive process. }