Lambda the Ultimate

For the past few months I've been working on a language that I thought of as a hybrid of Scheme and Erlang. Lisp-1, non-hygienic macros, message-passing concurrency, implicit parallelism on function args, single assignment, no mutable values. Mostly I'm pleased with what I've learned from it, but today I realized that I couldn't see it as a usable language.

The problem is that single assignment prevents the user from redefining functions at the REPL. Or, rather, you can do it (it creates a new environment containing the new binding), but it doesn't affect the functions that use the old binding. I don't have a problem with that in ML; but I just couldn't see myself using a Lisp that didn't let me redefine functions.

I just wanted to post about it, on the theory that we don't see enough people talking about their failures. Maybe somebody else will see this and avoid the trap I painted myself into; or maybe they'll be inspired to find a way I didn't think of.

Oh, and why single assignment? Because it means that environments are immutable, too—the only time you get to bind is when you create a new environment, with (let)—which means that environments can safely be shared across processes, which makes processes cheaper. It also means that it's relatively safe to evaluate function arguments in parallel, since there are no assignments to get out of order. (It's only relatively safe, though, since message send/receive could get misordered.)

One decision that I'm still pleased with: I disallowed arbitrary cons cells; all lists are proper lists, as in, say, ML. I'm of the opinion that Lisp constructs such as (1 2 3 . 5) are more trouble than they're worth; every time you iterate over a list, you have to decide whether to check for improper lists or just have (car) throw an error. Also, when all lists are proper, and immutable, more optimizations become possible, such as, under the hood, using an array instead of a linked list.

In First-class Macros Have Types, POPL 2000, Alan Bawden describes a way to make macros behave as first class values.

In modern Scheme, a macro captures the lexical environment where it is defined. This creates an opportunity for extending Scheme so that macros are first-class values. The key to achieving this goal, while preserving the ability to compile programs into reasonable code, is the addition of a type system. Many interesting things can be done with first-class macros, including the construction of a useful module system in which modules are also first-class.

Bawden points out that while he used a static type system...

[t]here is no fundamental reason why this macro type system needs to be static. The same safety could be achieved using dynamic typing....The compiler would emit code to check the tags at runtime to make sure that a value used as an operator always had the type that the programmer promised the compiler it would have.