Footnote content differences vs. original SICP text (full sweep, for editorial review)

[martin-henz]

Summary

Comparing our generated Scheme-edition PDF (https://sicp.sourceacademy.org/sicp.pdf) against the original MIT Press text (via the official free HTML edition — see methodology note below), I content-aligned every footnote in the book against MIT's original and pulled out every pair whose content differs, plus every footnote present on only one side.

Footnote reference numbers drift from MIT's throughout the book (e.g. our footnote 10 in §1.1 vs. MIT's footnote 10 being entirely different footnotes) because our edition has added, removed, and reworded footnotes and citations over the years — that drift by itself isn't a bug, so naive number-to-number comparison is useless. I instead matched footnotes by text similarity (sequence alignment), which is robust to the drift.

I'm flagging everything found here rather than pre-filtering by my own judgment of what's "obviously" intentional editorial work — most of it is probably fine (citation updates, modernized phrasing), but a few items look worth a closer look, and only a maintainer familiar with the editorial history can really tell the difference.

Methodology

I diffed against MIT's free HTML edition (.../full-text/book/book.html and friends) rather than the MIT PDF directly, because the MIT PDF's embedded font drops historic ligatures ("Th", "tt") on text extraction, which makes naive text-diffing unreliable. The HTML edition is the same underlying text and extracts cleanly.

Caveat: some entries in the raw appendix below are truncated or merged mid-sentence — an artifact of my own footnote-boundary-detection heuristic on the PDF side, not necessarily of the book. Treat the raw appendix as pointers to go check the real page rather than verbatim quotes.

Likely fine (citation/style modernization or copyediting) — listed for completeness, not urgent

