M-expression

From Wikipedia, the free encyclopedia

In computer programming, M-expressions (or meta-expressions) were intended to be a human-readable form of S-expressions as part of the Lisp programming language. M-expressions were used for the original theoretical language in early papers about Lisp, but they were never actually implemented.

As John McCarthy explained in History of Lisp:

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

S-expressions intended to represent data structures or parsed mathematical expressions look like this:

(+ 4 (- 5 3))

which is simply prefix notation for 4 + (5 - 3). However, in Lisp, lists and programming constructs such as a conditional branch are also represented in this way, for example:

(if (> a 5) do-this or-else-do-this)

A representation was developed so that this could be written down in a more user friendly way, for example [1, 2, 3] for a list. These M-expressions were then to be translated to S-expressions to be executed, hence the meta designation.

A few examples of an M-expression and the equivalent S-expression follow.

[1, 2, 3]                        (quote (1 2 3)) or '(1 2 3)
car[X]                           (car X)
car[append[[1,2,3], [4,5,6]]]    (car (append '(1 2 3) '(4 5 6)))

However, Lisp programmers quickly adapted to use S-expressions directly for both data and program code, and M-expressions fell into disuse.

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, 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 Python, borrow heavily from Lisp, but use an ALGOL-like syntax that differs from both S-expressions and M-expressions.

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, were introduced in Scheme Request For Implementation 49 as an auxiliary syntax for Scheme, but they have not been widely adopted. The BYOND internet game development language, a relatively unknown but fairly advanced system based loosely around BASIC but with some LISP-like aspects, uses solely I-expressions.

In addition, the Mathematica language uses a syntax similar to the original M-expression syntax, where lists can be written using braces (which can also be written using M-expression notation), and M-expression notation for functions.