|This article needs additional citations for verification. (August 2013) (Learn how and when to remove this template message)|
The initial implementation of Lisp was expected to be a very long process, as contemporary compilers took years to write. Implementation began with hand-compiling particular[which?] functions while the M-expression sublanguage was still tentative.
Data to be manipulated using M-expressions was to be written using S-expressions. M-expressions were used for the original theoretical language in early papers about Lisp, but the first working implementation of Lisp interpreted encodings of M-expressions as S-expressions, and M-expressions were never actually implemented.
|This section needs expansion. You can help by adding to it. (January 2017)|
An S-expression represents data made up of atoms and pairs[further explanation needed]. As originally described, an atom was a symbol written in upper case, and a pair was delimited by parentheses. Shorthand list notation was described, though it originally separated list elements by commas rather than whitespace. For example (using spaces rather than commas):
((A B) (C D) (E F))
which represents a list of three elements, each of which is a list of two symbols.
An M-expression could also use operator names, meta-variables, and argument lists. Operator names and meta-variable names were in lower case, to show that they were not symbols (i.e., not data). Argument lists were delimited by brackets,
, and their elements were separated by semicolons. For example:
car[cons[(A . B); x]]
which represents a two-part operation. The first part constructs a pair from the data structure
(A . B) and whatever data is represented by the meta-variable called
x. The second part extracts the first element of the constructed pair.
In McCarthy's original published paper on Lisp, as a demonstration of the theoretical universality of the language, he described a function
eval, which would take as input an S-expression encoding of an M-expression, and execute the M-expression program encoded by that S-expression. Here are a few examples of M-expressions and their encodings as S-expressions (again using the modern list notation):
(A B C) (QUOTE (A B C)) car[x] (CAR X) car[append[(A B C); (D E F)]] (CAR (APPEND (QUOTE (A B C)) (QUOTE (D E F))))
Rise of S-expressions
Stephen B. Russell and Daniel J. Edwards realized[when?] that an implementation of
eval would be in effect a full implementation of S-expression-encoded Lisp as an interpreter.[further explanation needed] He[clarification needed] quickly[clarification needed] hand-compiled the
eval function— an easy task compared to the anticipated many-year compiler construction.
With a complete Lisp implementation[clarification needed], a community of Lisp programmers favoring the implemented S-expression developed, and M-expressions receded in importance, and were ultimately never implemented in the original version of Lisp.
As described by John McCarthy:
The project of defining M-expressions precisely and compiling them or at least translating them into S-expressions was neither finalized nor explicitly abandoned. It just receded into the indefinite future, and a new generation of programmers appeared who preferred internal notation to any FORTRAN-like or ALGOL-like notation that could be devised.
While it is not uncommon for Lisp programmers to devise an alternate form for the language (of which MLISP is one example), some of which use M-expressions, such dialects generally lack the homoiconicity of S-expressions[dubious ], which is considered an important part of the expressiveness of the language. As a result, virtually all mainstream Lisp dialects retain S-expressions as the main (or sole) syntax. Exceptions to this include Logo, which could be considered (loosely) to be an M-expression Lisp. Several other languages, such as Dylan and Ruby, borrow heavily from Lisp, but use an ALGOL-like syntax that differs from both S-expressions and M-expressions.
The syntax of ML, a functional programming language, provides somewhat similar syntax, as it is derived from math notation as well. However, additional concepts, such as type annotations and pattern matching, hide this similarity.[how?]
The Mathematica language uses a syntax similar to the original M-expression syntax, where lists can be written using braces[clarification needed] (which can also be written using M-expression notation[clarification needed]), and functions using M-expressions[how?].
A more recent variant is I-expressions, which use indentation to indicate parentheses implicitly, and are thus in some ways intermediate between S-expressions and M-expressions. I-expressions were introduced in Scheme Request For Implementation 49 as an auxiliary syntax for Scheme, but they have not been widely adopted.
- "LISP 1.5 Programmer's Manual" (PDF). Community.computerhistory.org. Retrieved 2013-09-02.
- "The implementation of LISP". Formal.stanford.edu. 1996-02-05. Retrieved 2013-08-24.