Philip Wadler - Definitional Interpreters for Higher-Order Programming Languages

Please sign up at Skills Matter (https://skillsmatter.com/meetups/8146-papers-we-love-meetup) also

Certain papers change your life. McCarthy’s ‘Recursive Functions of Symbolic Expressions and their Computation by Machine (Part I)’ (1960) changed mine, and so did Landin’s ‘The Next 700 Programming Languages’ (1966). And I remember the moment, halfway through my graduate career, when Guy Steele handed me Reynolds’s ‘Definitional Interpreters for Higher-Order Programming Languages’ (1972).

It is now common to explicate the structure of a programming language by presenting an interpreter for that language. If the language interpreted is the same as the language doing the interpreting, the interpreter is called meta-circular.

Interpreters may be written at differing levels of detail, to explicate different implementation strategies. For instance, the interpreter may be written in a continuation-passing style; or some of the higher-order functions may be represented explicitly using data-structures, via defunctionalisation.

More elaborate interpreters may be derived from simpler versions, thus providing a methodology for discovering an implementation strategy and showing it correct. Each of these techniques has become a mainstay of the study of programming languages, and all of them were introduced in this single paper by Reynolds.