• §1.2 fn36/35, §1.2 fn40/39, §2.3 fn40/40: updated citations (e.g. "Knuth 1981"→"Knuth 1997b", "Cormen, Leiserson, and Rivest 1990"→"...and Stein 2022", B.C./A.D.→BCE/CE).
• §2.2 fn15/15: MIT's aside about APL replaced with one about Python.
• §3.4 fn36/35, §3.5 fn60/59 (Eratosthenes/sieve correction, citing O'Neill 2009 — this looks like a deliberate, well-known scholarly fix), and assorted quote-character/dash/angle-bracket typographic-only diffs (§1.1 fn13, fn20; §3.1 fn3; §3.3 fn30; §4.1 fn11).

Worth a closer look

• §3.1 footnote 7 (page ~197): attribution changed from "E. Cesàro" (MIT) to "G. Lejeune Dirichlet" (ours) for the theorem about GCD probability. This is a factual claim, not a style choice — worth confirming it's an intentional correction and not a mix-up.
• §3.5 footnote 64/63: MIT states pn+1 < pn² (strict inequality); ours states pn+1 ≤ pn² (non-strict), and similarly < 2pn vs ≤ 2pn two more times in the same footnote. Could be a deliberate correction of the bound, or could be a transcription slip — worth a math check.
• §5.5 footnote 38/40 (page ~529): reads "Making a compiler generate tail-recursive code might seem like a straightforward idea. But However, compilers for common languages..." — "But However" together looks like a leftover word from an edit; probably should just be "But" or "However".
• §4.1 footnote 19 (page ~324): MIT has a substantial paragraph about Alan Turing (his 1936 paper, the Church-Turing thesis, a Hodges 1983 biography reference) following the shared opening sentence about evaluators emulating each other. That whole paragraph doesn't appear in our edition. Possibly a deliberate trim, but it's a fairly well-known/valuable historical aside to lose silently.
• A handful of other spots where MIT has an extra sentence or two that ours doesn't (§1.2 fn47/46, §2.2 fn18/18, §2.2 fn22/22, §3.3 fn20/19, §4.4 fn66/67, §5.3 fn8/9, §5.4 mit-fn26) — mostly look like minor, probably-intentional trims, but flagging since I didn't verify each one individually.

Full raw list (70 entries) posted as a follow-up comment below, since it doesn't fit in the issue body.

[martin-henz]

Footnote diff appendix (part 1 of 2)

1.1 — ours#1 / mit#None — REMOVED_FROM_OURS

• OURS: Evaluate the subexpressions of the combination.

1.1 — ours#2 / mit#None — REMOVED_FROM_OURS

• OURS: Apply the procedure that is the value of the leftmost subexpression (the operator) to the arguments that are the values of the other subexpressions (the operands). Even this simple rule illustrates some important points about processes in general. First, observe that the first step dictates that in order to accomplish the evaluation

1.1 — ours#9 / mit#9 — CONTENT_DIFF(sim=0.88)

• OURS: Chapter 3 will show that this notion of environment is crucial for understanding how the interpreter works. Chapter 4 will use environments for implementing interpreters.
• MIT: Chapter 3 will show that this notion of environment is crucial, both for understanding how the interpreter works and for implementing interpreters.

1.1 — ours#10 / mit#10 — CONTENT_DIFF(sim=0.01)

• OURS: These values are substituted for the formal parameters x and y in the body of sum-of-squares, reducing the expression to (+ (square 6) (square 10)) If we use the definition of square, this reduces to (+ (* 6 6) (* 10 10)) which reduces by multiplication to (+ 36 100) and finally to 136 The process we have just described is called the substitution model for procedure application. It can be taken as a model that determines the “meaning” of procedure application, insofar as the procedures in this chapter are concerned. However, there are two points that should be stressed: • The purpose of the substitution is to help us think about procedure application, not to provide a description of how the interpreter really works. Typical interpreters do not evaluate procedure applications by manipulating the text of a procedure to substitute values for the formal parameters. In practice, the “substitution” is accomplished by using a local environment for the formal parameters. We will discuss this more fully in chapters 3 and 4 when we examine the implementation of an interpreter in detail. • Over the course of this book, we will present a sequence of increasingly elaborate models of how interpreters work, culminating with a complete implementation of an interpreter and compiler in chapter 5. The substitution model is only the first of these models—a way to get started thinking formally about the evaluation process. In general, when modeling phenomena in science and engineering, we begin with simplified, incomplete models. As we examine things in greater detail, these simple models become inadequate and must be replaced by more refined models. The substitution model is no exception. In particular, when we address
• MIT: It may seem strange that the evaluation rule says, as part of the first step, that we should evaluate the leftmost element of a combination, since at this point that can only be an operator such as + or * representing a built-in primitive procedure such as addition or multiplication. We will see later that it is useful to be able to work with combinations whose operators are themselves compound expressions.

1.1 — ours#13 / mit#13 — CONTENT_DIFF(sim=0.97)

• OURS: Throughout this book, we will describe the general syntax of expressions by using italic symbols delimited by angle brackets—e.g., ⟨name⟩—to denote the “slots” in the expression to be filled in when such an expression is actually used.
• MIT: Throughout this book, we will describe the general syntax of expressions by using italic symbols delimited by angle brackets -- e.g., -- to denote the ``slots'' in the expression to be filled in when such an expression is actually used.

1.1 — ours#15 / mit#15 — CONTENT_DIFF(sim=0.02)

• OURS: If the body of the function is a sequence of statements, the body is evaluated with the parameters replaced, and the value of the application is the value of the return expression of the first return statement encountered.
• MIT: Despite the simplicity of the substitution idea, it turns out to be surprisingly complicated to give a rigorous mathematical definition of the substitution process. The problem arises from the possibility of confusion between the names used for the formal parameters of a procedure and the (possibly identical) names used in the expressions to which the procedure may be applied. Indeed, there is a long history of erroneous definitions of substitution in the literature of logic and programming semantics. See Stoy 1977 for a careful discussion of substitution.

1.1 — ours#16 / mit#16 — CONTENT_DIFF(sim=0.02)

• OURS: Despite the simplicity of the substitution idea, it turns out to be surprisingly complicated to give a rigorous mathematical definition of the substitution process. The problem arises from the possibility of confusion between the names used for the formal parameters of a procedure and the (possibly identical) names used in the expressions to which the procedure may be applied. Indeed, there is a long history of erroneous definitions of substitution in the literature of logic and programming semantics. See Stoy 1977 for a careful discussion of substitution.
• MIT: In chapter 3 we will introduce stream processing, which is a way of handling apparently ``infinite'' data structures by incorporating a limited form of normal-order evaluation. In section 4.2 we will modify the Scheme interpreter to produce a normal-order variant of Scheme.

1.1 — ours#17 / mit#17 — CONTENT_DIFF(sim=0.03)

• OURS: In chapter 3 we will introduce stream processing, which is a way of handling apparently “infinite” data structures by incorporating a limited form of normal-order evaluation. In section 4.2 we will modify the Scheme interpreter to produce a normal-order variant of Scheme. 18. “Interpreted as either true or false” means this: In Scheme, there are two distinguished values that are denoted by the constants #t and #f. When the interpreter checks a predicate’s
• MIT: ``Interpreted as either true or false'' means this: In Scheme, there are two distinguished values that are denoted by the constants #t and #f. When the interpreter checks a predicate's value, it interprets #f as false. Any other value is treated as true. (Thus, providing #t is logically unnecessary, but it is convenient.) In this book we will use names true and false, which are associated with the values #t and #f respectively.

1.1 — ours#20 / mit#19 — CONTENT_DIFF(sim=0.92)

• OURS: A minor difference between if and cond is that the ⟨e⟩part of each cond clause may be a sequence of expressions. If the corresponding ⟨p⟩is found to be true, the expressions ⟨e⟩are evaluated in sequence and the value of the final expression in the sequence is returned as the value of the cond. In an if expression, however, the ⟨consequent⟩and ⟨alternative⟩must be single expressions.
• MIT: A minor difference between if and cond is that the part of each cond clause may be a sequence of expressions. If the corresponding

  is found to be true, the expressions are evaluated in sequence and the value of the final expression in the sequence is returned as the value of the cond. In an if expression, however, the and must be single expressions.

1.1 — ours#21 / mit#20 — CONTENT_DIFF(sim=0.88)

• OURS: Declarative and imperative descriptions are intimately related, as indeed are mathematics and computer science. For instance, to say that the answer produced by a program is “correct” is to make a declarative statement about the program. There is a large amount of research aimed at establishing techniques for proving that programs are correct, and much of the technical difficulty of this subject has to do with negotiating the transition between imperative statements (from which programs are constructed) and declarative statements (which can be used to deduce things). In a related vein, an important current area in programming-language design is the exploration of so-called very high-level languages, in which one actually programs in terms of declarative statements. The idea is to make interpreters sophisticated enough so that, given
• MIT: Declarative and imperative descriptions are intimately related, as indeed are mathematics and computer science. For instance, to say that the answer produced by a program is correct'' is to make a declarative statement about the program. There is a large amount of research aimed at establishing techniques for proving that programs are correct, and much of the technical difficulty of this subject has to do with negotiating the transition between imperative statements (from which programs are constructed) and declarative statements (which can be used to deduce things). In a related vein, an important current area in programming-language design is the exploration of so-called very high-level languages, in which one actually programs in terms of declarative statements. The idea is to make interpreters sophisticated enough so that, given what is'' knowledge specified by the programmer, they can generate ``how to'' knowledge automatically. This cannot be done in general, but there are important areas where progress has been made. We shall revisit this idea in chapter 4.

1.1 — ours#29 / mit#28 — CONTENT_DIFF(sim=0.88)

• OURS: Embedded definitions must come first in a procedure body. The management is not responsible for the consequences of running programs that intertwine definition and use; see also footnotes ?? and ?? in section 1.3.2.
• MIT: Embedded definitions must come first in a procedure body. The management is not responsible for the consequences of running programs that intertwine definition and use.

1.2 — ours#5 / mit#None — REMOVED_FROM_OURS

• OURS: Therefore the number of steps k grows as the logarithm (to the base φ) of n. Hence, the order of growth is Θ(log n).

1.2 — ours#36 / mit#35 — CONTENT_DIFF(sim=0.64)

• OURS: The elements of Pascal’s triangle are called the binomial coefficients, because the nth row consists of the coefficients of the terms in the expansion of (x + y)n. This pattern for computing the coefficients appeared in Blaise Pascal’s 1653 seminal work on probability theory, Traité du triangle arithmétique. According to Edwards (2019), the same pattern appears in the works of the eleventh-century Persian mathematician Al-Karaji, in the works of the twelfth-century Hindu mathematician Bhaskara, and in the works of the thirteenth-century Chinese mathematician Yang Hui.
• MIT: The elements of Pascal's triangle are called the binomial coefficients, because the nth row consists of the coefficients of the terms in the expansion of (x + y)n. This pattern for computing the coefficients appeared in Blaise Pascal's 1653 seminal work on probability theory, Traité du triangle arithmétique. According to Knuth (1973), the same pattern appears in the Szu-yuen Yü-chien (``The Precious Mirror of the Four Elements''), published by the Chinese mathematician Chu Shih-chieh in 1303, in the works of the twelfth-century Persian poet and mathematician Omar Khayyam, and in the works of the twelfth-century Hindu mathematician Bháscara Áchárya.

1.2 — ours#40 / mit#39 — CONTENT_DIFF(sim=0.96)

• OURS: This iterative algorithm is ancient. It appears in the Chandah-sutra by Áchárya, written before 200 BCE. See Knuth 1997b, section 4.6.3, for a full discussion and analysis of this and other methods of exponentiation.
• MIT: This iterative algorithm is ancient. It appears in the Chandah-sutra by Áchárya Pingala, written before 200 B.C. See Knuth 1981, section 4.6.3, for a full discussion and analysis of this and other methods of exponentiation.

1.2 — ours#47 / mit#46 — CONTENT_DIFF(sim=0.87)

• OURS: The reduction steps in the cases where the exponent e is greater than 1 are based on the fact that, for any integers x, y, and m, we can find the remainder of x times y modulo m by computing separately the remainders of x modulo m and y modulo m, multiplying these, and then taking the remainder of the result modulo m. For instance, in the case where e is even, we compute the remainder of be/2 modulo m, square this, and take the remainder modulo m. This technique
• MIT: The reduction steps in the cases where the exponent e is greater than 1 are based on the fact that, for any integers x, y, and m, we can find the remainder of x times y modulo m by computing separately the remainders of x modulo m and y modulo m, multiplying these, and then taking the remainder of the result modulo m. For instance, in the case where e is even, we compute the remainder of be/2 modulo m, square this, and take the remainder modulo m. This technique is useful because it means we can perform our computation without ever having to deal with numbers much larger than m. (Compare exercise 1.25.)

1.3 — ours#1 / mit#None — REMOVED_FROM_OURS

• OURS: The ability to directly manipulate procedures provides an analogous increase in the expressive power of a programming language. For example, in section 1.3.1 we introduced the sum procedure, which takes a procedure term as an argument and computes the sum of the values of term over some specified interval. In order to define sum, it is crucial that we be able to speak of a procedure such as term as an entity in its own right, without regard for how term might be expressed with more primitive operations. Indeed, if we did not have the notion of “a procedure,” it is doubtful that we would ever even think of the possibility of defining an operation such as sum. Moreover, insofar as performing the summation is concerned, the details of how term may be constructed from more primitive operations are irrelevant.

1.3 — ours#50 / mit#49 — CONTENT_DIFF(sim=0.95)

• OURS: This series, usually written in the equivalent form π 4 = 1 – 1 3 + 1 5 – 1 7 + · · · , is due to Leibniz. We’ll see how to use this as the basis for some fancy numerical tricks in section 3.5.3.
• MIT: This series, usually written in the equivalent form (/4) = 1 - (1/3) + (1/5) - (1/7) + ···, is due to Leibniz. We'll see how to use this as the basis for some fancy numerical tricks in section 3.5.3.

1.3 — ours#55 / mit#54 — CONTENT_DIFF(sim=0.96)

• OURS: Understanding internal definitions well enough to be sure a program means what we intend it to mean requires a more elaborate model of the evaluation process than we have presented in this chapter. The subtleties do not arise with internal definitions of procedures, however. We will return to this issue in sections 3.2.4 and 4.1.6, after we learn more about the evaluation of blocks.
• MIT: Understanding internal definitions well enough to be sure a program means what we intend it to mean requires a more elaborate model of the evaluation process than we have presented in this chapter. The subtleties do not arise with internal definitions of procedures, however. We will return to this issue in section 4.1.6, after we learn more about evaluation.

1.3 — ours#58 / mit#57 — CONTENT_DIFF(sim=0.65)

• OURS: Try this during a boring lecture: Set your calculator to radians mode and then repeatedly press the cos button until you obtain the fixed point. 59. 7→(pronounced “maps to”) is the mathematician’s way of writing lambda. y 7→x/y means (lambda(y) (/ x y)), that is, the function whose value at y is x/y.
• MIT: Try this during a boring lecture: Set your calculator to radians mode and then repeatedly press the cos button until you obtain the fixed point.

1.3 — ours#60 / mit#58 — CONTENT_DIFF(sim=0.20)

• OURS: Observe that this is a combination whose operator is itself a combination. Exercise 1.4 already demonstrated the ability to form such combinations, but that was only a toy example.
• MIT: (pronounced ``maps to'') is the mathematician's way of writing lambda. y x/y means (lambda(y) (/ x y)), that is, the function whose value at y is x/y.

1.3 — ours#None / mit#59 — ADDED_IN_OURS

• MIT: Observe that this is a combination whose operator is itself a combination. Exercise 1.4 already demonstrated the ability to form such combinations, but that was only a toy example. Here we begin to see the real need for such combinations -- when applying a procedure that is obtained as the value returned by a higher-order procedure.

2.1 — ours#3 / mit#3 — CONTENT_DIFF(sim=0.87)

• OURS: Another way to define the selectors and constructor is (define make-rat cons) (define numer car) (define denom cdr) The first definition associates the name make-rat with the value of the expression cons, which is the primitive procedure that constructs pairs. Thus make-rat and cons are names for the same primitive constructor. Defining selectors and constructors in this way is efficient: Instead of make-rat calling cons, make-rat is cons, so there is only one procedure called, not two, when make-rat is called. On the other hand, doing this defeats debugging aids that trace procedure calls or put breakpoints
• MIT: Another way to define the selectors and constructor is (define make-rat cons) (define numer car) (define denom cdr) The first definition associates the name make-rat with the value of the expression cons, which is the primitive procedure that constructs pairs. Thus make-rat and cons are names for the same primitive constructor. Defining selectors and constructors in this way is efficient: Instead of make-rat calling cons, make-rat is cons, so there is only one procedure called, not two, when make-rat is called. On the other hand, doing this defeats debugging aids that trace procedure calls or put breakpoints on procedure calls: You may want to watch make-rat being called, but you certainly don't want to watch every call to cons. We have chosen not to use this style of definition in this book.

2.2 — ours#0 / mit#None — REMOVED_FROM_OURS

• OURS: The plan for even-fibs is analogous. Unfortunately, the two procedure definitions above fail to exhibit this signal-flow structure. For instance, if we examine the sum-odd-squares procedure, we find that the enumeration is implemented partly by the null? and pair? tests and partly by the tree-recursive structure of the procedure. Similarly, the accumulation is found partly in the tests and partly in the addition used in the recursion. In general, there are no distinct parts of either procedure that correspond to the elements in the signal-flow description. Our two procedures decompose the computations in a different way, spreading the enumeration over the program and mingling it with the map, the filter, and the accumulation. If we could organize our programs to make the signal-flow

2.2 — ours#7 / mit#7 — CONTENT_DIFF(sim=0.65)

• OURS: The notion that a means of combination should satisfy closure is a straightforward idea. Unfortunately, the data combiners provided in many popular programming languages do not satisfy closure, or make closure cumbersome to exploit. In Fortran or Basic, one typically combines data elements by assembling them into arrays—but one cannot form arrays whose elements are themselves arrays. Pascal and C admit structures whose elements are structures. However, this requires that the programmer manipulate pointers explicitly, and adhere to the
• MIT: The notion that a means of combination should satisfy closure is a straightforward idea. Unfortunately, the data combiners provided in many popular programming languages do not satisfy closure, or make closure cumbersome to exploit. In Fortran or Basic, one typically combines data elements by assembling them into arrays -- but one cannot form arrays whose elements are themselves arrays. Pascal and C admit structures whose elements are structures. However, this requires that the programmer manipulate pointers explicitly, and adhere to the restriction that each field of a structure can contain only elements of a prespecified form. Unlike Lisp with its pairs, these languages have no built-in general-purpose glue that makes it easy to manipulate compound data in a uniform way. This limitation lies behind Alan Perlis's comment in his foreword to this book: ``In Pascal the plethora of declarable data structures induces a specialization within functions that inhibits and penalizes casual cooperation. It is better to have 100 functions operate on one data structure than to have 10 functions operate on 10 data structures.''

2.2 — ours#9 / mit#9 — CONTENT_DIFF(sim=0.96)

• OURS: Since nested applications of car and cdr are cumbersome to write, Lisp dialects provide abbreviations for them—for instance, (cadr ⟨arg⟩) = (car (cdr ⟨arg⟩)) The names of all such procedures start with c and end with r. Each a between them stands for a car operation and each d for a cdr operation, to be applied in the same order in which they appear in the name. The names car and cdr persist because simple combinations like cadr are pronounceable.
• MIT: Since nested applications of car and cdr are cumbersome to write, Lisp dialects provide abbreviations for them -- for instance, The names of all such procedures start with c and end with r. Each a between them stands for a car operation and each d for a cdr operation, to be applied in the same order in which they appear in the name. The names car and cdr persist because simple combinations like cadr are pronounceable.

2.2 — ours#15 / mit#15 — CONTENT_DIFF(sim=0.78)

• OURS: Richard Waters (1979) developed a program that automatically analyzes traditional Fortran programs, viewing them in terms of maps, filters, and accumulations. He found that fully 90 percent of the code in the Fortran Scientific Subroutine Package fits neatly into this paradigm. One of the reasons for the success of Lisp as a programming language is that lists provide a standard medium for expressing ordered collections so that they can be manipulated using higher-order operations. Many modern languages, such as Python, have learned this lesson.
• MIT: Richard Waters (1979) developed a program that automatically analyzes traditional Fortran programs, viewing them in terms of maps, filters, and accumulations. He found that fully 90 percent of the code in the Fortran Scientific Subroutine Package fits neatly into this paradigm. One of the reasons for the success of Lisp as a programming language is that lists provide a standard medium for expressing ordered collections so that they can be manipulated using higher-order operations. The programming language APL owes much of its power and appeal to a similar choice. In APL all data are represented as arrays, and there is a universal and convenient set of generic operators for all sorts of array operations.

2.2 — ours#18 / mit#18 — CONTENT_DIFF(sim=0.71)

• OURS: This approach to nested mappings was shown to us by David Turner, whose languages KRC and Miranda provide elegant formalisms for dealing with these constructs. The examples in this
• MIT: This approach to nested mappings was shown to us by David Turner, whose languages KRC and Miranda provide elegant formalisms for dealing with these constructs. The examples in this section (see also exercise 2.42) are adapted from Turner 1981. In section 3.5.3, we'll see how this approach generalizes to infinite sequences.

2.2 — ours#22 / mit#22 — CONTENT_DIFF(sim=0.77)

• OURS: The picture language is based on the language Peter Henderson created to construct images like M.C. Escher’s “Square Limit” woodcut (see Henderson 1982). The woodcut incorporates a
• MIT: The picture language is based on the language Peter Henderson created to construct images like M.C. Escher's ``Square Limit'' woodcut (see Henderson 1982). The woodcut incorporates a repeated scaled pattern, similar to the arrangements drawn using the square-limit procedure in this section.

2.2 — ours#23 / mit#23 — CONTENT_DIFF(sim=0.49)

• OURS: William Barton Rogers (1804–1882) was the founder and first president of MIT. A geologist and talented teacher, he taught at William and Mary College and at the University of Virginia. In 1859 he moved to Boston, where he had more time for research, worked on a plan for establishing a “polytechnic institute,” and served as Massachusetts’s first State Inspector of Gas Meters. When MIT was established in 1861, Rogers was elected its first president. Rogers espoused an ideal of “useful learning” that was different from the university education of the time, with its overemphasis on the classics, which, as he wrote, “stand in the way of the broader, higher and more practical instruction and discipline of the natural and social sciences.” This education was likewise to be different from narrow trade-school education. In Rogers’s words:
• MIT: William Barton Rogers (1804-1882) was the founder and first president of MIT. A geologist and talented teacher, he taught at William and Mary College and at the University of Virginia. In 1859 he moved to Boston, where he had more time for research, worked on a plan for establishing a polytechnic institute,'' and served as Massachusetts's first State Inspector of Gas Meters. When MIT was established in 1861, Rogers was elected its first president. Rogers espoused an ideal of useful learning'' that was different from the university education of the time, with its overemphasis on the classics, which, as he wrote, stand in the way of the broader, higher and more practical instruction and discipline of the natural and social sciences.'' This education was likewise to be different from narrow trade-school education. In Rogers's words: The world-enforced distinction between the practical and the scientific worker is utterly futile, and the whole experience of modern times has demonstrated its utter worthlessness. Rogers served as president of MIT until 1870, when he resigned due to ill health. In 1878 the second president of MIT, John Runkle, resigned under the pressure of a financial crisis brought on by the Panic of 1873 and strain of fighting off attempts by Harvard to take over MIT. Rogers returned to hold the office of president until 1881. Rogers collapsed and died while addressing MIT's graduating class at the commencement exercises of 1882. Runkle quoted Rogers's last words in a memorial address delivered that same year: As I stand here today and see what the Institute is, ... I call to mind the beginnings of science. I remember one hundred and fifty years ago Stephen Hales published a pamphlet on the subject of illuminating gas, in which he stated that his researches had demonstrated that 128 grains of bituminous coal -- '' Bituminous coal,'' these were his last words on earth. Here he bent forward, as if consulting some notes on the table before him, then slowly regaining an erect position, threw up his hands, and was translated from the scene of his earthly labors and triumphs to the tomorrow of death,'' where the mysteries of life are solved, and the disembodied spirit finds unending satisfaction in contemplating the new and still unfathomable mysteries of the infinite future. In the words of Francis A. Walker (MIT's third president): All his life he had borne himself most faithfully and heroically, and he died as so good a knight would surely have wished, in harness, at his post, and in the very part and act of public duty.

2.2 — ours#25 / mit#25 — CONTENT_DIFF(sim=0.94)

• OURS: Rotate180 rotates a painter by 180 degrees. Instead of rotate180 we could say (compose flip-vert flip-horiz), using the compose procedure from exercise 1.42.
• MIT: Rotate180 rotates a painter by 180 degrees (see exercise 2.50). Instead of rotate180 we could say (compose flip-vert flip-horiz), using the compose procedure from exercise 1.42.

2.3 — ours#40 / mit#40 — CONTENT_DIFF(sim=0.94)

• OURS: Examples of such structures include B-trees and red-black trees. There is a large literature on data structures devoted to this problem. See Cormen, Leiserson, Rivest, and Stein 2022.
• MIT: Examples of such structures include B-trees and red-black trees. There is a large literature on data structures devoted to this problem. See Cormen, Leiserson, and Rivest 1990.

2.5 — ours#57 / mit#57 — CONTENT_DIFF(sim=0.70)

• OURS: To make this work completely smoothly, we should also add to our generic arithmetic system the ability to coerce a “number” to a polynomial by regarding it as a polynomial of degree zero
• MIT: To make this work completely smoothly, we should also add to our generic arithmetic system the ability to coerce a ``number'' to a polynomial by regarding it as a polynomial of degree zero whose coefficient is the number. This is necessary if we are going to perform operations such as which requires adding the coefficient y + 1 to the coefficient 2.

3.1 — ours#3 / mit#3 — CONTENT_DIFF(sim=0.97)

• OURS: We have already used cond and in begin implicitly in our programs, because in Scheme the body of a procedure can be a sequence of expressions. Also, the consequent part of each clause in a cond expression can be a sequence of expressions rather than a single expression.
• MIT: We have already used begin implicitly in our programs, because in Scheme the body of a procedure can be a sequence of expressions. Also, the part of each clause in a cond expression can be a sequence of expressions rather than a single expression.

3.1 — ours#7 / mit#7 — CONTENT_DIFF(sim=0.87)

• OURS: This theorem is due to G. Lejeune Dirichlet. See section 4.5.2 of Knuth 1997b for a discussion and a proof.
• MIT: This theorem is due to E. Cesàro. See section 4.5.2 of Knuth 1981 for a discussion and a proof.

3.2 — ours#1 / mit#None — REMOVED_FROM_OURS

• OURS: Evaluate the subexpressions of the combination.12

3.2 — ours#2 / mit#12 — CONTENT_DIFF(sim=0.02)

• OURS: Apply the value of the operator subexpression to the values of the operand subexpressions. The environment model of evaluation replaces the substitution model in specifying what it means to apply a compound procedure to arguments. In the environment model of evaluation, a procedure is always a pair consisting of some code and a pointer to an environment. Procedures are created in one way only: by evaluating a lambda expression. This produces a procedure whose code is obtained from the text of the lambda expression and whose environment is the environment in which the lambda expression was evaluated to produce the procedure. For example, consider the procedure definition (define (square x) (* x x)) evaluated in the global environment. The procedure definition syntax is just syntactic sugar for an underlying implicit lambda expression. It would have been equivalent to have used13 (define square (lambda (x) (* x x))) which evaluates (lambda (x) (* x x)) and binds square to the resulting value, all in the global environment. Figure 3.2 shows the result of evaluating this define expression. The procedure object is a pair whose code specifies that the procedure has one formal parameter, namely x, and a procedure body (* x x). The environment part of the procedure is a pointer to the program environment, since that is the environment in which the lambda expression was evaluated to produce the procedure. A new binding, which associates the procedure object with the symbol square, has been added to the program frame. In general, define creates definitions by adding bindings to frames. Now that we have seen how procedures are created, we can describe how procedures are applied. The environment model specifies: To apply a procedure to arguments, create a new environment containing a frame that binds the parameters to the values of the arguments. The enclosing environment of this frame is the environment specified by the procedure. Now, within this new environment, evaluate the procedure body. To show how this rule is followed, figure 3.3 illustrates the environment structure created by evaluating the expression (square 5) in the global environment, where square is the procedure generated in figure 3.2. Applying the procedure results in the creation of a new environment, labeled E1 in the figure, that begins with a frame left). However, this order should always be considered to be an implementation detail, and one should never write programs that depend on some particular order. For instance, a sophisticated compiler might optimize a program by varying the order in which subexpressions are evaluated. The ECMAScript standard specifies evaluation of subexpressions from left to right.
• MIT: Assignment introduces a subtlety into step 1 of the evaluation rule. As shown in exercise 3.8, the presence of assignment allows us to write expressions that will produce different values depending on the order in which the subexpressions in a combination are evaluated. Thus, to be precise, we should specify an evaluation order in step 1 (e.g., left to right or right to left). However, this order should always be considered to be an implementation detail, and one should never write programs that depend on some particular order. For instance, a sophisticated compiler might optimize a program by varying the order in which subexpressions are evaluated.

3.2 — ours#12 / mit#13 — CONTENT_DIFF(sim=0.04)

• OURS: Assignment introduces a subtlety into step 1 of the evaluation rule. As shown in exercise 3.8, the presence of assignment allows us to write expressions that will produce different values depending on the order in which the subexpressions in a combination are evaluated. Thus, to be precise, we should specify an evaluation order in step 1 (e.g., left to right or right to
• MIT: If there is already a binding for the variable in the current frame, then the binding is changed. This is convenient because it allows redefinition of symbols; however, it also means that define can be used to change values, and this brings up the issues of assignment without explicitly using set!. Because of this, some people prefer redefinitions of existing symbols to signal errors or warnings.

3.2 — ours#13 / mit#None — REMOVED_FROM_OURS

• OURS: Footnote ?? in chapter 1 mentions subtle differences between the two in full JavaScript, which we will ignore in this book.

3.3 — ours#16 / mit#None — REMOVED_FROM_OURS

• OURS: This explains why the program in footnote ?? of chapter 1 goes wrong. The time between creating the binding for a name and evaluating the declaration of the name is called the temporal dead zone (TDZ).

3.3 — ours#20 / mit#19 — CONTENT_DIFF(sim=0.67)

• OURS: The two pairs are distinct because each call to cons returns a new pair. The symbols are shared; in Scheme there is a unique symbol with any given name. Since Scheme provides no
• MIT: The two pairs are distinct because each call to cons returns a new pair. The symbols are shared; in Scheme there is a unique symbol with any given name. Since Scheme provides no way to mutate a symbol, this sharing is undetectable. Note also that the sharing is what enables us to compare symbols using eq?, which simply checks equality of pointers.

[martin-henz]

Footnote diff appendix (part 2 of 2)

3.3 — ours#30 / mit#29 — CONTENT_DIFF(sim=0.96)

• OURS: Observe that the if expression in this procedure has no alternative expression. Such a “one-armed if expression” is used to decide whether to do something, rather than to select between two expressions. An if expression returns an unspecified value if the predicate is false and there is no alternative.
• MIT: Observe that the if expression in this procedure has no expression. Such a ``one-armed if statement'' is used to decide whether to do something, rather than to select between two expressions. An if expression returns an unspecified value if the predicate is false and there is no .

3.3 — ours#34 / mit#33 — CONTENT_DIFF(sim=0.32)

• OURS: The expression-oriented format is convenient because it avoids the need to name the intermediate expressions in a computation. Our original formulation of the constraint language is cumbersome in the same way that many languages are cumbersome when dealing with operations on compound data. For example, if we wanted to compute the product (a + b) · (c + d),
• MIT: The expression-oriented format is convenient because it avoids the need to name the intermediate expressions in a computation. Our original formulation of the constraint language is cumbersome in the same way that many languages are cumbersome when dealing with operations on compound data. For example, if we wanted to compute the product (a + b) · (c + d), where the variables represent vectors, we could work in ``imperative style,'' using procedures that set the values of designated vector arguments but do not themselves return vectors as values: (v-sum a b temp1) (v-sum c d temp2) (v-prod temp1 temp2 answer) Alternatively, we could deal with expressions, using procedures that return vectors as values, and thus avoid explicitly mentioning temp1 and temp2: (define answer (v-prod (v-sum a b) (v-sum c d))) Since Lisp allows us to return compound objects as values of procedures, we can transform our imperative-style constraint language into an expression-oriented style as shown in this exercise. In languages that are impoverished in handling compound objects, such as Algol, Basic, and Pascal (unless one explicitly uses Pascal pointer variables), one is usually stuck with the imperative style when manipulating compound objects. Given the advantage of the expression-oriented format, one might ask if there is any reason to have implemented the system in imperative style, as we did in this section. One reason is that the non-expression-oriented constraint language provides a handle on constraint objects (e.g., the value of the adder procedure) as well as on connector objects. This is useful if we wish to extend the system with new operations that communicate with constraints directly rather than only indirectly via operations on connectors. Although it is easy to implement the expression-oriented style in terms of the imperative implementation, it is very difficult to do the converse.

3.4 — ours#36 / mit#35 — CONTENT_DIFF(sim=0.87)

• OURS: To quote some graffiti seen on a building wall in Cambridge, Massachusetts: “Time is a device that was invented to keep everything from happening at once.”
• MIT: To quote some graffiti seen on a Cambridge building wall: ``Time is a device that was invented to keep everything from happening at once.''

3.4 — ours#48 / mit#47 — CONTENT_DIFF(sim=0.49)

• OURS: There are many variants of such instructions—including test-and-set, test-and-clear, swap, compare-and-exchange, load-reserve, and store-conditional—whose design must be carefully matched to the machine’s processor–memory interface. One issue that arises here is to determine what happens if two processes attempt to acquire the same resource at exactly the same time by
• MIT: There are many variants of such instructions -- including test-and-set, test-and-clear, swap, compare-and-exchange, load-reserve, and store-conditional -- whose design must be carefully matched to the machine's processor-memory interface. One issue that arises here is to determine what happens if two processes attempt to acquire the same resource at exactly the same time by using such an instruction. This requires some mechanism for making a decision about which process gets control. Such a mechanism is called an arbiter. Arbiters usually boil down to some sort of hardware device. Unfortunately, it is possible to prove that one cannot physically construct a fair arbiter that works 100% of the time unless one allows the arbiter an arbitrarily long time to make its decision. The fundamental phenomenon here was originally observed by the fourteenth-century French philosopher Jean Buridan in his commentary on Aristotle's De caelo. Buridan argued that a perfectly rational dog placed between two equally attractive sources of food will starve to death, because it is incapable of deciding which to go to first.

3.4 — ours#75 / mit#50 — CONTENT_DIFF(sim=0.05)

• OURS: As shown in the diagram, the reason for this anomaly is that Paul’s assignment of 75 to balance is made under the assumption that the value of balance to be decremented is 100. That assumption, however, became invalid when Peter changed balance to 90. This is a catastrophic failure for the banking system, because the total amount of money in the system is not conserved. Before the transactions, the
• MIT: This may seem like a strange point of view, but there are systems that work this way. International charges to credit-card accounts, for example, are normally cleared on a per-country basis, and the charges made in different countries are periodically reconciled. Thus the account balance may be different in different countries.

3.5 — ours#1 / mit#None — REMOVED_FROM_OURS

• OURS: The same idea is pervasive throughout all of engineering. For example, electrical engineers use many different languages for describing circuits. Two of these are the language of electrical networks and the language of electrical systems. The network language emphasizes the physical modeling of devices in terms of discrete electrical elements. The primitive objects of the network language are primitive electrical components such as resistors, capacitors, inductors, and transistors, which are characterized in terms of physical variables called voltage and current. When describing circuits in the network language, the engineer is concerned with the physical characteristics of a design. In contrast, the primitive objects of the system language are signal-processing modules such as filters and amplifiers. Only the functional behavior of the modules is relevant, and signals are manipulated without concern for their physical realization as voltages and currents. The system language is erected on the network language, in the sense that the elements of signal-processing systems are constructed from electrical networks. Here, however, the concerns are with the large-scale organization of electrical devices to solve a given application problem; the physical feasibility of the parts is assumed. This layered collection of languages is another example of the stratified design technique illustrated by the picture language of section 2.2.4.

3.5 — ours#51 / mit#52 — CONTENT_DIFF(sim=0.02)

• OURS: This may seem like a strange point of view, but there are systems that work this way. International charges to credit-card accounts, for example, are normally cleared on a per-country basis, and the charges made in different countries are periodically reconciled. Thus the account balance may be different in different countries.
• MIT: Physicists sometimes adopt this view by introducing the ``world lines'' of particles as a device for reasoning about motion. We've also already mentioned (section 2.2.3) that this is the natural way to think about signal-processing systems. We will explore applications of streams to signal processing in section 3.5.3.

3.5 — ours#53 / mit#None — REMOVED_FROM_OURS

• OURS: Physicists sometimes adopt this view by introducing the “world lines” of particles as a device for reasoning about motion. We’ve also already mentioned (section 2.2.3) that this is the

3.5 — ours#60 / mit#59 — CONTENT_DIFF(sim=0.54)

• OURS: Exercises such as 3.51 and 3.52 are valuable for testing our understanding of how delay works. On the other hand, intermixing delayed evaluation with printing—and, even worse, with assignment—is extremely confusing, and instructors of courses on computer languages have
• MIT: Exercises such as 3.51 and 3.52 are valuable for testing our understanding of how delay works. On the other hand, intermixing delayed evaluation with printing -- and, even worse, with assignment -- is extremely confusing, and instructors of courses on computer languages have traditionally tormented their students with examination questions such as the ones in this section. Needless to say, writing programs that depend on such subtleties is odious programming style. Part of the power of stream processing is that it lets us ignore the order in which events actually happen in our programs. Unfortunately, this is precisely what we cannot afford to do in the presence of assignment, which forces us to be concerned with time and change.

3.5 — ours#61 / mit#60 — CONTENT_DIFF(sim=0.18)

• OURS: This method is reminiscent of the ancient sieve of Eratosthenes, named for Eratosthenes, a third-century BCE Alexandrian Greek mathematician. His sieve finds the primes by repeatedly crossing off the multiples of each prime in turn; although ancient, it has formed the basis for special-purpose hardware “sieves” that, until the 1970s, were the most powerful tools in existence for locating large primes. Since then, however, these methods have been superseded by outgrowths of the probabilistic techniques discussed in section 1.2.6. But the stream-based method given here is not actually Eratosthenes’s sieve: as Melissa E. O’Neill shows in O’Neill 2009, it tests each candidate for divisibility by the primes found so far—a form of trial division—rather than crossing off multiples, and is substantially less efficient than the sieve of Eratosthenes.
• MIT: Eratosthenes, a third-century B.C. Alexandrian Greek philosopher, is famous for giving the first accurate estimate of the circumference of the Earth, which he computed by observing shadows cast at noon on the day of the summer solstice. Eratosthenes's sieve method, although ancient, has formed the basis for special-purpose hardware ``sieves'' that, until recently, were the most powerful tools in existence for locating large primes. Since the 70s, however, these methods have been superseded by outgrowths of the probabilistic techniques discussed in section 1.2.6.

3.5 — ours#62 / mit#61 — CONTENT_DIFF(sim=0.63)

• OURS: We have named these figures after Peter Henderson, who was the first person to show us diagrams of this sort as a way of thinking about stream processing.
• MIT: We have named these figures after Peter Henderson, who was the first person to show us diagrams of this sort as a way of thinking about stream processing. Each solid line represents a stream of values being transmitted. The dashed line from the car to the cons and the filter indicates that this is a single value rather than a stream.

3.5 — ours#64 / mit#63 — CONTENT_DIFF(sim=0.98)

• OURS: This last point is very subtle and relies on the fact that pn+1 ≤p2 n. (Here, pk denotes the kth prime.) Estimates such as these are very difficult to establish. The ancient proof by Euclid that there are an infinite number of primes shows that pn+1 ≤p1p2 · · · pn + 1, and no substantially better result was proved until 1851, when the Russian mathematician P. L. Chebyshev established that pn+1 ≤2pn for all n. This result, originally conjectured in 1845, is known as Bertrand’s hypothesis. A proof can be found in section 22.3 of Hardy and Wright 1960.
• MIT: This last point is very subtle and relies on the fact that pn+1 < pn2. (Here, pk denotes the kth prime.) Estimates such as these are very difficult to establish. The ancient proof by Euclid that there are an infinite number of primes shows that pn+1< p1 p2 ··· pn + 1, and no substantially better result was proved until 1851, when the Russian mathematician P. L. Chebyshev established that pn+1< 2pn for all n. This result, originally conjectured in 1845, is known as Bertrand's hypothesis. A proof can be found in section 22.3 of Hardy and Wright 1960.

3.5 — ours#66 / mit#65 — CONTENT_DIFF(sim=0.97)

• OURS: We can’t use let to bind the local variable guesses because the value of guesses depends on guesses itself. Exercise 3.63 addresses why we want a local name here.
• MIT: We can't use let to bind the local variable guesses, because the value of guesses depends on guesses itself. Exercise 3.63 addresses why we want a local variable here.

4.1 — ours#1 / mit#None — REMOVED_FROM_OURS

• OURS: To evaluate a combination (a compound expression other than a special form), evaluate the subexpressions and then apply the value of the operator subexpression to the values of the operand subexpressions.

4.1 — ours#2 / mit#None — REMOVED_FROM_OURS

• OURS: To apply a compound procedure to a set of arguments, evaluate the body of the procedure in a new environment. To construct this environment, extend the environment part of the procedure object by a frame in which the formal parameters of the procedure are bound to the arguments to which the procedure is applied. These two rules describe the essence of the evaluation process, a basic cycle in which expressions to be evaluated in environments are reduced to procedures to be applied to arguments, which in turn are reduced to new expressions to be evaluated in new environments, and so on, until we get down to symbols, whose values are looked up in the environment, and to primitive procedures, which are applied directly (see figure ??).4 This evaluation cycle will be embodied by the interplay between the two critical procedures in the evaluator, eval and apply, which are described in section 4.1.1 (see figure ??). The implementation of the evaluator will depend upon procedures that define the syntax of the expressions to be evaluated. We will use data abstraction to make the evaluator independent of the representation of the language. For example, where we take a closer look at the evaluation process by implementing the evaluator as a simple register machine.

4.1 — ours#3 / mit#3 — CONTENT_DIFF(sim=0.84)

• OURS: Even so, there will remain important aspects of the evaluation process that are not elucidated by our evaluator. The most important of these are the detailed mechanisms by which procedures call other procedures and return values to their callers. We will address these issues in chapter 5,
• MIT: Even so, there will remain important aspects of the evaluation process that are not elucidated by our evaluator. The most important of these are the detailed mechanisms by which procedures call other procedures and return values to their callers. We will address these issues in chapter 5, where we take a closer look at the evaluation process by implementing the evaluator as a simple register machine.

4.1 — ours#4 / mit#4 — CONTENT_DIFF(sim=0.96)

• OURS: If we grant ourselves the ability to apply primitives, then what remains for us to implement in the evaluator? The job of the evaluator is not to specify the primitives of the language, but rather to provide the connective tissue—the means of combination and the means of abstraction—that binds a collection of primitives to form a language. Specifically: • The evaluator enables us to deal with nested expressions. For example, although simply applying primitives would suffice for evaluating the expression (+ 1 6), it is not adequate for handling (+ 1 (* 2 3)). As far as the primitive procedure + is concerned, its arguments must be numbers, and it would choke if we passed it the expression (* 2 3) as an argument. One important role of the evaluator is to choreograph procedure composition so that (* 2 3) is reduced to 6 before being passed as an argument to +. • The evaluator allows us to use variables. For example, the primitive procedure for addition has no way to deal with expressions such as (+ x 1). We need an evaluator to keep track of variables and obtain their values before invoking the primitive procedures. • The evaluator allows us to define compound procedures. This involves keeping track of procedure definitions, knowing how to use these definitions in evaluating expressions, and providing a mechanism that enables procedures to accept arguments. • The evaluator provides the special forms, which must be evaluated differently from procedure calls.
• MIT: If we grant ourselves the ability to apply primitives, then what remains for us to implement in the evaluator? The job of the evaluator is not to specify the primitives of the language, but rather to provide the connective tissue -- the means of combination and the means of abstraction -- that binds a collection of primitives to form a language. Specifically: The evaluator enables us to deal with nested expressions. For example, although simply applying primitives would suffice for evaluating the expression (+ 1 6), it is not adequate for handling (+ 1 (* 2 3)). As far as the primitive procedure + is concerned, its arguments must be numbers, and it would choke if we passed it the expression (* 2 3) as an argument. One important role of the evaluator is to choreograph procedure composition so that (* 2 3) is reduced to 6 before being passed as an argument to +. The evaluator allows us to use variables. For example, the primitive procedure for addition has no way to deal with expressions such as (+ x 1). We need an evaluator to keep track of variables and obtain their values before invoking the primitive procedures. The evaluator allows us to define compound procedures. This involves keeping track of procedure definitions, knowing how to use these definitions in evaluating expressions, and providing a mechanism that enables procedures to accept arguments. The evaluator provides the special forms, which must be evaluated differently from procedure calls.

4.1 — ours#11 / mit#11 — CONTENT_DIFF(sim=0.98)

• OURS: These selectors for a list of expressions—and the corresponding ones for a list of operands—are not intended as a data abstraction. They are introduced as mnemonic names for the basic list operations in order to make it easier to understand the explicit-control evaluator in section 5.4.
• MIT: These selectors for a list of expressions -- and the corresponding ones for a list of operands -- are not intended as a data abstraction. They are introduced as mnemonic names for the basic list operations in order to make it easier to understand the explicit-control evaluator in section 5.4.

4.1 — ours#19 / mit#19 — CONTENT_DIFF(sim=0.57)

• OURS: The fact that the machines are described in Lisp is inessential. If we give our evaluator a Lisp program that behaves as an evaluator for some other language, say C, the Lisp evaluator will emulate the C evaluator, which in turn can emulate any machine described as a C program. Similarly, writing a Lisp evaluator in C produces a C program that can execute any Lisp program. The deep idea here is that any evaluator can emulate any other. Thus, the notion of “what can in principle be computed” (ignoring practicalities of time and memory required) is independent of the language or the computer, and instead reflects an underlying notion of
• MIT: The fact that the machines are described in Lisp is inessential. If we give our evaluator a Lisp program that behaves as an evaluator for some other language, say C, the Lisp evaluator will emulate the C evaluator, which in turn can emulate any machine described as a C program. Similarly, writing a Lisp evaluator in C produces a C program that can execute any Lisp program. The deep idea here is that any evaluator can emulate any other. Thus, the notion of what can in principle be computed'' (ignoring practicalities of time and memory required) is independent of the language or the computer, and instead reflects an underlying notion of computability. This was first demonstrated in a clear way by Alan M. Turing (1912-1954), whose 1936 paper laid the foundations for theoretical computer science. In the paper, Turing presented a simple computational model -- now known as a Turing machine -- and argued that any effective process'' can be formulated as a program for such a machine. (This argument is known as the Church-Turing thesis.) Turing then implemented a universal machine, i.e., a Turing machine that behaves as an evaluator for Turing-machine programs. He used this framework to demonstrate that there are well-posed problems that cannot be computed by Turing machines (see exercise 4.15), and so by implication cannot be formulated as ``effective processes.'' Turing went on to make fundamental contributions to practical computer science as well. For example, he invented the idea of structuring programs using general-purpose subroutines. See Hodges 1983 for a biography of Turing.

4.2 — ours#40 / mit#40 — CONTENT_DIFF(sim=0.98)

• OURS: This is the procedural representation described in exercise 2.4. Essentially any procedural representation (e.g., a message-passing implementation) would do as well. Notice that we can install these definitions in the lazy evaluator simply by typing them at the driver loop. If we had originally included cons, car, and cdr as primitives in the global environment, they will be redefined. (Also see exercises 4.34 and 4.35.)
• MIT: This is the procedural representation described in exercise 2.4. Essentially any procedural representation (e.g., a message-passing implementation) would do as well. Notice that we can install these definitions in the lazy evaluator simply by typing them at the driver loop. If we had originally included cons, car, and cdr as primitives in the global environment, they will be redefined. (Also see exercises 4.33 and 4.34.)

4.3 — ours#None / mit#49 — ADDED_IN_OURS

• MIT: This is taken from a booklet called ``Problematical Recreations,'' published in the 1960s by Litton Industries, where it is attributed to the Kansas State Engineer.

4.4 — ours#60 / mit#61 — CONTENT_DIFF(sim=0.91)

• OURS: Interest in logic programming peaked during the early 1980s when the Japanese government began an ambitious project aimed at building superfast computers optimized to run logic programming languages. The speed of such computers was to be measured in LIPS (Logical Inferences Per Second) rather than the usual FLOPS (FLoating-point Operations Per Second). Although the project succeeded in developing hardware and software as originally planned, the international computer industry moved in a different direction. See Feigenbaum and Shrobe 1993 for an overview evaluation of the Japanese project. The logic programming community has also moved on to consider relational programming based on techniques other than simple pattern
• MIT: Interest in logic programming peaked during the early 80s when the Japanese government began an ambitious project aimed at building superfast computers optimized to run logic programming languages. The speed of such computers was to be measured in LIPS (Logical Inferences Per Second) rather than the usual FLOPS (FLoating-point Operations Per Second). Although the project succeeded in developing hardware and software as originally planned, the international computer industry moved in a different direction. See Feigenbaum and Shrobe 1993 for an overview evaluation of the Japanese project. The logic programming community has also moved on to consider relational programming based on techniques other than simple pattern matching, such as the ability to deal with numerical constraints such as the ones illustrated in the constraint-propagation system of section 3.3.5.

4.4 — ours#66 / mit#67 — CONTENT_DIFF(sim=0.87)

• OURS: Because matching is generally very expensive, we would like to avoid applying the full matcher to every element of the data base. This is usually arranged by breaking up the process into a fast, coarse match and the final match. The coarse match filters the data base to produce a small set of candidates for the final match. With care, we can arrange our data base so that some of the work of coarse matching can be done when the data base is constructed rather then when we want to select the candidates. This is called indexing the data base. There is a
• MIT: Because matching is generally very expensive, we would like to avoid applying the full matcher to every element of the data base. This is usually arranged by breaking up the process into a fast, coarse match and the final match. The coarse match filters the data base to produce a small set of candidates for the final match. With care, we can arrange our data base so that some of the work of coarse matching can be done when the data base is constructed rather then when we want to select the candidates. This is called indexing the data base. There is a vast technology built around data-base-indexing schemes. Our implementation, described in section 4.4.4, contains a simple-minded form of such an optimization.

4.4 — ours#78 / mit#79 — CONTENT_DIFF(sim=0.90)

• OURS: A discussion and justification of this treatment of not can be found in the article “Negation as Failure” by Clark (1978).
• MIT: A discussion and justification of this treatment of not can be found in the article by Clark (1978).

4.4 — ours#79 / mit#80 — CONTENT_DIFF(sim=0.59)

• OURS: In general, unifying ?y with an expression involving ?y would require our being able to find a fixed point of the equation ?y = expression involving ?y. It is sometimes possible to syntactically form an expression that appears to be the solution. For example, ?y = (f ?y) seems to have the fixed point (f (f (f ... ))), which we can produce by beginning with the expression (f ?y) and repeatedly substituting (f ?y) for ?y. Unfortunately, not every such equation has a meaningful fixed point. The issues that arise here are similar to the issues of manipulating infinite series in mathematics. For example, we know that 2 is the solution to the equation y = 1 + y/2. Beginning with the expression 1 + y/2 and repeatedly substituting 1 + y/2 for y gives 2 = y = 1 + y/2 = 1 + (1 + y/2)/2 = 1 + 1/2 + y/4 = · · · , which leads to 2 = 1 + 1/2 + 1/4 + 1/8 + · · · . However, if we try the same manipulation beginning with the observation that –1 is the solution to the equation y = 1 + 2y, we obtain –1 = y = 1 + 2y = 1 + 2(1 + 2y) = 1 + 2 + 4y = · · · , which leads to –1 = 1 + 2 + 4 + 8 + · · · . Although the formal manipulations used in deriving these two equations are identical, the first result is a valid assertion about infinite series but the second is not. Similarly, for our unification results, reasoning with an arbitrary syntactically constructed expression may lead to errors.
• MIT: In general, unifying ?y with an expression involving ?y would require our being able to find a fixed point of the equation ?y = <expression involving ?y>. It is sometimes possible to syntactically form an expression that appears to be the solution. For example, ?y = (f ?y) seems to have the fixed point (f (f (f ... ))), which we can produce by beginning with the expression (f ?y) and repeatedly substituting (f ?y) for ?y. Unfortunately, not every such equation has a meaningful fixed point. The issues that arise here are similar to the issues of manipulating infinite series in mathematics. For example, we know that 2 is the solution to the equation y = 1 + y/2. Beginning with the expression 1 + y/2 and repeatedly substituting 1 + y/2 for y gives which leads to However, if we try the same manipulation beginning with the observation that - 1 is the solution to the equation y = 1 + 2y, we obtain which leads to Although the formal manipulations used in deriving these two equations are identical, the first result is a valid assertion about infinite series but the second is not. Similarly, for our unification results, reasoning with an arbitrary syntactically constructed expression may lead to errors.

5.3 — ours#None / mit#7 — ADDED_IN_OURS

• MIT: This is precisely the same ``tagged data'' idea we introduced in chapter 2 for dealing with generic operations. Here, however, the data types are included at the primitive machine level rather than constructed through the use of lists.

5.3 — ours#7 / mit#8 — CONTENT_DIFF(sim=0.05)

• OURS: This is precisely the same “tagged data” idea we introduced in chapter 2 for dealing with generic operations. Here, however, the data types are included at the primitive machine level rather than constructed through the use of lists. Type information may be encoded in a variety of ways, depending on the details of the machine on which the Lisp system is to be implemented. The execution efficiency of Lisp programs will be strongly dependent on how cleverly this choice is made, but it is difficult to formulate general design rules for good choices. The most straightforward way to implement
• MIT: Type information may be encoded in a variety of ways, depending on the details of the machine on which the Lisp system is to be implemented. The execution efficiency of Lisp programs will be strongly dependent on how cleverly this choice is made, but it is difficult to formulate general design rules for good choices. The most straightforward way to implement typed pointers is to allocate a fixed set of bits in each pointer to be a type field that encodes the data type. Important questions to be addressed in designing such a representation include the following: How many type bits are required? How large must the vector indices be? How efficiently can the primitive machine instructions be used to manipulate the type fields of pointers? Machines that include special hardware for the efficient handling of type fields are said to have tagged architectures.

5.3 — ours#8 / mit#9 — CONTENT_DIFF(sim=0.78)

• OURS: This decision on the representation of numbers determines whether eq?, which tests equality of pointers, can be used to test for equality of numbers. If the pointer contains the number itself, then equal numbers will have the same pointer. But if the pointer contains the index of a location
• MIT: This decision on the representation of numbers determines whether eq?, which tests equality of pointers, can be used to test for equality of numbers. If the pointer contains the number itself, then equal numbers will have the same pointer. But if the pointer contains the index of a location where the number is stored, equal numbers will be guaranteed to have equal pointers only if we are careful never to store the same number in more than one location.

5.4 — ours#None / mit#26 — ADDED_IN_OURS

• MIT: This implementation of tail recursion in ev-sequence is one variety of a well-known optimization technique used by many compilers. In compiling a procedure that ends with a procedure call, one can replace the call by a jump to the called procedure's entry point. Building this strategy into the interpreter, as we have done in this section, provides the optimization uniformly throughout the language.

5.5 — ours#38 / mit#40 — CONTENT_DIFF(sim=0.94)

• OURS: Making a compiler generate tail-recursive code might seem like a straightforward idea. But However, compilers for common languages, including C and Pascal, do not always do this, and therefore these languages cannot represent iterative processes in terms of procedure call alone. The difficulty with tail recursion in these languages is that their implementations use the stack to store procedure arguments and local variables as well as return addresses. The Scheme implementations described in this book store arguments and variables in memory to be garbage-collected. The reason for using the stack for variables and arguments is that it avoids the need for garbage collection in languages that would not otherwise require it, and is generally believed to be more efficient. Sophisticated Lisp compilers can, in fact, use the stack for arguments without destroying tail recursion. (See Hanson 1990 for a description.) There is also some debate about whether stack allocation is actually more efficient than garbage collection in the first place, but the details seem to hinge on fine points of computer architecture. (See Appel 1987 and Miller and Rozas 1994 for opposing views on this issue.)
• MIT: Making a compiler generate tail-recursive code might seem like a straightforward idea. But most compilers for common languages, including C and Pascal, do not do this, and therefore these languages cannot represent iterative processes in terms of procedure call alone. The difficulty with tail recursion in these languages is that their implementations use the stack to store procedure arguments and local variables as well as return addresses. The Scheme implementations described in this book store arguments and variables in memory to be garbage-collected. The reason for using the stack for variables and arguments is that it avoids the need for garbage collection in languages that would not otherwise require it, and is generally believed to be more efficient. Sophisticated Lisp compilers can, in fact, use the stack for arguments without destroying tail recursion. (See Hanson 1990 for a description.) There is also some debate about whether stack allocation is actually more efficient than garbage collection in the first place, but the details seem to hinge on fine points of computer architecture. (See Appel 1987 and Miller and Rozas 1994 for opposing views on this issue.)