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
DEFINE (( (FIND (LAMBDA (X Y)
(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
NIL, but that's a design flaw in Mitchell's code rather than
a syntax difference.)
- Page 25
- In the table, the entries for
are messed up: Lisp
rplaca corresponds to Scheme
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
- 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
and symbols like
'A. The passage should read something like
Suppose we call this list
x and we want to change the
third element of list
'E. In pure Lisp, we
cannot change any of the cells of this list, but we can define a new list
The following expression constructs this new list; `
means ``car of the cdr of
x'' and `
means ``cdr of the cdr of the cdr of
(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
'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
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
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
~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
- 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, http://docs.freebsd.org/info/gcc/gcc.info.Template_Instantiation.html,
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
fun f(x) = not (f x);
- Page 162, line 2 of first paragraph
- The comma after `simple' should be
- Page 163, lines 13 and 14
- `fixed-memory location' should be `fixed memory
- 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
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
- 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 `
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 `
- 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 `
- 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 `
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.
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
- 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
- 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."
- 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, `
should be `
- 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
- 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 , 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 `
- Page 474, third line from the bottom
- `assginments' should be
- 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,
- 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 , 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 `
- Page 498, lines 4 and 5 after the display
- `thumb rules' should be `rules
- Page 500, second line
- `a Prolog's built-in' should be `a Prolog
- 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
- Page 504, second paragraph after second display.
- The fonts for `
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
- Page 506, fourth line of subsection ``Idiosyncratic control''
recursion' should be `recursion'.
- Page 507, second line of subsection ``No modules and no objects''
Prolog Standard.as' 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
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
- 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
- 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
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