Lisp Workshop  Step 5: Lambda
THIS PAGE IS A WORK IN PROGRESS
The theory section isn’t yet complete, and not all of the tasks have been added. If you’re done with all of the extra tasks from the previous steps, and you’re comfortable with a harder challenge, feel free to attempt the tasks here. If not, please be patient  we’re working as hard as we can to get this finished!
Complexity: Long
 motivation: simple arithmetical functions? reuse RSA from earlier?
 explain parameters/arguments
 explain application
 capture avoiding substitution (not necessary?)
 beta reduction
 closures
 recursion? currently just extra task, maybe it’s worth spinning this into a separate step?
 desugaring (extra section in extra tasks?)
Task
Add a special form to your interpreter, called lambda
. It takes two arguments; a symbol n
, and an expression e
. When evaluating a lambda applied to an argument v
, a lambda should add n > v
to the environment when evaluating e
.
((lambda x (+ x 1)) 41)
> (+ x 1) [environment now contains (x > 42)]
> (+ 41 1)
> 42
Be sure to watch out for cases like (lambda x (lambda x (+ x 1)))
! Make sure the inner x
takes precedence over the outer x
. As an example, ((lambda x (lambda x (+ x 1))) 1 2)
should evaluate to 3
, not 2
. Not convinced? Step through this problem on pen and paper by substituting the arguments one by one.
You should also extend your define
function to accept the following form:
(define func (arg) body)
which should be equivalent to:
(define func (lambda arg body))
You can check the number of elements in a define
expression to determine which form to use, or you couuld just offer the new form under a different name (defun
is quite common). Both are perfectly sensible ways to implement this; think about which one you’d prefer to use when writing a program!
Once this is done, you’ll have implemented a fully Turing complete programming language! Congratulations!
Extra Challenges
These are some extra challenges you can attempt to build your understanding further, and make your interpreter more featurecomplete. None of them are required for a fullyfunctional interpreter. They are listed in order of subjective difficulty; if you struggle on the later ones, you should move on to the next step and come back later. Depending on your language choice, they might be easier or harder than anticipated!

Add support for let statements. Let statements are convenient syntactic sugar for temporarily binding an expression to a name. In Lisp, these look like this:
(let ((x 1) (y 2)) (+ x y))
This expression should return:
3
let
takes two arguments: a list of pairs of symbols and expressions, and an expression. We’re representing a list as an SExpression with an arbitrary number of elements, and a pair as an SExpression with exactly two elements. It’s perfectly fine to hardcode this syntax into your evaluator.Semantically,
(let ((x v)) e)
is equivalent to((lambda x e) v)
, and(let ((x1 v2) (x2 v2)) e)
is equivalent to(let ((x1 v1)) (let ((x2 v2)) e)))
. We recommend that you directly desugarlet
expression in this way; it saves you from having to implement capture avoiding substitution again! 
Allow
lambda
s and toplevel declarations to take more than one argument.Hint: desugar
(lambda (x y z) e)
into(lambda x (lambda y (lambda z e)))

Support recursion in toplevel definitions.
For example, when evaluating the following file:
(define factorial (n) (if (equals? 0 n) 1 (+ n (factorial ( n 1))))) (factorial 5)
you should see:
120

Write a selfhosting interpreter. This means reimplementing everything you’ve done so far as a program in your language.