Definitional interpreters for higher-order programming languages

TLDR

Higher‑order languages are typically defined by interpreters written in lambda‑calculus‑based languages, with examples such as LISP, SECD, PL/I, GEDANKEN, and recent work by Morris and Wadsworth, and these definitions are classified by the presence of higher‑order functions and the evaluation strategy inherited from the defining language. The paper investigates defining a simple applicative language through an interpreter written in a similar language. The authors construct such an interpreter in a lambda‑calculus‑based language and discuss how imperative features like jumps and assignment can be incorporated. The study demonstrates that definitions across these classifications can be derived from one another via informal yet constructive methods.

Abstract

Higher-order programming languages (i.e., languages in which procedures or labels can occur as values) are usually defined by interpreters which are themselves written in a programming language based on the lambda calculus (i.e., an applicative language such as pure LISP). Examples include McCarthy's definition of LISP, Landin's SECD machine, the Vienna definition of PL/I, Reynolds' definitions of GEDANKEN, and recent unpublished work by L. Morris and C. Wadsworth. Such definitions can be classified according to whether the interpreter contains higher-order functions, and whether the order of application (i.e., call-by-value versus call-by-name) in the defined language depends upon the order of application in the defining language. As an example, we consider the definition of a simple applicative programming language by means of an interpreter written in a similar language. Definitions in each of the above classifications are derived from one another by informal but constructive methods. The treatment of imperative features such as jumps and assignment is also discussed.