17 Loot: lambda the ultimate

17.1 Functions in their most general form

We’ve been building up the pieces of functions, first with second-class functions, then with tail-calls, then with first-class function pointers.

Now we’re ready to deal with functions in their most general form: λ-expressions.

We add λ-expressions to the syntax and remove the (fun ,Variable) and (call ,Expr ,@(Listof Expr)) forms. We no longer need a separate syntactic form for referencing the name of a function, we can just use variable binding. Likewise, we use the same syntax as Racket for function application:

For the moment, Formals can be defined as a list of variables:

But it’s possible to extend the λ-notation to include the ability to define variable-arity functions, as you will see in (part "Assignment 6").

17.2 Long Live Lambda!

Let’s start by developing the interpreter for Loot, where the relevant forms are λs and applications:

; Expr REnv -> Answer

(define (interp-env e r)

; ...

[(lam-e xs e)  '...]

[(app-e e es)  '...])

These two parts of the interpreter must fit together: λ is the constructor for functions and application is deconstructor. An application will evaluate all its subexpressions and the value produced by e ought to be the kind of value constructed by λ. That value needs to include all the necessary information to, if given the values of the arguments es, evaluate the body of the function in an environment associating the parameter names with the arguments’ values.

So how should functions be represented? Here is a simple idea following the pattern we’ve used frequently in the interpreter:

• Q: How can we represent strings?

• A: With strings!

• Q: How can we represent booleans?

• A: With booleans!

• Q: How can we represent numbers?

• A: With numbers!

• Q: How can we represent pairs?

• A: With pairs!

• Q: etc.

• A: etc.

Great, so we will use function to represent functions. We can implement function application with function application. Let’s fill in what we know so far:

; Expr REnv -> Answer

(define (interp-env e r)

; ...

[(lam-e xs e)

(λ ??? '...)]

[(app-e e es)

(let ((f (interp-eval e r))

(vs (interp-eval* es r)))

(apply f vs))])

It’s not totally clear what parameters the representation of a function should have or what we should in the body of that function. However, the code in the interpretation of an application sheds light on both. First, it’s clear a function should potentially take any number of arguments:

; Expr REnv -> Answer

(define (interp-env e r)

; ...

[(lam-e xs e)

(λ vs '...)]

[(app-e e es)

(let ((f (interp-eval e r))

(vs (interp-eval* es r)))

(apply f vs))])

Second, what should happen when a function is applied? It should produce the answer produced by the body of the λ expression in an environment that associates xs with vs. Translating that to code, we get:

; Expr REnv -> Answer

(define (interp-env e r)

; ...

[(lam-e  xs e)

(λ vs (interp-env e (zip xs vs)))]

[(app-e e es)

(let ((f (interp-eval e r))

(vs (interp-eval* es r)))

(apply f vs))])

and completed the implementation of the interpreter.

There are, however, problems.

For one, this approach does not model how λ-expressions are able to capture the environment in which they are evaluated. Consider:

(let ((y 8))

(λ (x) (+ x y)))

This evaluates to a function that, when applied, should add 8 to its argument. It does so by evaluating the body of the λ, but in an environment that both associates x with the value of the argument, but also associates y with 8. That association comes from the environment in place when the λ-expression is evaluated. The interpreter as written will consider y is unbound!

The solution is easy: in order for (Loot) functions to capture their (implicit) environment, we should capture the (explicit) environment in the (Racket) function:

; Expr REnv -> Answer

(define (interp-env e r)

; ...

[(lam-e xs e)

(λ (vs) (interp-env e (append (zip xs vs) r)))]

[(app-e e es)

(let ((f (interp-eval e r))

(vs (interp-eval* es r)))

(apply f vs))])

The last remaining issue is we should do some type and arity-checking:

; Expr REnv -> Answer

(define (interp-env e r)

; ...

[(lam-e xs e)

(λ (vs)

(if (= (length xs) (length vs))

(interp-env e (append (zip xs vs) r))

'err))]

[(app-e e es)

(let ((f (interp-eval e r))

(vs (interp-eval* es r)))

(if (procedure? f)

(apply f vs)

'err))])

The complete interpreter is:

loot/interp.rkt

#lang racket

(provide (all-defined-out))

(require "ast.rkt" "syntax.rkt")

;; type Expr =

;; ...

;; | `(λ ,(Listof Variable) ,Expr)

;; type Value =

;; ...

;; | Function

;; type Function =

;; | (Values ... -> Answer)

(define (interp p)

(match (desugar-prog p)

[(prog _ e)

(interp-env e '())]))

;; Expr REnv -> Answer

(define (interp-env e r)

(match e

[(nil-e) '()]

[(int-e i) i]

[(bool-e b) b]

[(prim-e p es)

(match (interp-env* es r)

[(list vs ...) (interp-prim p vs)]

[_ 'err])]

[(if-e e0 e1 e2)

(match (interp-env e0 r)

['err 'err]

[v

(if v

(interp-env e1 r)

(interp-env e2 r))])]

[(var-e x)

(lookup r x)]

[(let-e (list (binding x e0)) e1)

(match (interp-env e0 r)

['err 'err]

[v

(interp-env e1 (ext r x v))])]

[(letr-e bs e)

(letrec ((r* (λ ()

(append

(zip (get-vars bs)

;; η-expansion to delay evaluating r*

;; relies on RHSs being functions

(map (λ (l) (λ vs (apply (interp-env l (r*)) vs)))

(get-defs bs)))

r))))

(interp-env e (r*)))]

[(lam-e xs e)

(λ vs

(if (= (length vs) (length xs))

(interp-env e (append (zip xs vs) r))

'err))]

[(app-e e es)

(match (interp-env* (cons e es) r)

[(list f vs ...)

(if (procedure? f)

(apply f vs)

'err)]

[_ 'err])]))

;; (Listof Expr) REnv -> (Listof Value) | 'err

(define (interp-env* es r)

(match es

['() '()]

[(cons e es)

(match (interp-env e r)

['err 'err]

[v (cons v (interp-env* es r))])]))

;; Any -> Boolean

(define (prim? x)

(and (symbol? x)

(memq x '(add1 sub1 + - zero?

box unbox empty? cons car cdr))))

;; Any -> Boolean

(define (syntactic-value? x)

(or (int-e? x)

(bool-e? x)

(nil-e? x)))

;; Prim (Listof Value) -> Answer

(define (interp-prim p vs)

(match (cons p vs)

[(list 'add1 (? integer? i0))  (add1 i0)]

[(list 'sub1 (? integer? i0))  (sub1 i0)]

[(list 'zero? (? integer? i0)) (zero? i0)]

[(list 'box v0)                (box v0)]

[(list 'unbox (? box? v0))     (unbox v0)]

[(list 'empty? v0)             (empty? v0)]

[(list 'cons v0 v1)            (cons v0 v1)]

[(list 'car (cons v0 v1))      v0]

[(list 'cdr (cons v0 v1))      v1]

[(list '+ (? integer? i0) (? integer? i1))

(+ i0 i1)]

[(list '- (? integer? i0) (? integer? i1))

(- i0 i1)]

[_ 'err]))

;; Env Variable -> Answer

(define (lookup env x)

(match env

['() 'err]

[(cons (list y i) env)

(match (symbol=? x y)

[#t i]

[#f (lookup env x)])]))

;; Env Variable Value -> Value

(define (ext r x i)

(cons (list x i) r))

(define (zip xs ys)

(match* (xs ys)

[('() '()) '()]

[((cons x xs) (cons y ys))

(cons (list x y)

(zip xs ys))]))

We now have the full power of λ expressions in our language. We can write recursive functions, using only anonymous functions, via the Y-combinator:

Examples

> (interp (sexpr->prog     '(λ (t)        ((λ (f) (t (λ (z) ((f f) z))))         (λ (f) (t (λ (z) ((f f) z))))))))

#<procedure:...ngs/loot/interp.rkt:56:5>

For example, computing the triangular function applied to 10:

Examples

> (interp (sexpr->prog     '(((λ (t)          ((λ (f) (t (λ (z) ((f f) z))))           (λ (f) (t (λ (z) ((f f) z))))))        (λ (tri)          (λ (n)            (if (zero? n)                1                (+ n (tri (sub1 n)))))))       10)))

56

One of the niceties of using Racket functions to represent Loot functions is we can define Racket functions via the interpretation of Loot functions:

Examples

> (define Y     (interp (sexpr->prog       '(λ (t)          ((λ (f) (t (λ (z) ((f f) z))))           (λ (f) (t (λ (z) ((f f) z)))))))))

> (define tri     (interp (sexpr->prog '(λ (tri)                            (λ (n)                              (if (zero? n)                                  1                                  (+ n (tri (sub1 n)))))))))

And then use them from within Racket:

Examples

> ((Y tri) 10)

56

We can also “import” Racket functions in to Loot:

Examples

> (interp-env (sexpr->expr '(expt 2 10))               `((expt ,expt)))

1024

17.3 Lambda is Dead!

Now the question you might naturally wonder is: how does implementing functions in terms of functions help me implement functions in x86, which after all, doesn’t have λ?

The answer is that from this point, in which we have an understandable account of functions, we can iteratively revise the interpreter to eliminate the use of functions while computing equivalent results. Doing so will shed light on the lower-level implementation of functions in the compiler.

Consider again what it is that a λ-expression is doing for you:

• it is packaging up the parameters, body, and environment, so that

• when applied it can evaluate the body, binding the parameters, in an extension of the functions environment.

We can achive these things without using a function value by:

• creating a data structure to hold the parameters, body, and environment, and

• rewriting the application of the function to use those values to evaluate the body, binding the parameters, etc.

So we are changing the representation of functions from:

To:

; type Value =

; | ....

; | ‘(closure ,Formals ,Expr ,Env)

When a λ is evaluated, a closure is created. When a function is applied, we deconstruct the closure and execute the code that used to be in the (Racket) function:

; Expr REnv -> Answer

(define (interp-env e r)

; ...

[(lam-e xs e)

(closure xs e r)]

[(app-e e es)

(let ((f (interp-eval e r))

(vs (interp-eval* es r)))

(match f

[(closure xs e r)

(if (= (length vs) (length xs))

(interp-env e (append (zip xs vs) r))

'err)]

[_ 'err]))])

We can give it a try:

Examples

> (interp (sexpr->prog '(λ (x) x)))

(closure '(x) (var-e 'x) '())

> (interp (sexpr->prog '((λ (x) (λ (y) x)) 8)))

(closure '(y) (var-e 'x) '((x 8)))

Notice in the second example how the closure contains the body of the function and the environment mapping the free variable 'x to 8.

We can also confirm our larger example works:

Examples

> (interp (sexpr->prog     '(((λ (t)          ((λ (f) (t (λ (z) ((f f) z))))           (λ (f) (t (λ (z) ((f f) z))))))        (λ (tri)          (λ (n)            (if (zero? n)                1                (+ n (tri (sub1 n)))))))       10)))

56

While can’t apply the interpretation of functions in Racket like we did previously, we can apply-function the interpretation of functions:

Examples

> (define Y     (interp (sexpr->prog       '(λ (t)          ((λ (f) (t (λ (z) ((f f) z))))           (λ (f) (t (λ (z) ((f f) z)))))))))

> (define tri     (interp (sexpr->prog              '(λ (tri)                (λ (n)                  (if (zero? n)                      1                      (+ n (tri (sub1 n)))))))))

> (apply-function (apply-function Y tri) 10)

56

The process we used to eliminate function values from the interpreter is an instance of a general-purpose whole-program transformation called defunctionalization for replacing function values with data structures.

17.4 Defunctionalization at work

Let’s digress for a moment and learn this very useful transformation.

Here is a data type for representing regular expressions:

; type Regexp =

; | 'zero

; | 'one

; | ‘(char ,Char)

; | ‘(times ,Regexp ,Regexp)

; | ‘(plus ,Regexp ,Regexp)

; | ‘(star ,Regexp)

The regular expression 'zero matches nothing; 'one matches the empty string; `(char ,c) matches the character c; `(times ,r1 ,r2) matches the concatenation of a string matching r1 followed by a string matching r2; `(plus ,r1 ,r2) matching either a string matching r1 or a string matching r2; and `(star ,r) matches a string made up of any number of substrings, each of which match r.

A really nice way to write a matcher is to use a continuation-passing style that keeps track of what is required of the remainder of the string after matching a prefix against the regexp:

loot/regexp.rkt

#lang racket

(provide accepts)

;; type Regexp =

;; | 'zero

;; | 'one

;; | `(char ,Char)

;; | `(times ,Regexp ,Regexp)

;; | `(plus ,Regexp ,Regexp)

;; | `(star ,Regexp)

;; Regexp String -> Boolean

(define (accepts r s)

(matcher r (string->list s) (λ (cs) (empty? cs))))

;; Regexp (Listof Char) ((Listof Char) -> Bool) -> Bool

(define (matcher r cs k)

(match r

['zero #f]

['one (k cs)]

[`(char ,c)

(match cs

['() #f]

[(cons d cs) (and (char=? c d) (k cs))])]

[`(plus ,r1 ,r2)

(or (matcher r1 cs k) (matcher r2 cs k))]

[`(times ,r1 ,r2)

(matcher r1 cs (λ (cs) (matcher r2 cs k)))]

[`(star ,r)

(letrec ((matcher* (λ (cs) (or (k cs) (matcher r cs matcher*)))))

(matcher* cs))]))

But what if needed to program this regular expression matching without the use of function values? We can arrive at such code systematically by applying defunctionalization.

loot/regexp-defun.rkt

#lang racket

(provide accepts)

;; type Regexp =

;; | 'zero

;; | 'one

;; | `(char ,Char)

;; | `(times ,Regexp ,Regexp)

;; | `(plus ,Regexp ,Regexp)

;; | `(star ,Regexp)

;; type K =

;; | '(k0)

;; | `(k1 ,Regexp ,K)

;; | `(k2 ,K ,Regexp)

;; Regexp String -> Boolean

(define (accepts r s)

(matcher r (string->list s) '(k0)))

;; Regexp (Listof Char) K -> Bool

(define (matcher r cs k)

(match r

['zero #f]

['one (apply-k k cs)]

[`(char ,c)

(match cs

['() #f]

[(cons d cs)

(and (char=? c d) (apply-k k cs))])]

[`(plus ,r1 ,r2)

(or (matcher r1 cs k) (matcher r2 cs k))]

[`(times ,r1 ,r2)

(matcher r1 cs `(k1 ,r2 ,k))]

[`(star ,r)

(apply-k `(k2 ,k ,r) cs)]))

;; K (Listof Char) -> Bool

(define (apply-k k cs)

(match k

[`(k0) (empty? cs)]

[`(k1 ,r2 ,k) (matcher r2 cs k)]

[`(k2 ,k* ,r) (or (apply-k k* cs) (matcher r cs k))]))

And we get the same results:

Examples

> (accepts `(star (char #\a)) "aaaaa")

#t

> (accepts `(star (char #\a)) "aaaab")

#f

> (accepts `(star (plus (char #\a) (char #\b))) "aaaab")

#t

17.5 Compiling Loot

Compiling a λ-expression will involve generating two different chunks of instructions:

• one to implement the function, i.e. the code to be executed when the function created by the λ-expression is called, and

• one to create a closure, i.e. to capture the environment at the point the λ-expression is evaluated.

17.6 Compiling Function Definitions

The first part closely follows the appoach of defining a function definition (define (f x ...) e) from our previous compilers.

Ther are two important differences from the past though:

• λ-expressions don’t have a name, and

• the body of the λ-expression may reference variables bound outside of the λ-expression.

To deal with the first issue, we first make a pass over the program inserting computed names for each λ-expression.

To accomodate this, we will introduce the following data type for “labelled” expressions, along with the lam-t constructor:

; type LExpr =

; ....

; | ‘(λ ',Symbol ,Formals ,Expr)

An LExpr is just like a Expr except that λ-expressions have the form like (λ 'fred (x) (+ x x)). The symbol 'fred here is used to give a name to the λ-expression. The use of quote is so that LExprs are still a valid subset of Racket expressions.

The first step of the compiler will be to label every λ-expression using the following function:

; Expr -> LExpr

(define (label-λ e)

(match e

[(? imm? i)       e]

[(var-e v)        e]

[(prim-e p es)    (prim-e p (map label-λ es))]

[(if-e e0 e1 e2)  (if-e (label-λ e0) (label-λ e1) (label-λ e2))]

[(let-e bs body)  (let-e (bindings-map-def label-λ bs) (label-λ body))]

[(letr-e bs body) (letr-e (bindings-map-def label-λ bs) (label-λ body))]

[(lam-e xs e0)    (lam-t (gensym) xs (label-λ e0))]

[(app-e f es)     (app-e (label-λ f) (map label-λ es))]))

Here it is at work:

Examples

> (label-λ (sexpr->expr     '(λ (t)       ((λ (f) (t (λ (z) ((f f) z))))        (λ (f) (t (λ (z) ((f f) z))))))))

(lam-t 'g7304 '(t) (app-e (lam-t 'g7305 '(f) (app-e (var-e 't) (list (lam-t 'g7306 '(z) (app-e (app-e (var-e 'f) (list (var-e 'f))) (list (var-e 'z))))))) (list (lam-t 'g7307 '(f) (app-e (var-e 't) (list (lam-t 'g7308 '(z) (app-e (app-e (var-e 'f) (list (var-e 'f))) (list (var-e 'z))))))))))

Now turning to the second issue–λ-expression may reference variables bound outside of the expression—let’s consider how to compile something like (λ (x) z)?

There are many possible solutions, but perhaps the simplest is to compile this as a function that takes two arguments, i.e. compile it as if it were: (λ (x z) z). The idea is that a λ-expression defines a function of both explicit arguments (the parameters) and implicit arguments (the free variables of the λ-expression).

This will have to work in concert with closure creation and function calls. When the λ-expression is evaluated, a closure will be created storing the value of z. When the function is applied, the caller will need to retrieve that value and place it as the second argument on stack before calling the function’s code.

To implement this, we will need to compute the free variables, which we do with the following function:

; LExpr -> (Listof Variable)

(define (fvs e)

(define (fvs e)

(match e

[(? imm? i)       '()]

[(var-e v)        (list v)]

[(prim-e p es)    (apply append (map fvs es))]

[(if-e e0 e1 e2)  (append (fvs e0) (fvs e1) (fvs e2))]

[(let-e bs body)  (append (apply append (map fvs (get-defs bs)))

(remq* (get-vars bs) (fvs body)))]

[(letr-e bs body) (remq* (get-vars bs) (append (apply append (map fvs (get-defs bs))) (fvs body)))]

[(lam-t _ xs e0)  (remq* xs (fvs e0))]

[(lam-e xs e0)    (remq* xs (fvs e0))]

[(app-e f es)     (append (fvs f) (apply append (map fvs es)))]))

(remove-duplicates (fvs e)))

We can now write the function that compiles a labelled λ-expression into a function in assembly:

; Lambda -> Asm

(define (compile-λ-definition l)

(match l

[(lam-t f xs e0)

(let ((c0 (compile-tail-e e0 (reverse (append xs (fvs l))))))

`(,f

,@c0

ret))]

[(lam-e _ _) (error "Lambdas need to be labeled before compiling")]))