A Better Let

The “let” form is, in my humble opinion, the worst bit of syntax in Lisp, requiring lots of superfluous parenthesis. I have devised a new syntax which removes these redundancies and improves readability.

<let> = ( let [<name> <exp>]* <exp>+ )

For example, the below expression:

(let ((x (* a a))
      (y (+ a a)))
  (- x y))

Can be expressed as:

(let x (* a a)
     y (+ a a)
  (- x y))

Which is much more pleasant. It is also quite easy to parse - here’s my implementation, which converts the bindings into an immediate lambda application:

(define (expand-let x vars vals)
  (if (or (pair? (car x)) (nil? (cdr x)))
      `((lambda ,(reverse vars) ,@x) ,@(reverse vals))
      (expand-let (cddr x)
                  (cons (car x) vars)
                  (cons (cadr x) vals))))

(define-macro (let . x)
  (expand-let x '() '()))

Another approach, which I am quite fond of, is extending the basic syntax of lambda so that we can introduce new bindings using an infix equality. The bindings can appear anywhere in the body except the very end since it must evaluate to a value.

<lambda> = ( lambda <formals> <stmt>* <exp> )
<stmt>   = <name> = <exp>
         | <exp>

The syntax is quite cute and convenient. It is mostly unambigous since there is no valid reason to evaluate a variable followed by an “=” in a lambda body. For example:

(lambda (a)
  x = (* a a)
  y = (+ x x)
  (- x y))

When we introduce a binding in the lambda body, it is as if the rest of the body is wrapped in another lambda taking the new binding as an argument. The above expression is equivalent to:

(lambda (a)
  ((lambda (x)
    ((lambda (y) (- x y))
     (+ x x)))
   (* a a)))

It would make sense to allow the binding syntax in other block forms such as begin. This is pretty trivial:

(define-macro (begin . exps)
  `((lambda () ,@exps)))

At the moment I am reading many papers (Citeseer and ACM Portal can be addictive!) on functional language implementation. My original interpreter which I wrote before the one I released here used an internal pre-compiled AST with parent-linked array activation frames. My current rewritten version uses a much less efficient direct interpretation of the list structure with association list environments. This was mainly done as a fun exercise - now I want to move onto something better.

Programs will again be represented by an AST. Variable nodes were previously represented as a (level, offset) pair where the level was the number of parent links you had to follow up from the current environment. I will now have three types of variable: locally bound (simply a stack offset), free (an offset into a free variable frame - see below), or global.

Closures will be represented by a code pointer and an array of free variables. Bound variables will be passed on the stack which we can deterministically push and pop, so we don’t need to garbage-collect normal activation frames, only free variable frames. If you don’t used closed variables you don’t have to pay the price. Mutable closed variables will in general require a ref cell.

A nice optimisation, if we create multiple lambdas which share the same free variables, would be to share a single free variable frame. The compiler could determine which implementation will use less space. In some cases this will eliminate the need for ref cells. This will make object-oriented techniques built on lambdas acceptably efficient.

I am also going to change my object representation so I can have unboxed tagged types such as fixed-sized integers, chars, booleans and nil.