Errata for "Concepts, Techniques, and Models of Computer Programming" (second and third printings)

Errata for “Concepts, Techniques, and Models of Computer Programming” (second and third printings)

“Nothing that Man creates should be too perfect, lest it make the gods jealous and bring down their wrath.”

This page lists all known errors and their corrections for the second and third printings of the book. The errors in the most recent, fourth printing, are given here and the errors in the first printing are given here. If you find any new errors, please notify one of the authors. We use the following notation for the corrections: positive line numbers start counting from the top of the text body (including section titles); negative line numbers start counting from the bottom (including section titles and footnote text).

Page 31, figure 2.1, line 3: "N" (first occurrence) should be "'N'".
Page 31, figure 2.1, line 6: add '1' before 'else'.
Page 56, line -9: "D multiples" should be "D=C*C multiplies".
Page 65, line 9: "it has no free identifier occurrences" should be "the only free identifier occurrence, Browse, is defined in the global environment of the interactive interface".
Page 65, line -9: "E|_{{<z>₁,...,<z>_n}}" should be "E|_{{<z>₁,...,<z>_k}}".
Page 67, line 15: "[<feat>₁ ··· <feat>_n]" should be "{<feat>₁, ..., <feat>_n}".
Page 81, table 2.4: Add the case "<expression> <consBinOp> <expression>" to the definition of <expression> and add the rule "<consBinOp> ::= '#' | '|'". This ensures that the table defines the syntax of all the section's examples.
Page 100, line 2: "Any two partial values can be unified." should be "Any two compatible partial values can be unified."
Page 103, line -5: "at least one of them is unbound" should be "at least one of them is unbound and there are no pairwise incompatible nodes elsewhere".
Page 104, line -6: "(1917-)" should be "(1917-2008)".
Page 107, line -14: "If a function body has an" should be "If a function returns a result through an".
Page 129, line 15: "T₁ ··· T_n, T" should be "T₁ ··· T_n T".
Page 158, line -9: "a record" should be "a record with atoms as features".
Page 173, line 6: "1+T(s)" should be "1+M(s)".
Page 176, line 3: "18" should be "24".
Page 176, line 7: "two years" should be "18 months".
Page 179, line 3: "principle" should be "principal".
Page 179, line 24: "the free variables" should be "the free identifiers".
Page 191, line -21: "fun {$ T T}: <bool>" should be "fun {$ T}: <bool>".
Page 195, line -16: "{Pop {EmptyStack}}" should be "For an unbound E, {Pop {NewStack} E}".
Page 197, line -8: "<Value>₁" should be "the last argument".
Page 198, line -3: "four" should be "three".
Page 222, lines 10-13: The text from "First" to "when execution starts." should be replaced by:
First, a read-only variable is created. Second, when the value of the read-only variable is needed (i.e., the program attempts to invoke a module operation), then the functor value is loaded from memory and called in a new thread with as arguments the modules it imports. This is called dynamic linking, as opposed to static linking in which the functor is installed when execution starts. Third, the functor call returns the new module and binds it to the variable.
Page 226, line -12: "S1 ?Sn" should be "?S1 Sn".
Page 232, line 9: "section 3.4.4" should be "section 3.4.5".
Page 232, footnote: "from Olivier Danvy" should be "from Olivier Danvy and Mayer Goldberg".
Page 249, line -12: "Y" should be "Xs".
Page 249, line -7: "Remark" should be "We remark".
Page 262, figure 4.13: "Xs={Generate 0 150000}" should be "{DGenerate 0 Xs}" and "S={Sum Ys 0}" should be "S={DSum Ys 0 150000}".
Page 275, line 4: "has its has its" should be "has its".

Page 276, figure 4.21: The definitions of Spawn and Resume in the book have a race condition: they do not guarantee that a thread is suspended before another thread resumes it. The following definitions do provide this guarantee:

 fun {Spawn P}
 Id Ok in
    thread
       Id={Thread.this}
       {Wait Ok}
       {P}
    end
    {Thread.suspend Id}
    Ok=unit
    Id
 end

 proc {Resume Id}
 Ok Me={Thread.this} in
    thread
       {Thread.suspend Me}
       Ok=unit
       {Thread.resume Id}
    end
    {Wait Ok}
 end

Pages 283 and 796 (by-need semantics): The book gives a semantics where a variable is needed by an operation if the variable must be determined for the operation to continue. The implementation has a slightly different semantics that gives strictly more needed variables: a variable is needed if there is a suspension on the variable (see footnote on page 796). This makes a difference in calculations with unbound variables, such as the bottom example of page 283: the implementation will execute the comparison, whereas the book's semantics will not.
Page 325, line -3: "A insecure" should be "An insecure".
Page 338, line -4: "Some of" should be "All".
Page 347, line -5: "{NewPort S P}" should be "{NewPort ?S ?P}".
Page 373, figure 5.11: In the transition from "Wait for doors" to "Moving=false", the action "New Pos: NPos" should be moved to the right of the slash, and another action "New Sched: nil" should be added there.
Page 373, figure 5.11: replace both occurrences of "/=" by "\=".
Page 393, figure 5.22, line 13: Add "end" to the end of the line.

