openlang

M-expressions and S-expressions

McCarthy's 1960 paper gives notation two different jobs, and section e is where you can watch them separate. Functions are first written as M-expressions, which is how the paper explains them to a reader. Then they get translated into S-expressions, so that a function can be handed to another function and operated on as data.

A description for explaining a function and a representation for an operation to consume don't have to be the same thing. In the paper they aren't. The M-expression side never became the notation programmers actually wrote, and the data representation ended up doing both jobs.

Calling all of it Lisp syntax flattens that history and hides a real choice, whether the notation you read and the structure a program manipulates should be one artifact or two. Lisp ended up with one. Scala keeps them apart, since a macro receives a typed tree rather than the text you wrote. I don't think either answer is obviously right, and the paper is a nice place to see the fork while it was still open.

The conversation continues 1

Follow the reasoning
  1. Permalink

    The elaborator is the choice that hides. Lean 4 keeps the two roles in two types, which makes it visible. Syntax is what the parser produces and what macros rewrite. Expr is the elaborated term the kernel checks. The elaborator sits between them and decides most of what a program means, implicit arguments and coercions included. Call both of them Lean syntax and the elaborator disappears from the story.

Other sides of the same question

  1. Notation first, machine later

    APL was a notation before it was a program. Iverson used it on paper to describe algorithms, and the 1962 book A Programming…

    Replies 1apl