Editing M-expression

{{Short description|Proposed syntax for the Lisp language}}
{{More citations needed|date=August 2013}}
[[File:John McCarthy Stanford.jpg|thumb|100px|John McCarthy]]
In [[computer programming]], '''M-expressions''' (or '''meta-expressions''') were an early proposed syntax for the [[Lisp (programming language)|Lisp programming language]], inspired by contemporary languages such as [[Fortran]] and [[ALGOL]]. The notation was never implemented into the language and, as such, it was never finalized.<ref>{{Cite web|url=http://www-formal.stanford.edu/jmc/history/lisp/node3.html|title=The implementation of LISP|website=www-formal.stanford.edu|access-date=2020-03-29}}</ref>

M-expressions are a syntax for LISP code and provide [[function notation]], syntax for a {{code|cond|lisp}} 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.<ref name=LISP15/>

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 (computer scientist)|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-expression]]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 (compilers)|self-hosting]].<ref name="lisp1960">McCarthy, John (April 1960) "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I"</ref> The draft version of this paper is known as "AI Memo 8".<ref>{{cite web |last1=McCarthy |first1=John |title=Recursive Functions of Symbolic Expressions and Their Computation by Machine (AI Memo 8) |url=https://www.informatimago.com/develop/lisp/com/informatimago/small-cl-pgms/aim-8/index.html |date=March 1959 |url-status=dead |archive-url=https://web.archive.org/web/20210307145003/https://www.informatimago.com/develop/lisp/com/informatimago/small-cl-pgms/aim-8/index.html |archive-date=7 March 2021 }}</ref>

{| class="wikitable"
|+ Example M-expressions (LISP 1.5, 1965)<ref name=LISP15/>
! Expression type
! Mathematical notation
! M-expression
! Modern Lisp S-expression
|-
| List value
| <math>(1, 2, 3)</math>
| {{code|(1, 2, 3)}}
| {{code|2=lisp|(quote (1 2 3))}}
|-
| Function application
| <math>f(x, y)</math>
| {{code|f[x;y]}}
| {{code|2=lisp|(f x y)}}
|-
| Function definition
| <math>\mathrm{square}: x \mapsto x \cdot x</math>
| {{code|1=label[square;λ[[x];times[x;x]]]}}
| {{code|2=lisp|(define square (lambda (x) (* x x)))}}
|-
| Conditional expression
| <math>\begin{cases}
  -x, & \text{if } x < 0 \\
  x,  & \text{otherwise} 
\end{cases}
</math>
| {{code|[lessp[x;0] → minus[x]; T → x]}}
| {{code|2=lisp|(cond ((< x 0) (- x)) (t x))}}
|}

McCarthy had planned to develop an automatic Lisp compiler ([[LISP 2]]) using M-expressions as the language syntax and S-expressions to describe the compiler's internal processes. [[Steve Russell (computer scientist)|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 (computing)|interpreter]] program that could execute S-expressions.<ref name=LISP15>{{cite web |url=http://community.computerhistory.org/scc/projects/LISP/book/LISP%201.5%20Programmers%20Manual.pdf |date=1965|title=LISP 1.5 Programmer's Manual |publisher=Community.computerhistory.org |access-date=2013-09-02 |url-status=dead |archive-url=https://web.archive.org/web/20060211020233/http://community.computerhistory.org/scc/projects/LISP/book/LISP%201.5%20Programmers%20Manual.pdf |archive-date=2006-02-11 }}</ref> 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:

{{quote|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.<ref>{{cite web|url=http://www-formal.stanford.edu/jmc/history/lisp/node3.html |title=The implementation of LISP |publisher=Formal.stanford.edu |date=1979-02-12 |access-date=2013-08-24}}</ref>|''[http://www-formal.stanford.edu/jmc/history/lisp/lisp.html History of Lisp]''}}

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.<ref name=AOL>{{cite web |url=https://dl.acm.org/doi/10.5555/542865 |date=1978|title=Anatomy of LISP |publisher=McGraw-Hill, Inc.}}</ref>

== Examples ==

The definitions for the functions apply and eval from the Lisp 1.5 Manual, page 13.

 apply[fn;x;a] =
    [atom[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[caddr[fn];parlis[cadr[fn];x;a]];
     eq[car[fn];LABEL] → apply[caddr[fn];x;cons[cons[cadr[fn];caddr[fn]];a]]]

 eval[e;a] =
    [atom[e] → cdr[assoc[e;a]];
     atom[car[e]] →
           [eq[car[e],QUOTE] → 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]]s, [[pattern matching]], and [[backtracking]] were incorporated. It eventually evolved into an abandoned [[LISP70]] draft. M-LISP ([[MetaLISP]]) from 1989 was another attempt to blend M-expressions with Scheme.<ref name="xl"/>

A parser for the "[[AI Memo]] 8" M-expression is available in [[Common Lisp]], but the author intends it as a case against M-expressions due to its perceived inability to cope with macros.<ref>{{cite web |title=A Parser for M-Expressions |url=https://www.informatimago.com/develop/lisp/com/informatimago/small-cl-pgms/m-expression/ |url-status=dead |archive-url=https://web.archive.org/web/20210324084457/https://www.informatimago.com/develop/lisp/com/informatimago/small-cl-pgms/m-expression/ |archive-date=24 March 2021 |quote=Let's newbies play with them, and realize how impractical they are. Note for example, that we cannot use macros anymore because their syntax would need to be known by the M-expression parser.}}</ref>

==Further development==
A [[CGOL]] (1977) was implemented in [[MacLisp]] and follows a similar goal of introducing Algol-like syntax with infix operators.<ref name="xl">{{cite web |last1=Lee |first1=Xah |title=LISP Infix Syntax Survey |url=http://xahlee.info/comp/lisp_sans_sexp.html}}</ref> It is known to work on [[Armed Bear Common Lisp]].<ref name="armed bear">[http://abcl-dev.blogspot.co.uk/2010/04/cgol-on-abcl.html CGOL on ABCL] ''Development of the Armed Bear Common Lisp implementation'' blog.</ref>

{{anchor|I-expression}}A more recent (circa 2003) variant is the ''I-expression'', which use [[off-side rule|indentation]] to indicate parentheses implicitly, and are thus in some ways intermediate between S-expressions and M-expressions.  I-expressions were introduced in [[Scheme Requests for Implementation|Scheme Request For Implementation]] 49 as an auxiliary syntax for [[Scheme (programming language)|Scheme]], but they have not been widely adopted.<ref>{{cite web |last1=Möller |first1=Egil |title=SRFI 49: Indentation-sensitive syntax |url=http://srfi.schemers.org/srfi-49/srfi-49.html |website=srfi.schemers.org |date=2003}}</ref>

{{anchor|T-expression}}A further development is the "sweet" ''t-expression'', which has [[infix operator]]s 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.<ref>{{cite web |last1=Wheeler |first1=DA |title=SRFI 110: Sweet-expressions (t-expressions) |url=https://srfi.schemers.org/srfi-110/srfi-110.html |website=srfi.schemers.org |date=2013}}</ref>

Additional syntax-related include Apple's [[Dylan (programming language)|Dylan]] (Algol-like tokens) and [[Clojure]]'s addition of other literal syntaxes.<ref name="xl"/>

==Notes==
{{NoteFoot}}


==References==
<references/>

[[Category:Lisp (programming language)]]