(sarabander.github.io) Structure and Interpretation of Computer Programs, 2e: Top

ROAM_REFS: https://sarabander.github.io/sicp/html/2_002e2.xhtml#FOOT72

^{72} The use of the word “closure” here comes from abstract algebra, where a set of elements is said to be closed under an operation if applying the operation to elements in the set produces an element that is again an element of the set. The Lisp community also (unfortunately) uses the word “closure” to describe a totally unrelated concept: A closure is an implementation technique for representing procedures with free variables. We do not use the word “closure” in this second sense in this book.

ROAM_REFS: https://sarabander.github.io/sicp/html/2_002e5.xhtml#FOOT118

This statement, which also appears in the first edition of this book, is just as true now as it was when we wrote it twelve years ago. Developing a useful, general framework for expressing the relations among different types of entities (what philosophers call “ontology”) seems intractably difficult. The main difference between the confusion that existed ten years ago and the confusion that exists now is that now a variety of inadequate ontological theories have been embodied in a plethora of correspondingly inadequate programming languages. For example, much of the complexity of object-oriented programming languages—and the subtle and confusing differences among contemporary object-oriented languages—centers on the treatment of generic operations on interrelated types. Our own discussion of computational objects in Chapter 3 avoids these issues entirely. Readers familiar with object-oriented programming will notice that we have much to say in chapter 3 about local state, but we do not even mention “classes” or “inheritance.” In fact, we suspect that these problems cannot be adequately addressed in terms of computer-language design alone, without also drawing on work in knowledge representation and automated reasoning.

ROAM_REFS: https://sarabander.github.io/sicp/html/3_002e3.xhtml#FOOT148

The subtleties of dealing with sharing of mutable data objects reflect the underlying issues of “sameness” and “change” that were raised in 3.1.3. We mentioned there that admitting change to our language requires that a compound object must have an “identity” that is something different from the pieces from which it is composed. In Lisp, we consider this “identity” to be the quality that is tested by

eq?

, i.e., by equality of pointers. Since in most Lisp implementations a pointer is essentially a memory address, we are “solving the problem” of defining the identity of objects by stipulating that a data object “itself” is the information stored in some particular set of memory locations in the computer. This suffices for simple Lisp programs, but is hardly a general way to resolve the issue of “sameness” in computational models.

ROAM_REFS: https://sarabander.github.io/sicp/html/3_002e5.xhtml#FOOT186

There are many possible implementations of streams other than the one described in this section. Delayed evaluation, which is the key to making streams practical, was inherent in Algol 60's call-by-name parameter-passing method. The use of this mechanism to implement streams was first described by Landin (1965). Delayed evaluation for streams was introduced into Lisp by Friedman and Wise (1976). In their implementation,

cons

always delays evaluating its arguments, so that lists automatically behave as streams. The memoizing optimization is also known as call-by-need. The Algol community would refer to our original delayed objects as call-by-name thunks and to the optimized versions as call-by-need thunks.

ROAM_REFS: https://sarabander.github.io/sicp/html/3_002e5.xhtml#FOOT200

This is a small reflection, in Lisp, of the difficulties that conventional strongly typed languages such as Pascal have in coping with higher-order procedures. In such languages, the programmer must specify the data types of the arguments and the result of each procedure: number, logical value, sequence, and so on. Consequently, we could not express an abstraction such as “map a given procedure

proc

over all the elements in a sequence” by a single higher-order procedure such as

stream-map

. Rather, we would need a different mapping procedure for each different combination of argument and result data types that might be specified for a

proc

. Maintaining a practical notion of “data type” in the presence of higher-order procedures raises many difficult issues. One way of dealing with this problem is illustrated by the language ML (Gordon et al. 1979), whose “polymorphic data types” include templates for higher-order transformations between data types. Moreover, data types for most procedures in ML are never explicitly declared by the programmer. Instead, ML includes a type-inferencing mechanism that uses information in the environment to deduce the data types for newly defined procedures.

