Lambda: The Ultimate Declarative/Abstract

by Guy L. Steele, Jr.

LAMBDA

THE ULTIMATE DECLARATIVE

by

Guy Lewis Steele Jr.^[1]

Abstract:

In this paper, a sequel to LAMBDA: The Ultimate Imperative, a new view of LAMBDA as a renaming operator is presented and contrasted with the usual functional view taken by LISP. This view, combined with the view of function invocation as a kind of generalized GOTO, leads to several new insights into the nature of the LISP evaluation mechanism and the symmetry between form and function, evaluation and application, and control and environment. It also complements Hewitt's actors theory nicely, explaining the intent of environment manipulation as cleanly, generally, and intuitively as the actors theory explains control structures. The relationship between functional and continuation-passing styles of programming is also clarified.

This view of LAMBDA leads directly to a number of specific techniques for use by an optimizing compiler:

1. Temporary locations and user-declared variables may be allocated in a uniform manner.
2. Procedurally defined data structures may compile into code as good as would be expected for data defined by the more usual declarative means.
3. Lambda-calculus-theoretic models of such constructs as GOTO, DO loops, call-by-name, etc. may be used directly as macros, the expansion of which may then compile into code as good as that produced by compilers which are designed especially to handle GOTO, DO, etc.

The necessary characteristics of such a compiler designed according to this philosophy are discussed. Such a compiler is to be built in the near future as a testing ground for these ideas.

Keywords: environments, lambda-calculus, procedurally defined data, data types, optimizing compilers, control structures, function invocation, temporary variables, continuation passing, actors, lexical scoping, dynamic binding

This report describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the laboratory's artificial intelligence research is provided in part by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Research contract N00014-75-C-0643.

1. NSF Fellow