Errata, Concepts in Programming Languages

John C. Mitchell, Cambridge University Press, 2002

If you have corrections that are not listed already, I would appreciate email. In the interest of time, many of these comments and corrections are copied directly from messages I have received.- JCM

Page 17, Exercise 2.2, page 17
wording seems confusing. First, it talks about writing a program that takes P as an input (and no arguments for P) and then passes P to function Halt0. Then, the second paragraph starts talking about a program that takes both P and n as input. A bit confusing. -Petri
Page 18
"... emacs is written in Lisp, as is the linux graphical toolkit gtk ..." - Delete reference to gtk
Page 24
The ``Historical Lisp'' described in section 3.3 uses a Scheme-like syntax for function definitions. This is a bit of revisionism. In LISP 1.5, the definition of find would have been written thus:
            (COND ((EQ Y NIL) NIL)
                  ((EQ X (CAR Y)) X)
                  (T (FIND X (CDR Y)))))) ))
(Actually, it would probably have been written so as to make it possible to distinguish a successful search from an unsuccessful one even when X is NIL, but that's a design flaw in Mitchell's code rather than a syntax difference.)
Page 25
In the table, the entries for rplaca and rplacd are messed up: Lisp rplaca corresponds to Scheme set-car! and Lisp rplacd to Scheme set-cdr!. Also, there is no reason to capitalize `setq'. Early implementations of Lisp for environments that supported lower-case letters were mostly case-insensitive.
Page 27
The value  of  (cond (diverge 1) (true 0)) is undefined if diverge is some expression whose evaluation does not terminate.  For example, we may define a loop function (define loop (lambda (x) (loop (loop x)))) and let diverge be the expression (loop 2).
Page 29, fourth line up from the second diagram
The phrase `may be represented' should be deleted from "We may represent an atom may be represented ..."
Page 33, third line down from the first display
`(plus (square x) y)' should be `(+ (square x) y)'.
Pages 38 and 39, from just after the box-and-pointer diagram to just after the second display on page 39
In this passage, there is a persistent confusion, aggravated by a typographical error, between identifiers like x and symbols like 'A. The passage should read something like this:

Suppose we call this list x and we want to change the third element of list x to 'E. In pure Lisp, we cannot change any of the cells of this list, but we can define a new list with elements 'A, 'B, 'E, 'D. The following expression constructs this new list; `(cadr x)' means ``car of the cdr of x'' and `(cdddr x)' means ``cdr of the cdr of the cdr of x''.

(cons (car x) (cons (cadr x) (cons 'E (cdddr x))))

Note that evaluating this expression involves creating new cons cells for the first three elements of the list and, if there is no further use for them, eventually garbage-collecting the old cells used for the first three elements of x. In contrast, in impure Lisp, we can change the third cell directly by using the expression

(rplaca (cddr x) 'E)

If all we need is the list we obtained by replacing the third element of x with 'E, then this expression gets the result we want far more efficiently.

Page 38, second last line:
"... and we want to change the third element of list x to '" (' -> y)
Page 45, line 4
`deos' should be `does'
Page 45, Problem 3.7(d)
an correctly functioning -> a correctly functioning
Page 49, fifth line down from the photograph
`Backus naur form' should be `Backus-Naur form'.
Page 65, third equation
There should be another set of parentheses in the expression after the second equals sign. The additional parentheses begin right after the symbol f and are shown here larger and in white:
    Yf = (lx.f(xx))(lx.f(xx)) = f ( (lx.f(xx))(lx.f(xx)) ) = f(Yf)
