Supriya Ghosh (Editor)

M expression

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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

Contents

Background

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

S-expressions

An S-expression represents data made up of atoms and pairs. 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

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 that an implementation of eval would be in effect a full implementation of S-expression-encoded Lisp as an interpreter. He quickly hand-compiled the eval function— an easy task compared to the anticipated many-year compiler construction.

With a complete Lisp implementation, 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

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

ML

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.

Mathematica

The Mathematica language uses a syntax similar to the original M-expression syntax, where every piece of Mathematica code is an expression of the form f[x1,...,xk]. ("f" is called a "head" in Mathematica jargon, and the whole form is called "full form") The difference is that commas are used instead of semicolons for separating parts of expressions, uppercase/lowercase distinction is used for separating built-in and user-defined heads, and it has many shortcut notations for special heads. For example, lists are represented with head List (as List[2,4,7] for example), but are usually written (on both input and output) with braces (as {2,4,7}). As another example, semicolon (as in a=3; a+5) is used as an infix form of CompoundExpression head (the full form of that example being CompoundExpression[Set[a,3],Plus[a,5]]).

I-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. I-expressions were introduced in Scheme Request For Implementation 49 as an auxiliary syntax for Scheme, but they have not been widely adopted.

References

M-expression Wikipedia