Wadler's Blog

I've added online links to the relevant papers (not behind paywalls), copied here.

Papers we love: John Reynolds, Definitional Interpreters for Higher-Order Programming Languages

7 June 2016, Skills Matter, London.
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.

Related material

• John Reynolds, Definitional Interpreters for Higher-Order Programming Languages, 1972.
• John Reynolds, Definitional Interpreters for Higher-Order Programming Languages, 1998.
• John Reynolds, Definitional Interpreters Revisited, 1998.
• John Reynolds, The Discoveries of Continuations, 1993.
• John McCarthy, Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, 1960.
• John McCarthy, Towards a Mathematical Science of Computation, 1962.
• Peter Landin, The Next 700 Programming Languages, 1966.
• Gordon Plotkin, Call-by-value, Call-by-name, and the Lambda Calculus, 1975.
• Robin Milner, A Theory of Type Polymorphism in Programming, 1978.
• Fermin Reig, ed, Reminiscences of Influential Papers, SIGPLAN Notices, 38(12):9—10, December 2003.

Labels: Functional Programming, Programming Languages, Theory, Types