When did the idea of macros (user-defined code transformation) appear?

Question

I have read McCarthy's 1960 paper on LISP and found no reference to anything that's similar to user-defined macros or normal order evaluation. I was wondering when marcos first appeared in programming language history (and also in Lisp history):

• When was the idea of user-defined code transformation (before interpretation or compilation) first described (theoretically)?
• What was the first programming language implementation to have Lisp-like macros (by "Lisp-like" I mean "using a readable Turing-complete language to do code-transformation")? (including non-Lisps -- Forth for example is quite old, but I'm not sure if the first Forth implementation already had "IMMEDIATE")
• Also which of those was the first high-level programming language (exclude assembler languages...)
• What was the first Lisp dialect to have macros?

Thank you!

Answer 1

I think the idea goes back to Post systems, rewriting with strings ("if you see this string, replace it with that string"). Post systems are Turing-capable, and can thus compute anything (including program texts!). Emil Post's paper on these is dated 1943, but supposedly he did the original conceptualization in the 1920s.

The General Purpose Macro Processor, one of the first widely used ones, was available in the early 60s.

TRAC is another early macro processor dating to the same period. The History of Computer Languages (TRAC) says it was designed in 1959.

Both of these are Turing-capable macro processors.

SNOBOL also dates from the same period.

The fact that very general-purpose macro processors were being built in the early 60s hints to me that there were likely special-purpose macro processors built before then to provide inspiration. I'm pretty sure macro processors were in use in assemblers before this point, but I don't have specific evidence.

I know that COBOL has so-called COPY libs, which are a cross between macros and include files. I don't know when this was introduced into COBOL, but the langauge goes back to 1958.

It is interest to note that LISP macros can be considered to be a special case of tree-to-tree rewrites ("if you see an s-expression that looks like this, replace it by an s-expression that looks like that"). Trees can be easily modelled as strings (see: "LISP" :) and thus LISP macros are a special case of string rewriting.

The generalized case of tree-rewriting is now the basis for Program Transformation Systems, which can carry out massive changes on program text.

Answer 2

To look for how macros where introduced into Lisp, you should look for mentions of FEXPRs and FSUBRs which the predecessors of modern Lisp macros (or more accurately, FEXPRs are the predecessors of user-defined macros). These are mentioned in several places -- for example, in the From LISP 1 to LISP 1.5 section of McCarthy's History of Lisp. But in fact, it's also mentioned earlier than that: in p.48 of the LISP I PROGRAMMER'S MANUAL (from 1960) you can see a description of FEXPRs and FSUBRs.

BTW, it's a little bogus to compare Lisp macros with string-based systems. The advantage of using a tree transformer vs string manipulations is significant enough to make it a completely different system. Another important aspect of Lisp macros is that they are local transformation vs a global program transformation (the most obvious paper to read for this is Felleisen's On the Expressive Power of Programming Languages). And of course there's a whole area here -- going from FEXPRs to the modern, more well behaved macros, then to hygienic macros in Scheme (which deal with a representation that is richer than symbolic parse trees), then a combination of macros and a module system, syntax expansion phases, etc etc etc. There's probably enough stuff here for a few years of reading...

Answer 3

From The Evolution of Lisp (Steele/Gabriel):

3.3 Macros

Macros appear to have been introduced into Lisp by Timothy P. Hart in 1963 in a short MIT AI Memo [Hart, 1963],

Timothy P. Hart, MACRO Definitions for LISP, October 1963