Programming Languages: Principles and Paradigms

Allen Tucker and Robert Noonan

Errata list for first printing (October 2001) - lists all corrections as of January 20, 2003.
(Negative line numbers mean "from bottom of page.")

Page Line Change from: to:

5 2 [Linda 1980] [Carriero 1980]
3 [HPF 1995] [Adams 1997]
-8 [K&R 1988] [Kernighan 1988]
19 -5 [Naur 1960] [Naur 1963]
27 -2 [a-za-Z ] [a-zA-Z0-9!-~ ]
29 7 an in-order a post-order
10 an in-order a post-order
31 10 an inorder a post-order
35 -13 about 8 about 7
-12 18 16
40 Fig 2.17 Term term () {...} Expression term () {...}
Factor factor () {...} Expression factor () {...}
43 -3 begins with 1, 1, begins with 0, 1, 1,
-2 fib(n) = 1 if n = 0 or 1 fib(n) = n if n = 0 or 1
46 Ex 2.3 tokenStream TokenStream
51 -21 raise cause
-19 raise cause
62 -11 Q[s.target\s.source] Q[s.source\s.target]
63 5 ( m = max ( a, b ) } { m = max ( a, b ) }
66 14 1≤i∧i≤n 1≤i+1∧i+1≤n
81 6 M : Division × Σ → Σ M : Division × Σ → Value
12 these expression these expressions
13 M(z+2)*y, M((z+2)*y,
Page Line Change from: to:
91 -1 1 1000 0000 101 1000 0 1000 0000 101 1000
0000 0000 0000 0000 0000 0000
94 2 n/a (first occurrence) .
Tbl 4.3
3 n/a (first occurrence) sizeof
5 n/a n/a n/a n/a n/a n/a new
6 () sizeof ()
() n/a n/a ()
7 () n/a ()
8 , (2 times) n/a (2 times)
100 -5 program. program. (Technically, % is not a
Jay operator, but for the purpose
of this example we will assume it
is.)
105 13 i+1 i+increment
107 6 CaseHead Cases CaseHead Case
8 Statements Statement
12, 13 CaseHead followed by a list series of CaseHeads followed by
of statements a statement
114 -2 global variables... and their global variables and methods–
types that is, all pairs of globals and
their types, and all pairs of meth-
ods and return types.
115 1 tm g = { 〈 h, int〉 , 〈 i, int〉 }  〈 h, int〉 , 〈 i, int〉 , 〈 A, void〉 , 
tm g =  
 〈 B, void〉 , 〈 main, void〉 

13 declarations g declarations and methods g,

23 V ( p.globals ) V ( tm g )

24 typing m (p.globals, typing m ( tm g,

25 global variable global variable and method

Page Line Change from: to:
29 { 〈 h, int〉 , 〈 i, int〉 } tm g

30 { 〈 h, int〉 , 〈 i, int〉 } tm g

31 { 〈 h, int〉 , 〈 i, int〉 } tm g

32 { 〈 h, int〉 , 〈 i, int〉 } tm g

121 23 the product a composite

25 given by γ m ( v ) , and the defined by the function
γ m ( v ) = max x : 〈 v, x〉 ∈ γ m . The

122 1-3 a value in ... method m. the largest x in the range {0, ..., a
- 1} for variable v in which
〈 v, x〉 ∈ γ m .

125 19 γg U γg ∪

31 γg U γg ∪

128 -2 σ – c .params – c .locals σ

129 1-6 removes... That is: effectively makes m’s parameters
and locals most visible by assign-
ing them the largest (maximum)
addresses.
Deactivation of a call reverses
the effect of the activation by
removing the stack frame thus
created and making the calling
method’s parameters and locals
most visible again. That is:
7 σ) U c.params U c.locals σ)
17 γ main – { 〈 a, 2〉 , 〈 b, 3〉 } U γ main ∪

18 〈 h, 0〉 , 〈 h, 0〉 , 〈 i, 1〉 , 〈 a, 2〉 , 〈 b, 3〉 ,
23 is declared locally within A has a higher address within γ A
Page Line Change from: to:
24-25 are also removed ... call. are also inaccessible to A, pro-
vided that strong type checking
rules are employed.
29 γ A – { 〈 x, 4〉 , …, 〈 j, 7〉 } U γA ∪

30 〈 i, 1〉 , 〈 i, 1〉 , 〈 a, 2〉 , 〈 b, 3〉 , 〈 x, 4〉 ,
〈 y, 5〉 , 〈 i, 6〉 , 〈 j, 7〉 ,
130 2 〈 h, 0〉 , 〈 h, 0〉 , 〈 i, 1〉 , 〈 a, 2〉 , 〈 b, 3〉 ,
133 13 / ∧ (two times)
16 [-5] [-5];
139 -3 〈 a, undef 〉 〈 b, undef 〉

〈 a + 1, undef 〉 〈 b + 1, undef 〉

〈 a + k – 1, undef 〉 〈 b + k – 1, undef 〉
140 -3 µ U { 〈 a + i, new ( d i .size )〉 } µ 1 U { 〈 a + i, b〉 }
where 〈 b, µ 1〉 = new ( d i .size, µ )

141 Fig 5.11 @A[0] γ ( A[0] )

2 int[10]) int[10];
10 delete ( a + i, d i . size ) delete ( a + i, d i . size, µ )
U { 〈 a + i, unused〉 }
11 µ U { 〈 a + i, unused〉 } µ U { 〈 a + i, unused〉 } otherwise
142 Fig 5.12 @p.x γ ( p.x )
@p.y γ ( p.y )
-11 b = @new ( k ) ( b, µ′ ) = new ( k, µ )
145 12 p->next p.next
151 Ex 5.1a µ σ
Ex 5.1b µ(µ( x)) µ(γ ( x))
Ex 5.1f µ σ
152 15 search binsearch
Page Line Change from: to:
17 search binsearch
20 int result; boolean result;
-7 [[2..7]; [2..7];
153 25 µ U { 〈 a + i, unused〉 } µ U { 〈 a + i, unused〉 } otherwise
172 23-24 int pop(STACK int pop(STACK*
void push(STACK void push(STACK*
173 9 int pop(STACK int pop(STACK*
12-15 if (!empty()) { if (!empty(*stack)) {
rslt=stack->val; rslt=(*stack)->val;
tmp=stack; tmp=*stack;
stack=stack->val; *stack=(*stack)->val;
20 void push(STACK stack, void push(STACK* stack,
21 STACK tmp = (STACK) STACK tmp;
malloc(sizeof(struct tmp=(STACK)malloc(sizeof(
Node)); struct Node));
23-24 tmp->next=stack; tmp->next=*stack;
stack=tmp; *stack=tmp;
27 if (!empty()) { if (!empty(*stack)) {
187 Fig 7.15 public intVal public int intVal
Fig 7.16 public isUndef( ) public boolean isUndef( )
{ returns true; } { return true; }
200 3 [2000] [2001]
201 3 Meyers Meyer
202 9 !empty(stack) !empty( )
208 -10 [λx (λx
209 4 ( abz ) abz
7 (λy…b ( (λy…b )
(λx…a ( (λx…a )
217 -7 (length ()) (length ‘())
218 24 (if (null? alist) () (if (null? alist) ‘()
219 3 (if (null? alist) () (if (null? alist) ‘()
Page Line Change from: to:
4-5 (if (equal? x) ... (if (equal? y) ...
(cons y ... (cons x ...
20 (if (null? alist) () (if (null? alist) ‘()
22-23 (if (equal? x) ... (if (equal? y) ...
(cons y ... (cons x ...
-3 (if (null? alist) () (if (null? alist) ‘()
222 21 equal equal?
22 equal equal?
-3 equal equal?
-2 equal equal?
225 9 gett get
226 18 (atom? expr) (not (list? expr))
232 26 (if (null? lst) () (if (null? lst) ‘()
233 4 (if (null? lst) () (if (null? lst) ‘()
233 24 [Haskell 1999] [Thompson 1999]
245 3 Block Block BlockType
9 Block (1st occurrence) Blocktype
Block (2nd occurrence) Blocktype deriving (Show)

248 Ex 8.1c ( λv ⋅ ( λw ⋅ w ) ( ( λx ⋅ x )y ( λz ⋅ z ) ) ) ( ( λv ⋅ ( λw ⋅ w ) ) ( ( λx ⋅ x ) ( y ( λz ⋅ z ) ) ) )
249 Ex 8.12 nx
n–1
nu
n–1

250 Ex 8.25 unary operator not Jay unary operator "!"

Ex 8.26 eval("+" y 2)... eval(Binary "+" (Var y)
(Lit (Intval 2)))...
251 Ex 8.30 Rewrite the... Haskell lists. Give a complete... Haskell recur-
sive data types.
Ex 8.31 Rewrite the... Haskell lists. Give a complete... Haskell recur-
sive data types.
257 19 only if if
283 -11 fib(0, 1). fib(0, 0).
 Page Line Change from: to:
-8 8th 9th
-6 Answer = 8 Answer = 9
-4 ? - fib(8, Answer). ? - fib(9, Answer).
284 5 fib(0, 1). fib(0, 0).
8 Answer = 8 Answer = 9
285 Ex 9.10 nx
n–1
nu
n–1

287 -4 ... in Exercise 9.20 ... in Exercise 9.17

288 27 [c,b,d,a] [c,b,d,a], Answer
308 26 lastX, lastY Math.min(lastX, x),
Math.min(lastY, y)
330 Fig 11.3 in inn

4, 16, 17
331 -14 V(nonempty); signal(nonempty);
344 -2 Sleepy Sleeping
348 12 <w, 9> <w, 4>
361 12 } {
375 19-21 However, if ... disappears. (Delete this sentence.)
380 -8 However, in However, if
-5 Using the ... program. (Delete this sentence.)
387 2 choice = new Button(); choice = new Choice();

Additional Bibliography Entries

1. Carriero, Nicholas and David Gelernter. [1990]. How To Write Parallel Programs: A
First Course. MIT Press.
2. Cooper, James W. [2000]. Java Design Patterns: A Tutorial. Addison-Wesley.
3. Hoare, C. A. R. [1974]. Monitors: an operating system concept. Communications of
ACM, 17 (October 1974), pp. 549-557.
4. Horstmann, Cay S. [1995]. Mastering Object-Oriented Design in C++. John Wiley.
5. Liskov, B. H. and J. Guttag [2001]. Program Development in Java. Addison-Wesley.
6. Perry, Jo Ellen and Harold D. Levin [1996]. An Introduction to Object-Oriented
Design in C++. Addison-Wesley.
7. Pountain, Dick [1995]. Constraint logic programming. Byte, 20, 2, pp. 159-160.
8. Thompson, Simon [1999]. Haskell: The Craft of Functional Programming. Addison-
Wesley.