Back when I was in high school (back in the early 1980’s) I learned Lisp. One of the things I really liked about the language was it’s expressiveness: because the language was such as simple one, it was fairly easy to build recursive pattern-matching and recursive search algorithms on arbitrary S-expressions, which made the development of things like a recursive descent algorithm for theorem proving relatively straight forward.

So my goal is to build an embedded Lisp interpreter/byte-code compiler that can run on a “small” footprint such as the iPhone.

(Note: I put “small” in quotes because, honestly, an iPhone is not a “small” device, CPU wise or memory-wise in the scope of the types of CPUs and memory footprints where Lisp was originally used. Back in the 80’s a computer as powerful as the iPhone with as much memory would have filled a room and cost millions.)

There are some language decisions that need to be made first.

Dynamic binding verses Lexical binding

“Binding” expresses the relationship between a variable and it’s value. A variable “a” is bound to “1” when you write an expression “a = 1;” in C.

In the Lisp world there are two types of binding: lexical binding and dynamic binding.

To summarize, lexical binding is similar to C: there are global variables and variables within the scope of a function. A function defines the variables used within that function, and when a variable is resolved, the interpreter looks for variables either within the immediate function scope or in global scope.

Dynamic binding, first demonstrated in the original Lisp language, is different. Instead, there are nothing but a global stack of variables. A function call may declare new variables or variables that are already existing in the global pool; the new variables are added to the list of variables, and when the function returns, those variables that shadowed others already in the pool have their values effectively put back.

One way to think of dynamic binding is to think of all of the variables in the current system in a linked list of variables:

This shows the variables a, b and c defined in our system. When we resolve a variable ‘a’, we start from the pointer ‘globals’, and walk the list until we find ‘a’; we then use that location for our variable binding.

Now suppose we call into a new function ‘foo’ defined as

(define (foo a) ...some function...)

When we invoke the function (foo 5) the invocation will push a new variable ‘a’ onto our global list of variables, saving the old value of the global pointer onto a stack:

When we then resolve the value of variable ‘a’, we walk the global list, and find the first variable ‘a’, which shadows the old variable ‘a’.

The upshot of dynamic verses lexical assignments is that the variable value to use within a function is dependent on the current global context in a dynamic environment, while in a static environment the value is completely defined: it is either locally declared or a global (albeit undefined) value.

So, in the following example:

(define a 1)
(define b 2)
(define c 3)

(define (foo a) (bar))
(define (bar) a)

Invoking (foo 5) in a dynamic environment would mask the value of a = 1 in our global stack, so when (bar) is invoked, a resolves to 5:

> (foo 5)
5

However, in a lexical environment, when bar is defined, the variable ‘a’ is bound to the global definition of ‘a’, as it would be in C. Thus, invoking (foo 5) does not mask the value of the global variable ‘a’ in bar, and invoking (foo 5) returns 1:

> (foo 5)
1

From my perspective, I would personally prefer a lexical LISP to a dynamic LISP, for two reasons:

(1) Because the variables are completely defined within the context of a single function call, it is easier to compile Lisp statements: as we process each statement, we know where in the list of global variables the variable will be. If we haven’t seen the variable, we can simply create a new undefined variable in the global variable space. This means our compiler can create a global array of variables, and each variable name resolves to a fixed index in that global array of variables.

The same can be said of local variables: as we invoke a function we create a new array of local variables: entering a function pushes a fixed size array onto an invocation stack, and all local variable references become a fixed index into that array.

Thus, variable resolution is linear in time.

(2) Functions are “well-defined” rather than depends on side effects, and we minimize accidentally breaking a function that relies on global variable state.

Poor function ‘bar’ would be in serious trouble if we depended on the global variable ‘a’ and it was aliased by accident by another function that calls ‘bar’.

Fexprs verses macros

Yes, I know supposedly this has been settled in favor of macros since the 1980’s and the publishing of Kent Pitman’s “Special Forms in Lisp” where he condemned the use of fexpr functions because you cannot perform static analysis on the forms. (Paper)

But I’d like to revisit the whole thing for just a moment.

In Lisp, a function call such as (+ a b) first evaluates a, then b, then calls the function ‘+’. So if a = 5 and b = 3, then we evaluate a, evaluate b, then add them together to return 8.

So far so good. But what if you want to set the value of a to 5 via a function via a hypothetical ‘set’ function. The natural way to write this would be (set a 4); however, this would first evaluate a (to 5), evaluate 4 (which is a special form which evaluates to itself), then calls the function ‘set’ with the arguments 5 and 4–which is illegal.

To get around this, we could use the ‘quote’ “function”, a special form of “function” which returns the literal value of it’s parameter: (quote a) evaluates to the literal ‘a’, and then write (set (quote a) 4)–which will call the function ‘set’ with the arguments ‘a’ and 4.

Ideally, though, we’d like to create a new function, call it ‘setq’, which automatically quotes the first parameter, evaluates the second, then passes them to our ‘set’ function.

