LambdaMessageSend: functional programming in Squeak
(an introduction)

by Stéphane Rollandin
hepta@zogotounga.net


Metaprogramming in Smalltalk

It is often said that the Smalltalk equivalent of a lambda expression is a block. While this is true in a practical sort of way, it should be emphasized that a block is a compiled piece of Smalltalk code (associated with an environment).

In Squeak we have class MessageSend which is a frozen full message send: when evaluated, the MessageSend selector is sent with the MessageSend arguments to the MessageSend receiver.

To me this looks like the form of choice for metaprogramming in Smalltalk, better than blocks.

Here is a simple MessageSend:
ms := MessageSend
	receiver: 1
	selector: #+
	argument: 2
Doing ms value returns 3 all right.

There is a severe limitation though: MessageSend can not be nested.

Here enters LambdaMessageSend, a subclass of MessageSend: LambdaMessageSends can be nested.
Back to our example:
lms := LambdaMessageSend
	receiver: 1
	selector: #+
	argument: 2

lms printString = '(1 + 2)'             "true"
Doing lms value also returns 3.

Now let's try this:
lms := LambdaMessageSend
	receiver: lms
	selector: #+
	argument: 2

lms printString = '((1 + 2) + 2)'       "true"
This time lms value returns 5.
The receiver has been evaluated along with the whole LambdaMessageSend.


Variables

If we want to change the innermost selector in our example from #+ to #- we can do so by doing
lms receiver selector: #-
We can see that lms now prints as '((1 - 2) + 2)' and that lms value indeed returns 1. But this is a bit cumbersome.

