M-expression

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In computer programming, M-expressions (or meta-expressions) are syntactic expressions designed for representing functions originally intended for the Lisp programming language.

Background[edit]

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.

List notation[edit]

S-expressions[edit]

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.

Eval function[edit]

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))))

Interpreter development[edit]

Rise of S-expressions[edit]

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][1] 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.

Eventual implementation[edit]

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.

There is also an implementation of an interpreter for M-LISP in Common Lisp, which evaluates M-Expressions.

Variants[edit]

ML[edit]

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?]

Mathematica[edit]

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?].

I-expressions[edit]

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.

References[edit]

  1. ^ "LISP 1.5 Programmer's Manual" (PDF). Community.computerhistory.org. Retrieved 2013-09-02. 
  2. ^ "The implementation of LISP". Formal.stanford.edu. 1996-02-05. Retrieved 2013-08-24. 

External links[edit]