Page:AIM-353.djvu/1

From Wikisource
Jump to: navigation, search
This page has been validated.

MASSACHUSETTS INSTITUTE OF TECHNOLOGY
ARTIFICIAL INTELLIGENCE LABORATORY

AI Memo No. 353 March 10, 1976
LAMBDA
THE ULTIMATE IMPERATIVE
by
Guy Lewis Steele Jr. and Gerald Jay Sussman

Abstract

We demonstrate how to model the following common programming constructs in terms of an applicative order language similar to LISP:

  • Simple Recursion
  • Iteration
  • Compound Statements and Expressions
  • GO TO and Assignment
  • Continuation-Passing
  • Escape Expressions
  • Fluid Variables
  • Call by Name, Call by Need, and Call by Reference

The models require only (possibly self-referent) lambda application, conditionals, and (rarely) assignment. No complex data structures such as stacks are used. The models are transparent, involving only local syntactic transformations.

Some of these models, such as those for GO TO and assignment, are already well known, and appear in the work of Landin, Reynolds, and others. The models for escape expressions, fluid variables, and call by need with side effects are new. This paper is partly tutorial in intent, gathering all the models together for purposes of context.


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.