Page 394, figure 5.23: The semantics in figure 5.23 is wrong since it only looks at the first message. The correct semantics is as follows:

 T(receive ... end Sin Sout) ≡
    local
       fun {Loop S T#E Sout}
          if {IsDet S} then
             case S of M|S1 then
                case M
                of T(Pattern1) then E=S1 T(Body1 T Sout)
                ...
                [] T(PatternN) then E=S1 T(BodyN T Sout)
                else E1 in E=M|E1 {Loop S1 T#E1 Sout} end
             end
          else E=S T(BodyT T Sout) end
       end T
    in
       {Loop Sin T#T Sout}
    end

The loop is needed since the message removed from the mailbox is not necessarily the first.

Page 400, lines 1-2: "{Call Ping ping(0)}" should be "{Call pingobj ping(0)}" and "{Call Pong pong(10000000)}" should be "{Call pongobj pong(10000000)}".
Page 402, line -18: "one-argument function" should be "zero-argument function".
Page 402, line -7: "A=B" should be "A==B".

Page 426: The definition of NewCollection near the bottom of the page should be as follows:

 fun {NewCollection}
    S={NewStack}
    proc {Put X} {S.push X} end
    fun {Get} {S.pop} end
    fun {IsEmpty} {S.isEmpty} end
 in
    collection(put:Put get:Get isEmpty:IsEmpty)
 end

The definition in the book has three typos.

Page 428, line 3: "{C1 union(C2)}" should be "{C1.union C2}".
Page 429, line 5: "{C union(D)}" should be "{C.union D}".

Page 431: The Call by value example is better written as:

 procedure sqr(a:integer);
 begin
    a:=a*a;
 end;
 var c:integer;
 c:=25;
 sqr(c);
 browse(c);  /* value of c unchanged */

with Oz translation:

 proc {Sqr D}
    A={NewCell D}
 in
    A:=@A*@A
 end
 local
    C={NewCell 0}
 in
    C:=25
    {Sqr @C}
    {Browse @C}  /* content of C unchanged */
 end

This gives a more reasonable definition of sqr and shows how to pass variables by value.

Page 458, line -11: "This" should be "This is".
Page 471, line -6: "implemented" should be "implemented with".
Page 472, line -9: "IncWords" should be "IncWord".
Page 550, line 9: "{Minus {Inter A1 A2} A3}" should be "{Minus {Inter A2 A3} A1}".
Pages 559-560: The short-circuit protocol can be greatly simplified by relying on the FIFO property of port objects. The methods newsucc and newpred are not needed. The method kill(X S) can be replaced by:
```
 meth kill(X S)
    if @alive then
       if S==1 then @last=@ident
       elseif X mod @step==0 then
          alive:=false
          {@pred setSucc(@succ)}
          {@succ setPred(@pred)}
          {@succ kill(X+1 S-1)}
       else
          {@succ kill(X+1 S)}
       end
    else {@succ kill(X S)} end
 end
```
This works because the FIFO property guarantees that the setSucc and setPred messages arrive at their destinations before the kill messages.
Page 586, figure 8.9: "meth init" should be "meth init X in".

Pages 598-599, figures 8.19-20: The code for NewGRLock and NewMonitor incorrectly handles reentrancy. The problem is that if we have the lock and we execute LockM again, it will incorrectly release the lock. To fix, replace the definitions of GetLock, LockM, and WaitM by:

 fun {GetLock}
    if {Thread.this}\=@CurThr then Old New in
       {Exchange Token1 Old New}
       {Wait Old}
       Token2:=New
       CurThr:={Thread.this}
       true
    else false end
 end

 proc {LockM P}
    if {L.get} then
       try {P} finally {L.release} end
    else {P} end
 end

 proc {WaitM}
 X in
    {Q.insert X} {L.release} {Wait X}
    if {L.get} then skip end
 end

The new definition of GetLock will return true if it got the lock, and false otherwise.

Page 723: The network protocols for literals are described incorrectly. Literals are either names or atoms. Names have token equality and atoms have structure equality. Both names and atoms are copied eagerly but exist only once on a site. Names have a globally unique identity. Atoms are put in a symbol table per site.
Page 752, line -3: "equation" should be "equations".
Page 757: The definition of Palindrome should be corrected as follows:
```
 proc {Palindrome ?A}
    B C X Y
 in
    A::0#9999 B::0#99 C::0#99
    A=:B*C
    X::1#9 Y::0#9
    A=:X*1000+Y*100+Y*10+X
    {FD.distribute ff [X Y B C]}
 end
```
The new definition solves exactly the same problem as the relational version in chapter 9 (page 629). The old definition solves a slightly different problem.
Page 793, line 6: "{n}" should be "{N→n}".
Page 794, line -13: "the pair ξ:y" should be "the pair ξ:x".
Page 826, lines -2 to -4: The text from "The arity of a record" to "and returns the record arity." should be replaced by:
The arity of a record is the set of features of the record. The call {Arity R} executes as soon as R is bound to a record and returns the arity represented as a list of the features of the record sorted lexicographically.
Page 835, line 15: "finally <in(α)>" should be "finally <inStatement>".
Page 853, line 5: Insert the following bibliography entries:
- Hassan Aït-Kaci. An Introduction to LIFE—Programming with Logic, Inheritance, Functions, and Equations. In Logic Programming, Proceedings of the 1993 International Symposium, pages 52-68, Vancouver, British Columbia, October 1993. MIT Press.
- Hassan Aït-Kaci and Andreas Podelski. Towards a Meaning of LIFE. Journal of Logic Programming, 16(3): 195-234, 1993.
- Hassan Aït-Kaci and Roger Nasr. LOGIN: A Logic Programming Language with Built-In Inheritance. Journal of Logic Programming, 3(3): 185-215, 1986.

Back to the book