The Kernel Programming Language (2010)

Would you recommend Common Lisp as the lisp dialect for a new beginner and for an eventual hobby project? Do you recommend SBCL over other Common Lisp implementations?

Because everything is a fexpr, with lambda built on top of it, when you call a function you're not passing it values, you're passing it code and a first class environment to use to execute it.

Further, because macro like features are first class, they're executed each time they're used as opposed to generating code.

I believe there are decent implementations but I bet they put a fair amount of work in to making them fast. The naive reference implementation is extremely slow.

While my toy project is a bit different and probably even more wasteful (with a list calling convention and immutability), it faces similar challenges. Take a read through core.clj and try to spot where the 88 million function calls are spent.

A naive implementation has to do a ridiculous number of scope lookups, even before you get to anything else.

Also instead of compile time macros, one has runtime fexprs, which means the equivalent of macro expansion happens every invocation.

However, one can have kernel style semantics with at least moderately reasonable performance by basically applying a combination of constant folding and expansion caching.

It's a bunch of extra effort though, and non-trivial to make work, though I'm currently experimenting myself with something where I'm willing to do that.

A key part is to be able to recognise fexprs that are 'really' just macros and pre-expand them and cache the expansion - without at least that you're screwed.

I'm also experimenting with what else I can cache given the principle that everything is a lexical environment.

I'm rather enjoying myself ... but understand the risks.

I hope you mean it's not of much practical use to languages that already support macro definitions :) because otherwise, some would consider it very useful to be able to define arbitrary macros/syntactic forms!

For more detail on how this works, I'll try to describe how it is implemented.

When the evaluator sees a combination such as (f (x y)), it evaluates f and checks if the result is a combiner (and terminates if not). It then tests if f is operative, and if so, it passes the operand list (x y) to the body of f, along with the current environment. If f is applicative, it evaluates each item in the operand list (by recursively calling the evaluator on each individually) to produce a list of arguments. The evaluator then conses the underlying combiner of the applicative with the argument list, and recursively calls the evaluator with the result. Something like this:

    ($define! eval 
      ($lambda (object env)
        ($if (not? (environment? env))
          (error "Second argument to eval must be an environment")
          ($cond ((symbol? object) (lookup env object))
                 ((pair? object)
                     ($let ((comb (car object)))
                         ($cond ((operative? comb) (call comb (cdr object)) env)
                                ((applicative? comb)
                                   ($let ((app (unwrap comb))
                                          (args (eval-list (cdr object) env)))
                                       (eval (cons app args) env)))
                                (#t (error "The first item of a combination must be a combiner")))))

                 ;; If object is neither symbol nor pair, it must be a self-evaluating term.
                 (#t object)))))

The primitives used here, which I'll leave out for brevity:

    (lookup env symbol) ; returns the expression mapped to the symbol in the dynamic environment env.
    (call operative operand env) ; calls operative with operands and the dynamic environment.
    (unwrap applicative) ; returns the underlying combiner of the applicative.
    (eval-list objs env) ; evaluate each item in the list objs using the dynamic environment, in no specific order.

You can see the simplicity of this interpreter. It does not need special consideration for operators like || and &&, or any other special form. The only special forms are the primitives themselves, which are all operatives. The behaviour of `call` depends on whether or not an operative is primitive or not. Primitives are implementation specific as they're part of the interpreter itself.

Operatives which are not primitive are called compound operatives, and are constructed using $vau, as in the above example for the $and? operative. It has the form:

    ($vau formal-parameter-tree  symbol-for-dynamic-env  operative-body)

You can consider a compound operative to merely be a structure (or 4-tuple) which stores its 3 arguments plus the environment which is passed to `call` when the `$vau` operative itself is evaluated. (The static environment of the operative)

When the compound operative is later called, it constructs a new environment with its static environment as the parent, called the local-evironment. It then maps, in the local-environment, each symbol from its formal parameter tree to the respective operand in the operand list passed to it (the structures of the operands must match the parameter tree). It also maps the symbol-for-dynamic-environment to the environment passed to it by eval. Call then simply evaluates the body of the combiner with `local-environment` as the environment. Eg:

    ($define! call-compound-operative 
      ($lambda (operative operands env)
        ($let ((local-env (make-environment (get-static-env operative))))
            (set-parameters! local-env (get-parameter-tree operative) operands)
            (set! local-env (get-symbol-for-dynamic-env operative) env)
            (eval (get-body operative) local-env))))

> Most languages don't offer any alternative, although Lisp does offer alternatives, which are to quote x, or to implement f as a macro which is expanded at compile time.

Mathematica allows you to pass symbolic expressions in this way too, no?