Higher-Order and Symbolic Computation, 11(4)363-397
Definitional Interpreters for Higher-Order Programming LanguagesJohn C. Reynolds, Systems and Information Science, Syracuse University
|
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 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.
Keywords: programming language, language definition, interpreter, lambda calculus, applicative language, higher-order function, closure, order of application, continuation, LISP, GEDANKEN, PAL, SECD machine, J-operator, reference |
This article can be downloaded [here] or locally [here].
![[picture of journal cover]](../LISP.JPG)