Fexpr

Last updated

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.

Contents

Origin of the name "fexpr"

In early Lisp, the environment mapped each symbol to an association list, rather than directly to a value. [1] 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 function whose operands are passed unevaluated, regardless of whether the function is primitive or user-defined. [2]

KeyStoresDefined byFunction/Special form
APVALdata value——
APVAL1data value——
SUBRfunctionsystemfunction
FSUBRfunctionsystemspecial-form
EXPRfunctionuserfunction
FEXPRfunctionuserspecial-form

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(xyz)e($if(>=?(evalxe)0)(evalye)(evalze))))

This definition provides a fexpr called $f, 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 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.

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. [3] However, it was still sometimes necessary to provide a local name for the dynamic environment, to avoid capturing the local parameter names. [4]

Mainstream use and deprecation

Fexpr support continued in Lisp 1.5, the last substantially standard dialect of Lisp before it fragmented into multiple languages. [5] In the 1970s, the two dominant Lisp languages [6] — MacLisp and Interlisp — both supported fexprs. [7]

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.

MACRO's offer an adequate mechanism for specifying special form definitions and ... FEXPR's do not. ... It is suggested that, in the design of future Lisp dialects, serious consideration should be given to the proposition that FEXPR's should be omitted from the language altogether. [8]

Since the decline of MacLisp and Interlisp, the two Lisp languages that had risen to dominance by 1993 [9] — Scheme and Common Lisp — do not support fexprs. newLISP does support fexprs, but calls them "macros". In Picolisp 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. 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. [10]

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). [11] 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. [10] In 2007, John N. Shutt proposed an extension of lambda calculus that would model fexprs without suppressing rewriting of operands, avoiding Wand's result. [12]

See also

The following languages implement fexprs or near equivalents:

Footnotes

  1. ↑ McCarthy et al., Lisp I Programmer's Manual, pp. 88–91.
  2. ↑ Pitman, The Revised MacLisp Manual, p. 75.
  3. ↑ Steele and Gabriel, "The Evolution of Lisp", pp. 239–240.
  4. ↑ Pitman, The Revised MacLisp Manual, p. 62
  5. ↑ Steele and Gabriel, "The Evolution of Lisp", pp. 231-232.
  6. ↑ Steele and Gabriel, "The Evolution of Lisp", p. 235.
  7. ↑ Pitman, The Revised MacLisp Manual, p. 182.
  8. ↑ Pitman, "Special Forms in Lisp", p. 179.
  9. ↑ Steele and Gabriel, "The Evolution of Lisp", pp. 245–248
  10. 1 2 Wand, "The Theory of Fexprs is Trivial", p. 189.
  11. ↑ Mitchell, "On Abstraction and the Expressive Power of Programming Languages", section 7.
  12. ↑ Shutt, "vau-calculi and the theory of fexprs".

Related Research Articles

<span class="mw-page-title-main">Common Lisp</span> Programming language standard

Common Lisp (CL) is a dialect of the Lisp programming language, published in American National Standards Institute (ANSI) standard document ANSI INCITS 226-1994 (S20018). The Common Lisp HyperSpec, a hyperlinked HTML version, has been derived from the ANSI Common Lisp standard.

<span class="mw-page-title-main">Lisp (programming language)</span> Programming language family

Lisp is a family of programming languages with a long history and a distinctive, fully parenthesized prefix notation. Originally specified in 1960, Lisp is the second-oldest high-level programming language still in common use, after Fortran. Lisp has changed since its early days, and many dialects have existed over its history. Today, the best-known general-purpose Lisp dialects are Common Lisp, Scheme, Racket and Clojure.

<span class="mw-page-title-main">Macro (computer science)</span> Rule for substituting a set input with a set output

In computer programming, a macro is a rule or pattern that specifies how a certain input should be mapped to a replacement output. Applying a macro to an input is known as macro expansion. The input and output may be a sequence of lexical tokens or characters, or a syntax tree. Character macros are supported in software applications to make it easy to invoke common command sequences. Token and tree macros are supported in some programming languages to enable code reuse or to extend the language, sometimes for domain-specific languages.

Rebol is a cross-platform data exchange language and a multi-paradigm dynamic programming language designed by Carl Sassenrath for network communications and distributed computing. It introduces the concept of dialecting: small, optimized, domain-specific languages for code and data, which is also the most notable property of the language according to its designer Carl Sassenrath:

Although it can be used for programming, writing functions, and performing processes, its greatest strength is the ability to easily create domain-specific languages or dialects

<span class="mw-page-title-main">Scheme (programming language)</span> Dialect of Lisp

Scheme is a dialect of the Lisp family of programming languages. Scheme was created during the 1970s at the MIT Computer Science and Artificial Intelligence Laboratory and released by its developers, Guy L. Steele and Gerald Jay Sussman, via a series of memos now known as the Lambda Papers. It was the first dialect of Lisp to choose lexical scope and the first to require implementations to perform tail-call optimization, giving stronger support for functional programming and associated techniques such as recursive algorithms. It was also one of the first programming languages to support first-class continuations. It had a significant influence on the effort that led to the development of Common Lisp.

