Fexpr

Fexpr is a noun.  It's pronounced FEKSper.  A fexpr is a procedure that acts on the syntax of its operands, rather than on the values determined by that syntax.

This is only in the world of Lisp programming languages — not that only Lisps happen to have fexprs, but that having fexprs (and having the related characteristics that make them a really interesting feature) seemingly causes a programming language to be, at some deep level, a dialect of Lisp.  That's a clue to something:  although this acting-on-syntax business sounds superficial, it's a gateway to the deepest nature of the Lisp programming-language model.  Fexprs are at the heart of the rhyming scheme of Lisp.

Data as programs

When Lisp reads a syntax (i.e., source code) expression, it immediately represents the expression as a data structure; or at least, in theory it does.  For fexprs to even make sense, this would have to be true:  a procedure in a program acts on data, so if you're passing the operand syntax expressions to a procedure, those expressions have to be data.  The Lisp evaluator then interprets the syntax expression in data form, and that's the whole of Lisp:  read an expression and evaluate it, read another and evaluate it, and so on.

But Lisp was designed, from the start, specifically for manipulating an especially simple and general kind of data structures, essentially trees (though they can also be viewed as nested lists, hence the name of the language, short for LISt Processing).  And syntax expressions are represented as these same trees that are already Lisp's native data structure.  And, the Lisp evaluator algorithm isn't limited to data that started life as a representation of syntax:  any data value can, in principle, be evaluated.  Which means that a fexpr doesn't have to act on syntax.

The theory of fexprs

One reason it matters that fexprs can act on non-syntax, is because of a notorious theoretical result about fexprs.  Proving programs correct usually makes heavy use of determining whether any two source expressions are interchangeable.  When two source expressions may be operands to a fexpr, though, they won't be interchangeable in general unless they're syntactically identical.  So with fexprs in the language, no two distinct operands are ever universally interchangeable.  This was famously observed by Mitch Wand in a journal article back in 1998, The Theory of Fexprs is Trivial.

But while a fexpr can analyze any syntactic operand down to the operand's component atoms, computed operands are a different matter.  It's almost incidental that some computed data structures are encapsulated, so can't be fully analyzed by fexprs.  The more important point is, even if the structure resulting from computation can be fully analyzed, the process by which it was computed is not subject to analysis.  If a fexpr is given an operand 42, the fexpr can't tell how that operand was arrived at; it might have been specified in source code, or computed by multiplying 6 times 7, or computed in any of infinitely many other possible ways.

So, suppose one sets up a computational calculus, something like lambda-calculus, for describing computation in a Lisp with fexprs.  Source expressions are terms in the calculus, and no two of them are contextually equivalent (i.e., interchangeable as subterms of all larger terms).  But —unless the calculus is constructed pathologically— there are still very many terms in the calculus, representing intermediate states of subcomputations, that are contextually equivalent.

I've developed a calculus like that, by the way.  It's called vau-calculus.

Deep fexprs

We're about to need much better terminology.  The word fexpr is a legacy from the earliest days of Lisp, and procedure is used in the Lisp world with several different meanings.  Here's more systematic terminology, that I expanded from Scheme for use with the Kernel programming language.

A list to be evaluated is a combination; its first element is the operator, and the rest of its elements are operands.  The action designated by the operator is a combiner.  A combiner that acts directly on its operands is an operative.  (Legacy terms: an operative that is a data value is a fexpr, an operative that is not a data value is a special form.)  A combiner that isn't operative is applicative; in that case, the operands are all evaluated, the results of these evaluations are called arguments, and the action is performed on the arguments instead of on the operands.

It might seem that applicative combinations would be more common, and far more varied, than operative combinations.  Explicitly visible operatives in a Lisp program are largely limited to a small set, used to define symbols (in Kernel, mainly $define!  and $let), construct applicatives ($lambda), and do logical branching ($if  and $cond) — about half a dozen operatives, used over and over again.  The riotous variety of programmer-defined combiners are almost all applicative.

But looking closely at the above definition of applicative, it implies that every applicative has an operative hiding inside it.  Once an argument list has been computed, it's just another list of data values — and those values are then acted on directly with no further processing, which is what one does when calling an operative!  Applicative +, which evaluates its operands to arguments and then adds the arguments, has an underlying operative that just adds its operands; and so on.

Vau-calculus

