M-expression

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

In computer programming, M-expressions (or meta-expressions) were an early proposed syntax for the Lisp programming language, inspired by contemporary languages such as Fortran and ALGOL. In particular, they did not feature the heavy use of parentheses for which Lisp became notorious.

Background[edit]

John McCarthy published the first paper on Lisp in 1960 while a research fellow at the Massachusetts Institute of Technology. In it he described a language of symbolic expressions (S-expressions) that could represent complex structures in the form of lists. Then he defined a set of primitive operations on the S-expressions, and a language of meta-expressions (M-expressions) that could be used to define more complex operations. Finally, he showed how the meta-language itself could be represented with S-expressions, resulting in a system that was potentially self-hosting.[1]

Example M-expressions
Expression type Mathematical notation M-expression Modern Lisp S-expression
List value [1;2;3] (quote (1 2 3))
Function application f[x;y] (f x y)
Function definition label[square;λ[[x];product[x;x]]] (defun square (x) (* x x))
Conditional expression [lessthan[x;0] → negative[x]; T → x] (cond ((< x 0) (- x)) (t x))

McCarthy had planned to develop an automatic Lisp compiler using M-expressions as the language syntax and S-expressions to describe the compiler's internal processes. Stephen B. Russell read the paper and suggested to him that S-expressions were a more convenient syntax. Although McCarthy disapproved of the idea, Russell and colleague Daniel J. Edwards hand-coded an interpreter program that could execute S-expressions.[2] This program was adopted by McCarthy's research group, establishing S-expressions as the dominant form of Lisp.

McCarthy reflected on the fate of M-expressions in 1979:

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

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. ^ McCarthy, John (April 1960) "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I"
  2. ^ "LISP 1.5 Programmer's Manual" (PDF). Community.computerhistory.org. Archived from the original (PDF) on 2006-02-11. Retrieved 2013-09-02. 
  3. ^ "The implementation of LISP". Formal.stanford.edu. 1979-02-12. Retrieved 2013-08-24. 

External links[edit]