Maclisp is a programming language, a dialect of the language Lisp. It originated at the Massachusetts Institute of Technology's (MIT) 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; Jon L. White was responsible for its later maintenance and development. The name Maclisp began being used in the early 1970s to distinguish it from other forks of PDP-6 Lisp, notably BBN Lisp.

In computer programming, the scope of a name binding is the part of a program where the name binding is valid; that is, where the name can be used to refer to the entity. In other parts of the program, the name may refer to a different entity, or to nothing at all. Scope helps prevent name collisions by allowing the same name to refer to different objects – as long as the names have separate scopes. The scope of a name binding is also known as the visibility of an entity, particularly in older or more technical literature—this is from the perspective of the referenced entity, not the referencing name.

In programming languages, a closure, also lexical closure or function closure, is a technique for implementing lexically scoped name binding in a language with first-class functions. Operationally, a closure is a record storing a function together with an environment. The environment is a mapping associating each free variable of the function with the value or reference to which the name was bound when the closure was created. Unlike a plain function, a closure allows the function to access those captured variables through the closure's copies of their values or references, even when the function is invoked outside their scope.

In computer science, a dynamic programming language is a class of high-level programming languages, which at runtime execute many common programming behaviours that static programming languages perform during compilation. These behaviors could include an extension of the program, by adding new code, by extending objects and definitions, or by modifying the type system. Although similar behaviors can be emulated in nearly any language, with varying degrees of difficulty, complexity and performance costs, dynamic languages provide direct tools to make use of them. Many of these features were first implemented as native features in the Lisp programming language.

In computer programming, an assignment statement sets and/or re-sets the value stored in the storage location(s) denoted by a variable name; in other words, it copies a value into the variable. In most imperative programming languages, the assignment statement is a fundamental construct.

Metaprogramming is a programming technique in which computer programs have the ability to treat other programs as their data. It means that a program can be designed to read, generate, analyze or transform other programs, and even modify itself while running. In some cases, this allows programmers to minimize the number of lines of code to express a solution, in turn reducing development time. It also allows programs a greater flexibility to efficiently handle new situations without recompilation.

<span class="mw-page-title-main">Conditional (computer programming)</span> Control flow statement that executes code according to some condition(s)

In computer science, conditionals are programming language commands for handling decisions. Specifically, conditionals perform different computations or actions depending on whether a programmer-defined Boolean condition evaluates to true or false. In terms of control flow, the decision is always achieved by selectively altering the control flow based on some condition . Although dynamic dispatch is not usually classified as a conditional construct, it is another way to select between alternatives at runtime. Conditional statements are the checkpoints in the programe that determines behaviour according to situation.

In some programming languages, eval, short for the English evaluate, is a function which evaluates a string as though it were an expression in the language, and returns a result; in others, it executes multiple lines of code as though they had been included instead of the line including the eval. The input to eval is not necessarily a string; it may be structured representation of code, such as an abstract syntax tree, or of special type such as code. The analog for a statement is exec, which executes a string as if it were a statement; in some languages, such as Python, both are present, while in other languages only one of either eval or exec is.

Short-circuit evaluation, minimal evaluation, or McCarthy evaluation is the semantics of some Boolean operators in some programming languages in which the second argument is executed or evaluated only if the first argument does not suffice to determine the value of the expression: when the first argument of the AND function evaluates to false, the overall value must be false; and when the first argument of the OR function evaluates to true, the overall value must be true.

In computer programming, operators are constructs defined within programming languages which behave generally like functions, but which differ syntactically or semantically.

MLISP is a variant of Lisp with an Algol-like syntax based on M-Expressions, which were the function syntax in the original description of Lisp by John McCarthy. McCarthy's M-expressions were never implemented in an exact form.

The computer programming languages C and Pascal have similar times of origin, influences, and purposes. Both were used to design their own compilers early in their lifetimes. The original Pascal definition appeared in 1969 and a first compiler in 1970. The first version of C appeared in 1972.

In computing, IIf is a function in several editions of the Visual Basic programming language and ColdFusion Markup Language (CFML), and on spreadsheets that returns the second or third parameter based on the evaluation of the first parameter. It is an example of a conditional expression, which is similar to a conditional statement.

In computer programming, homoiconicity is a property of some programming languages. A language is homoiconic if a program written in it can be manipulated as data using the language, and thus the program's internal representation can be inferred just by reading the program itself. This property is often summarized by saying that the language treats code as data.

In computer programming, an anonymous function is a function definition that is not bound to an identifier. Anonymous functions are often arguments being passed to higher-order functions or used for constructing the result of a higher-order function that needs to return a function. If the function is only used once, or a limited number of times, an anonymous function may be syntactically lighter than using a named function. Anonymous functions are ubiquitous in functional programming languages and other languages with first-class functions, where they fulfil the same role for the function type as literals do for other data types.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.