M-expression

From Wikipedia, the free encyclopedia
Jump to navigation Jump to 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.

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