680 Chapter 15 Functional Programming Languages
functions to names so that functions could be referenced by other functions
and by themselves. This name binding was specified by a list consisting of the
function name and a list containing the lambda expression, as in(function_name (LAMBDA (arg 1 ... argn) expression))If you have had no prior exposure to functional programming, it may seem
odd to even consider a nameless function. However, nameless functions are
sometimes useful in functional programming (as well as in mathematics and
imperative programming).^3 For example, consider a function whose action is
to produce a function for immediate application to a parameter list. The pro-
duced function has no need for a name, for it is applied only at the point of its
construction. Such an example is given in Section 15.5.14.
LISP functions specified in this new notation were called S-expressions,
for symbolic expressions. Eventually, all LISP structures, both data and code,
were called S-expressions. An S-expression can be either a list or an atom. We
will usually refer to S-expressions simply as expressions.
McCarthy successfully developed a universal function that could evaluate
any other function. This function was named EVAL and was itself in the form of
an expression. Two of the people in the AI Project, which was developing LISP,
Stephen B. Russell and Daniel J. Edwards, noticed that an implementation of
EVAL could serve as a LISP interpreter, and they promptly constructed such
an implementation (McCarthy et al., 1965).
There were several important results of this quick, easy, and unexpected
implementation. First, all early LISP implementations copied EVAL and were
therefore interpretive. Second, the definition of M-notation, which was the
planned programming notation for LISP, was never completed or imple-
mented, so S-expressions became LISP’s only notation. The use of the same
notation for data and code has important consequences, one of which will be
discussed in Section 15.5.14. Third, much of the original language design
was effectively frozen, keeping certain odd features in the language, such as
the conditional expression form and the use of () for both the empty list and
logical false.
Another feature of early LISP systems that was apparently accidental
was the use of dynamic scoping. Functions were evaluated in the environ-
ments of their callers. No one at the time knew much about scoping, and
there may have been little thought given to the choice. Dynamic scoping was
used for most dialects of LISP before 1975. Contemporary dialects either
use static scoping or allow the programmer to choose between static and
dynamic scoping.
An interpreter for LISP can be written in LISP. Such an interpreter, which
is not a large program, describes the operational semantics of LISP, in LISP.
This is vivid evidence of the semantic simplicity of the language.- There are also uses of nameless subprograms in imperative programming.