Lambda the Ultimate

Definitional Interpreters for Higher-Order Programming Languages
started 9/30/2003; 1:35:48 AM - last post 10/7/2003; 5:10:22 AM

Ehud Lamm - Definitional Interpreters for Higher-Order Programming Languages

9/30/2003; 1:35:48 AM (reads: 10737, responses: 1)

Definitional Interpreters for Higher-Order Programming Languages

John C. Reynolds: Definitional Interpreters for Higher-Order Programming Languages. Higher-Order and Symbolic Computation, 11(4), 1998, pages 363-397.

This paper was mentioned here a few times but we never did discuss its impact. Why not now?

If you haven't read the paper, but studied programming languages, perhaps that easiest way to describe the paper is to say that it is the origin of the EOPL approach: Language understanding by building (applicative) interpreters. Closures, continutations (and CPS), defunctionalization - it's all there.

From a historical perspective it is worth spending a few seconds to ponder the conclusion of Reynold's Definitional Interpreters Revisited (Higher-Order and Symbolic Computation, 11(4), 1998, pages 355-361):

Perhaps the real mystery about these concepts is that they appear, with easily recognizable similarity in such a variety of settings: with and without types, in denotational and operational semantics, in interpreters, and even in the transformation of arbitrary programs.

Posted to history by Ehud Lamm on 9/30/03; 1:36:36 AM

Luke Gorrie - Re: Definitional Interpreters for Higher-Order Programming Languages

10/7/2003; 5:10:22 AM (reads: 195, responses: 0)

Definitional interpreters seem to me to have gone out of fashion. Recent programming languages papers seem to prefer more abstract formal semantics for defining languages.

This bothers me, since I find it much easier to understand languages described by interpreters in e.g. Scheme. Formal semantics is much less approachable for me, at least for now.

What I really want to know is: what should one read to get enough background to understand modern programming languages papers? I'm thinking of the ones presented at ICFP conferences.

I've had a little exposure to formal semantics in from older programming languages books. But when I'm attending programming languages talks I never recognise or understand anything written on the slides -- it all looks like squiggles and greek letters to me. I'd very much like to understand what people are talking about!

(A similar question would be, "What does one need to learn to understand definitional interpreters written in Scheme?", and a reasonable answer would be to read Structure and Interpretation of Computer Programs. Is there a similarly straight-forward answer to my question?)