diiq’s posterous

(mac while (test . body)
  (w/uniq (gf gp)
    `((rfn ,gf (,gp)
        (when ,gp ,@body (,gf ,test)))
      ,test)))

(def while ('test ... 'body)
  (when ,test *body (while ,test *body)))

Above, I've typed out two definitions of while.

Some experienced lisper, less calm and collected then you, dear reader, is already yelling at the screen about recursive macros and leaky abstractions. To them: just breathe. It'll be OK. I promise.

The first definition is from Arc, Paul Graham's hundred-year-language. The second is from Eight, an exotic lisp I've been growing in my hothouse. The differences between these two whiles illustrate much of the uniqueness of eight, so I'm going to dwell for a moment or two, and hopefully persuade a still-hyperventilating hacker that I'm not insane.

I'm going to start with the while from Arc (feel free to skip this discussion if you're particularly facile with macros in arc --- but reading it won't hurt).

  (mac while (test . body)

It's a macro, which means that its arguments will not be evaluated; instead, the syntax-tree --- the code itself --- will be bound to test and body. body is a dotted "rest" argument, so it will accept as many extra arguments as the function is given.

     (w/uniq (gf gp)

This line binds the symbols gf and gp to two unique symbols --- ones guaranteed never to accidentally appear anywhere else.  This is necessary to prevent a leaky abstraction due to variable capture. There are excellent discussions of this in On Lisp: http://www.bookshelf.jp/texi/onlisp/onlisp_10.html, and Practical Common Lisp: http://gigamonkeys.com/book/macros-defining-your-own.html#plugging-the-leaks . I'll assume that you're rolling your eyes, sighing softly, "We know all this, Sam!" Sorry! But these things you must remember, or nothing that follows will seem wondrous. Bear with me for three more lines.

     `((rfn ,gf (,gp)

rfn locally binds a function to the unique symbol bound to gf (I'll call it the 'gf-unique-function'). A local function is necessary because while is recursively defined, and the end condition is based on data, not code. A macro by itself would recurse infinitely, because it has no access to the evaluated value of the expression bound to test (which is why the backtick is there --- while generates an expasion rather than executing a function).

        (when ,gp ,@body (,gf ,test)))

Here's the body of the gf-unique-function. It says: "When the argument is true, both do the code that's been bound to body, and call gf-unique-function again with the expression bound to test as an argument."

      ,test)))

This line prepares the first call of the gf-unique-function with the expression in test as an initial argument.

Whew! Keep in mind that while is a simple macro. setforms, for example, is over 100 tokens long!

while in Eight looks like this:

  (def while ('test ... 'body)
          (when ,test *body (while ,test *body)))

The first line defines a function of two arguments. In eight, functions can either evaluate their arguments (like an arc function does) OR they can take unevaluated code (like a macro). They're a funcro. Uhhh... A maction? I call them velcros, if no one minds the copyright infringement. All that you need to keep in mind is that quoted argumentss (both arguments are quoted in this example) will be bound to unevaluated code. The elipsis signals a "rest" argument, just like the cons-dot in arc.

The second line says: when the evaluation of the code in test is true, execute the code from body, and then call while with the same arguments that were given originally.

All velcros in Eight are evaluated at runtime, and so have access to data as well as code. No local function is needed.

The poor anxious hyperventilating lisper is jumping up and down like a elementry-school student that needs to pee. "What about abstraction leaks!?! You're doomed!!!" (They probably mean to say, "If you're executing the code of test and body in this new context, won't there be the possibility of the variable capture of symbols test and body?")

Well, young'un, that would be true if I didn't have one more trick up my sleeve: the closure algebra. In eight, every object is a closure. (Needs-to-pee reader has gotten a puzzled look on their face, but has finally sat down. Maybe they ran out of exclamation marks.)

What I mean is that every symbol and every cons cell has an associated object which describes the bindings of the symbols inside --- just like a traditional closure describes the bindings of any free variables inside a function. In Eight, a closure is populated by the quote operator; when a chunk of code is quoted (that is, when it is transformed from code into data) it is scanned for currently-bound variables, and a set of bindings is generated. With a little work, cons, car, and cdr can be redefined to ensure that these closures behave as expected when combined and divided*.

When code is quoted and bound to test and body, all the symbols within that code remains bound to the proper values, regardless of the scope where it is finally executed.

Whoops! The rascal's back out of their little plastic chair, and they've knocked all the crayons off their desk. "Ooo! Ooo! What about anaphoric macros and abstractions that I want to leak and and! Ooo!"

I'll resist the urge to tousle their hair, and just mention the 'leak' operator, which introuces a leak into a closure at any time:

(def aif (it 'then ... 'elses)
  (if it ,(leak 'it then)
          (cdr elses)
           (aif *elses)
         ,(car elses)))

Here's arc's implementation, for comparison:

(mac aif (expr . body)
  `(let it ,expr
     (if it
         ,@(if (cddr body)
               `(,(car body) (aif ,@(cdr body)))
               body))))

*if you must, see my unrevised attempt to formalize the closure algebra here: http://wiki.github.com/diiq/eight/the-closure-algebra

CODA:

While Eight is still VERY much a work in progress, the current revision is available at http://github.com/diiq/eight/ .

It is my belief that runtime-macros make Eight essentially uncompilable. Does anyone have any ideas on how a cleverer person might tackle compiling such a language?

EDIT: capitalized Eight for clarity