Errata for Foundations of Object-Oriented Languages: Types and Semantics Special thanks to those who have pointed out the errors below. If you find an error not listed here, please e-mail kim@cs.williams.edu so that I can update this list. Page 28, Paragraph beginning "Let us compare...", second sentence at end of first line begins "message..." it should be "Message..." Page 28, 2nd line of 3rd full paragraph: Drop "s" from "allows". Page 32, next to last line of 1st paragraph of section 2.6: Add "names and" between "include the" and "types". Page 44, line 5 from bottom, "node setNext(newNode)" should be " node setNext(new Node)" Page 46, Paragraph beginning "invariant type systems...", first word should be "Invariant". Page 47, Figure 3.6: "class ColorCircleClass..." should be "inherits CircleClass" rather than "inherits Circle". Page 80, 2nd paragraph of 5.1.4: the record name should be "PersonType", not PersonInfo. Page 85, 3rd full paragraph: Drop "there can be" from 5th line Page 89: 2nd line of 4th paragraph: Drop "do" before "careful". Page 91, bottom of page: class ColorRect should inherit from Rect, that is, it should read: class ColorRect inherits Rect { Page 98, 5th line from bottom, replace "but" with "and". Page 102, 4th line of 2nd full paragraph: "This" should be "Thus". Page 104: Stein Krogdahl has pointed out to me that some of my history of Simula 67 was off. Simula 1 was designed to support discrete simulation, but Simula 67 was designed as a general purpose language. Also Simula 67 supported the same kind of virtual procedures as later languages, and this was taken over fairly directly in C++, for example. Page 106: function register(s:S) should have parameter "o:O" not "s:S". Page 107, figure 7.3: Class WindowObserverClass should inherit ObserverClass and WindowSubjectClass should inherit SubjectClass. Page 107, 3rd line of class WindowSubjectClass, replace "Event" by "WindowEvent". Page 110, line 3: "shown" should be "show". Page 111, 4th paragraph, line 3: "results" should be "result". Page 124. Add footnote that -> is right associative and application is left associative. I.e., A -> B -> C = A -> (B -> C) while M N P = (M N) P. Page 124, 2nd line of paragraph 4, add "in function definitions" after "abstraction". Page 125, line 9: "type s" should be "types" (no space). page 128, 2nd full paragraph: Second occurrence of substitution in the margin can be removed. The second italicized occurrence in the text of that paragraph should be regular roman font. Page 129, paragraph 6, line 1: "(4)" should be "(5)". Page 130, formulas on lines 1, 2, 7, 8, plus formula to right of = in line labeled (5'): Insert open parenthesis immediately after "." that follows the lambda. Page 130, 3rd full paragraph, 2nd line: "alpha convert" should be "alpha-convert". Page 130. "Eta" rule should be restricted to the case where x is not free in M. Similarly for the eta rule on page 139. Page 131, 2nd full paragraph, line 1: The italic "dred" is supposed to be a Tex macro with a double arrow and delta as shown 3 lines below. Page 131, 3rd displayed formula: A left parenthesis after the M is missing. It should read "M((plus 17)17)" with all occurrences of plus and 17 underlined. Page 132, section 8.2 heading: replace pairs by tuples. Page 133, line 8, replace dred by a double barbed arrow with a "delta" on top (as in the displayed formula 3 lines down). Page 133, last line of 4th paragraph, insert "first component of the" after "47 into the". Page 133 line 5th from bottom: replace "one is added.." by "doubles the value". Page 136, Constant rule should have "c: C", not "c: N". Page 139, Rule \sigma, replace "inj" by "in". Rule "false", final result after arrows should be "N", not "M". Rule \eta needs to be restricted as with the rule on page 130. Page 141, line 11: Replace "pairs" by "tuples". Page 142, line 6: Replace "kind s" by "kinds". Page 143, 3rd full paragraph. In the two sentences that start with "kind" the 'k' should be upper-case. Page 143, full paragraph 4, line 2: Add a space beween "*" and "to". Page 147, line 2 and TypeLet rule: "[nu^\kappa / mu]" should be "[mu / nu^\kappa]". Page 147, 3rd and 4th displayed formulas: Add parentheses around "pi beta" and "pi nu". Page 149, 3rd line of 4th paragraph: Start sentence "The ..." with capital "T". Page 151: Add a footnote clarifying that a congruence relation is an equivalence relation (reflexive, symmetric, and transitive) that allows substitutions of congruent terms inside expressions. Page 157, Definition 9.4.1, 2nd line: Replace subscript "rr" by subscript "<:". Page 159, Rules BdPoly and BdExist. Replace "w" by "v" in both hypotheses. Page 160, Rule ConstructorApp<:. The kind of "nu" should be "kappa" not "kappa' ". As written the constructor application does not make sense. Page 161, 3rd from last line. The type of m should be S -> Boolean, not S' -> Boolean. Page 175, Figure 10.2, line 2: Erase "Ref" and "ref". As a result the 2nd and 3rd paragraphs on page 174 no longer are relevant for this example. Instead it would be useful to add a discussion that instance variables declared and initialized in the instance variable section to have type T and initial value v, will be used as having type Ref T in the methods. Moreover, when an object is created, the initial value of the corresponding instance variable will be ref v. The declaration in the class should not have the "ref"s because only the initial value of the variable is provided there, not a reference to that value. Page 175, Figure 10.2: In the set and bump methods, the lines before the return statement are terminated by ";". According to the grammar on page 177, those semicolons should not be there because ";" is a statement separator, not terminator. This (inconsequential) error occurs in several other examples as well. It could be fixed by enriching the grammar to allow the placement of an empty statement before the "return" clause. Page 179: Add "nop" to the list of expressions so that "return nop" is legal. Also, change the syntax of Stmt so that E' := E is a valid statement. This allows the statement self.x := ... to be legal. The type checking rule Assn in Figure 10.10 on page 194 stays the same (aside from replacing id by E'). The translation of SOOL to /\^P_sub in Figure 11.3 on page 211 changes only by also requiring a translation of the left-hand side of the assignment. In the text I tried to finesse the difference between methods returning values and those that were used as statements by writing those methods so that they returned nop. I am no longer convinced that is a good solution. In particular, there are difficulties in that those statement methods are not listed as part of Stmt in Definition 10.2.2. I would now change this as follows: Add to Definition 10.2.2: PBlk \in PBlock ::= TDs CDs {S} S \in Stmt ::= ... (as before) ... | procedure (id_1: T_1,...,id_n: T_n) is PBlk We now must add new type-checking and semantic rules for these terms, though their form will be obvious. We+++ would also have to add new cases to the proofs of correctness, though again these would be very straightforward. Page 188, TypeDef rule of Figure 10.7: The restriction on the rule should be "t not appear in C or T" to match the restriction on type constraint systems in Definition 10.2.4, clause 2. Page 188, line 6 of text: Replace "Const" by "Constant" Page 191, line 4: Replace <: by :>. That is, ObjectType M should be a subtype of ObjectType M' rather than the reverse. Page 191, 3rd full paragraph: Drop "s" from "rules". Page 192, rule "Type Abbrev": "T" in "C(T)" should be teletype, not italics. Page 196, line 15: Add "type and" before "constant definitions". Page 198, 2 lines before displayed formula with "self.x": Replace "Assignment" by "Assn". Page 203, lines 3 and 4 from bottom: Replace ":=" by "=" in all parts of the definitions of inst and inst^ref. Page 205, last full paragraph: Both occurrences of methfun(o) should be replaced by methfun(inst). Page 206, 4th line from bottom: Drop extra ")" from end of closeobj's type. Page 209, Fig 11.2, 4th rule. Remove "Ref" from type of "val E" and add it to type of "E" to make it "Ref T". Page 209, Fig. 11.2: in 7th from last line, add subscript "i" to ".m" at end of line. Similarly in 4th from last line, add subscript "i" to ".m" at end of line. In 2nd to last line, add subscript "k" to ".l" at end of line. Page 211, line 4 of text: Add space after "nop" Page 211, last line "set(7:Command)]" should be "set(7):Command]". Page 214, paragraph 2: Both occurrences of "methfun'" in teletype font should be in italics. Also replace both occurrences of "inst" by "inst'". (The use of "inst" wasn't wrong, but it is easier to understand with both replaced by "inst'". Page 217, lines 3 and 4: "i" subscripts should be "1". Also in both definitions of "methfun'" on that page, add a ")" before |}. Page 219. next to last line: "IV ref= TC[IV ref sup]" should be "IV ref= TC[IV ref]" Page 222, line 3, "VisObjectType(IV ref sub, M sup)" should be "VisObjectType(IV ref, M)" Page 232, last line: In "IVR' <: Tc[IV^ref]", add subscript of "sup" to "IV^ref". Page 235, 4th translation, fix in same way as error on page 209. Page 235, "Block" rule: "E1:T" should read "E1:U1", "Ek:T" should read "Ek:Uk" Page 235, rules 10, 11, 12: Add subscript "i" to ".m" in rules 10 and 11, and add subscript "k" to "l" in rule 12. (See errata for page 209.) Page 236, line 9 from the bottom of Figure 12.8, close should have type SelfType -> ObjectType M' (i.e., add " ' " to last M. Page 243, 3rd paragraph of proof of 13.1.9: The last "Tc[S]" should be "Tc[T]". page 244, line 11: "E:S" should be in teletype font, not italics. Page 244, line 8 from bottom: "Tc[S'] <: Tc[S]" should be "Tc[S] <: Tc[T]". Page 254: middle of page "Tc[E <=m]" needs a space between "<=" and "m" Page 254: 3rd line from bottom: end of line has an extra "|}" Page 257, 7th line from bottom: Drop "s" from "canonical derivations". Page 258, line 1 of section 3.3: "I" in "In" should be lower case. Page 266, line 4 of Figure 14.3: Replace "x" by "self.x". In line 8, add "self <=" before "get()" to obtain "self <= set(self <= get() + 1)". The parameter type of the set method in ClrCellClass should be Integer rather than int. Page 272, line 3 of section 14.4: Drop the "ly" from "similarly". Page 274, line 7: "ObjectType VM" should be "ObjectType VM'" (missing a quote). Page 280, line 7, In definition of c^2, replace superscripts "1" by "2". Page 280, end of Figure 14.10: Add the definition of E' from the last 2 lines of Figure 14.9 on the previous page. Page 293, lines 4th to 6th from bottom: Replace all occurrences of "T" by "t". Also line 6th from bottom: Make "send" into "sends". Page 295, 8th line from bottom: Add an extra "}" before ";". Page 297, Figure 15.5, line 1: Erase superscript of "X" in 2 occurrences on right side of definition. Page 297, Figure 15.5, line 3: Define C' = C U {t <: T} Page 307, 2nd line of Fig. 16.4: Reverse the occurrences of nil and MyType Page 313, line 9: Add ")" before "Thus if". Page 315, Subclass rule : In 2nd and 3rd lines of hypothesis (type-checking) inst and meth), replace "MyType" in type by "MT". Page 322, line 7: definition of type of closeobj has an extra right parenthesis before "->" (and some minor font problems with parentheses). Page 322, line 16: The type expression after "SelfType is interpreted ..." also has an extra right parenthesis at the end. Page 324, lines 8-11: Italicized versions of MyType and MyType' should have been italicized MT and MT'. Page 328, Formula 16.1, extra parenthesis from previous error should be added to the end of the type expression. Page 333: Definition 17.2.1: Add to the end of the first sentence the phrase "generalized type constructor constraints". Page 333, line 6 of Definition 17.2.1: Replace "A is defined as follows:" by "A generalized type constructor constraint system is defined as follows:". Page 335, last word of paragraph 3 should be "PMOOL" rather than "PSOOL". Page 337: line 7, replace "eq" by "equal". Page 337: in the definition of add, replace first occurrence of "ge(" by "greaterThan(" and second occurrence of "ge(" by "lessThan".. Page 337, lines 7 and 8 of method add: Insert space before "<=". Page 338, 1st line: Replace "StringType" by "StringMT". Page 343, line after translation of "function..." add definition of E' = E U {id_1: T_1, ..., id_n: T_n} where U represents union. Page 343, translation of Block: Add small "delta" over first "=". Pages 344 & 345: Theorem 17.5.1, 17.5.2, and 17.5.3 (and line two above 17.5.3) all should refer to PMOOL rather than SOOL. Page 351, line 11: change "uses" to "use". Page 359, Subclass rule: Delete last hypothesis of rule, and change 4th bulletted item after the rule to read: The type of l sub_{i_j} in M_{sub}(MT) is the same as in M_{sup}(MT). (Justification: Because this is the language without subtyping, no changes of method types are allowed in subclasses.) Page 364, line 8: "language" should be "languages". Page 364, next to last paragraph. The reference to the paper by Bono and Bugliesi should have a bibliography entry with the following information: @article( BonoBug,author={V. Bono and M. Bugliesi}, title="Matching for the Lambda Calculus of Objects", journal="Theor. Computer Science", volume="212", year="1999", pages="101-140") Last updated: December 8, 2004.