Page 68, line 5
"The function would not be defined on machine states in which the value of z is not a nonnegative integer" (The function will still do x :=0, y := 0)
Page 75 display
complictated --> complicated
Page 79, line 12
"... Cumputing Machinery ..." (Cumputing -> Computing)
Page 85 ex 4.9b l3
or --> for
Page 87, first line of the code displayed in Exercise 4.11
`if = x=0' should be `if x = 0'
Page 95: (ALGOL 60)  / Hans J. Schneider
You are right that students are irritated by the way that semicolons must be used between statements. I had to teach ALGOL 60 from 1961 to 1975, and I agree with this opinion. Contrary to your comment in this paragraph, it is possible to put a semicolon before an "end", because the syntax allows the empty statement! (Even a sequence of semicolons is allowed !) Nevertheless, there is a position where no semicolon is allowed: before "else", since this does not indicate the beginning of a new statement. If you want to have more than one statement between "then" and "else", you must use the "begin-end"-construct. Indeed, this syntax is irritating.
Page 96 last para:
The reference to "Backus Normal Form" should be accompanied by a note that it soon became known as "Backus Naur Form", perhaps at Donald Knuth's suggestion (CACM 7:12 (1964) 735-736).
Page 97, line 9 from the bottom
`design' should be `designed'.
Page 98, second full paragraph
Mitchell's assertion that ``procedure parameters could not be procedures with procedure parameters'' in Pascal is incorrect. Contrary to what he claims, the example that he gives in the second display on page 98 is legal in Pascal; the file refutation.p demonstrates this point.
Page 98, second line of the second display
The comma after k is erroneous and should be deleted.
Pages 98-99:
Standard Pascal requires that an array parameter be specified by a named type, making the last line of p. 98 incorrect; it would have to be type small_array = array[1..10] of integer; procedure p(a: small_array) [even when Pascal allows conformant array parameters, actual dimensions aren't given in the procedure declaration]
Page 108, lines 1 and 2 of subsection ``Integers''
In Standard ML, literals denoting negative integers begin with tildes rather than minus signs: ~1, ~2, and so on. The minus sign is used only for the subtraction operation.
Page 109, second display
`Chelsey' should be `Chelsea' (both times).
Page 122, line 12
"... this language combines many if the important ..." (if -> of)
Page 134, line 11
`mean' should be `means'.
Page 134, line 3 above the table at the bottom
`error' should be `errors'.
Page 136, section 6.3.2, step 1
"A assign a type ..." (delete A)
Page 141, line 7 of Example 6.5
Remove the period (.) in the type expression and add parentheses to change "int-> int.* int" to "(int -> int)* int".
Page 148, first line below boldface heading C++ Implementation 
The book says,  "C++ templates are instantiated at program link time" and then describes a situation in which a function template and the code that calls it are compiled separately. There are actually several wasy that templates and instantiation oare implemented in C++. See, for example,, for some discussion.
Page 151, line 21 (bullet 3.0 + 2.0) 
"... the compiler will produce machine instructions that perform integer addition" (integer -> floating point)
Page 153, last word on the page
Page 155, 9th last line
"1. Assign a type ... by using the known type of a symbol of a type variable" (known type of a symbol OR a type variable)
Page 159 Ex 6.8:
Two errors a) the first display calls reduce as a curried function, but the definition gives it in uncurried form. b) The first line of the definition specifies reduce as projection on its second argument, making the second line redundant. SML v110 reports a duplicated pattern-match and rejects the definition, rather than giving it the type shown.
Page 160, Ex 6.10:
the first line of the display needs parentheses around the function-application: fun f(x) = not (f x);
Page 162, line 2 of first paragraph
The comma after `simple' should be deleted.
Page 163, lines 13 and 14
`fixed-memory location' should be `fixed memory location'.
Page 169, last line before Example 7.1
There should be a period at the end of the sentence.
Page 171 Fig 7.4 legend:
funtion --> function
page 171, temporary storage, ....
Change with to when so the phrase with the function executes reads when the function executes
Page 178, 1st sentence under "Example 7.6":
The Example 7.5 (pseudo)code to which it refers is not ML.
Page 182, 10th last line
"The map function take ..." (take -> takes)
Page 187, line 1
The identifier compose should be printed in the font used for ML code.
Page 187, line 5:
computes --> compute (or get --> gets).
Pages 187-188 (Example 7.9)
The function that is called make_counter in the ML version is renamed mk_counter in the C version. Figure 7.10 uses both of these names, as well as the contracted form make_c.
Page 188, Fig 7.10, upper-left cell:
"make c" --> "make_c", as used in the following text, sec 1.
Page 190, first line of Chapter Summary
Blocks are not always identified by begin and end markers. In Scheme, for instance, each top-level definition begins a new block, which ends (with no marker) at the end of the program.
Page 191, Problem 7.1, part (a)
In line 9 of the code, change  <= to >= . Line 9 of part (a) should then match line 9 of the code in part (b).
Page 194, fifth line from the bottom of the page
The period after `power(a, a, c)' should be a question mark.
Pages 207-208, 
The phrase `determining to where a jump goes', which bridges , should be `determining the target of a jump'.
Page 209, 8.2.2, line 2
"Exceptions declarations ..." (exceptions -> exception)
Page 210, line 11
"If <exp2> raises an exception or <exp2> raises an exception that doesn't match <pattern> ..." (change second <exp2> to <exp1>)
Page 210, second last line (code sample):
"else if x 10 then ..." (missing operator)
Page 210, second line from the bottom (in the code example)
A relational operator is missing between `x' and `10'.
Page 210 ML display under "Examples":
the three occcurences of integer constants should be reals: ... else 1.0/x; ... => 0.0 ... => 1.0 for consistency, the following text should also use real constants.
Page 213, 8th last line
Subsection -> subsection
Page 215
In the first example in the subsection ``Static and dynamic scope'', the text refers to a variable X, but the accompanying code uses the variable x instead. Since ML is case-sensitive, it makes a difference; all the occurrences of `x' (in the code, and in the line just below the code display) should be changed to `X'.
Page 216,
The paragraph right below the illustration says that "all of the activation records below the activation record with handler X and value 6 are removed from the run-time stack because they are not needed to continue the computation." The handler for the raised exception is the handler with value 2, though. I believe that only activation records up to the one with handler X and value 2 (the one labeled "g(f)" in the picture) should be popped.
The paragraph in the book is bad. The handler is the one just above the call, so only the bottom activation record is popped off the stack.
Page 221, CPS
CPS stands for "continuation passing style". I prefer the term "continuation-passing form", which is used in the text. The abbreviation CPS should be defined in the text but it is not.
Page 222, Continuations and Tail Recursion, line 15
(code sample formatting, fun factk(n) = let fun should go under bar)
Page 226, last two lines before the fourth display
The double quotation mark that precedes the phrase `unevaluated delay' should be attached to it, but has instead been set at the end of the preceding line.
Page 227, last line
(noone -> no one, nobody)
Page 228, last line of para 3:
are --> as.
Page 229, first line of Exercise 8.2
The identifier `t1' should be `tl' (that is, tee-one should be tee-ell).
Page 229:
The answer to the final question in Ex 8.2 depends on the fact, unstated in the text, that the ML specification requires that operator arguments be evaluated left-to-right.
Page 236, eighth line after photograph
`As of the' should be `As of'.
Page 267, second paragraph above Example 9.13
A range is a pair of non-negative integers, with the first less than or equal to the second and the second less than or equal to the length of the array.
page 260, paragraph 3:
The book currently says, "You may have noticed that the C++ keyword associated with a type variable is `class'." As the rest of the book reflects, there's also `typename', which was added in Standard C++ (for other reasons), but can be used interchangeably with `class' in template parameter type declarations. Therefore, this paragraph may not be needed now.
Page 261: (ML Polymorphism) / Hans J. Schneider
In the example, you have a parameter "less" that is not used in the body of the function. I think that "<" should be read "less".
Page 276, ex 9.5:
2nd line of the pop def. should be pop(Push(x,s)) = s
Page 292, code sample
"Singleton* Singleton::_singleton = 0" (_singleton -> _instance)
Page 305, last line
(circle representation missing radius)
Page 308, 4th last line
"... changes to color of the point..." (to -> the)
Page 309, first line
Page 309, sixth line from the bottom
`Java array array assignment' should be `Java array assignment'.
Page 316 para 2 line 3:
Figure 7.1 --> Figure 11.4
Page 318, line 4
"... the ColoredPoint method can be compiled ..." (ColoredPoint -> draw)
Page 325,  Figure 11.6 on , 
the label on the second box in the third row from the bottom should be `Sequenceable' rather than `Sequenceab'.
Page 325, Fig 11.6:
Sequenceab --> Sequenceable [box near the bottom]
Page 345 "Casts and Conversions", line 10:
"Point objects can be treated as ColorPoint objects". Isn't it the reverse?
Page 347, line 8
"... constructors are class methods ..." Aren't C++ constructors always called against a newly created object, thus making them more like instance methods?)
Page 350, 8th last
"As a consequence of subtyping, a program may assign a colored point to a pointer to a point ..." (a bit confusing statement)
Page 351, line 11
"Unlike in Smalltalk, here there ..." (delete 'here')
Page 352, 10th last (code line)
"int A::g(A* this, int x)..." (int x -> int y to make consistent with code above)
Page 353
Under the subheading "Scope Qualifiers" you have some examples of quantified names formed with ::, ->, and, . The third example is "o.n" and the associated comment should read "object o of class C followed by member name n." ~ajith
Page 353, 8th last line
"o.n /* pointer p to object ..." (comment doesn't make sense)
Page 355, 12.4, 2nd line
"... occurs only when inhertance is used" (inhertance -> inheritance)
Page 357, ColorPoint code sample
possibly move ColorPoint's "move"-method one step up, so that ColorPoint's two first methods are the same as Point's two methods.
Page 381
In the third line of the code example, in the wing comment, `OPENor' should be `OPEN or'.
Page 398, code sample
realign "ArrayStoreException" to be part of the comment
Page 406, second line before Section 13.4.4
`no instance of class' should be `no instance of a class'.
Page 401, Example 13.1
In the definition of class Node, the signature Node (Node n, int e) of the constructor should be Node (Node n, Object e) so that the assignment "element=e" will compile.
Page 421, Ex 13.3 (a), line 3:
alright --> all right
p.434 line 13 from the bottom: 
there one sequence of program actions  -->  there is at most one sequence of program actions
Page 435, 4th last
"In unbuffered communication, a data item sent before the receiver is ready to accept that it may be lost" (restructure sentence)
Page 443, second line from the bottom
`a forwarded' should be `a forwarder'.
Page 453
In the declaration of the mvar datatype at the bottom of the page, there should be a comma after `putCh: 'a chan'.
Page 457, line 7 after the first display
`are a reentrant' should be `are reentrant'.
Page 457, 15th last lin
Subsection -> subsection
Page 459, lines 7 and 8 after the display
`simultaneouosly' (divided over the two lines) should be `simultaneously'.
Page 462, line 12 after the diagram
`placed shared memory' should be `placed in shared memory'.
Page 463, first paragraph before the display
The sentence containing the reference to the Pugh paper is garbled in several ways. It should look something like this:

Here is the outline of a simple program (devised by William Pugh in ``The Java memory model is fatally flawed,'' Concurrency: practice and experience 12 [2000], 445-455) whose behavior is affected by the relaxed prescient store rule.

Page 470, line 5
`g := false' should be `go := false'.
Page 473, last line
`Mycamera' should be `MyCamera'.
Page 474, third line from the bottom
`assginments' should be `assignments'.
Page 475, last paragraph. The reference to Kowalski's paper is garbled; it should read as follows

This was eventually achieved by Robert Kowalski (``Predicate logic as a programming language,'' in Proceedings of IFIP Congress 74, North-Holland, 1974).

Page 476, line 10
`now called Warren Abstract Machine' should be `now called the Warren Abstract Machine'.
Page 481, line 3 of Section 15.3.4
There should be a period after the abbreviation `vol'. Better yet, the whole reference should be correctly formatted: `(``An efficient unification algorithm,'' ACM transactions on programming languages and systems 4 [1982], 258-282)'.
Page 482, first line of Section 15.4
The adjective `rule-based' should be hyphenated in both cases.
Page 483, first line of Section 15.4.2
`A nondeterminism' should be `Nondeterminism'.
Page 488
The beginning of the paragraph just preceding Section 15.5.2 should be indented.
Page 491, line 3 above the first display
`y2' should be `y'.
Page 498, lines 4 and 5 after the display
`thumb rules' should be `rules of thumb'.
Page 500, second line
`a Prolog's built-in' should be `a Prolog primitive'.
Page 501, second line above subsection ``Call''
The adjective `two-line' should be hyphenated.
Page 501, last sentence. 
It is not true that ``no counterpart of failing computations exists in other programming paradigms.'' For instance, SNOBOL4 and Icon, which are primarily based on the imperative paradigm, support success and failure of expressions, goal-directed evaluation, and control backtracking.
Page 504, second paragraph after second display. 
The fonts for `A' and `B' are wrong throughout the paragraph.
Page 505, third paragraph of Section 15.8, first line
`the terms' should be either `the term' or `terms'.
Page 506, sixth line of subsection ``Lack of types''
`the queries' should be `queries'.
Page 506, fourth line of subsection ``Idiosyncratic control''
`the recursion' should be `recursion'.
Page 507, second line of subsection ``No modules and no objects''
`ISO Prolog' should be `ISO Standard Prolog'.
Page 507, fifth line of subsection ``No modules and no objects''
`object-programming' should be `object-oriented'.
Page 507, first paragraph
The sentence beginning `But no compile-time checking' is contains several errors and should be rewritten, perhaps as follows:

However, no checks at compilation time enforce the conventions of this style. Design errors will be discovered at run time or not at all.

Page 507, second line above Section 15.9
`succeeded to embrace' should be `succeeded in embracing'.
Several formulas containing lambda-expressions have the English word `lambda' in place of the Greek letter that it denotes.
Page 521,  `alpha conversion'
The word `alpha-converted' should be hyphenated.
Page 521, `confluence'
Even in confluent calculi, the order in which one applies reduction rules is sometimes the key difference between a process of evaluation that terminates and one that does not. This is not an unimportant difference.
Page 524, `variable capture'
The exclamation point in the equation should be deleted

Ex. 5.3a has a simple answer that is probably not what you intend: ...

Ex 7.10b seems to be asking for an affirmative answer, by contrast with 7.10c. But if so, ...


Thanks to the many readers who contributed corrections, including Hans J. Schneider, John David Stone, Jonathan Wellons, and students and teaching assistants of Stanford CS 242.

Return to J Mitchell home page