Certain papers change your life. McCarthy’s ‘Recursive Functions of Symbolic Expressions and their Computation by Machine (Part I)’ (1960) changed Philip's, and so did Landin’s ‘The Next 700 Programming Languages’ (1966). And he remembers the moment, halfway through my graduate career, when Guy Steele handed him 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.
You can find the relevant papers here.
YOU MAY ALSO LIKE:
Philip Wadler on Reynolds’s ‘Definitional Interpreters for Higher-Order Programming Languages’
Philip Wadler has contributed to the designs of Haskell, Java, and XQuery, and is a co-author of XQuery from the Experts (Addison Wesley, 2004) and Generics and Collections in Java (O'Reilly, 2006).