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; while, 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
Association list
In computer programming and particularly in Lisp, an association list, often referred to as an alist, is a linked list in which each list element comprises a key and a value. The association list is said to associate the value with the key...
, rather than directly to a value. 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 (APVAL and APVAL1); and four keys used to store a function, to be looked up when the symbol occurred as an operator. Of the function keys, SUBR indicated a compiled ordinary function, whose operands were evaluated and passed to it; FSUBR indicated a compiled special form, whose operands were passed unevaluated; EXPR indicated a user-defined ordinary function; and FEXPR 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
First-class object
In programming language design, a first-class citizen , in the context of a particular programming language, is an entity that can be constructed at run-time, passed as a parameter, returned from a subroutine, or assigned into a variable...
function whose operands are passed unevaluated, regardless of whether the function is primitive or user-defined.
Key
Stores
Defined by
Function/Special form
APVAL
data value
--
--
APVAL1
data value
--
--
SUBR
function
system
function
FSUBR
function
system
special-form
EXPR
function
user
function
FEXPR
function
user
special-form
Example
As a simple illustration of how fexprs work, here is a fexpr definition written in the Kernel programming language
Kernel (programming language)
Kernel is a Scheme-like programming language by John N. Shutt in which all objects are first-class.-Example:In the programming language Scheme, and is a macro, because must not evaluate the division. This means it cannot be used in higher-order functions; it is second-class...
, 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 $f, which takes three operands. When the fexpr is called, a local environment
Namespace (computer science)
A namespace is an abstract container or environment created to hold a logical grouping of unique identifiers or symbols . An identifier defined in a namespace is associated only with that namespace. The same identifier can be independently defined in multiple namespaces...
is created by extending the static environment where the fexpr was defined. Local bindings are then created: symbols x, y, and z are bound to the three operands of the call to the fexpr, and symbol e is bound to the dynamic environment from which the fexpr is being called. The body of the fexpr, ($if ...), 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.
In computer programming, scope is an enclosing context where values and expressions are associated. Various programming languages have various types of scopes. The type of scope determines what kind of entities it can contain and how it affects them—or semantics...
: 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. However, it was still sometimes necessary to provide a local name for the dynamic environment, to avoid capturing the local parameter names.
Mainstream use and deprecation
Fexpr support continued in Lisp 1.5, the last substantially standard dialect of Lisp before it fragmented into multiple languages. In the 1970s, the two dominant Lisp languages — MacLisp
Maclisp
MACLISP is a dialect of the Lisp programming language. It originated at MIT's Project MAC in the late 1960s and was based on Lisp 1.5. Richard Greenblatt was the main developer of the original codebase for the PDP-6; Jonl White was responsible for its later maintenance and development...
Interlisp was a programming environment built around a version of the Lisp programming language. Interlisp development began in 1967 at Bolt, Beranek and Newman in Cambridge, Massachusetts as BBN LISP, which ran on PDP-10 machines running the TENEX operating system...
International Conference on Functional Programming
The International Conference on Functional Programming is an annual academic conference in the field of computer science sponsored by the ACM SIGPLAN, in association with IFIP Working Group 2.8 ....
Kent M. Pitman is the President of and has been involved for many years in the design, implementation and use of Lisp and Scheme systems. He is often better known by his initials KMP.Kent Pitman is the author of the Common Lisp Condition System...
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
Static code analysis
Static program analysis is the analysis of computer software that is performed without actually executing programs built from that software In most cases the analysis is performed on some version of the source code and in the other cases some form of the object code...
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 have risen to dominance — Scheme and Common Lisp
Common Lisp
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
newLISP is an open source scripting language in the Lisp family of programming languages developed by Lutz Mueller and released under the GNU General Public License.-History:newLISP originated in 1991 and was originally developed on a Sun-4 workstation...
does support fexprs, but calls them "macros". In Picolisp
Picolisp
PicoLisp is an open source Lisp dialect. Itruns on Linux and other POSIX-compliant systems.- Features :Its most prominent feature is "simplicity". It is built on top of a singleinternal data type , without giving up flexibility and expressivepower...
all built-in functions are fsubrs, while Lisp-level functions are exprs, fexprs, lexprs, 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
Reflection (computer science)
In computer science, reflection is the process by which a computer program can observe and modify its own structure and behavior at runtime....
. To support reflection, these Lisps support procedures that can reify
Reification (computer science)
Reification is the process by which an abstract idea about a computer program is turned into an explicit data model or other object created in a programming language. A computable/addressable object — a resource — is created in a system as a proxy for a non computable/addressable object...
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.
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). In 1998, Mitchell Wand
Mitchell Wand
Mitchell Wand is a Computer Science professor at Northeastern University. He received his Ph.D. degrees from MIT. His research has centred on programming languages and is a member of the Northeastern Programming Research Lab. He is also the co-author of Essentials of Programming Languages.-External...
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
— a device that suppresses rewriting of operands — produces a formal system
Formal system
In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...
In mathematical logic, a theory is a set of sentences in a formal language. Usually a deductive system is understood from context. An element \phi\in T of a theory T is then called an axiom of the theory, and any sentence that follows from the axioms is called a theorem of the theory. Every axiom...
. In 2007, John N. Shutt proposed an extension of lambda calculus that would model fexprs without suppressing rewriting of operands, in an attempt to avoid Wand's result.
Kernel is a Scheme-like programming language by John N. Shutt in which all objects are first-class.-Example:In the programming language Scheme, and is a macro, because must not evaluate the division. This means it cannot be used in higher-order functions; it is second-class...
The ECL programming language and system were an extensible high-level programming language and development environment developed at Harvard University in the 1970s. The name 'ECL' stood for 'Extensible Computer Language' or 'EClectic Language'...
newLISP is an open source scripting language in the Lisp family of programming languages developed by Lutz Mueller and released under the GNU General Public License.-History:newLISP originated in 1991 and was originally developed on a Sun-4 workstation...
PicoLisp is an open source Lisp dialect. Itruns on Linux and other POSIX-compliant systems.- Features :Its most prominent feature is "simplicity". It is built on top of a singleinternal data type , without giving up flexibility and expressivepower...
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