In a computational calculus for fexprs, it's a big advantage to represent each applicative explicitly as a wrapper (to indicate the operands are to be evaluated) around another underlying combiner.  That way, the calculus can formally reason about argument evaluation separately from reasoning about the underlying actions.  Vau-calculus works that way.  The whole calculus turns out to have three parts.  There's one part that only represents tree/list structures, and no computation takes place purely within that part.  There's one part that only deals with computations via fexprs.  And then, linking those two, there's the machinery of evaluation, which is where the wrapper-to-induce-operand-evaluation comes in.

Fascinatingly, of these three parts of vau-calculus, the one that deals only with computations involving fexprs is (give or take) lambda-calculus.  One could reasonably claim —without contradicting Mitch Wand's perfectly valid result, but certainly contrasting with it— that the theory of fexprs is lambda-calculus.

(Vau-calculus seems a likely topic for a future blog entry here.  Meanwhile, if you're really feeling ambitious, the place to look is my dissertation.)

[Note:  I've since blogged on vau-calculus here.]

Kernel

What works for a computational calculus also works for a Lisp language:  represent each applicative as a wrapper around an underlying combiner.  The Kernel programming language does this.  An applicative unwrap  takes an applicative argument and returns the underlying combiner of that argument; and an applicative wrap  takes any combiner at all as an argument, and returns an applicative whose underlying combiner is that argument.

This makes Kernel a powerful tool for programmers to fluently manipulate the operand-evaluation process, just as the analogous device in vau-calculus allows reasoning about operand-evaluation separately from reasoning about the underlying lambda-calculus computations.

Kernel (evaluator)

Here's the central logic of the Kernel evaluator (coded in Kernel, then put in words).

($define! eval
   ($lambda (expr env)
      ($cond ((symbol? expr)  (lookup expr env))
             ((pair? expr)
                (combine (eval (car expr) env)
                         (cdr expr)
                         env))
             (#t  expr))))

($define! combine
   ($lambda (combiner operands env)
      ($if (operative? combiner)
           (operate combiner operands env)
           (combine (unwrap combiner)
                    (map-eval operands env)
                    env))))

To evaluate an expression in an environment:  If it's a symbol, look it up in the environment.  If it's a pair (which is the more general case of a list), evaluate the operator in the environment, and combine  the resulting combiner with the operands in the environment. If it's neither a symbol nor a pair, it evaluates to itself.

To combine a combiner with an operands-object:  If the combiner is operative, cause it to act on the operands-object (and give it the environment, too, since some operatives need that).  If the combiner is applicative, evaluate all the operands in the environment, and recursively call combine  with the underlying combiner of the applicative, and the list of arguments.

Kernel (fluently doing nothing)

When evaluating syntax read directly from a source file, the default case of evaluation —the one explained in boldface— is why a literal constant, such as an integer, evaluates to itself.  What makes it worth boldfacing, though, is that when evaluating computed expressions, that case helps keep environments from bleeding into each other (in Lisp terminology, it helps avoid accidental bad hygiene).  Here's a basic example.

Lisp apply  overrides the usual rule for calling an applicative, by allowing a single arbitrary computation-result to be used in place of the usual list of arguments.  The first argument to apply  is the applicative, and its second argument is the value to be used instead of a list of arguments.  In Kernel, and then in words:

($define! apply
   ($lambda (appv args)
      (eval (cons (unwrap appv) args)
            (make-environment))))

To apply an applicative to an args-object, construct a combination whose operator is the underlying combiner of the applicative, and whose operands-object is the args-object; and then evaluate the constructed combination in a freshly created empty environment.  When the constructed combination is evaluated, its operator evaluates to itself because it's a combiner.  This defaulting operator evaluation doesn't need anything from the environment where the arguments to apply  were evaluated, so the constructed combination can be evaluated in an empty environment — and the environment of the call to apply  doesn't bleed into the call to the constructed combination.

In a standard Kernel environment, (apply list 2) evaluates to 2.

A more impressive illustration is the way $lambda  can be defined hygienically in Kernel using more primitive elements of the language.  I should make that a separate post, though.  The earlier parts of this post deliberately didn't assume Lisp-specific knowledge at all, and in the later parts I've tried to ease into Lisp somewhat gently — but $lambda  gets into a whole nother level of Lisp sophistication (which is what makes it a worthwhile example), so it just feels logically separate.

[Note: I did later post on Kernel hygiene and $lambda, here.]