Parsing, Racket-style "Syntax Objects" and Operand Capture

[Brandon Bloom]

Hi all,

I'm working on an interpreter for a superset of Clojure that I'm calling Extensible Clojure, or EClj for short. EClj will have first-class environments, fexprs, and a programable effect system in the style of Eff. In the process of developing EClj, I think I've discovered a convenient solution to the "Operand Capture" problem described in the Kernel literature.

Operating on the design principle that composability prefers singular, centralized values, I decided to merge expressions and their environments in to Syntax Objects in the style of Racket. After the reader, traditional analyzers produce decorated abstract syntax trees. Unlike the traditional approach, syntax objects are shallow: The recursion is provided by the evaluator, not the analyzer/parser. Because of this, it plays nicely with fexpr's outside-in explicit evaluation style. When parsing a list in to a syntax object, I can do one layer of sub-parsing to ensure lexical environment is preserved unless explicitly discarded.

Consider some symbol x and some environment e. In Clojure notation, (map->Syntax {:head :name, :form x, :env e}) would produce a record that prints as #Syntax{:head :name, :form x, :env e}. Records are like maps, but are tagged differently for the purposes of equality and type dispatch. The evaluator operates on syntax objects and dispatches on the :head key.

Parsing a list like (f x) would result in a syntax object of the form #Syntax{:head :invoke, :f f, :args [x], :env ...}

So now consider:

(defn call [f x] (apply f [x]))

(call quote 1)

With Kernel-style semantics, this would break the hygiene of call. However, once implemented, EClj will parse this as:

#Syntax{:head :invoke, :f #Syntax{:head :eval, :form f, :env {f ..., x 1, ...}}, :args [#Syntax[{:head :eval, :form x ...

The :head :eval is basically an intentional deferral of the shallow analysis. Instead of parsing a symbol to :head :name, the syntax objects are simply bundling a form with an environment. In this case, the :f key would be evaluated, resolved to an fexpr, and then applied to the :args key. The result would be:

'#Syntax{:head :eval, :form x, :env {x 1, ...}}

Note the leading quote. Quoting syntax is an idempotent no-op, but eval undoes the syntax. And since the syntax holds the lexical environment, the following works as expected:

(eval (call quote 1)) ; returns 1

If you want to write a fexpr that examines the form of its arguments, you simply extract the :form key and operate on that.

I plan to implement this quite soon, but I figured I'd type my notes up for public consumption. Please let me know if this is clear and/or makes any sense at all. I'm curious to hear what fexpr-savvy folks think of this approach.

Cheers,

Brandon