M-expression

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

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.

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

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:

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

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.

...
Wikipedia