ROAM_REFS: https://sarabander.github.io/sicp/html/3_002e5.xhtml#FOOT204

The object model approximates the world by dividing it into separate pieces. The functional model does not modularize along object boundaries. The object model is useful when the unshared state of the “objects” is much larger than the state that they share. An example of a place where the object viewpoint fails is quantum mechanics, where thinking of things as individual particles leads to paradoxes and confusions. Unifying the object view with the functional view may have little to do with programming, but rather with fundamental epistemological issues.

ROAM_REFS: https://sarabander.github.io/sicp/html/4_002e1.xhtml#FOOT213

As mentioned in 2.3.1, the evaluator sees a quoted expression as a list beginning with

quote

, even if the expression is typed with the quotation mark. For example, the expression

'a

would be seen by the evaluator as

(quote a)

. See Exercise 2.55.

ROAM_REFS: https://sarabander.github.io/sicp/html/4_002e1.xhtml#FOOT228

Wanting programs to not depend on this evaluation mechanism is the reason for the “management is not responsible” remark in Footnote 28 of Chapter 1. By insisting that internal definitions come first and do not use each other while the definitions are being evaluated, the IEEE standard for Scheme leaves implementors some choice in the mechanism used to evaluate these definitions. The choice of one evaluation rule rather than another here may seem like a small issue, affecting only the interpretation of “badly formed” programs. However, we will see in 5.5.6 that moving to a model of simultaneous scoping for internal definitions avoids some nasty difficulties that would otherwise arise in implementing a compiler.

ROAM_REFS: https://sarabander.github.io/sicp/html/4_002e1.xhtml#FOOT232

This technique is an integral part of the compilation process, which we shall discuss in Chapter 5. Jonathan Rees wrote a Scheme interpreter like this in about 1982 for the T project (Rees and Adams 1982). Marc Feeley (1986) (see also Feeley and Lapalme 1987) independently invented this technique in his master's thesis.

ROAM_REFS: https://sarabander.github.io/sicp/html/4_002e2.xhtml#FOOT238

The word thunk was invented by an informal working group that was discussing the implementation of call-by-name in Algol 60. They observed that most of the analysis of (“thinking about”) the expression could be done at compile time; thus, at run time, the expression would already have been “thunk” about (Ingerman et al. 1960).

ROAM_REFS: https://sarabander.github.io/sicp/html/4_002e2.xhtml#FOOT239

This is analogous to the use of

force

on the delayed objects that were introduced in Chapter 3 to represent streams. The critical difference between what we are doing here and what we did in Chapter 3 is that we are building delaying and forcing into the evaluator, and thus making this uniform and automatic throughout the language.

ROAM_REFS: https://sarabander.github.io/sicp/html/4_002e2.xhtml#FOOT240

Lazy evaluation combined with memoization is sometimes referred to as call-by-need argument passing, in contrast to call-by-name argument passing. (Call-by-name, introduced in Algol 60, is similar to non-memoized lazy evaluation.) As language designers, we can build our evaluator to memoize, not to memoize, or leave this an option for programmers (Exercise 4.31). As you might expect from Chapter 3, these choices raise issues that become both subtle and confusing in the presence of assignments. (See Exercise 4.27 and Exercise 4.29.) An excellent article by Clinger (1982) attempts to clarify the multiple dimensions of confusion that arise here.

ROAM_REFS: https://sarabander.github.io/sicp/html/4_002e2.xhtml#FOOT241

Notice that we also erase the

env

from the thunk once the expression's value has been computed. This makes no difference in the values returned by the interpreter. It does help save space, however, because removing the reference from the thunk to the

env

once it is no longer needed allows this structure to be garbage-collected and its space recycled, as we will discuss in 5.3.

Similarly, we could have allowed unneeded environments in the memoized delayed objects of 3.5.1 to be garbage-collected, by having

memo-proc

do something like

(set! proc '())

to discard the procedure

proc

(which includes the environment in which the

delay

was evaluated) after storing its value.