Page:AIM-379.djvu/3

A Different View of LAMBDA

Historically, LAMBDA expressions in LISP have been viewed as functions: objects which, when applied ordered sets of arguments, yield single values. These single values typically then become arguments for yet other functions. The consistent use of functions in LISP leads to what is called the applicative programming style. Here we discuss a more general view, of which the functional view will turn out to be a special case. We will consider a new interpretation of LAMBDA as an environment operator which performs the primitive declarative operation of renaming a quantity, and we will consider a function call to be a primitive unconditional imperative operator which includes GOTO as a special case. (In an earlier paper [Steele 76] we described LAMBDA as "the ultimate imperative". Here we assert that this was unfortunately misleading, for it is function invocation which is imperative.)

Primitive Operations in Programming Languages

What are the primitive operations common to all high-level programming languages? It is the data manipulation primitives which most clearly differentiate high-level languages: FORTRAN has numbers, characters, and arrays; PL/I has strings and structures as well; LISP has list cells and atomic symbols. All have, however, similar notions of control structures and of variables.

If we ignore the various data types and data manipulation primitives, we find that only a few primitive ideas are left. Some of these are:

• Transfer of control
• Environment operations
• Side effects
• Process synchronization

Transfer of control may be subdivided into conditional and unconditional transfers. Environment operations include binding of variables on function entry, declaration of local variables, and so on. Side effects include not only modifications to data structures, but altering of global variables and input/output. Process synchronization includes such issues as resource allocation and passing of information between processes in a consistent manner.

Large numbers of primitive constructs are provided in contemporary programming languages for these purposes. The following short catalog is by no means complete, but only representative:

• Transfer of control
  • Sequential blocks
  • GOTO
  • IF-THEN-ELSE
  • WHILE-DO, REPEAT-UNTIL, and other loops
  • CASE
  • SELECT
  • EXIT (also known as ESCAPE or CATCH/THROW)
  • Decision tables