4 ms·
An FEXPR is similar to a function (EXPR), except that its operands are not be implicitly evaluated before being passed to the body of the FEXPR. Consider the fo
by sparkie 6y ago
An FEXPR is similar to a function (EXPR), except that its operands are not be implicitly evaluated before being passed to the body of the FEXPR. Consider the following:
(if (and a b) x y)
Were it the case that `if`, `and` were regular functions, then `b` would get evaluated even if `a` was #f (but we expect short-circuiting behavior). Also, both `x` and `y` would be evaluated, regardless of the condition, but we clearly only want to evaluate one or the other. Functions implicitly evaluate their operands before passing the resulting arguments to the body of the function.
In most lisps, `if`, `and`, `or` are not functions, but special forms which are second-class citizens. They must appear in their own names when used, and you can't assign them to another name.
FEXPRs are an abstraction which allow you to write your own "special forms", and decide how and whether or not the operands should be evaluated within the body of the FEXPR. They are unlike macros or quotation however, in that they don't merely suppress the evaluation of a syntactic list at some stage before regular evaluation, but they pass the parsed operand list to the body of the FEXPR during evaluation. FEXPRs are also first-class items, so you can assign them to a variable, and pass them around like first-class lambdas.
Consider the following (simplified) description for a evaluator:
EVAL takes a term, call it T.
If T is a symbol, look it up in the current dynamic environment and return the value to which it is mapped.
If not found, raise an error.
If T is a cons cell, take the CAR and call it C and take the CDR and call it L.
If C is an FEXPR, call C, passing the value L.
If C is an EXPR, evaluate each value in the list L, constructing a new list of results, call it A. Next, call C, passing the value A.
If C is neither an FEXPR nor EXPR, raise an error.
Otherwise, T must be a self-evaluating term, so return T.
Note that the core circular evaluator does not need to contain cases for special forms like `if`, `and`, `or`, `quote`, etc, as these should be implemented as FEXPRs. In this regard, the evaluator for a language supporting FEXPR may actually be simpler than one without.
The main area where FEXPR cause issues is due to the dynamic environment which was prevelant in the Lisps of its day, but features similar to FEXPRs have been used since in languages where lexical scoping is the default behavior, and the results are a bit more promising. Kernel in particular is worth checking out if you wish to explore further. (Start with: http://klisp.org/ http://klisp.org/). Also picolisp, which I'm less familiar with.
As some others have pointed out, FEXPRs do present a real problem in producing optimized code, because they are a runtime phenomena and not much can be reasoned about the behavior one might expect during compilation. A program using FEXPRs is likely to be slower than one using macros, which is likely the main reason they were sidelined. FEXPRs are more powerful than macros, but as the OP points out, usually too powerful that it becomes difficult or impossible to reason about programs.
The more constrained version used in Kernel is much easier to reason about, almost as powerful, but it does not resolve the performance issues, and attempts to try usually end up reinventing something like macros, which are less powerful.
While the OP argues that "`Safe' FEXPRs turn out to be the subsetof FEXPRs that can be understood as source->source translations," I would debate that in the context of Kernel, where its version of FEXPRs (called Operatives) are more tightly constrained due to a clever implementation of environments in Kernel. I have come across many safe use-cases for Operatives which would be difficult or impossible to express in macros. In general, I find them much more intuitive than macros, and quotation is completely unnecessary in Kernel (although possible, for better or worse).