Jump to content
 







Main menu
   


Navigation  



Main page
Contents
Current events
Random article
About Wikipedia
Contact us
Donate
 




Contribute  



Help
Learn to edit
Community portal
Recent changes
Upload file
 








Search  

































Create account

Log in
 









Create account
 Log in
 




Pages for logged out editors learn more  



Contributions
Talk
 



















Contents

   



(Top)
 


1 Background  





2 Examples  





3 Implementations  



3.1  For LISP  







4 Further development  





5 Notes  





6 References  














M-expression






Русский
 

Edit links
 









Article
Talk
 

















Read
Edit
View history
 








Tools
   


Actions  



Read
Edit
View history
 




General  



What links here
Related changes
Upload file
Special pages
Permanent link
Page information
Cite this page
Get shortened URL
Download QR code
Wikidata item
 




Print/export  



Download as PDF
Printable version
 
















Appearance
   

 






From Wikipedia, the free encyclopedia
 


John McCarthy

Incomputer programming, M-expressions (ormeta-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]

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[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.[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 type LISP M-expression corresponding LISP S-expression
Literal atomic symbol, written in uppercase ALPHA123 (QUOTE ALPHA123)
Literal list in cons notation (A . (B . NIL)) (QUOTE (A . (B . NIL)))
Literal list in list notation (A B C 1 2 3) (QUOTE (A B C 1 2 3))
Identifier for variables and functions, written in lowercase in M-Expressions name123 NAME123
Function application with variables f[x;y] (F X Y)
Function application on an S-Expression car[(A B C)] (CAR (QUOTE (A B C)))
Function application on two S-Expressions cons[A;(B C D)] (CONS (QUOTE A) (QUOTE (B C D)))
Conditional expression [lessp[x;0] → minus[x]; T → x] (COND ((LESSP X 0) (MINUS X)) (T X))
Recursive function definition label[ff;λ[[x];[atom[x] → x; T → ff[car[x]]]]] (LABEL FF (LAMBDA (X) (COND ((ATOM X) X) (T (FF (CAR 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. 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]

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[edit]

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[edit]

For LISP[edit]

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[edit]

ACGOL (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[edit]


References[edit]

  1. ^ "The implementation of LISP". www-formal.stanford.edu. Retrieved 2020-03-29.
  • ^ a b c "LISP 1.5 Programmer's Manual" (PDF). Community.computerhistory.org. 1965. Archived from the original (PDF) on 2006-02-11. Retrieved 2013-09-02.
  • ^ McCarthy, John (April 1960) "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I"
  • ^ McCarthy, John (March 1959). "Recursive Functions of Symbolic Expressions and Their Computation by Machine (AI Memo 8)".
  • ^ "The implementation of LISP". Formal.stanford.edu. 1979-02-12. Retrieved 2013-08-24.
  • ^ "Anatomy of LISP". McGraw-Hill, Inc. 1978.
  • ^ a b c Lee, Xah. "LISP Infix Syntax Survey".
  • ^ "A Parser for M-Expressions". 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.
  • ^ CGOL on ABCL Development of the Armed Bear Common Lisp implementation blog.
  • ^ Möller, Egil (2003). "SRFI 49: Indentation-sensitive syntax". srfi.schemers.org.
  • ^ Wheeler, DA (2013). "SRFI 110: Sweet-expressions (t-expressions)". srfi.schemers.org.

  • Retrieved from "https://en.wikipedia.org/w/index.php?title=M-expression&oldid=1224587915"

    Category: 
    Lisp (programming language)
    Hidden categories: 
    Articles with short description
    Short description matches Wikidata
    Articles needing additional references from August 2013
    All articles needing additional references
     



    This page was last edited on 19 May 2024, at 07:31 (UTC).

    Text is available under the Creative Commons Attribution-ShareAlike License 4.0; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.



    Privacy policy

    About Wikipedia

    Disclaimers

    Contact Wikipedia

    Code of Conduct

    Developers

    Statistics

    Cookie statement

    Mobile view



    Wikimedia Foundation
    Powered by MediaWiki