M-expression

Last updated
John McCarthy John McCarthy Stanford.jpg
John McCarthy

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. The notation was never implemented into the language and, as such, it was never finalized. [1]

Contents

M-expressions are a syntax for LISP code and provide function notation, syntax for a cond 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. [2]

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.

The M-Expression form

append[listvar;(PARIS BERLIN NEWYORK TOKYO)]

then needs to be transformed to the S-Expression form

(APPEND LISTVAR (QUOTE (PARIS BERLIN NEWYORK TOKYO)))

Background

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. [3] The draft version of this paper is known as "AI Memo 8". [4]

Example M-expressions (LISP 1.5, 1965) and their S-Expression representation [2]
Expression typeLISP M-expressioncorresponding LISP S-expression
Literal atomic symbol, written in uppercaseALPHA123(QUOTEALPHA123)
Literal list in cons notation(A . (B . NIL))(QUOTE(A.(B.NIL)))
Literal list in list notation(A B C 1 2 3)(QUOTE(ABC123))
Identifier for variables and functions, written in lowercase in M-Expressionsname123NAME123
Function application with variablesf[x;y](FXY)
Function application on an S-Expressioncar[(A B C)](CAR(QUOTE(ABC)))
Function application on two S-Expressionscons[A;(B C D)](CONS(QUOTEA)(QUOTE(BCD)))
Conditional expression[lessp[x;0] → minus[x]; T → x](COND((LESSPX0)(MINUSX))(TX))
Recursive function definition1=label[ff;λ[[x];[atom[x] → x; T → ff[car[x]]]]]}}(LABELFF(LAMBDA(X)(COND((ATOMX)X)(T(FF(CARX))))))

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

—  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. [6]

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 macros, 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. [7]

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

Further development

A CGOL (1977) was implemented in MacLisp and follows a similar goal of introducing Algol-like syntax with infix operators. [7] It is known to work on Armed Bear Common Lisp. [9]

A more recent (circa 2003) variant is the I-expression, 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. [10]

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

Additional syntax-related include Apple's Dylan (Algol-like tokens) and Clojure's addition of other literal syntaxes. [7]

