Programming Languages and Compilers Commons^™

Definitional Interpreters For Higher-Order Programming Languages, John C. Reynolds

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

Abstract. Higher-order programming languages (i.e., languages in which procedures or labels can occur as values) are usually defined by interpreters that 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 …