Instead we can define a LambdaMessageSend with a slot, like this:
lms := (LambdaMessageSend
	receiver: (LambdaMessageSend
                        receiver: 1
                        selector: (LambdaSlot id: #op)
                	argument: 2)
	selector: #+
	argument: 2) 
        ofVariable: #op.

lms printString = Lop.{(1 perform: <op> withArguments: #(2)) + 2}.       "true"
lms value = lms               "true"
The lms we just created is actually a function of one variable (labelled #op). The last line of code above shows it evaluates to itself.

We can inject #+ into the slot by doing
lms substituteSlot: (#op -> #+)
which returns a LambdaMessageSend printing as '((1 + 2) + 2)', similar to the one we defined previously.
Note that lms has not been changed by this substitution, so we can do
lms substituteSlot: (#op -> #-)
and get in return the other LambdaMessageSend, which prints as '((1 - 2) + 2)'.


An usable API (let the fun begin)

Fortunately the horrible code above is not required to construct our function. It can also be created this way:
lms := ((1 lambda: #(2)) + 2)
while the substitution can itself be performed like this:
lms <@ #+
(lms <@ #+) value = 5  "true"
We may also substitute and evaluate on the fly (this is a one-step evaluation; see below for details):
(lms <~ #+) = 5  "true"
These arrow-like selectors are the functional API for LambdaMessageSend. There are many of them, and they make it real easy to program functionally in Smalltalk.

Let's see how easy it is with a few examples, where we play with a receiver or an argument instead of a selector:
1 + 2 + 2                                     "an expression we want to parametrize"

f := 1 + Lambda n + 2                         "replacing the inner 2 with a slot"
f printString = 'Ln.{(1 + <n>) + 2}'  
(f <~ -1) = 2                           "true"

g := (1 + Lambda n + Lambda m)                  "replacing both arguments with slots"
g printString = 'Ln.Lm.{(1 + <n>) + <m>}' 
(g <~~ #(10 100)) = 111                 "true"
(g <~ 10 <~ 100) = 111                  "true"

h := g <~ 10                                    "so what is this ?"
h printString = 'Lm.{11 + <m>}'                    

Auto-expansion

The simple way to built a lambda expression is based on the fact that a LambdaMessageSend encoutering a message it does not understand will, instead of raising an error, return another lambda expression, an extended version of itself encompassing the message. This is the auto-expansion mechanism: we can always start with an atomic LambdaMessageSend and have it grow automatically.

We use Lambda to form an atomic expression (e.g. an identity function).
When Lambda is sent a symbol, it returns an identity function using that symbol as the slot identifier.
For example:
Lambda x printString = 'Lx.{<x>}'  
Lambda x <~ 'hello' = 'hello'
Since LambdaMessageSends do not understand #, we can expand our function like this:
f := Lambda x, ' there' .
f <~ 'hello' = 'hello there'
It can be further expanded ad infinitum:
f := Lambda x, ' ', Lambda y . 
f <~~ #('hello' 'world') = 'hello world'

f := f copyFrom: Lambda beg to: Lambda end .
f printString = 'Lx.Ly.Lbeg.Lend.{((<x> , '' '') , <y>) copyFrom: <beg> to: <end>}'
f <~~ #('hello' 'world' 5 7) = 'o w'

Composition, quotation and high-order functions

Notice how substitution works:
((Lambda x + 1) <@ 10) printString = '(10 + 1)' 
(Lambda x + 1) <~ 10 = 11 
((Lambda x + 1) <~ (Lambda y * 2)) printString = '(Ly.{<y> * 2} + 1)'
The last example seems weird; this is probably not what was intended.
Instead we would like the function Lambda y * 2 to replace the slot x in Lambda x + 1 in order to obtain a new function of variable y. So what is missing is the promotion of y to the rank of variable for the overall resulting function.

This can be asked for explicitely by sending #ofVariable:
(((Lambda x + 1) <~ (Lambda y * 2)) ofVariable: #y) printString = 'Ly.{(<y> * 2) + 1}'
It can also be done by using #'<=' instead of #'<~'
((Lambda x + 1) <= (Lambda y * 2)) printString = 'Ly.{(<y> * 2) + 1}'

We can also force a LambdaMessageSend to expand over a message it DOES understand by first quoting it.
#quoted does the job:
Lambda g isLambdaMessageSend = true
Lambda g quoted isLambdaMessageSend isLambdaMessageSend = true 

Thus a composition operator could be defined as follows:
compose := Lambda f quoted <= Lambda g.                 "see why we need #'<=' here ?"
compose printString = 'Lf.Lg.{<f> <= <g>}'.               "true"

h := compose <~~ {Lambda x + 1 . Lambda y * 2}.
h printString = 'Ly.{(<y> * 2) + 1}'

Reduction and evaluation strategy

The algorithm followed when evaluating (or "reducing") a lambda expression is not trivial, in the sense that different results can be produced by different evaluation strategies for some higher-order expressions.

The reduction operated after substituting slots via #'<~' is a one-step reduction in which, like in MessageSend>>#value, the LambdaMessageSend receiver is simply sent the selector with the arguments.
If no error is raised then we have the reduced value (else we consider that this LambdaMessageSend can not be reduced).

A full reduction can also be performed by recursively reducing receiver, selector and arguments before evaluating the LambdaMessageSend.

To fully reduce the expression we use #'<~&' :
(((1 lambda + 2) * Lambda x) + 4 <~ 1) printString = '(((1 + 2) * 1) + 4)'
(((1 lambda + 2) * Lambda x) + 4 <~& 1) = 7
Also, #fullyReduced performs a full reduction and return the result (the initial expression is left unchanged as always)
(((1 lambda + 2) * Lambda x) + 4 <~ 1) fullyReduced = 7

This evaluation strategy is the default one, but it can be changed for a specific LambdaMessageSend by sending it #withEvaluationStategy:
See the subclasses of LMSEvaluationStrategy for the currently implemented strategies.


Normal order evaluation and lambda calculus

Sending #withNormalOrder to a LambdaMessageSend returns a lambda expression those evaluation strategy is normal-order (where the arguments are being substituted unevaluated). This is suitable for lambda calculus.

See Lambda class-side methods for examples; the category 'lambda calculus' provides a library of common combinators, and a simple (and slow) evaluator.


For example the library defines
(Lambda C: 2) printString = 'Lf.Lx.{<f> <~ (<f> <~ <x>)}'                       "2 as a Church numeral"
Lambda ZEROP printString = 'Ln.{(<n> <~ La1.{Lx.Ly.{<y>}}) <~ Lx.Ly.{<x>}}'     "Church numeral isZero test"
Lambda IFTHENELSE printString = 'La.Lb.Lc.{(<a> <~ <b>) <~ <c>}'                
which can be fed to the evaluator as in
Lambda reduce: {#IFTHENELSE . {#ZEROP . {#C: . 2}} . true . false}              "array-based lisp-like syntax"
...which returns false


The (in)famous fixed-point combinator Y is also available:
Lambda Y printString = 'Lf.{Lx.{<f> <~ (<x> <~ <x>)} <~ Lx.{<f> <~ (<x> <~ <x>)}}'
(see LambdaTest>>#testY to see it in action).

For the record, the equivalent combinator when using the default (applicative-order) evaluation strategy is
Lambda LMSY printString = 'Lf.{Lx.{<x> <~ <x>} <~ (<f> <= Lx.{<x> <@ <x>})}'
(you will find a derivation of this result in FunctionaltalkTest>>#testRecursion)


Parameters (and a note on mutability)

In pure functional programming, functions are immutable. Indeed all operations we performed so far modify copies of lambda expression.

Now for practical purposes I found it very convenient to define particular slots in a lambda expression as being parameters, associated to a default value which we can change (this is extensively used in µO). In this regard immutability is broken.

For example here is how we can define a sine function which first extremum is a specific point:
| p x |
	
x := Lambda x.
p := Lambda point default: (Float pi@1); description: 'first extremum'.

sine := (((Lambda freq * x) sin * Lambda amp)
		<<== {#freq -> (Float quoted pi / (2 * p x)) . #amp -> p y})
	ofVariables: {x . p}.

sine printString = 'Lx.Lpoint.{((Float pi / (2 * <point> x)) * <x>) sin * <point> y}'.        "true"
sine is a function of two variables, one of them being a parameter.
Thus it has a default form:
sine default printString = 'Lx.{((Float pi / 6.283185307179586) * <x>) sin * 1}'
sine default <~& Float pi = 1.

sine reducedDefault printString = 'Lx.{(0.5 * <x>) sin * 1}'.
sine reducedDefault <~ Float pi = 1.

That default form can be changed by setting the parameter default value:
sine parametrize: #point default: 1@-1.

sine default printString = 'Lx.{((Float pi / 2) * <x>) sin * -1}'.                        
sine default <~& 1 = -1.

Compilation

Evaluating a lambda expression is slow. However it can be compiled for efficiency. Its compiled form (cached internally) is a block.
f := Lambda x * Lambda y.
tf := [10000 timesRepeat: [f <~~ #(5 10)]] timeToRun. 
f compile.
tfcomp := [10000 timesRepeat:  [f compiled value: 5 value: 10]] timeToRun.
tf / tfcomp > 450    "true"
Beware that the compiled form semantics is the same as the expression ONLY in presence of non-lambdas arguments. It is thus very unsafe to compile high-order functions. Also note that evaluating a compiled form always implies a full reduction.

See FunctionalTest>>#testCompiledFormSemantics for details.


Arrow operators summary

        x := Lambda x.
        y := Lambda y.
        z := Lambda z.
operator action example returns
x + (y * 10) Lx.Ly.{<x> + (<y> * 10)}
<~ reduce first variable (x + (y * 10)) <~ 5 Ly.{5 + (<y> * 10)}
<~~ reduce first variables (x + (y * 10)) <~~ #(5 1) 15
<<~ reduce specific slot (x + (y * 10)) <<~ (#y -> 5) Lx.{<x> + 50}
<<~~ reduce specific slots (x + (y * 10)) <<~~ {#y -> 5 . #x -> 1} 51
<@ substitute first variable (x + (y * 10)) <@ 5 Ly.{5 + (<y> * 10)}
<@@ substitute first variables (x + (y * 10)) <@@ #(5 1) (5 + (1 * 10))
<<@ substitute specific slot (x + (y * 10)) <<@ (#y -> 5) Lx.{<x> + (5 * 10)}
<<@@ substitute specific slots (x + (y * 10)) <<@@ {#y -> 5 . #x -> 1} (1 + (5 * 10))
<= inline at first variable (x + (y * 10)) <= (z + 1) Lz.Ly.{(<z> + 1) + (<y> * 10)}
<== inline at first variables (x + (y * 10)) <== {5 . z sqrt} Lz.{5 + (<z> sqrt * 10)}
<<= inline at specific slot (x + (y * 10)) <<= (#y -> (z + y)) Lx.Lz.Ly.{<x> + ((<z> + <y>) * 10)}
<<== inline at specific slots (x + (y * 10)) <<== {#y -> z . #x -> z} Lz.{<z> + (<z> * 10)}
o: composition (x + 1) o: (y * 10) Lx.{(<x> + 1) * 10}
,<~ quoted reduction (x + (y * 10)) ,<~ z Lx.Ly.Lz.{(<x> + (<y> * 10)) <~ <z>}
,<~~ quoted reduction (x + (y * 10)) ,<~~ {1 . z} Lx.Ly.Lz.{((<x> + (<y> * 10)) <~ 1) <~ <z>}
,,<~ quoted reduction (x ,<~ (y * 10)) ,,<~ (z + 1) (Lx.Ly.{<x> <~ (<y> * 10)} <~ Lz.{<z> + 1})
,,<= quoted inlining (x + (y * 10)) ,,<= (z + 1) (Lx.Ly.{<x> + (<y> * 10)} <= Lz.{<z> + 1})


to these we must add: ... which makes a total of 49 arrow operators !

Note that some of them may be equivalent depending on the evaluation strategy (for example under normal order #'<~' does the same as #'<~&') and on the nature of their arguments (with a non-lambda argument #'<=' is equivalent to #'<~')


Download

The most current code is available on SqueakMap: check up the entry LambdaMessageSend.
It can be installed in a 3.8 or newer image (last tested on 5.1).

You can also get it here: FunctionalTalk-39.sar, although this may not be the latest version.



back to the main software page