M-expression
   HOME

TheInfoList



OR:

In
computer programming Computer programming or coding is the composition of sequences of instructions, called computer program, programs, that computers can follow to perform tasks. It involves designing and implementing algorithms, step-by-step specifications of proc ...
, M-expressions (or meta-expressions) were an early proposed syntax for the
Lisp programming language Lisp (historically LISP, an abbreviation of "list processing") is a family of programming languages with a long history and a distinctive, fully parenthesized Polish notation#Explanation, prefix notation. Originally specified in the late 1950s, ...
, inspired by contemporary languages such as Fortran and
ALGOL ALGOL (; short for "Algorithmic Language") is a family of imperative computer programming languages originally developed in 1958. ALGOL heavily influenced many other languages and was the standard method for algorithm description used by the ...
. The notation was never implemented into the language and, as such, it was never finalized. M-expressions are a syntax for LISP code and provide function notation, syntax for a form and for embedded literal data (via S-expressions) into programs. Thus M-Expressions used S-Expressions for literal data. The syntax for S-Expressions ("The Data Language") and M-Expressions ("The Meta Language") is defined on pages 8 and 9 of the Lisp 1.5 manual. M-Expressions also had a corresponding S-Expression representation. Code was manually translated from M-Expressions to S-Expressions. The in M-expressions embedded literal data, then had to be quoted in S-Expressions.


Background

John McCarthy published the first paper on Lisp in 1960 while a research fellow at the
Massachusetts Institute of Technology The Massachusetts Institute of Technology (MIT) is a Private university, private research university in Cambridge, Massachusetts, United States. Established in 1861, MIT has played a significant role in the development of many areas of moder ...
. In it he described a language of symbolic expressions (
S-expression In computer programming, an S-expression (or symbolic expression, abbreviated as sexpr or sexp) is an expression in a like-named notation for nested List (computing), list (Tree (data structure), tree-structured) data. S-expressions were invented ...
s) 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.McCarthy, John (April 1960) "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I" The draft version of this paper is known as "AI Memo 8". McCarthy had planned to develop an automatic Lisp compiler (
LISP 2 LISP 2 is a programming language proposed in the 1960s as the successor to Lisp. It had largely Lisp-like semantics and ALGOL 60-like syntax. It is remembered mostly for its syntax, yet it had many features beyond those of early Lisps. Early Li ...
) 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 Interpreting is translation from a spoken or signed language into another language, usually in real time to facilitate live communication. It is distinguished from the translation of a written text, which can be more deliberative and make use o ...
program that could execute S-expressions. 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 book ''Anatomy of LISP'' by John Allen explains the definition of M-expressions and uses them throughout the book to explain Lisp and its implementation.


Examples