Notes


    Related Research Articles

    <span class="mw-page-title-main">Common Lisp</span> Programming language standard

    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). The Common Lisp HyperSpec, a hyperlinked HTML version, has been derived from the ANSI Common Lisp standard.

    <span class="mw-page-title-main">Lisp (programming language)</span> Programming language family

    Lisp is a family of programming languages with a long history and a distinctive, fully parenthesized prefix notation. Originally specified in the late 1950s, it is the second-oldest high-level programming language still in common use, after Fortran. Lisp has changed since its early days, and many dialects have existed over its history. Today, the best-known general-purpose Lisp dialects are Common Lisp, Scheme, Racket, and Clojure.

    <span class="mw-page-title-main">Scheme (programming language)</span> Dialect of Lisp

    Scheme is a dialect of the Lisp family of programming languages. Scheme was created during the 1970s at the MIT Computer Science and Artificial Intelligence Laboratory and released by its developers, Guy L. Steele and Gerald Jay Sussman, via a series of memos now known as the Lambda Papers. It was the first dialect of Lisp to choose lexical scope and the first to require implementations to perform tail-call optimization, giving stronger support for functional programming and associated techniques such as recursive algorithms. It was also one of the first programming languages to support first-class continuations. It had a significant influence on the effort that led to the development of Common Lisp.

    The SECD machine is a highly influential virtual machine and abstract machine intended as a target for compilers of functional programming languages. The letters stand for stack, environment, control, dump, respectively, which are the internal registers of the machine. The registers stack, control, and dump point to stacks, and environment points to an associative array.

    Maclisp is a programming language, a dialect of the language Lisp. It originated at the Massachusetts Institute of Technology's (MIT) Project MAC in the late 1960s and was based on Lisp 1.5. Richard Greenblatt was the main developer of the original codebase for the PDP-6; Jon L. White was responsible for its later maintenance and development. The name Maclisp began being used in the early 1970s to distinguish it from other forks of PDP-6 Lisp, notably BBN Lisp.

    <span class="mw-page-title-main">S-expression</span> Data serialization format

    In computer programming, an S-expression is an expression in a like-named notation for nested list (tree-structured) data. S-expressions were invented for and popularized by the programming language Lisp, which uses them for source code as well as data.

    In computer science, Backus–Naur form is a notation used to describe the syntax of programming languages or other formal languages. It was developed by John Backus and Peter Naur. BNF can be described as a metasyntax notation for context-free grammars. Backus–Naur form is applied wherever exact descriptions of languages are needed, such as in official language specifications, in manuals, and in textbooks on programming language theory. BNF can be used to describe document formats, instruction sets, and communication protocols.

    In computer programming, CAR (car) and CDR (cdr) are primitive operations on cons cells introduced in the Lisp programming language. A cons cell is composed of two pointers; the car operation extracts the first pointer, and the cdr operation extracts the second.

    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 accidental capture was well known in the Lisp community before the introduction of hygienic macros. Macro writers would use language features that would generate unique identifiers or use obfuscated identifiers to avoid the problem. Hygienic macros are a programmatic solution to the capture problem that is integrated into the macro expander. The term "hygiene" was coined in Kohlbecker et al.'s 1986 paper that introduced hygienic macro expansion, inspired by terminology used in mathematics.

    In some programming languages, eval, short for evaluate, is a function which evaluates a string as though it were an expression in the language, and returns a result; in others, it executes multiple lines of code as though they had been included instead of the line including the eval. The input to eval is not necessarily a string; it may be structured representation of code, such as an abstract syntax tree, or of special type such as code. The analog for a statement is exec, which executes a string as if it were a statement; in some languages, such as Python, both are present, while in other languages only one of either eval or exec is.

    MLISP is a variant of Lisp with an Algol-like syntax based on M-Expressions, which were the function syntax in the original description of Lisp by John McCarthy. McCarthy's M-expressions were never implemented in an exact form.

    In computer science, function composition is an act or mechanism to combine simple functions to build more complicated ones. Like the usual composition of functions in mathematics, the result of each function is passed as the argument of the next, and the result of the last one is the result of the whole.

    <span class="mw-page-title-main">Syntax (programming languages)</span> Set of rules defining correctly structured programs

    In computer science, the syntax of a computer language is the rules that define the combinations of symbols that are considered to be correctly structured statements or expressions in that language. This applies both to programming languages, where the document represents source code, and to markup languages, where the document represents data.

    String functions are used in computer programming languages to manipulate a string or query information about a string.

    In computer programming, homoiconicity is an informal property of some programming languages. A language is homoiconic if a program written in it can be manipulated as data using the language. The program's internal representation can thus be inferred just by reading the program itself. This property is often summarized by saying that the language treats code as data. The informality of the property arises from the fact that, strictly, this applies to almost all programming languages. No consensus exists on a precise definition of the property.

    PC-LISP is an implementation of the Franz Lisp dialect by Peter Ashwood-Smith.

    CGOL 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 history of the programming language Scheme begins with the development of earlier members of the Lisp family of languages during the second half of the twentieth century. During the design and development period of Scheme, language designers Guy L. Steele and Gerald Jay Sussman released an influential series of Massachusetts Institute of Technology (MIT) AI Memos known as the Lambda Papers (1975–1980). This resulted in the growth of popularity in the language and the era of standardization from 1990 onward. Much of the history of Scheme has been documented by the developers themselves.

    In the programming language Lisp, the reader or read function is the parser which converts the textual form of Lisp objects to the corresponding internal object structure.

    <span class="mw-page-title-main">LFE (programming language)</span>

    Lisp Flavored Erlang (LFE) is a functional, concurrent, garbage collected, general-purpose programming language and Lisp dialect built on Core Erlang and the Erlang virtual machine (BEAM). LFE builds on Erlang to provide a Lisp syntax for writing distributed, fault-tolerant, soft real-time, non-stop applications. LFE also extends Erlang to support metaprogramming with Lisp macros and an improved developer experience with a feature-rich read–eval–print loop (REPL). LFE is actively supported on all recent releases of Erlang; the oldest version of Erlang supported is R14.

    References

    1. ↑ "The implementation of LISP". www-formal.stanford.edu. Retrieved 2020-03-29.
    2. 1 2 3 "LISP 1.5 Programmer's Manual" (PDF). Community.computerhistory.org. 1965. Archived from the original (PDF) on 2006-02-11. Retrieved 2013-09-02.
    3. ↑ McCarthy, John (April 1960) "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I"
    4. ↑ McCarthy, John (March 1959). "Recursive Functions of Symbolic Expressions and Their Computation by Machine (AI Memo 8)". Archived from the original on 7 March 2021.
    5. ↑ "The implementation of LISP". Formal.stanford.edu. 1979-02-12. Retrieved 2013-08-24.
    6. ↑ "Anatomy of LISP". McGraw-Hill, Inc. 1978.
    7. 1 2 3 Lee, Xah. "LISP Infix Syntax Survey".
    8. ↑ "A Parser for M-Expressions". Archived from the original on 24 March 2021. 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.
    9. ↑ CGOL on ABCL Development of the Armed Bear Common Lisp implementation blog.
    10. ↑ Möller, Egil (2003). "SRFI 49: Indentation-sensitive syntax". srfi.schemers.org.
    11. ↑ Wheeler, DA (2013). "SRFI 110: Sweet-expressions (t-expressions)". srfi.schemers.org.
    This page is based on this Wikipedia article
    Text is available under the CC BY-SA 4.0 license; additional terms may apply.
    Images, videos and audio are available under their respective licenses.