Fexpr

In Lisp programming languages, a fexpr is a function whose operands are passed to it without being evaluated. When a fexpr is called, only the body of the fexpr is evaluated; no other evaluations take place except when explicitly initiated by the fexpr. In contrast, when an ordinary Lisp function is called, the operands are evaluated automatically, and only the results of these evaluations are provided to the function; and when a (traditional) Lisp macro is called, the operands are passed in unevaluated, but whatever result the macro function returns is automatically evaluated.

Origin of the name "fexpr"

In early Lisp, the environment mapped each symbol to an association list, rather than directly to a value.McCarthy et al., ''Lisp I Programmer's Manual'', pp. 88–91. Standard keys for these lists included two keys used to store a data value, to be looked up when the symbol occurred as an argument ( and ); and four keys used to store a function, to be looked up when the symbol occurred as an operator. Of the function keys, indicated a compiled ordinary function, whose operands were evaluated and passed to it; indicated a compiled special form, whose operands were passed unevaluated; indicated a user-defined ordinary function; and indicated a user-defined special form. The only difference between a FEXPR and an EXPR was whether the operands were automatically evaluated.

In strict original usage, a FEXPR is therefore a user-defined function whose operands are passed unevaluated. However, in later usage the term ''fexpr'' may describe any first-class function whose operands are passed unevaluated, regardless of whether the function is primitive or user-defined.Pitman, ''The Revised MacLisp Manual'', p. 75.

Example

As a simple illustration of how fexprs work, here is a fexpr definition written in the Kernel programming language, which is similar to Scheme. (By convention in Kernel, the names of fexprs always start with .)

($define! $f
($vau (x y z) e
($if (>=? (eval x e) 0)
(eval y e)
(eval z e))))

This definition provides a fexpr called , which takes three operands. When the fexpr is called, a local environment is created by extending the static environment where the fexpr was defined. Local bindings are then created: symbols , , and are bound to the three operands of the call to the fexpr, and symbol is bound to the dynamic environment from which the fexpr is being called. The body of the fexpr, ..., is then evaluated in this local environment, and the result of that evaluation becomes the result of the call to the fexpr. The net effect is that the first operand is evaluated in the dynamic environment, and, depending on whether the result of that evaluation is non-negative, either the second or the third operand is evaluated and that result returned. The other operand, either the third or the second, is not evaluated.

This example is statically scoped: the local environment is an extension of the static environment. Before about 1980, the Lisp languages that supported fexprs were mainly dynamically scoped: the local environment was an extension of the dynamic environment, rather than of the static environment.Steele and Gabriel, "The Evolution of Lisp", pp. 239–240. However, it was still sometimes necessary to provide a local name for the dynamic environment, to avoid capturing the local parameter names.Pitman, ''The Revised MacLisp Manual'', p. 62

Mainstream use and deprecation

Fexpr support continued in Lisp 1.5, the last substantially standard dialect of Lisp before it fragmented into multiple languages.Steele and Gabriel, "The Evolution of Lisp", pp. 231-232. In the 1970s, the two dominant Lisp languagesSteele and Gabriel, "The Evolution of Lisp", p. 235. — MacLisp and Interlisp — both supported fexprs.Pitman, ''The Revised MacLisp Manual'', p. 182.

At the 1980 Conference on Lisp and Functional Programming, Kent Pitman presented a paper "Special Forms in Lisp" in which he discussed the advantages and disadvantages of macros and fexprs, and ultimately condemned fexprs. His central objection was that, in a Lisp dialect that allows fexprs, static analysis cannot determine generally whether an operator represents an ordinary function or a fexpr — therefore, static analysis cannot determine whether or not the operands will be evaluated. In particular, the compiler cannot tell whether a subexpression can be safely optimized, since the subexpression might be treated as unevaluated data at run-time.