The definitions for the functions apply and eval from the Lisp 1.5 Manual, page 13. apply n;x;a= tom[fn→ [eq[fn;CAR">n.html" ;"title="tom[fn">tom[fn→ [eq[fn;CAR→ caar[x">n">tom[fn<_a>→ ________[eq[fn;CAR.html" ;"title="n.html" ;"title="tom[fn">tom[fn→ [eq[fn;CAR">n.html" ;"title="tom[fn">tom[fn→ [eq[fn;CAR→ caar[x eq[fn;CDR] → cdar[x]; eq[fn;CONS] → cons[car[x];cadr[x; eq[fn;ATOM] → atom[car[x; eq[fn;EQ] → eq[car[x];cadr[x; T → apply[eval[fn;a];x;a; eq[car[fn];LAMBDA] → eval addr[fnparlis[cadr[fn">n.html" ;"title="addr[fn">addr[fnparlis[cadr[fnx;a">n">addr[fn<_a>parlis[cadr[fn.html" ;"title="n.html" ;"title="addr[fn">addr[fnparlis[cadr[fn">n.html" ;"title="addr[fn">addr[fnparlis[cadr[fnx;a; eq[car[fn];LABEL] → apply addr[fnx;cons[cons[cadr[fn];caddr[fn;a] eval[e;a] = [atom[e] → cdr[assoc[e;a; atom[car q[car[eQUOTE">ar[e.html" ;"title="q[car[e">q[car[eQUOTE→ cadr[e">ar[e">q[car[e<_a>QUOTE.html" ;"title="ar[e.html" ;"title="q[car[e">q[car[eQUOTE">ar[e.html" ;"title="q[car[e">q[car[eQUOTE→ cadr[e eq[car[e];COND] → evcon[cdr[e];a]; T → apply[car[e];evlis[cdr[e];a];a; T → apply[car[e];evlis[cdr[e];a];a Using the function eval on an s-expression. eval[(EQ (QUOTE A) (CAR (CONS (QUOTE A) (QUOTE (B C D)))));NIL]


Implementations


For LISP

MLisp was a contemporary (1968–1973) project to implement an M-expression-like frontend for Lisp. A few extra features like
hygienic macro In computer science, hygienic macros are macros whose expansion is guaranteed not to cause the accidental capture of identifiers. They are a feature of programming languages such as Scheme, Dylan, Rust, Nim, and Julia. The general problem of ...
s,
pattern matching In computer science, pattern matching is the act of checking a given sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually must be exact: "either it will or will not be a ...
, and
backtracking Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it de ...
were incorporated. It eventually evolved into an abandoned LISP70 draft. M-LISP ( MetaLISP) from 1989 was another attempt to blend M-expressions with Scheme. A parser for the " AI Memo 8" M-expression is available in
Common Lisp Common Lisp (CL) is a dialect of the Lisp programming language, published in American National Standards Institute (ANSI) standard document ''ANSI INCITS 226-1994 (S2018)'' (formerly ''X3.226-1994 (R1999)''). The Common Lisp HyperSpec, a hyperli ...
, but the author intends it as a case against M-expressions due to its perceived inability to cope with macros.


Further development

A
CGOL CGOL (pronounced ''"see goll"'') is an alternative syntax featuring an extensible algebraic notation for the Lisp programming language. It was designed for MACLISP by Vaughan Pratt and subsequently ported to Common Lisp. The notation of CGOL is ...
(1977) was implemented in
MacLisp Maclisp (or MACLISP, sometimes styled MacLisp or MacLISP) is a programming language, a dialect of the language Lisp. It originated at the Massachusetts Institute of Technology's (MIT) Project MAC (from which it derived its prefix) in the late 19 ...
and follows a similar goal of introducing Algol-like syntax with infix operators. It is known to work on
Armed Bear Common Lisp Common Lisp (CL) is a dialect of the Lisp (programming language), Lisp programming language, published in American National Standards Institute (ANSI) standard document ''ANSI INCITS 226-1994 (S2018)'' (formerly ''X3.226-1994 (R1999)''). The Comm ...
.CGOL on ABCL
''Development of the Armed Bear Common Lisp implementation'' blog.
A more recent (circa 2003) variant is the ''I-expression'', which use
indentation __FORCETOC__ In the written form of many languages, indentation describes empty space ( white space) used before or around text to signify an important aspect of the text such as: * Beginning of a paragraph * Hierarchy subordinate concept * Qu ...
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. A further development is the "sweet" ''t-expression'', which has infix operators without precedence. Like I-expressions, t-expressions are only a simple transformation away from S-expressions, so that theoretically they can be used on any Lisp dialect and not interfere with features like macros. Additional syntax-related include Apple's Dylan (Algol-like tokens) and
Clojure Clojure (, like ''closure'') is a dynamic programming language, dynamic and functional programming, functional dialect (computing), dialect of the programming language Lisp (programming language), Lisp on the Java (software platform), Java platfo ...
's addition of other literal syntaxes.


Notes

{{NoteFoot


References

Lisp (programming language)