Errata for “Concepts, Techniques, and Models of Computer Programming”

For the fourth printing (since 2008), this page is like the legendary book about snakes in Ireland: Chapter 1. There are no snakes. The end. There are no known errors in the fourth printing. This page lists all known errors and their corrections for the second and third printings of the book. For those who have a copy of the first printing, its errors 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; negative line numbers start counting from the bottom.

The authors wish to thank the following people for their help in finding errors in the book: Hassan Aït-Kaci, Stefan Andrei, Christopher Campbell, Raphaël Collet, Arnaud Dagnelies, Olivier Danvy, Juan Francisco Diaz, Isabelle Dony, Jeff Jackson, John Johnson, Kent Johnson, Harish Karnick, Waclaw Kusnierczyk, Irene Langkilde-Geary, Gary T. Leavens, Mark S. Miller, David R. Musser, Konstantin Popov, Chris Rathman, Fred Spiessens, and Tony Tanami Vågenes.

• 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 67, line 15: "[<feat>₁ ··· <feat>_n]" should be "{<feat>₁, ..., <feat>_n}".
• 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 179, line 3: "principle" should be "principal".
• Page 179, line 24: "the free variables" should be "the free identifiers".
• 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 232, footnote: "from Olivier Danvy" should be "from Olivier Danvy and Mayer Goldberg".
• 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 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
  

• By-need semantics (page 283, page 796): 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 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 393, figure 5.22, line 13: Add "end" to the end of the line.
• Page 402, line -18: "one-argument function" should be "zero-argument function".
• 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 550, line 9: "{Minus {Inter A1 A2} A3}" should be "{Minus {Inter A2 A3} A1}".
• 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 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