Since the decline of MacLisp and Interlisp, the two Lisp languages that had risen to dominance by 1993Steele and Gabriel, "The Evolution of Lisp", pp. 245–248 — Scheme and Common Lisp — do not support fexprs. newLISP does support fexprs, but calls them "macros". In Picolisp all built-in functions are , while Lisp-level functions are exprs, fexprs, , or a mixture of those.

Fexprs since 1980

Starting with Brian Smith's 3-Lisp in 1982, several experimental Lisp dialects have been devised to explore the limits of computational reflection. To support reflection, these Lisps support procedures that can reify various data structures related to the call to them — including the unevaluated operands of the call, which makes these procedures fexprs. By the late 1990s, fexprs had become associated primarily with computational reflection.Wand, "The Theory of Fexprs is Trivial", p. 189.

Some theoretical results on fexprs have been obtained. In 1993, John C. Mitchell used Lisp with fexprs as an example of a programming language whose source expressions cannot be formally abstract (because the concrete syntax of a source expression can always be extracted by a context in which it is an operand to a fexpr).Mitchell, "On Abstraction and the Expressive Power of Programming Languages", section 7. In 1998, Mitchell Wand showed that adding a fexpr device to lambda calculus — a device that suppresses rewriting of operands — produces a formal system with a trivial equational theory, rendering it impossible to make source-to-source optimizations without a whole-program analysis. In 2007, John N. Shutt proposed an extension of lambda calculus that would model fexprs without suppressing rewriting of operands, avoiding Wand's result.Shutt, "vau-calculi and the theory of fexprs".

See also

* ISWIM
* DWIM

The following languages implement fexprs or near equivalents:

* the ECL programming language provides parameter type ("bind-class") UNEVAL, which specifies that a syntax tree for the argument expression is to be bound to the parameter.
* io, methods (blocks) can use introspection, using call to refer to the entire call and manipulate that. Se
call and self slots in io

* Kernel uses $vau to create fexprs, similar to how lambda creates functions in Scheme.
* newLISP uses define-macro to define fexprs. Se
section "Fexpr macros and rewrite macros"

* In PicoLisp, (de foo X ...) defines an fexpr foo that when called binds X to the list of unevaluated argument expressions. Se
Evaluation in PicoLisp

* R parameters are generally bound to promises (resulting in lazy evaluation), and calling substitute(param) on a parameter yields the argument expression, se
Substitutions in R

* In REBOL, argument expressions not to be evaluated need to be wrapped in a block (square brackets) by the caller. In other words, you can not define a callee that prevents argument evaluation. Se
this article
with examples. In this sense, REBOL does not have fexprs, it just makes it easy to emulate some of their uses. In a language with true fexprs, fexpr calls look like normal function calls. In REBOL on the other hand, calls where the arguments are not evaluated always look different from normal function calls.

Footnotes

References

* Accessed May 11, 2010.
* John C. Mitchell

''Science of Computer Programming'' 212 (1993), pp. 141–163. (Special issue of papers from Symp. Theor. Aspects of Computer Software, Sendai, Japan, 1991.) Accessed January 24, 2008.
* Kent M. Pitman

Proceedings of the 1980 ACM Conference on Lisp and Functional Programming, 1980, pp. 179–187. Accessed January 25, 2008.
* Kent M. Pitman, ''The Revised MacLisp Manual'' (Saturday evening edition), MIT Laboratory for Computer Science Technical Report 295, May 21, 1983.
* John N. Shutt, "vau-calculi and the theory of fexprs", talk
New England Programming Languages and Systems Symposium Series (NEPLS)
October 18, 2007

accessed January 27, 2008.
* Guy L. Steele and Richard P. Gabriel, "The Evolution of Lisp", ''ACM SIGPLAN Notices'' 28 no. 3 (March 1993), pp. 231–270.
* Mitchell Wand

''Lisp and Symbolic Computation'' 10 no. 3 (May 1998), pp. 189–199. Accessed January 25, 2008.

{{refend

Lisp (programming language)
Programming constructs