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:

Two things to note: for now you can ignore the Name parameter, and 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 Assignment 6: Arities!.

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 _ xs e)  '...]

[(App 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 _ xs e)

(λ ??? '...)]

[(App 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 _ xs e)

(λ vs '...)]

[(App 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 _ xs e)

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

[(App 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 _ xs e)

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

[(App 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 _ xs e)

(λ (vs)

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

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

'err))]

[(App 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 interp interp-env interp-prim1)

(require "ast.rkt"

"env.rkt"

"interp-prims.rkt")

;; type Answer = Value | 'err

;; type Value =

;; | Integer

;; | Boolean

;; | Character

;; | (Fun f)

;; | Eof

;; | Void

;; | '()

;; | (cons Value Value)

;; | (box Value)

;; type REnv = (Listof (List Id Value))

;; type Defns = (Listof Defn)

;; Prog Defns -> Answer

(define (interp p)

(interp-env (desugar p) '()))

;; Expr Env Defns -> Answer

(define (interp-env e r)

(match e

[(Prog '() e) (interp-env e r)]

[(Int i)  i]

[(Bool b) b]

[(Char c) c]

[(Eof)    eof]

[(Empty)  '()]

[(Var x)  (lookup r x)]

[(Prim0 'void) (void)]

[(Prim0 'read-byte) (read-byte)]

[(Prim0 'peek-byte) (peek-byte)]

[(Prim1 p e)

(match (interp-env e r)

['err 'err]

[v (interp-prim1 p v)])]

[(Prim2 p e1 e2)

(match (interp-env e1 r)

['err 'err]

[v1 (match (interp-env e2 r)

['err 'err]

[v2 (interp-prim2 p v1 v2)])])]

[(If p e1 e2)

(match (interp-env p r)

['err 'err]

[v

(if v

(interp-env e1 r)

(interp-env e2 r))])]

[(Begin e1 e2)

(match (interp-env e1 r)

['err 'err]

[_ (interp-env e2 r)])]

[(Let x e1 e2)

(match (interp-env e1 r)

['err 'err]

[v (interp-env e2 (ext r x v))])]

[(LetRec bs e)

(letrec ((r* (λ ()

(append

(zip (map car bs)

;; η-expansion to delay evaluating r*

;; relies on RHSs being functions

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

(map cadr bs)))

r))))

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

[(Lam _ xs e1)

(lambda vs

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

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

'err))]

[(App f es)

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

[(list f vs ...)

(if (procedure? f)

(apply f vs)

'err)])]

[_         'err]))

;; (Listof Expr) REnv Defns -> (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))])]))

(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 (parse     '(λ (t)        ((λ (f) (t (λ (z) ((f f) z))))         (λ (f) (t (λ (z) ((f f) z))))))))

#<procedure:...ngs/loot/interp.rkt:76:8>

For example, computing the triangular function applied to 10:

Examples

> (interp (parse     '(((λ (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 (parse       '(λ (t)          ((λ (f) (t (λ (z) ((f f) z))))           (λ (f) (t (λ (z) ((f f) z)))))))))

> (define tri     (interp (parse '(λ (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 (parse '(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 _ xs e)

(Closure xs e r)]

[(App 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 (parse '(λ (x) x)))

'#s(Closure (x) #s(Lam lam7242 (x) #s(Var x)) ())

> (interp (parse '((λ (x) (λ (y) x)) 8)))

'#s(Closure (x) #s(Lam lam7243 (x) #s(Lam lam7244 (y) #s(Var 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 (parse     '(((λ (t)          ((λ (f) (t (λ (z) ((f f) z))))           (λ (f) (t (λ (z) ((f f) z))))))        (λ (tri)          (λ (n)            (if (zero? n)                1                (+ n (tri (sub1 n)))))))       10)))

'#s(Closure (t) #s(Lam lam7245 (t) #s(App #s(Lam lam7246 (f) #s(App #s(Var t) (#s(Lam lam7247 (z) #s(App #s(App #s(Var f) (#s(Var f))) (#s(Var z))))))) (#s(Lam lam7248 (f) #s(App #s(Var t) (#s(Lam lam7249 (z) #s(App #s(App #s(Var f) (#s(Var f))) (#s(Var z)))))))))) ((t 10) (t #s(Closure (tri) #s(Lam lam7250 (tri) #s(Lam lam7251 (n) #s(If #s(Prim1 zero? #s(Var n)) #s(Int 1) #s(Prim2 + #s(Var n) #s(App #s(Var tri) (#s(Prim1 sub1 #s(Var n)))))))) ()))))

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 (parse       '(λ (t)          ((λ (f) (t (λ (z) ((f f) z))))           (λ (f) (t (λ (z) ((f f) z)))))))))

> (define tri     (interp (parse              '(λ (tri)                (λ (n)                  (if (zero? n)                      1                      (+ n (tri (sub1 n)))))))))

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

'#s(Closure (t) #s(Lam lam7252 (t) #s(App #s(Lam lam7253 (f) #s(App #s(Var t) (#s(Lam lam7254 (z) #s(App #s(App #s(Var f) (#s(Var f))) (#s(Var z))))))) (#s(Lam lam7255 (f) #s(App #s(Var t) (#s(Lam lam7256 (z) #s(App #s(App #s(Var f) (#s(Var f))) (#s(Var z)))))))))) ((t 10) (t #s(Closure (tri) #s(Lam lam7257 (tri) #s(Lam lam7258 (n) #s(If #s(Prim1 zero? #s(Var n)) #s(Int 1) #s(Prim2 + #s(Var n) #s(App #s(Var tri) (#s(Prim1 sub1 #s(Var n)))))))) ()))))

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.

This is the reason for the Name field in the Lam constructor.

; type Expr =

; ....

; | Lam Name [Variable] Expr

Now λ-expressions have the form like (Lam 'fred '(x) (+ x x)). The symbol 'fred here is used to give a name to the λ-expression.

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

; Expr -> Expr

(define (label-λ e)

(match e

[(Prog ds e)     (Prog (map label-λ ds) (label-λ e))]

[(Defn f xs e)   (Defn f xs (label-λ e))]

[(Prim1 p e)     (Prim1 p (label-λ e))]

[(Prim2 p e1 e2) (Prim2 p (label-λ e1) (label-λ e2))]

[(If e1 e2 e3)   (If (label-λ e1) (label-λ e2) (label-λ e3))]

[(Begin e1 e2)   (Begin (label-λ e1) (label-λ e2))]

[(Let x e1 e2)   (Let x (label-λ e1) (label-λ e2))]

[(LetRec bs e1)  (LetRec (map (lambda (xs) (map label-λ xs)) bs) (label-λ e1))]

[(Lam '() xs e)  (Lam (gensym 'lam) xs (label-λ e))]

[(Lam n xs e)    (Lam (gensym n) xs (label-λ e))]

[(App f es)      (App (label-λ f) (map label-λ es))]

[_               e]))

Here it is at work:

Examples

> (label-λ (parse     '(λ (t)       ((λ (f) (t (λ (z) ((f f) z))))        (λ (f) (t (λ (z) ((f f) z))))))))

'#s(Prog () #s(Lam lam7263 (t) #s(App #s(Lam lam7264 (f) #s(App #s(Var t) (#s(Lam lam7265 (z) #s(App #s(App #s(Var f) (#s(Var f))) (#s(Var z))))))) (#s(Lam lam7266 (f) #s(App #s(Var t) (#s(Lam lam7267 (z) #s(App #s(App #s(Var f) (#s(Var f))) (#s(Var 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:

; Expr -> (Listof Variable)

(define (fvs e)

(define (fvs e)

(match e

[(Prim1 p e)     (fvs e)]

[(Prim2 p e1 e2) (append (fvs e1) (fvs e2))]

[(If e1 e2 e3)   (append (fvs e1) (fvs e2) (fvs e3))]

[(Begin e1 e2)   (append (fvs e1) (fvs e2))]

[(Let x e1 e2)   (append (fvs e1) (remq* (list x) (fvs e2)))]

[(LetRec bs e1)  (let ((bound (map car bs))

(def-fvs (append-map fvs-bind bs)))

(remq* bound (append def-fvs (fvs e1))))]

[(Lam n xs e1)   (remq* xs (fvs e1))]

[(Var x)         (list x)]

[(App f es)      (append (fvs f) (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 '() xs e) (error "Lambdas must be labelled before code-gen")]

[(Lam f xs e)

(let* ((free (remq* xs (fvs e)))

; leave space for RIP

(env (parity (cons #f (cons #f (reverse (append xs free)))))))

(seq

(Label (symbol->label f))

; we need the #args on the frame, not the length of the entire

; env (which may have padding)

; Ignore tail calls for now

(compile-e e env)

(Ret)))]))

The compiler will need to generate one such function for each λ-expression in the program. So we use a helper function for extracting all the λ-expressions and another for compiling each of them:

; LExpr -> (Listof LExpr)

; Extract all the lambda expressions

(define (λs e)

(match e

[(Prog ds e)     (append (append-map λs ds) (λs e))]

[(Defn f xs e)   (λs e)]

[(Prim1 p e)     (λs e)]

[(Prim2 p e1 e2) (append (λs e1) (λs e2))]

[(If e1 e2 e3)   (append (λs e1) (λs e2) (λs e3))]

[(Begin e1 e2)   (append (λs e1) (λs e2))]

[(Let x e1 e2)   (append (λs e1) (λs e2))]

[(LetRec bs e1)  (append (append-map lambda-defs bs) (λs e1))]

[(Lam n xs e1)   (cons e (λs e1))]

[(App f es)      (append (λs f) (append-map λs es))]

[_               '()]))

; [Lam] -> Asm

(define (compile-λ-definitions ds)

(seq

(match ds

['() (seq)]

[(cons d ds)

(seq (compile-λ-definition d)

(compile-λ-definitions ds))])))