When Lisp was first invented in the 1960’s, this was done using a special form, the fexpr function, which does not evaluate it’s parameters prior to invoking the function. This allows us to then define our ‘setq’ function. Using ‘nlambda’ syntax which indicates a fexpr function which does not evaluate it’s parameters, we could define setq as follows:

(define setq 
  (nlambda (var val) 
           (set var (eval val))))

This defines the symbol ‘setq’ as a lambda form which does not evaluate it’s parameters. Setq takes two parameters: ‘var’ and ‘val’. We then invoke our ‘set’ function with the value of ‘var’, but we evaluate the value in ‘val’. So when we invoke (setq a 5):

(setq a 5) ->
  [nlambda is invoked with var = 'a, val = '5, which expands to]
  (set 'a (eval '5)) ->
  (set a 5)

The beauty of being able to define our own fexprs via the nlambda mechanism is that we can quickly define a number of the special forms, such as quote:

(define quote (nlambda (a) a)))

Now, reviewing the Kent Pitman paper, it’s clear the first complaint he has, under the section “The Compiler’s Contract”, in fact has nothing to do with fexprs, and everything to do with compiling in a dynamic environment. But since I’ve decided above to use a lexical binding environment in my form of Lisp, the problem outlined in this section just goes away.

The second problem with fexprs, however, boils down to the problem of compilation: when compiling a function we cannot know how to generate the correct code to invoke a function within our compiled function unless we know if the code we’re calling is a regular lambda function or a special ‘nlambda’ function. To illustrate, suppose we define our ‘lambda’ keyword to invoke a compiler to compile our S-expression into a compiled form. So, we write the function:

(define foo (lambda (a) (bar a 5)))

Now, assuming ‘lambda’ compiles the parameters and body of our program into machine pseudo-code, and if we know all functions are lambda functions, then we could easily generate the following code:

function_prefix(1,0);   -- Special form which pulls 1 local variable from the stack into 'a'

push(0);                -- Push a (variable 0) onto stack
push_const(5);          -- Push constant 5 onto stack
call(bar);              -- Call bar. Return value puts value of bar onto stack

function_postfix;       -- Unwind the local variables, leaving the return value alone.

Here’s the thing, though: If ‘bar’ was a special ‘nlambda’ function, this behavior is incorrect. Instead, we would have wanted to generate:

function_prefix(1,0);   -- Special form which pulls 1 local variable from the stack into 'a'

push(a);                -- Push the symbol a onto stack
push_const(5);          -- Push constant 5 onto stack
call(bar);              -- Call bar. Return value puts value of bar onto stack

function_postfix;       -- Unwind the local variables, leaving the return value alone.

That is, how we compile a call to bar requires us to know if bar is a lambda or an nlambda function.

There are three solutions to this problem.

• Punt on fexpr forms and use macros instead.

The disadvantage of this solution is that we cannot define a number of very basic forms in Lisp; instead, our interpreter is complicated by having to redefine a number of basic forms (quote and cond, for example) as function calls into a special interpreter. This significantly increases the bootstrapping of an interpreter, since we need to handle a whole bunch of special forms, rather than just writing those special forms in Lisp and compiling them with our Lisp compiler.

• Require that any compiler we build compile against the full environment.

What this would mean is that rather than using the lambda and nlambda keywords to generate a compiled expression, we just use these keywords as markers, and our apply method (which evaluates lambda expressions) use those keywords to determine how it will interpret the expression. We then create a separate compile keyword which compiles functions based on the complete environment present at the time: at compile time we depend on all of the functions being available so we can make the determination if a function is a lambda or an nlambda form.

So our compile function would have the semantics of replacing a variable ‘a’ defined as (lambda vars prog) to a special #proc object containing byte code. It would fail if all of the functions invoked within the lambda procedure are not defined.

• Presume any function not defined (and any variable not defined) are lambda form functions.

This third option allows us to define lambda and nlambda as entry points into our bytecode compiler, with nlambda also marking the procedure as a special fexpr function. If we don’t see the function declared already, we then assume the function is a lambda form.

Because compilation does two things: it marks the type of function, and it compiles the function, if we have a situation where the definition of an fexpr form relies on a later fexpr form that hasn’t been defined yet, we could potentially use this fact by writing:

(define a (nexpr (b c) '()))   ;;; Dummy form

(define b (nexpr (i) 
   ...
   (a foo bar)                 ;;; Our call to a, knowing a is an fexpr
   ...)

(setq a (nexpr (b c) 
   ... the real code for a ... )

I suspect this shouldn’t happen very often. We could even put in a special check in our assignment operation to complain if we change the type of our global variable assignment between a normal function and an fexpr style function.

My take is to use fexpr forms; they greatly simplify bootstrapping a Lisp interpreter. I also plan to structure the compiler with the third option: variables that haven’t been defined yet in the global namespace will be automatically defined as the special symbol ‘undefined’ (so we know it’s index in the global space), and will be presumed to be a normal lambda function if invoked. This allows me to use the ‘lambda’ and ‘nlambda’ keywords as entrypoints into my bytecode compiler.

This afternoon I’m going to see if I can’t hack a little on my interpreter in Lisp; as I go along I will update this category with my results.