Tcl Lambda Abstraction

written 25 February 2002 being revised May 2006
Google site search

ContentsIntroductionBasicIntermediateAdvancedFuturePolicyInfrastructure

1   Lambda Command

The Tcl [lambda] command is created as a vehicle for experiments in function theory, functional language and artificial intelligence. It is created as an educational exercise which serves to illustrate the features of functional languages which differentiate them from imperative style languages by using an imperative language such as Tcl as a base. However the [lambda] command has its uses in Tcl where one wishes to create a procedure with local scope that exists only for the life of the module in which it is embedded. Tcl procedures have global scope and procedure names can proliferate and require awkward management as can be seen by the history of procedure namespace systems that have been appended to Tcl over the years. Tcl already has lambda abstractions in a global level represented by the -command options associated with many Tk widgets and some Tcl commands. However these can only reliably access global variables.

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.

λ-calculus and functional language recognise only functions. Within the context of Tcl, lambda abstractions are assigned to variables. Assigning λ-abstractions to procedures would acheive no useful result by definition and is a pointless exercise. λ-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 λ 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 regsubcommand 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 could clash with a similar usage in the parameter list in the procedure in which this lambda expression is embedded. It does not allow for Tcl's default argument specification as this would interfere with the currying process. This means that procedures such as 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. add1 would be reduced to {set x 1 ; expr $x + }.

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?

Using Lambda Safely

The sum example above illustrates a problem which arises when you invoke lambda. This oproblem is no different to handling temporary variables, i, j, k etc. Lambdas use x, y, z by convention. The expression
 % 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
1
You 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]
                
              
}
 
With this supersafe version of lambda we have:
 % 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 5
This 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????

2   Recursion in Lambda Expressions

In theory, lambda expressions can be used recursively, and this implementation is robust enough to do recursive calls. That old war horse the factorial function as used, though this example does not verify that the argument is indeed a positive integer.
% 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.

3   Performance

When timing the execution of the factorial example for increasing integer values, both the recursive and Y forms of lambda expression behaved linearly. Their performance was not unfavourable compared to the standard Tcl recursive procedure version which executed at 1.1 ms per integer step. The recursive lambda expression executed at 1.4 ms per integer step, and the Y expression at 3.4 ms per integer step. Obviously Y expressions are a theoretical luxury. In all lambda machines Y is replaced by an optimised builtin function. It would be interesting to see how closely lambda function performance matches that of procedures when the unkown precedure is embedded in the Tcl intepreter substitution scheme and lambda is coded in C.

A special thanks to Alexandre Ferrieux for providing the framework for the lambda procedure.

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

4   Combinatotrs

Allied to lambda is functional programming using the SKI combinators. These are important primitive functions which allow any kinds of functions to be optimised at execution. There are three base functions S, K (true) and I (identity) which have expressions which allow for optimisation in sometimes non-obvious ways. Because they are generalised functions they have a place in lambda functions which are also generalised functions, but also in Tcl itself as they provide some useful tricks.

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) -> x
I 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. }
©2000 - 2006 WEBSCOOL This page last updated 15 May 2006. All rights reserved - including copying or distribution of any portion of this document in any form or on any medium without authorisation. For more regarding the copyright.