Kenneth C Louden_ Kenneth Alfred Lambert - Programming languages_ principles and practice-Course Technology_Cengage Learning (2011)

Index A limited private type, 528 algebraic notation, 6 multidimensional arrays, 343–344 algebraic specification, 493 absolute values, 14 named scopes, 279 abstract classes, 151, 158, 170 name equivalence, 356–357 constants, 496 abstract data type. See ADT (abstract data type) nested procedures, 465–466 semantics, 535 abstractions, 6, 8–14, 144 numeric types, 351 sort-signature terminology, 533 abstract machine, 547 operator overloading, 285–287, 364 algebras, 558 abstract syntax, 216, 546 operators, 31 Algol60, 7, 142, 181 abstract syntax trees, 213–216 overloading, 194, 282 blocks, 262, 308, 402 access chaining, 468 packages, 10, 193, 263, 380, 509–515, 529 goals, 26 access links, 467–468 package specification, 380–381, 510, 511 pass by name, 410, 455 accessor methods, 165 parallel matrix multiplication, 621–622 stack-based environment, 308 Access-type Lifetime Rule, 470, 472 parameter communication, 458 structural equivalence, 343 access types, 299, 351 parse trees, 313 structured control, 402 activated, 448 pointers, 346, 511 syntax, 204 activation, 12, 292, 404 procedures, 12–13, 446 Algol68 real types, 351 blocks, 402 procedures, 459–472 reserved words, 236 bracketing keywords, 413 activation records, 292, 445, 448–449, 460, scalar types, 351 orthogonality, 32–33 scope, 265–267 structural equivalence, 343 462, 464, 471 short-circuit Boolean operators, 407 ALGOL (ALGOrithmic Language), 6–7, 26, 262 actual parameters, 13, 403, 450 static allocation, 289 Algol-like language, 309, 332 Ada, 7 statically typed, 39 ALGOrithmic Language. See ALGOL (ALGOrithmic subranges, 333–334, 362–363 Access-type Lifetime Rule, 472 subtypes, 339 Language) access types, 299, 351 symbolic constant, 432 algorithmic logic and Horn clauses, 129–130 aliases and subtypes rule, 357 symbol table, 280 algorithms and logic programming systems, 126 arrays, 342–343 syntax analysis, 313 aliases, 454 assignment operator (:=), 147 task rendezvous, 616–621 automatic garbage collection, 309 tasks, 14, 594, 611–612 for argument, 452 blocks, 262, 402 termination points, 418 assignment by sharing, 306 BNFs (Backus-Naur forms), 204 try-catch block, 428 data types, 355 bounded buffer as task, 619–620 type checking, 360 pointer variables, 304–306 bounded buffer problem, 613–615 type system, 331 semantics, 303–306 Cartesian products, 335 variable declarations, 268 side effects, 305 case statement, 415–416 variant record, 337 allocation, 197, 289–297 casts, 365–355, 366 while-loop, 417 alpha-conversion, 93 composite types, 351 Ada95, 608 ambiguity, 216–220 constant declaration, 302 Access-type Lifetime Rule, 470 ambiguous call, 283 constrained parameterization, 529 “address-of” operator, 299 ambiguous grammars, 217–218 dangling references, 307, 472 concurrency and monitors, 611–615 American National Standards Institute. See ANSI definitions, 257 data types, 299 dynamic allocation, 289 function parameters and types, 345 (American National Standards Institute) entry/accept mechanism, 617 object-oriented mechanisms, 193 Amoeba, 38 enumerated types, 332–333 procedures creating another procedure, and-parallelism, 622, 624–625 erroneous programs, 458 and special form, 77 exception handlers, 428, 429 471–472 Annotated Reference Manual. See ARM exceptions, 426, 427, 470 protected objects, 612 explicit conversions, 365 Ada83 and rendezvous, 616 (Annotated Reference Manual) (Ellis and explicitly parameterized functions, 380 ad hoc polymorphism, 194 Stroustrup) explicitly parameterized polymorphic ADT (abstract data type), 10, 492 anonymous functions, 74, 83 algebraic specification, 494–498 anonymous pointer type, 366 functions, 381–382 complex data type, 494 anonymous types, 330, 354 floating-point operations, 327 implementations, 497 anonymous union, 339 for-loop, 419 mathematics, 532–536 ANSI (American National Standards Institute), 16 function overloading, 284–285 mechanisms, 143, 498–500, 524–532 API (application programming interface), 10 functions, 446 model for specification, 532 APL and dynamic scoping, 277 generic packages, 194, 512–514 modules, 500–502 appending lists, 120 generic unit, 380 object-oriented programming, 493 append operation, 59, 60, 119 heap allocation, 295–296 semaphores, 605 application frameworks, 143–144 identifiers, 205, 236 signatures, 494, 533 application of expressions, 90–91 implicit conversions, 364, 365 sorts, 532–533 applicative order evaluation, 53, 404, 409 index set, 340 syntactic specification, 494 approximation, 573 instance variables, 195–196 arguments, 13, 403 integer types, 351 procedures, 445 lexical addresses, 262 thunks, 456 library I/O functions, 515 arithmetic and Prolog, 117–118 C7729_index.indd 647 03/01/11 10:47 AM

648 Index arithmetic operators in ML (MetaLanguage), 66 Backus, John, 6, 204 built-in arithmetic functions, 69 ARM (Annotated Reference Manual) (Ellis and Backus-Naur forms. See BNFs (Backus-Naur forms) built-in collections in imperative languages, 157 base classes, 181 built-in operators, overloading, 287 Stroustrup), 37 BASIC and goto statements, 420 Burstall, Rod, 65 Armstrong, Joe, 626 basic types, 350 busy-wait, 608 array-based queue class, 160 BCPL and abstractions, 35 byte code, 18 array constructor, 330 begin special form, 57 array data structure, 7 behaviors, 145 C arrays, 9, 330, 340–345 beta-abstraction, 92 beta-conversion, 92 C, 263 component type, 340 beta-reductions, 92, 94 address of operator (&), 298, 307 functional languages, 344 binary arithmetic operators, 66 ADT (abstract data types), 502–506 index type, 340 binary messages, 147 anonymous pointer type, 366 length, 341 binary operator, 403 arrays, 340–341, 347, 452 multidimensional, 343–344 binary search trees, 60, 73, 347 attributes, 257 printing contents, 149–150 binding list, 54 basic types, 350 unconstrained, 342 bindings, 257–260 blocks, 402 array types, 340–345, 384 BNFs (Backus-Naur forms), 204, 221 assemblers, 5, 18 scope, 263–265 Boolean operators, 407 assembly language, 4–6 binding times, 258–259 Cartesian products, 335 assignment Bison, 224, 233 casts, 365–366 denotational semantics, 561–563 blocked, 583 compilers and static type checking, 359 Java, 300 blocks, 148–149, 260–269 compound statements, 261 operational semantics, 551–553 constants, 302 programming languages, 299 activated, 448 dangling references, 306–307 return value, 32 allocating and deallocating space for, 291–292 data allocation strategy, 348 assignment by cloning, 299 block-structured languages, 447–448 data types, 277, 328 assignment by sharing, 299–300, 306 functions, 444 declaration before use rule, 264 assignment compatibility, 361 linked lists, 473–474 declarations, 261 assignment statements, 298 procedures, 444 definitions, 257, 260 axiomatic semantics, 569–570 reference counting, 475–476 derived types, 350 associativity, 216–220 scope rules, 265–266 disambiguating rule, 412 asynchronous exceptions, 424 stack frame, 448 do-while statement, 417 atomically, 604 symbol table, 269 dynamic allocation, 289 atoms, 50, 51 block structure, 262 end of line token, 206 AT&T Bell Labs, 181 block-structured languages enumerated types, 332–333 attribute functions, 367 activations of procedure blocks, 462 explicit conversions, 365 attributes, 257–260 blocks, 447–448 expressions, 52, 53, 444 automatic allocation, 294, 296 garbage collection, 308 flexibility, 36 automatic conversions, 284 global variables, 289 floating-point division, 330 automatic deduction systems, 104 lexical scope, 292 floating types, 350 automatic garbage collection, 473 local variables, 289 for-loop, 418 automatic memory management, 473–475 scope, 62 functions, 31, 163, 293, 344–345, 446 automatic theorem provers, 104 stack-based runtime environment, 469 function variable, 303 axiomatic semantics, 17, 104, 543, 565–571 block variables, 148 garbage, 307–308 assignment statements, 569–570 BNF grammar function-definition, 221 global procedures, 472 axiomatic specification, 567 BNF-like form grammars, 233 global variables, 268 distributivity of conjunction or disjunction, 568 BNF notation, 209, 221 if statements, 16–17 if statements, 570 BNF rules implicit conversions, 366 law of monotonicity, 568 abstract syntax, 216 implicitly or explicitly binding, 260 law of the excluded miracle, 568 recursive set equations, 348 implicit types, 361 predicate transformer, 567 semantics, 543 incomplete type, 261 proofs of program correctness, 571–574 BNFs (Backus-Naur forms), 204, 208–213, 221, 257 index set, 340 sample language, 569–571 body, 109, 445 instance variables, 195–196 statement-lists, 569 Boole, George, 104 integer calculator based on grammar, 227–230 weakest assertion or precondition, 567 Boolean expressions, 77, 406–407 integer division, 330 while statements, 571 bottom-up algorithm, 233 integral types, 350 wp predicate transformer, 568–569 bottom-up parsers, 224, 233 load-time constants, 302 axiomatic specification, 567 bounded buffer class, 605–606 member declarations, 262–263 axioms, 105, 107, 494–495 bounded buffer problem, 588, 613–615 memory leaks, 34 equality, 495, 534 bound identifier, 570 multidimensional arrays, 343–344 error axioms, 496 bound occurrence, 91–92 naming types, 330 quotient algebra, 533 bound variables, 63 numeric types, 350 axiom systems, 534–535 box-and-circle diagram, 297, 304–305 overlapping types, 362 box and pointer notation, 58–59 parametric polymorphism, 506 B bracketing keywords, 413 parsing, 236 branch instructions, 11 pass by reference, 453 backing store, 172–173 Brinch-Hansen, Per, 608 pass by value, 452 backtracking in Curry, 132–133 Brooks, Fred, 27 backtracks, 120–123 C7729_index.indd 648 03/01/11 10:47 AM

Index 649 pointers, 33, 346, 348 functions, 31, 446 calling context, 283 portability, 36 generic collection, 184–186 calling environment, 449 procedures, 31, 444 global variables, 268 call unwinding, 431 prototypes, 445, 502–503 goals, 27, 36 Cartesian products, 335–336 recorded structures, 195 implicit conversions, 365–366 case analysis and Curry, 131 recursion, 348 incomplete type, 261 case expressions, 68, 407–408 recursive declarations, 268 index set, 340 case-statements, 414–416 recursive definition, 278–288 inheritance, 191, 194 casts, 365–366 reserved words, 236 inline functions, 191 Centrum voor Wiskunde en Informatica. See CWI scanners, 206, 207–208 instance variables, 181–184 scope, 264 integer type, 334 (Centrum voor Wiskunde en Informatica) short-circuit Boolean operators, 407 keywords, 332 Cfront compiler, 36–37 shorthand notation, 10 member functions, 181–184, 191 character arithmetic, 334 stack-based runtime environment, 33 memory leaks, 34 children processes, 591 statements, 444 methods, 181–184 Chomsky, Noam, 204 static allocation, 289 Microsoft Foundation Classes, 144 Church, Alonzo, 8, 90 storage, 473 multidimensional arrays, 343–344 Church-Rosser theorem, 94 storage class, 296 multiple inheritance, 190–191 circlearea function, 55, 63 structural equivalence, 343 name clashes, 506 classes, 10 switch statement, 414–415 namespaces, 193, 263, 279, 506–509 symbol table, 278 object-oriented constructs, 287 abstract, 170 syntax diagrams, 223 object-oriented extension of C, 35–38 base classes, 181 termination points, 418 object-oriented features, 191 collection hierarchy, 158 type compatibility, 361 objects, 181, 182, 197 concrete, 170 type conversion, 364–365 operator overloading, 167, 183, 285–287, 364 declarations, 263, 269 type equivalence, 357–358 operators, 31 instance methods, 155 type nomenclature, 350 overloaded functions, 283 instance variables, 155 undiscriminated unions, 336 overloading, 194, 282 interfaces, 169–172 user-defined functions, 404–405 parametric polymorphism, 195 members, 181 variables, 32, 163, 299 pass by reference, 452–453 methods, 152–154 while-loop, 417 pass by value, 452 versus modules, 192–193 C++, 181–191 pointers, 346 namespaces as, 192–193 ambiguous call, 283 postfix & operator, 346 naming, 155 anonymous union, 339 private members, 181 object-oriented languages, 269, 336 arrays, 340, 347 protected members, 181 packages, 193 automatic conversions, 284 public members, 181 type checking, 192 base classes, 181 pure virtual declaration, 187–188 type constructors, 192 basic elements, 181–184 recursive declarations, 268 versus types, 192 Boolean operators, 407 reference arguments, 454 class loader, 509 casts, 365–366 references, 346 class messages, 146 Cfront compiler, 36–37 reserved words, 236 class method, 153–154, 164 classes, 181–184, 192–193, 336 retrospective, 37–38 class variables, 152 class mechanism, 193, 506 runtime environment, 197 clauses, 120 commercial implementation, 37 scope resolution operator (::), 182, 266, 267 client, 628–629 compatibility, 33, 36 semantics, 37 cloning objects, 306 compilation, 502–506 shared inheritance, 191 CLOS (Common Lisp Object System), 167, 194 complex addition, 194 short-circuit Boolean operators, 407 closed form, 450 constant declaration, 302 standard library modules, 427 closed-word assumption, 127 constructors, 182, 378, 528 statements, 444 closure, 451, 459 Cpre preprocessor, 37 static allocation, 289 CLU, 423, 520–521 data members, 181–184 statically typed, 39 coalescing, 474 data types, 283–284 static binding, 186–191 COBOL, 26–28, 343 declarations, 445 STL (Standard Template Library), 37 code definitions, 257, 260, 445 structs, 279 efficient, 28–30 dependencies, 529 structured if and for statements, 11 implementation of class, 192 derived classes, 181 template classes, 184–186 writability, 327 destructors, 182 templates, 194, 378–379, 506 code bloat, 376 dynamic allocation, 289, 293 type checking, 36, 359 code inlining, 404 dynamic binding, 186–191 type constructors, 192 code reuse, 150, 165 exception handlers, 427–429 undiscriminated unions, 336 coercions, 365 exceptions, 426 variables, 32, 183 collection classes and Smalltalk, 150 explicit conversions, 365 virtual functions, 186–191 collections, 157 explict parametric polymorphism, 378–380 while-loop, 417 built-in types, 159 expressions, 444 zero-overhead rule, 36 functional languages, 157 extensibility, 37 called, 13 hierarchy, 157–162 floating-point operations, 327 callee, 446 reference types, 169 for-loop, 418 caller, 446 type parameters, 168–169 column-major form, 344 COM (Common Object Model), 616 C7729_index.indd 649 03/01/11 10:47 AM

650 Index commits, 625 constructor chaining, 165 data types, 9, 326, 328–331 Common Lisp, 50 constructors, 497 algebraic specification, 493 Algol-like language, 332 lexical scoping, 277 arrays, 330 aliases, 355 macros, 34 C++, 182, 378, 528 anonymous, 330 statically scoped, 62–63 Java, 165, 182, 197, 378 characteristics, 492 Common Lisp Object System. See CLOS types, 346–349 versus classes, 192 variable initialization, 183 comparing, 70, 331 (Common Lisp Object System) consumer threads, 601 compatibility, 361 Common Object Model. See COM (Common context, 211 complex, 330 context-free grammar, 204, 208–213, constructors, 330, 335–349 Object Model) conversions, 283–284, 364–367 communicates, 449 235–236, 543 defining, 10 Communicating Sequential Processes language continue call, 609 dynamically allocating space, 349 continue operations, 609–610 dynamic scoping, 277 framework. See CSP (Communicating continue statement, 417 encapsulation, 493 Sequential Processes) language framework control, 425 environment, 349 communication problem, 585–586 explicit, 327 comparison operators basic abstractions, 10 implicit, 361–362 abstract classes, 151 exception handlers, 430–432 information hiding, 493 ordinal types, 334 operational semantics, 553–554 lists, 67 compatible types, 361 reduction rules, 553–554 mathematical concept, 493 compiled languages, 289 structured abstractions, 11–14 mechanism for constructing, 493 compiler-compilers, 224, 232 unit abstractions, 14 modifiability, 493 compilers, 7, 18–19, 547 control abstraction, 8 modules, 524, 529–531 basis for, 36 control facilities, 616 names, 330 dynamic type checking, 359 control information, 129–131 overlapping, 362–363 options, 589 control link, 462 recursive, 73 compile-time constants, 301–302 control mechanisms, 423 reusability, 493 complete, 534, 543 control problem, 108 security, 493 complex data types, 330, 494–495 control statements as set, 329 complex numbers, 494 denotational semantics, 563–564 shared operations, 363–364 components, 10 Smalltalk, 148–149 simple types, 332–334 component selector operation, 335 control structures, 122–126, 326 static binding, 277 component types, 340 conversion function, 69 synonyms, 73 composite types, 351 copy-in, 454 union, 336–339 composition, 49 copy-out, 454 user-defined, 72, 73, 330–331 compound statements, 261 copy-restore, 454 values, 55, 65 computational paradigms, 15 correctness rules and semantics, 360 computers Cpre preprocessor, 36–37 deadlock, 585–586 logic, 104 C programs and symbol table structure, 269–270 declaration equivalence, 358 multicore architectures, 7–8 critical region, 604 declarations, 9, 445 concatenation and regular expressions, 206 CSP (Communicating Sequential Processes) concatenation (++) operator, 82 accessibility, 266–268 concrete classes, 150–151, 158, 170 language framework, 616 Ada packages, 263 concrete syntax, 216 curried, 75–76 attributes, 257–258 concurrency, 611–615, 626 Curry, 131–134 blocks, 261–262 concurrent programming, 583 Curry, Haskell B., 75, 80, 131 classes, 263 cond form, 54 cut operator, 124–126 constructing environment, 289 conditional expressions, 54 CWI (Centrum voor Wiskunde en Informatica), 38 Java packages, 263 conditional statements, 411–416 C with Classes, 36 keyword modifiers, 268 conditions, 132–133, 618 language constructs, 261 condition variables, 609 D local, 261 connectives, 105, 110 member declarations, 262–263 consistent, 534, 543 daemons, 596 modules, 263 cons operator, 60, 82 Dahl, Ole-Johan, 142 namespaces, 263 constant procedure value, 447 dangling-else problem, 412–413 nested blocks, 266 constants, 105, 107, 205, 300–303 dangling references, 303–307, 470 nonlocal, 261 algebraic specification, 496 data, 8–10, 326 order within class, 269 compile-time, 301–302 recursive, 268 dynamic, 301–302 extension, 143 scope, 263–270 load-time, 301 finitude, 326 self-referential, 268 manifest, 301 data abstraction, 8 tasks, 263 names, 301 data constructors, 73, 338 type expressions, 354 static, 301–302 data encapsulation, 165 type information, 386–388 symbolic, 301 data entities, 326 declarative programming, 126 values are functions, 302–303 data keyword, 83 declarative style, 131 value semantics, 301 data members, 181–184 dedicated processors, 7 constrained parameterization, 529 data structures, 9, 492 deductive databases, 108 constrained parametric polymorphism, 372 data, 326 constructed lists, 120 naming, 9 Scheme, 57–60 data type queue, parameterized, 496 C7729_index.indd 650 03/01/11 10:47 AM

Index 651 definite clause grammars, 110 grammar rules, 232 runtime overhead, 431–432 definition, 445 left recursion removal, 226 termination model, 431 definitional interpreters, 547 Scheme, 51 exceptions, 423–427 definitional translator, 19 TinyAda, 237–239 propagating, 430 delayed evaluation, 54, 77–81, 93, 408, 455–458 Edinburgh LCF (Logic for Computable Functions) raising, 430, 477 Delay operation, 604, 609 executable specification, 555 delay special form, 78 system, 65 executing, 583 De Morgan, Augustus, 104 Edinburgh Prolog, 115 execution efficiency, 327 denotational semantics, 17, 542, 556–565 efficiency of execution, 27 execution model, 459 Eiffel, 532 existential quantifier, 106 assignment, 561–563 else clause, 54 existential type, 532 control statements, 563–564 empty environments, 545 explicit, 423 environments, 561–563 empty list, 67, 70 conversions, 365 implementing, 564–565 encapsulation, 144, 493, 501 exception testing, 425 integer arithmetic expressions, 560–561 “The End of History and the Last Programming pointer references, 295 semantic domains, 556, 558 polymorphism, 376–382 semantic functions, 559 Language” (Gabriel), 20 type information, 367 syntactic domains, 556, 558 entries explicitly binding, 260 dereferenced, 346 explicitly constrained parametric polymorphism, 382 dereferenced variables, 293, 361 entry barrier, 612–613 explicitly parameterized polymorphic data types, derivations, 209–210, 215–218 tasks, 616–617 derived classes, 181 entry/accept mechanism, 617 377–378 derived types, 350 entry barrier, 612–613 explicitly parameterized polymorphic functions, design criteria, 27–33 enumerated types, 332 design tool, 327 enumerations, 332, 338 381–382 destructors, 182 enumeration type, 384, 387 explicit parametric polymorphism, 376–377 Digitalk, 145 environments, 260, 289–297, 447 explict parametric polymorphism, 372, 378–380 Dijkstra, E. W., 411, 421, 604, 616 data types, 349 expression languages, 402 disambiguating rule, 218, 412 denotational semantics, 561–563 expressions, 402 discrete types, 351 exception handling, 477–478 discriminated unions, 336 fully dynamic, 469–472 control statements, 407–408 discriminator, 336 fully static, 459–461 forcing left-to-right execution, 57 distributed applications, 631 heap, 294 fully parenthesized, 404 distributed-memory system, 585–586 objects, 292 functional languages, 402 distributed system, 582 operational semantics, 551–553 identifiers, 403 distributivity of conjunction or disjunction, 568 procedures, 459–472 lazy evaluation, 80–81 documentation, 16 reduction rules, 551–553 literals, 403 domains, 47 sample language, 544–545 nonfunctional languages, 402 domain theory, 558 stack, 294 normal order of evaluation, 409–410 dot notation, 167 stack-based runtime, 462–469 operands, 388–389, 403 double-dispatch problem, 194 ep (environment pointer), 462–464 operators, 403 double-ended queue, 143 equality, 118–119, 495 polymorphic, 371 do-while statement, 417 equality types, 70 programming languages, 402 Dynabook Project, 142, 144 equations, 132, 494–497 rules for evaluating, 404 dynamic allocation, 293–294, 296 equivalence relation, 534 semantics, 402 dynamically computed procedures, 469–472 Ericsson, 626 sequence operator, 406 dynamically typed languages, 331 Erlang parallelism with message passing, 626–631 side effects, 402, 405–406 dynamic binding, 155, 176, 258 erroneous programs, 458 substitution rule, 409 member functions, 186–191 error axioms, 496 expression sequence, 71 methods, 196–197 eta-conversion, 93 expression statement, 444 dynamic constants, 301–302 eta-reduction, 93 expressiveness, 29 dynamic environment, 289, 449 Euclid extended BNF. See EBNF (extended BNF) dynamic link, 462 limiting aliasing, 305 extensibility, 38–39 dynamic memory management, 473–476 modules, 519–520 extensible languages, 34–35 dynamic scoping, 273, 467 simplicity and abstraction, 28 free variables and formal parameters, 63 Euclidian algorithm, 109, 118, 130 F symbol table, 274–277 evaluation rules, 51–53, 404 dynamic type checking, 55–56, 359 exception handlers, 423, 425, 427–429 fact function, 65–66, 68 dynamic typing, 145, 626 control, 430–432 factorial function, 56–57 pointers, 477 facts, 109 E scope, 429 fair scheduling, 608 try-catch blocks, 427–428 falls through, 415 EBNF rules exception handling, 423–432 FGHC (flat guarded Horn clauses), 625 if-statement, 411 control, 425 fields, 263 recursive-descent parser, 227 environments, 477–478 Fifth Generation Project, 104 syntax diagrams, 243–244 exception handlers, 423, 425, 427–429 filters, 80–81 top-level rule, 244 exceptions, 423, 425–427 final algebra, 535 functional mechanisms, 423 final semantics, 535 EBNFs (extended Backus-Naur forms), 204, object-oriented mechanisms, 423 finger typing, 39 220–224 resumption model, 431 finitude, 326 first-order predicate calculus, 105–109 C7729_index.indd 651 03/01/11 10:47 AM

652 Index fixed format language, 205 lambda form, 177 tail recursive, 56 fixed point, 94–95 lists, 344 type recognition, 56 flat guarded Horn clauses. See FGHC (flat map, 159 type specifier, 84 programs, 131 uncurried version, 76 guarded Horn clauses) safe union mechanism, 338 von Neumann concept, 13 flatten, 80–81 unification, 370 function types, 340–345 flexibility, 36 functional lazy languages, 81 functors, 515–518 floating-point division, 330 functional paradigm, 15 future, 624 floating types, 350 functional programming, 46 Follow sets, 232 assignment, 48–49 G force special form, 78 delayed evaluation, 54 for-each loop, 420 functional perspective, 131 Gabriel, Richard, 20 fork-join model, 592 generator-filter programming, 80 garbage, 303–309 fork-join parallelism, 597 lambda calculus, 90–95 garbage collection, 62, 145, 308–309, 472–473, for-loop, 173, 418–419 local state, 49 formal definition, 257 loops, 48 476 formal parameters, 445, 450 mathematics, 90–95 gcd function, 13, 49, 82, 303 formal semantics, 543 programs as functions, 47–50 generality, 30–31 recursion, 48–49 general-purpose programming languages, 26 axiomatic semantics, 565–571 static typing, 65–76 generational garbage collection, 476 denotational semantics, 556–565 variables, 48 generator-filter programming, 80 methods, 546 functional programs, 49 generators, 80–81 operational semantics, 547–556 function application, 47–48, 92 generic collections, 169, 184–186 sample small language, 543–547 function calls, 287 generic interfaces and classes, 194 FORmula TRANslation language. See FORTRAN function declaration, 65, 447 generic packages, 194, 512–514 function definitions, 47–48, 68 generic type variables, 375 (FORmula TRANslation language) function literal, 303 generic unit, 380 FORTH, 404 function overloading, 284–285 GIGI principle (garbage in, garbage out), 77 Fortran77, 420, 444 functions, 13–15, 105, 340–345, 403, 444, 612 global declaration, 266 FORTRAN (FORmula TRANslation language), 142 activations, 404 global environment, 449 anonymous, 74 global variables, 268 activation, 462 applicative order evaluation, 77 goal-oriented activity, 567 algebraic notation, 6 arguments, 75 goals, 26, 36, 108 calling procedures, 446 behavior, 85 Gödel, Kurt, 104 fully static environment, 459–461 body, 65 Goldberg, Adele, 144 functions, 446 bound variables, 63 Gosling, James, 162 multidimensional arrays, 343–344 calling, 66 goto controversy, 420–423 overloading, 282 closed form, 450 Graham, Paul, 20 pass by reference, 452, 454 closure, 451 grammar rules, 210, 220 procedures, 444, 446 composition, 49 static environment, 289 curried, 75–76 alternatives, 230–231 static storage allocation only, 29 declarations, 356 for declaration in EBNF, 232 structural equivalence, 343 defining, 47, 87 left factoring, 227 subroutines, 446 dependent variable, 47 recursive nature, 212 free algebra of terms, 533–534 domain, 47 set equation, 213 free-format language, 205 free variables, 63 special notation for, 221 free identifier, 570 functional languages, 444–445, 447 syntax diagrams, 222–224 free lists, 474 function parameters, 61 grammars, 16, 208–213 free occurrence, 91–92 higher-order, 13–14, 49, 61–62, 74–76 abstract syntax trees, 213–216 free variables, 63, 106 implementing methods as, 196 ambiguity, 216–220 fully curried, 76 independent variable, 47 associativity, 216–220 fully dynamic environment, 472 lists, 58 BNF-like form, 233 fully parenthesized, 404 naming, 65 context-free, 208–213 fully static environments, 459–461 nonstrict, 77 context-sensitive, 211 functional languages, 46 overloading names, 282 converting into parser, 230 arrays, 344 parameters, 61, 65, 450 disambiguating rule, 218 automatic garbage collection, 473 pass by name evaluation, 77–79 EBNFs, 220–224 collections, 157 polymorphic, 372–375 integer calculator based on, 227–230 constants, 301 prefix form, 403 left-associative, 218–219 delayed evaluation, 77–81, 455 primitive, 55 left-recursive rule, 219, 226 deterministic computation, 132 programs as, 47–50 metasymbols, 209 dynamic binding, 258 range, 47 parse trees, 213–216 exceptions, 425 recursive, 55, 74, 347 parsing techniques and tools, 224–235 expressions, 402 referential transparency, 49 precedence, 216–220 functions, 444–445, 447 return types, 31 right associative, 218–219 garbage collection, 308 return values, 74–75, 446 right-recursive rules, 219, 221 higher-order functions, 62 signatures, 86 start symbol, 209 if-else constructs, 125 syntax diagrams, 220–224 imperative constructs, 344 tokens, 224, 235–236 implicit pointers, 346 granularity, 592 integers, 326 C7729_index.indd 652 03/01/11 10:47 AM

Index 653 green threads, 595 explicitly parameterized polymorphic data subset types, 339 guarded do command, 417, 616 types, 377–378 vs. polymorphism, 194–195 guarded Horn clauses, 624–625 initial algebra, 534 guarded if statement, 411, 616 let-bound polymorphism, 375 initial semantics, 534 guards, 410–416, 625 occur-check, 375 inline functions, 191 simplifying type information, 371 inline member functions, 182 H type expression, 375 inlining, 404 Hoare, C. A. R., 27, 414, 608 inputLine function, 70–71 Hacker and Painters (Graham), 20 HOPE language, 65 inspectors, 497 handler stack maintenance, 478 Horn, Alfred, 109 instance definition, 86–87 handling exceptions, 477 Horn clauses, 109–111 instance messages, 146, 151 hardware interrupt, 583 algorithmic logic, 129–130 instance methods, 154–155 Haskell, 28 Euclid’s algorithm, 118 instance variables, 153 goal or lists of goals as, 112–113 Ada, 195–196 binding, 258 not expressing all of logic, 128–129 C, 195–196 class definition, 87 C++, 181–184 constants, 301 I classes, 155 default function definitions, 87 Java, 165 elements, 82–83 identifier role analysis, 312–315 Smalltalk, 152, 155 fully curried lazy language with overloading, identifiers, 205, 257, 382–383, 403 instantiated variables, 114 Institute of Electrical and Electronics Engineers. 81–89 attributes, 314 functions, 31 bound, 570 See IEEE (Institute of Electrical and heap allocation and deallocation, 295 free, 570 Electronics Engineers) Hindley-Milner type checking, 65 high-level languages, 312 integer arithmetic, 334 infinite lists, 84–85 roles, 312–313 integer arithmetic expressions instance definition, 86–87 type-compatible, 383 denotational semantics, 560–561 lambda calculus, 90 IEEE (Institute of Electrical and Electronics reduction rules, 548–551 lambda forms, 83 integer division, 330, 334 lazy evaluation, 80, 84–85, 410 Engineers), 326 integers, 326, 329 lists, 82, 84 IEEE 754 standard, 334 integral types, 350 modules, 10, 263 if-expressions, 54, 407–408 interfaces, 146, 193, 445 monads, 82 if form, 54, 77 class implementing, 169–172 overloaded functions, 86–90 if-statements, 410–414 Java, 167–168, 174–175, 177, 351 overloading, 194, 282 standards, 10 parameters, 133 axiomatic semantics, 570 static typing, 327 pattern matching, 82 dangling-else problem, 412–413 International Organization for Standardization. patterns, 84 disambiguating rule, 412 See ISO (International Organization for pointer manipulation, 295 imperative constructs, 344 Standardization) predefined functions, 82 imperative languages, 15, 46 interoperability, 10 predefined types, 87 atoms as identifiers, 50 interpreted languages prefix functions, 83 built-in collections, 157 dynamic scoping, 277 reverse function, 82 if-else constructs, 125 exceptions, 423 security, 33 loops, 56 interpreters, 18–19 signatures, 86 pointers, 348 attribute binding, 289 static type checking, 360 variables, 48 dynamic scoping, 277 strongly typed, 331 imperative programs and loops, 48–49 dynamic type checking, 359 syntax, 82 implicit, 361, 423 symbol table and environment, 289 tuples, 83 implicit conversions, 365, 366 intlist procedure, 80 type classes, 86–90 implicit dereferencing, 300 invocation, 12 type parameters, 168 implicitly binding, 260 ISO (International Organization for type synonyms, 83 implicitly constrained parametric polymorphism, 380 Standardization), 16 type variables, 83 implicit parametric polymorphism, 372 iteration, 11–12 unification, 120, 370 implicit types, 361–362 iterators, 12 user-defined data type, 89 incomplete type, 261, 505 backing store, 172–173 user-defined polymorphic types, 83 independence, 143–144, 534–535 for-each loop, 420 variables, 301 independent, 543 loops, 420 Haskell98, 81 independent variables, 47–48 polymorphic, 158 hd (head) operator, 67–68 indexed component references, 389–390 strings, 158 head, 109 index type, 340 header file, 502–503 inference rules, 107–108 J heap, 294–296, 473 infinite lists, 84–85 heavyweight processes, 583–584 infinite loops, 122, 124, 127, 129, 226 Java, 162–181, 608 higher-order functions, 13–14, 49, 61–62, 83, infix functions, 500 accessor methods, 165 infix operators, 66, 403–404 arrays, 341–342, 351 176–181 information hiding, 9–10, 144, 493, 501 assignment, 300, 361 high-level programming languages, 7 Ingalls, Daniel, 144 assignment by sharing, 306 inheritance, 150, 153 automatic conversions, 284 code, 27 object-oriented languages, 196–197, automatic garbage collection, 34, 309 identifiers, 312 Hindley-Milner type checking, 339–340, 362 repeated, 191 367–370 shared, 191 C7729_index.indd 653 03/01/11 10:47 AM

654 Index Java (cont.) numbers package, 165 lambda function, 78 backing store, 172–173 object instantiation, 163 language of the grammar, 211 basic elements, 163–167 objects, 163–167, 197, 452 language reference manual, 257 BNFs (Backus-Naur forms), 204 operators, 31 latent type checking, 55 Boolean operators, 407 output collection, 176 law of monotonicity, 568 bounded buffer example, 601–604 overlapping types, 362 law of the excluded miracle, 568 byte code, 18 overloaded operators, 167, 363–364 layout rule, 82 casts, 365 overloading, 194, 282 lazy evaluation, 80–81, 84–85, 131, 410, 455 classes, 163–167, 192, 263, 279, 351 packages, 10, 163, 167, 193, 279, 506–509 LC-3 assembly language, 5, 11 class loader, 509 pass by value, 452 least fixed point, 348 class method, 164 pointers, 33 least-fixed-point semantics, 95 cloning objects, 306 polymorphism, 167–175 least-fixed-point solution, 564 code dependencies, 509 portability, 162–163 left associative, 226 collection classes, 380 primitive types, 32–33, 163, 350–351 left-associative, 218–219, 221, 228 Collection interface, 168 private inner class, 171 left factoring, 227 collections, 32 processes, 14 leftmost derivation, 218 complex addition, 194 references, 163, 346 left recursion, 226 constants, 302 reference semantics, 166 left-recursive BNF grammar, 233 constructors, 165, 182, 197, 378 reference types, 32–33, 166, 169, 350–351 left-recursive rules, 219, 225–226 conversion functions, 367 reserved words, 236 legal programs, 331 daemons, 596 runtime garbage collection, 163 length, 341 dangling references, 307 scalar data types, 163 let-bound polymorphism, 375 data encapsulation, 165 shared data, 597–599 let form, 54–55, 64 deallocation routines, 197 short-circuit Boolean operators, 407 levels, 8, 262 default constructor, 165 shorthand notation, 10 LEX/Flex, 235 dot notation, 167 stacks, 170 lexical address, 262 do-while statement, 417 static allocation, 289 lexical environment, 467 dynamic allocation, 289 static binding, 175–176 lexical scope, 62–63, 264, 277, 467 explicit checks, 334 static constants, 302 lexical scoping rule, 449 explicit conversions, 365 static type checking, 181 lexical structures, 204–208 explicit dereferencing, 295 static typing, 175 lexics vs. syntax vs. semantics, 235–236 extensibility, 34 structural equivalence, 343 lifetimes, 289–297 fields, 263 Swing Toolkit, 10, 144 lifted domains, 561 filter method, 176–181 switch statement, 415 lightweight processes, 584 floating-point operations, 327, 330 temporary object, 167 limited private type, 528 for-loop, 418 threads, 14, 595–601 linked, 18 generic collections, 169, 184 try/catch exception-handling, 178 linked lists, 170–172, 473–474 generic interfaces and classes, 194 type compatibility, 361 linked nodes queues, 160–162 green threads, 595 type constructors, 351 LISP, 8, 28 heap allocation, 295 type equivalence, 358 higher-order functions, 176–181 type nomenclature, 350–351 and-parallelism, 622, 624 identifiers, 332 type parameters, 168 automatic garbage collection, 34 implicit conversions, 366 value semantics, 166 delayed evaluation, 54 implicit pointers, 346 variables, 163, 166 do loop, 34–35 index set, 340 while-loop, 173, 417 dynamic scoping, 50, 62, 277 inheritance, 167–175, 194 Java collection framework, 167–175 dynamic typing, 145 instance variables, 165 java.concurrent.locks package, 610–611 extensibility, 34–35 integers, 329–330, 334 java.lang package, 14, 163 fully parenthesized, 404 interfaces, 167–175, 177, 193, 351 Java packages, 263 functions, 444–445 interpreter, 162 java.util package, 163, 167 garbage collection, 145, 308 iterators, 12, 172–174, 178–179 javax.swing package, 10, 163 lambda calculus, 90 Java collection framework, 167–175 Jensen, J., 458 list data structure, 50 Java Virtual Machine (JVM), 162, 164 Jensen's device, 458 macros, 34 libraries, 38, 163, 167 jobs, 583 metacircular interpreter, 50 linked lists, 170 Johnson, Steve, 233 or-parallelism, 623 links, 172 JVM (Java Virtual Machine), 162, 164 packages, 10 Lock and Condition interfaces, 610 parallelism, 624 for loop, 173 K reference semantics, 300 loops, 12 static type-checking, 33 map method, 176–181 Kay, Alan, 144 uniform treatment of functions, 50 methods, 163–167, 263 keyword messages, 146–148 untyped languages, 331 method synchronization, 598 keywords, 52, 205, 332 variables, 33, 261 monitors, 609–610 Kowalski’s principle, 108 while loop, 34–35 multidimensional arrays, 343 list comprehensions, 84 name overloading, 288 L lists, 72 namespaces as classes, 193 appending, 59, 68, 120 native threads, 595 lambda abstraction, 90, 93 binary search tree, 57 lambda calculus, 8, 15, 90–95 box and pointer notation, 58–59 lambda expressions, 92–94 lambda forms, 54–55, 64, 83, 148, 177 C7729_index.indd 654 03/01/11 10:47 AM

Index 655 constructed, 120 imperative languages, 48–49, 56 directly accessing data, 196 data types, 67 iterators, 420 dynamic binding, 196–197 empty, 67 loop invariant, 573 formal semantics, 546 flatten, 80–81 restrictions, 419 header and comment, 152 functional languages, 344 sample language, 546 object-oriented languages, 195–196 functions, 58 sentinel-based, 422–423 synchronized and unsynchronized, 609 head, 58–59, 67–68, 119–120 structured exits, 422–423 Microsoft Foundation Classes, 144 infinite, 80, 84–85 terminating, 417–418 Milner, Robin, 65 lazy evaluation, 80 unstructured exits, 421–422 MIMD (multiple-instruction, multiple-data) linked lists, 170–172 l-value, 298, 361 recursive types, 347 systems, 584–585 reversing elements, 59 M Miranda, 81 same-fringe problem, 80–81 ML97, 65 with structure, 60 machine dependencies, 326 ML (MetaLanguage), 28, 65 tail, 58–59, 67–68, 119–120 machine independence, 7 tuple, 67 machine language, 3–5 ad hoc stream constructions, 80 literal array, 148 macros, 34 applicative order evaluation rule, 77 literals, 205, 301, 362, 403 Magnitude hierarchy, 150–157 arithmetic functions, 69 loaded, 18 mailboxes, 616, 630 arithmetic operators, 66 loader, 5 maintenance of free space, 473–475 array module, 344 load-time constants, 301 manifest constants, 301 assignment compatibility, 361 local declarations, 261 map function, 14, 61, 75, 83 binary arithmetic operators, 66 local scope, 296 maps, 13–14 binary search trees, 73–74 local symbol table, 278–279 binding, 258 local variable, 464 Erlang, 627 Boolean operators, 407 locations, 257 functional languages, 159 calling functions, 66 locks, 604 mark and sweep, 476 case construct, 416 logic, 104, 105–108 master, 619 constant, 303 logical expressions, 406–407 mathematical concept, 493 constraints, 69 logical inference rules, 548 mathematical function package, 500–501 conversion function, 69 logical statements, 104–106, 109 mathematical logic, 105 currying, 75–76 logical variables, 133–134, 626 mathematics data constructors, 73, 338 logic languages, 20, 108 ADT (abstract data type), 532–536 data structure, 72–74 programs, 131 functional programming, 90–95 data types, 72–74, 528 unification, 114, 371 independent variables, 48 elements, 65–72 logic paradigm, 15 lambda calculus, 90–95 empty list, 67 logic program, 108 parameters, 48 enumerated types, 332 logic programming, 46 principle of extensionality, 535–536 enumeration, 338 control information, 129–131 variables, 48 equality types, 70 first-order predicate calculus, 105 McCarthy, John, 8, 50, 277 evaluation rule, 66 functional perspective, 131 member declarations, 262–263 exception handlers, 428 Horn clauses, 109–111, 128–129 member functions, 181, 191, 336 exception handling, 429 logical variables, 133 dynamic binding, 186–191 exceptions, 426, 427 order of clauses, 122 inline, 182 explicit parametric polymorphism, 376–377 problems, 126–131 members, 181 expression sequence, 71 resolution, 111–115 memory, 260 fn reserved word, 74 specification activity, 126 compacted, 474–475 function composition, 75 unification, 111–115, 133 deallocating, 308, 473 function declaration, 65, 447 logic programming systems, 108 dynamic management, 473–476 function literal, 303 algorithmic control information, 130 free list, 474 functions, 71, 345 algorithms, 126 free space maintenance, 473–475 functors, 515–518, 530–531 breadth-first search, 122 heap, 473 fun reserved word, 65 closed-word assumption, 127 manual management, 473 heap allocation and deallocation, 295 control problem, 108 reclamation, 475–476 higher-order functions, 74–76 depth-first search, 122 wasted, 308 Hindley-Milner type checking, 65, 378 Horn clauses, 111, 112–113 message passing, 146, 588, 615–616 infix functions, 500 order clauses, 115 parallelism, 626–631 infix operators, 66 logic programs, 105–108 Message Passing Interface. See MPI (Message lambda calculus, 90 nonmonotonic reasoning, 128 lists, 66–67, 72 loop invariant, 573 Passing Interface) modules, 10, 263, 515–519 loops, 417–420 messages operators, 66 behavior, 419–420 overloading, 69 control and increment, 419 abstract classes, 151 parametric polymorphism, 65, 499 ensuring execution, 417 mutators, 146 pass by reference, 453 exiting, 420–423 receiver, 149 pointer manipulation, 295 functional programming, 48 selector, 146 polymorphic function, 69 guarded do, 417 metacircular interpreter, 50 safe union mechanism, 338 MetaLanguage. See ML (MetaLanguage) security, 33, 65 metalinguistic power, 63–64 short-circuit Boolean operators, 407 metasymbols, 209, 233 methods, 153–154, 336 C7729_index.indd 655 03/01/11 10:47 AM

656 Index ML (MetaLanguage) (cont.) multiply-typed values, 362–363 dynamic capabilities, 191 signatures, 515–518, 518 multiprocessor system, 582 exceptions, 425 special ADT mechanism, 498–500 multiprogramming, 582 garbage collection, 308 special forms, 77 mutators, 146 history, 142 static type checking, 360 mutual exclusion, 585, 608–609 implementation issues, 195–197 strings, 71 inheritance, 194–197, 339–340 structural equivalence, 343 N initialization, 197 structures, 70, 515–518 iterators, 12 syntactic sugar, 74 name capture problem, 92 methods, 195–196 tl (tail) operator, 67–68 name equivalence, 355–357, 383, 385 modules, 192–193 tuples, 72, 76, 336 name proliferation, 501 multi-dispatch problem, 194 type check expressions, 69 name resolution, 282–288 multimethods, 167, 194 type equivalence, 358 names, 257 objects, 195–196 types, 70 polymorphism, 194–195, 372 type variables, 194 associating to values, 54 runtime binding, 155 uncurried version of function, 76 attributes, 257–258 runtime environment, 191 unification, 120, 370 bound to attributes, 258–259 runtime penalty, 191 user-defined data types, 72, 73 bound to locations, 289 translator, 191 value constructors, 73 level number, 262 types, 192 values, 66 lexical address, 262 object-oriented paradigm, 15 variables, 298 offset, 262 object-oriented programming, 46, 142 wildcard pattern, 416 overloading, 287–288 ADT (abstract data types), 143, 493 wildcards, 68 namespaces, 279, 506–509 C++, 181–191 as classes, 192–193 code reuse and modifiability, 142 mnemonic symbols, 5 narrowing conversions, 365 encapsulation mechanisms, 144 mode declaration, 625 native threads, 595 independence, 143–144 models of computation, 8 natural numbers, 105 information-hiding mechanisms, 144 modification by extension, 143 natural semantics, 548 inheritance, 153, 362 Modula-2 Naur, Peter, 204 Java, 162–181 nested blocks, 266 polymorphism, 153 exported declarations, 522 nested procedures, 465–466, 468 reference semantics, 148 expressions not including function calls, 31 nested scopes, 310 Smalltalk, 144–162 modules, 521–524 nesting depth, 468 software reuse, 143–144 nested procedures, 465–466 nodes, 631 objects, 142, 195–196 subranges, 363 nondeterminism, 132–133 allocating, 197 Modula-3, 343 nonfunctional languages expressions, 402 behaviors, 145 modules, 10, 493 non-imperative languages and parallelism, 622–631 cloning, 306 ADT (abstract data type), 500–502 nonlocal declarations, 261 environment, 292 versus classes, 192–193 nonlocal references, 447–448 extent, 292 controlled scopes, 501 allocated statically, 465 implementation of, 195–196 data types, 524, 527–528 closure, 459 instantiation, 163 documenting dependencies, 502 scope rules, 447 interface, 146 earlier languages, 519–524 nonmonotonic reasoning, 128 lifetime, 292 implementations, 501 nonprocedure block, 449 message passing, 8 imported types, 529–531 nonstrict evaluation, 408 pointers, 292–293 instantiates, 520 nonstrict functions, 77, 94 properties, 145 libraries, 501 non-tail-recursive procedure, 60–61 wait-list, 599 name proliferation, 501 nonterminals, 210–211, 233 occam, 616 program decomposition, 501 derivation, 215 occur-check, 127, 375 semantics, 531–532 Follow sets, 232 offset, 262, 464 static entities, 524–527 nonterminal symbol, 244 one-dimensional arrays, 57 monads, 80, 82 normal order evaluation side effects, 410 opcode, 4 monitors, 588, 607–615 Norwegian Computing Center, 142 open conditions, 618 concurrency and, 611–615 notation, 116 operands, 388–389, 403 condition variables, 609 numbers as tokens, 235–236 operating systems java.concurrent.locks package, 610–611 numeric integer types, 334 integrating operation of processors, 586–587 mutual exclusion, 608–609 numeric types, 350–351 running programs in parallel, 591 synchronized objects, 609–610 Nygaard, Kristen, 142 operational semantics, 17, 542, 547–556 monomorphic, 372 abstract machine, 547 Moore’s Law, 7–8 O assignment, 551–553 most closely nested rule, 412 compilers, 547 most general assertion, 567 object identity, 167 control, 553–554 MPI (Message Passing Interface), 616 Objective-C, 192 definitional interpreters, 547 MPMD programming, 592 object-oriented languages, 15, 46 environments, 551–553 multidimensional arrays, 343–344 executable specification, 555 multi-dispatch problem, 194 allocation, 197 implementing, 555–556 Multilisp, 624 automatic garbage collection, 167, 473 logical inference rules, 548 multimethods, 167, 194 classes, 10, 192–193, 263, 269, 336 multiple inheritance, 190–191 conversion requirements, 366 design issues, 191–195 double-dispatch problem, 194 dynamic binding, 155, 196–197 C7729_index.indd 656 03/01/11 10:47 AM

Index 657 reduction machine, 547 distributed-memory system, 585–586 partial correctness, 574 reduction rules, 548–551 library of functions, 590–591 partial function, 47 operations MIMD (multiple-instruction, multiple-data) Pascal, 7 atomically, 604 extensions, 143 systems, 584–585 assignment operator (:=), 147 grouping, 206 procedure-level parallelism, 593–594 associating type with name, 328 redefinition, 143 process creation and destruction, 591–592 constants, 31 operator overloading processes, 583–584 declaration, 9 Ada, 286–287 shared-memory system, 585 declaration equivalence, 358 C++, 167, 285–286 SIMD (single-instruction, multiple-data) definitions, 257 Java, 167 disambiguating rule, 412 operators, 403 systems, 584–585 functions, 31 associativity, 403 statement-level parallelism, 593 gotos, 421 infix, 287, 403 parallel programming implicit types, 362 inline code, 403–404 bounded buffer problem, 588 nested procedures, 465–466 left-associative, 221, 228 message passing, 588, 615–621 pass by reference, 452–453 mix-fix form, 408 monitors, 588, 608–615 pass by value, 452 operands, 408 parallel matrix multiplication, 588 pointers restricted, 33 overloaded, 282, 363 producer-consumer problem, 588 predefined identifiers, 258–259 postfix, 403 program-level parallelism, 594–595 procedures, 31 precedence, 403 semaphores, 588, 604–608 procedure variables, 472 prefix, 403 threads, 588, 595–604 reference arguments, 454 right-associative, 221 parameter declarations, 479–480 strongly typed, 331 ternary, 408 parameter list, 450 subranges, 363 ordered, 332 parameter modes, 390, 479–481 symbolic constant, 432 ordinal types, 334 parameter-passing mechanisms symbol table, 278 or-parallelism, 623–624 delayed evaluation, 455–458 type equivalence, 358 or special form, 77 versus parameter specification, 458 pass by name, 77–79, 410, 455–458 orthogonal, 30–31 pass by name, 455–458 pass by need, 78 orthogonality, 31–32 pass by reference, 452–454 pass by reference, 452–454 output function, 70–71 pass by result, 454 pass by result, 454 overlapping types, 362–363 pass by value, 451–452 pass by value, 451–452 overloaded functions, 86–90, 283, 371 parameters, 13, 48, 450 pass by value-result, 454 boxing and tagging, 376 alias for argument, 452 pattern-directed invocation, 120 expansion, 376 checking references to, 480 pattern matching, 68, 338 symbol table, 282–283 functions, 65, 450 patterns and data constructors, 73 overloaded operators, 282, 363 pass by need, 78 Perl overloading, 194, 282–288 procedures, 450 dynamic scoping, 277 function names, 282 type checking, 459 shell languages, 39 names, 287–288 user-defined functions, 77 untyped languages, 331 operators, 282, 287 parameter specification versus parameter-passing pipes, 591 polymorphism, 371–372 PL/I exception handling, 423 scope, 281 mechanisms, 458 pointers, 292–293, 300, 346–349 overload resolution, 282, 284 parametric polymorphism, 194, 372 dangling references, 306–307 owners, 616 dereferenced, 346 generic collections, 169 exception handlers, 477 P parenthesized expressions, 50–52 imperative languages, 348 parent processes, 591 implicit, 346 packages, 10 Parlog, 625 manual dynamic allocation, 348 Ada, 193, 380, 509–515 parser generators, 224, 232–233 recursive types, 347 automatically dereferencing name, 512 parsers pointer semantics, 49, 299 automatic namespaces, 512 pointer variables, 304–306 classes, 193 bottom-up, 224, 233 polymorphic expression, 371 Java, 163, 167, 279, 506–509 parsing shell, 240 polymorphic functions, 69–70 package body, 381, 509 predictive, 230–231 polymorphic type checking, 367–376 package specification, 509 recognizer, 224 polymorphic types, 376 shift-reduce, 224 polymorphic typing, 131 package specification, 380–381, 509–510 top-down, 230 polymorphism, 144, 150, 153, 331 paradigms, 15 type descriptors, 384 ad hoc, 194 parallelism, 108, 582–583 parse trees, 213–216 explicit, 376–382 BNF notation, 221 versus inheritance, 194–195 and-parallelism, 622 derivations, 216–218 Java, 167–175 message passing, 626–631 terminals and nonterminals, 215 overloading, 371–372 non-imperative languages, 622–631 parsing, 110, 224–235 parametric, 194, 372 or-parallelism, 623 bottom-up, 224 Smalltalk, 154–155 procedure-level, 593 methods, 243–246 subtype, 194 program-level, 594–595 procedure, 225 pool dictionaries, 152 statement-level, 593 recursive-descent, 225 portability, 36, 39 parallel matrix multiplication, 588 single-symbol lookahead, 230 parallel processing, 582, 587–595 top-down, 224 parsing methods, 243 parsing shell, 240 C7729_index.indd 657 03/01/11 10:47 AM

658 Index positional property, 210 continue call, 609 logic, 20, 104 postconditions, 565–566 creation and destruction, 591–592 logic paradigm, 15 postfix operators, 346, 403 deadlock, 585–586 machine dependent, 326–327 PostScript, 404 executing, 583 machine language, 3–4 precedence, 216–220 granularity, 592 metasymbols, 209 preconditions, 565–566 heavyweight and lightweight, 583–584 models of computation, 8 predecessor, 332 parent, 591 monomorphic, 372 predefined identifiers, 205, 236, 258–259, 332 spawn, 627 object-oriented paradigm, 15 predefined operators, 405 spin, 608 operational semantics, 547–556 predefined types, 87, 332 starvation, 608 origins, 3–8 predicate calculus, 106–107, 110 suspending, 609 orthogonal, 30–32 predicates, 105, 107, 116, 360, 497 synchronizing, 604 paradigms, 15 predicate transformers, 543, 567 waiting, 583 parallel processing, 587–595 predictive parsers, 230–232 processors parameters, 78 prefix functions, 83 assigning, 589 precise semantic descriptions, 542 prefix operators, 403–404 communication problem, 585–586 predefined types, 332 prime numbers, 81 integrating operation, 586–587 procedures, 446 primitive functions, 55 mutual exclusion, 585 regularity, 30–33 primitive types, 32, 163, 166, 350–351 organization, 584 reliability, 30 principle of extensionality, 535–536 race condition, 585 security, 33–34 principle of longest substring, 205 producer-consumer problem, 588 semantics, 16–17, 204, 257–315 principle type, 374 producer threads, 601 special-purpose, 26 private inner class, 171 productions, 210–211 static typing, 328 private members, 181 program-level parallelism, 594–595 strict, 77 procedural interpretation, 110 programmer efficiency, 29–30 strongly typed, 331 procedure calls, 13, 462 programming, 46 syntax, 16–17, 29–30, 204 procedure declaration, 12, 447 declarative style, 131 tokens, 17, 204–208 procedure-level parallelism, 593–594 programming languages translators, 18–19 procedures, 12–13, 444, 612 abstractions, 7, 8–14 uniformity, 31–32 affected by parallelism, 582–583 von Neumann bottleneck, 15 activation, 12, 445–447 algebraic notation, 6 von Neumann model, 15 activation records, 449, 462 ALGOL family, 6–7 weakly typed, 331 activations, 459–472 API (application programming interface), 10 programs actual parameters, 13 assembly language, 4–6 byte code, 18 advanced inlining process, 455 assignment, 299 compilation, 18 allocation, 459–472 automatic memory management, 346 dangling references, 308 arguments, 13, 445 axiomatic semantics, 565–571 erroneous, 458 body, 445, 450 basic data abstractions, 8–9 functional languages, 131 called, 13, 448 BNFs (Backus-Naur forms), 204 as functions, 46, 47–50 callee, 446 compilers, 18 garbage, 308 caller, 446 computation without von Neumann identifiers, 205 calling, 445–446 legal, 331 closed form, 450 architecture, 7–8 logic language, 131 communication, 450 data, 326 mathematical description of behavior, 542 creating another procedure, 471–472 denotational definition, 557 predefined identifiers, 205 defining environment, 468 denotational semantics, 556–565 proofs of correctness, 542, 571–574 definition, 445–447 derivation, 209–210 reliability, 327 dynamically computed, 469–472 documentation, 16 robustness, 424 environments, 459–472 dynamic memory allocation at runtime, 29 security, 327 executing, 612 evolution of, 20 syntactic structure, 204 filters, 80–81 explicit types, 327 unsafe, 331 formal parameters, 445 expressions, 402 projection functions, 335 generators, 80–81 expressiveness, 29 Prolog, 104, 115–126 interface, 445 extensibility, 34–35 and-parallelism, 622, 624 invocation, 12 formal definitions, 16–17 appending lists, 120 lexical scope, 449, 467 fully curried, 76 arithmetic terms, 117–118 nested, 465–466, 468 functional paradigm, 15 backtracks, 120–123 nonlocal references, 447 function application, 47–48 clauses, 120 parameter-passing mechanisms, 451–459 function definition, 47–48 compilers, 116 parameters, 13, 450 functions, 446 constants, 116, 626 return-statement, 446 future of, 19–21 control structures, 122–126 semantics, 447–451 generality, 30–31 cut operator, 124–126, 129 specification, 445 goals, 26 data structures, 116 symbolic name, 447 grammar, 16 depth-first search, 122 processes, 14, 583–584 identifiers, 257 equality, 118–119 blocked, 583 imperative, 15 Euclid’s algorithm, 118 busy-wait, 608 interpreters, 18 evaluating arithmetic, 117–118 children, 591 lexics (lexical structure), 17, 204–208, 236 C7729_index.indd 658 03/01/11 10:47 AM

Index 659 execution, 116–117 primitive operations and data types, 38 reference types, 32, 166, 169, 350–351 functions, 116 reference semantics, 300 collections, 169 Horn clauses, 115, 129 reference types, 32 equality operator (==), 167 infinite loops, 122, 124, 127, 129 regularity, 38–39 reference semantics, 32 interpreters, 116–117 scripts, 39 lists, 116, 119 semantically safe, 33–34 referential transparency, 49, 409 logical variables, 134, 626 shorthand notation, 10 regular expressions, 206 loops, 122–126 simplicity, 38–39 regularity, 30–33, 38–39 notation, 116 static type-checking, 33 reinterprets, 366 or-parallelism, 623–624 syntax, 29–30, 38 reliability, 30, 33, 327 parallelism, 624–625 type checking, 40 Remote Method Invocation. See RMI (Remote pattern-directed invocation, 120 typeless variables, 29 pattern matching, 116 untyped languages, 331 Method Invocation) predicates, 116 variable declarations, 33 Remote Procedure Call. See RPC (Remote repetitive searches, 122–123 variable names, 261 resolution, 115, 121 virtual machine, 38 Procedure Call) search strategy, 121–122 Python virtual machine. See PVM (Python virtual remove ambiguities, 327 shorten clauses, 120 rendezvous, 616–621 sorting lists, 132 machine) repeated inheritance, 191 sorting program, 130 reserved words, 205, 236 standard predicates, 116 Q resolution, 115, 121 subgoals, 121 unification algorithm, 118–121, 127 Qlisp and-parallelism in let-bindings, 624 Horn clauses, 111–112 uninstantiated variables, 119 quantifiers, 106 resumption model, 431 variables, 116 queries, 108 returned values, 446 Prolog programs Queue data type, 505 return-statement, 446 append list operation, 119 queues reusability, 10 control information, 129–131 reusable code, 15 definite clause grammars, 110 linked lists, 170–172 reverse list operation, 119 execution, 116–117 linked nodes, 160–162 reverse operation, 59 reverse list operation, 119 QUICKSORT algorithm, 27 rev function, 70 promise to evaluate arguments, 78 quote keyword, 53 right associative, 218–219 proofs of program correctness, 571–574 quotient algebra, 533 right-associative operators, 221 propagating the exception, 430 right-recursive rule, 219, 227 properties, 145 R RMI (Remote Method Invocation), 616 protected objects, 612 robustness, 424 prototypes, 260, 445, 502–503 race condition, 585 row-major form, 344 proved, 105 raised, 423 RPC (Remote Procedure Call), 616 pseudoparallelism, 583 range, 47 Ruby, 20, 331 public members, 181 raw collections, 169 runtime binding, 155 pure functional program, 48 readability, 327 runtime environments, 13, 39 pure lambda calculus, 91 real numbers, 326–327 pure polymorphism, 372 real types, 351 dynamic scoping, 277 pure virtual declaration, 187–188 receive process, 627 language design, 308 pure virtual functions, 188–189 receiver object, 162 r-value, 298, 361 PVM (Python virtual machine), 39–40 receivers, 145, 149 Python reclamation of storage, 475–476 S application-specific libraries, 39 recognizer, 224, 232 automatic garbage collection, 34 records, 335 safe union mechanism, 338 byte code, 18 record structure, 335–336 same-fringe problem, 80–81 data types, 38 recursion, 56–57, 131 sample language, 543–547 dictionary, 38 doc, 10 functional programming, 48–49 abstract syntax, 546 dynamic typing vs. finger typing, 39–40 recursive data types, 73 axiomatic semantics, 569–571 extensibility, 34, 38–39 recursive declarations, 268 empty environments, 545 functions, 31 recursive-descent parser, 227 environments, 544–545 general-purpose scripting language, 38–40 recursive-descent parsing, 110, 225–227, 241 loops, 546 importance, 26 recursive functions, 8, 55, 74, 347 proofs of program correctness, 571–574 indentation, 205 recursive routines, 29 semantics of arithmetic expressions, 544 interactivity, 39 recursive subroutines, 29 statements, 545 machine-independent byte code, 39 recursive types, 346–349 type nomenclature, 349–315 modules, 10, 263 reduced, 224 save queue, 630 objects, 32 reduction machine, 547 scalar types, 163, 351 platforms, 39 reduction rules, 548 scanner generator, 235 portability, 39 scanners, 210 predefined identifiers, 205 control, 553–554 getToken procedure, 225 predefined operators, 31 environments, 551–553 token categories, 235–236 integer arithmetic expressions, 548–551 Scheme, 28, 50 lambda calculus, 90 ad hoc stream constructions, 80 reductions and transitivity rule, 550 applicative order evaluation, 53, 77 reference counting, 472, 475–476 atoms, 50, 51 references, 163, 346, 361 binding list, 54 reference semantics, 32, 147–148, 166, 299 box and pointer notation, 58–59 data structures, 57–60 C7729_index.indd 659 03/01/11 10:47 AM

660 Index Scheme (cont.) selectors, 146, 497 sieve of Eratosthenes algorithm, 81, 85 define special form, 55 semantically safe, 33–34 Signal operation, 604, 609 delayed evaluation, 54 semantic domains, 556–558 signatures, 86, 494, 515–518 delay special form, 78 semantic equations, 559 dynamic type checking, 55–56 semantic functions, 257–260, 559 free algebra of terms, 533–534 elements of, 50–55 semantics, 16–17, 204, 257–315 SIMD (single-instruction, multiple-data) systems, environment in, 52 evaluation rules, 51–53, 66 algebraic specification, 535 584–585 expressions, 50–54 aliases, 303–306 simple types, 332–334 extended Backaus-Naur form, 51 allocation, 289–297 Simula, 142, 181 force special form, 78 attributes, 257–260 Simula67, 35, 142 functions, 31, 54–55 axiomatic semantics, 543 single-entry, single-exit constructs, 402 heap allocation and deallocation, 295 binding, 257–260 single-instruction, multiple-data systems. See SIMD higher-order functions, 61–62 blocks, 260–269 if form, 54 BNF rules, 543 (single-instruction, multiple-data) systems interpreter, 63 constants, 300–303 single-processor models of computation, 8 lambda forms, 54–55, 148 correctness rules, 360 single program multiple data. See SPMD program- let form, 54 dangling references, 303–307 letrec form, 55 declarations, 260–269 ming (single program multiple data) lexical scoping, 277 denotational semantics, 542 single-symbol lookahead, 230 lists, 53, 57–60 environment, 260, 289–297 Smalltalk, 144–162 loops, 54 expressions, 402 memorization process, 78 formal and informal, 17 abstract classes, 151 metalinguistic power, 63–64 formal definition, 257 based-object approach, 195 non-tail recursion, 56–57 garbage, 303–309 basic elements, 145–150 pass by value, 54 identifiers, 257 binary messages, 147 pointer manipulation, 295 lifetimes, 289–297 blocks, 148–149 predicates, 360 locations, 257 classes, 145, 150–157, 155, 192, 263 primitives, 55, 59 memory, 260 class hierarchy, 150–157 quote special form, 53 name resolution, 282–288 class messages, 146 recursion, 56–57, 60 names, 257 class names, 146 semantics, 54 operational semantics, 542 class variables, 152 special forms, 52, 77 overloading, 282–288 collection classes, 150 statically scoped, 62–63 procedures, 447–451 collection methods, 176 strings, 57 scope, 260–269 collections, 157–162 symbolic information processing, 63–64 semantic functions, 257–260 comments, 146 symbols, 51, 53, 63 specifying, 257 concrete classes, 150–151 syntax, 51 state, 260 control statements, 148–149 tail recursion, 56–57 static expressions, 432–433 deallocation routines, 197 type checking, 359–360 store, 260 Dynabook Project, 144 vector type, 344 symbol table, 259, 269–281 dynamic binding, 155, 176 type inference, 360 dynamic typing, 145 scope, 260–269 values, 257 function variables, 345 bindings, 263–265 variables, 297–300 garbage collection, 145 block-structured languages, 62 vs. lexics vs. syntax, 235–236 instance messages, 146 declarations, 263–265, 269–270 semaphores, 588, 604–609 instance methods, 155 exception handlers, 429 sender, 145 instance variables, 152, 155 overloading, 281 send process, 627 iterators, 150, 158–159 scope holes, 266 sentinel-based loops, 422–423 keyword messages, 146–148 symbol table, 280 separate compilation, 502–506 lambda form, 177 variables, 62–63 sequence operator, 406 literal array, 148 sequence types, 340 Magnitude hierarchy, 150–157 scope analysis, 269, 309–312 server, 628–629 message passing, 146 scope hole, 266 set equation, 213 messages, 145, 150 scope of a binding, 263–264 set! special form, 57 methods, 145, 152, 470 scope resolution operator (::), 182, 266, 267 shadow, 266 mutator, 146 scope rules shared inheritance, 191 objects, 145, 167, 197 shared-memory model, 585, 604 parameters, 345 dynamic scoping, 273 shared operations, 363–364 polymorphic methods, 176 exception declarations, 426 shell languages, 39 polymorphism, 154–155 nonlocal references, 447 shift-reduce parsers, 224 pool dictionaries, 152 recursive declarations, 268 short-circuit Boolean operations, 408 queues, 160 static scoping, 273 short-circuit evaluation, 77, 406–407 receivers, 145 scoping structure, 279 side effects, 305 reference semantics, 147–148, 300 search strategy, 121–122 expressions, 402, 405–406 runtime binding, 155 section, 82 normal order evaluation, 410 sender, 145 security, 33–34 order of evaluation, 405–406 unary messages, 146 data types, 493 pass by name, 457 user interface, 145 ML (MetaLanguage), 65 variables, 147, 261 programs, 327 WIMP (windows, icons, mouse, pull-down menus) user interface, 144 Smalltalk-72, 145 C7729_index.indd 660 03/01/11 10:47 AM

Index 661 Smalltalk-76, 145 Stroustup, Mjarne, 35–38 T Smalltalk-80, 142, 145 structs, 278–279 Smalltalk/V, 145, 146 structural equivalence, 352–355 tags, 336 SML97, 65 structural operational semantics, 548 tail operator. See tl (tail) operator SML (Standard ML), 65 structure construction, 335 tail recursive, 56, 60 SNOBOL, 26, 277 structured abstractions, 8–9 target language, 18 software reuse, 143–144 structured control, 402 target program, 18 sorting, 532–533 task entries, 616 abstractions, 11–14 tasks, 14, 263, 594, 611–612 free algebra of terms, 533–534 constructs, 402 lists, 132 statements, 7 entries, 616–617 procedure, 129–130 structured language exceptions, 425 master, 619 source program, 18 structure member operation, 335 parallel matrix multiplication, 619 spaghetti code, 421 structures, 343, 515–518 rendezvous, 616–621 special forms, 52 subexpressions, 405 semaphore type, 619 specializes, 374 subgoals, 112, 121 template classes, 184–186 special symbols, 205 subprograms, 12 templates, 194, 378–379, 506 specifications, 110–111, 445, 543 subrange types, 332, 334, 384, 432 terminals, 210, 215–216 spin, 608 subroutines, 12, 446, 459–460 termination model, 431 spin-locks, 608 subset types, 339 terms, 106–107 SPMD programming (single program multiple substitution, 92 ternary operator, 408 substitution rule, 409 TestAndSet machine instruction, 607–608 data), 591 subtype polymorphism, 194, 372 theorems, 107–108 stack-based allocation, 294 subtypes, 339 threads, 14, 584, 588, 595–604 stack-based environment, 462–471 successor, 332 bounded buffer problem, 601–604 stack-based languages, 404 Sun Microsystems, 162 consumer, 601 stack frame, 448 suspend operations, 609–610 daemons, 596 stack unwinding, 431 Swing Toolkit, 10, 144 defining, 596 Standard ML. See SML (Standard ML) switch-statements, 414–416 destroying, 597 Standard Template Library. See STL (Standard symbolic, 301 fork-join parallelism, 597 symbolic constants, 432–435 interrupting, 597 Template Library) symbolic information processing, 53, 63–64 producer, 601 start symbol, 209–211 symbolic logic, 15 running, 596 starvation, 608 symbols, 53, 63, 269 sharing memory or resources, 597–598 state, 260 symbol table, 259, 269–281, 309–311 waiting for conditions and resuming execution, statement-level parallelism, 593 block declarations, 269 statements, 402, 444 compiler, 273 599–600 declarations, 269, 273 thrown, 423 conditional, 410–416 dynamically managed, 273–274 thunks, 456 sample language, 545 dynamic scope, 274–277 TinyAda single-entry, single-exit, 402 overloaded functions, 282–283 statically typed languages, 360, 367 scope, 279–281 assignment statements, 383 static binding, 175–176, 186–191 static declarations, 273 component references, 389–390 binding times, 258 structure, 269–273 data types, 313 data types, 277 type names, 313 declarations, 239, 386–388 static constants, 301–302 synchronized methods, 609 EBNF grammar, 237–239 static environment, 289, 449 synchronized objects, 609–610 expressions, 239, 388–389 static expressions, 390, 432–433, 435–436 synchronizing processes, 604 grammar rules, 243 static link, 467 synchronous exceptions, 424 identifiers, 309, 310–312, 312–315, 382–385 static scope, 62–63, 273 syntactic domains, 556–558 name equivalence, 383, 385 static semantic analysis, 259, 390 syntactic specification, 494 nested scopes, 310 static type checking, 33, 181, 327, 359 syntactic sugar, 10, 417 parameter modes, 390, 479–481 static types, 327 syntax, 16–17, 204 parser, 242–243, 383 static typing, 39, 65–76 abstract syntax, 216 procedure calls, 389–390 STL (Standard Template Library), 37 analysis, 259, 313 procedure declaration, 239, 311 stop and copy, 476 concrete syntax, 216 recursive rules, 239 storage class, 296 parameter modes, 479 scope, 309–312 storage semantics, 49, 300 static expressions, 432–433 semantic qualifiers, 237–239 store, 260 structure, 213 statements, 239 streams, 80, 85 syntax-directed semantics, 214 static expressions, 390, 432–436 strict evaluation, 404, 626 vs. lexics vs semantics, 235–236 static semantic analysis, 309–315, 390 strict functions, 94 syntax analyzer, 237–246 symbolic constants, 432, 433–435 strings, 57 syntax diagrams, 204, 220–224 symbol table, 309–311 iterators, 158 EBNF rules, 243–244 syntax analyzer, 237–246 predefined identifiers, 236 recursive-descent parser, 227 TEST program, 239–240 reading and writing, 71 syntax-directed semantics, 214 tokens, 240 reserved words, 236 syntax trees, 216–218 type checking, 382–390 strongly typed language, 327, 331 type checker, 368–370 type descriptors, 383–386 type checking parameters, 459 type equivalence, 383 unsafe program, 331 tl (tail) operator, 67–68 Stroustrup, Bjarne, 27, 36, 181 token delimiters, 205 C7729_index.indd 661 03/01/11 10:47 AM

662 Index tokens, 17, 204–208, 210, 233, 240–241 name equivalence, 355–357 variable annotations, 625 categories, 235–236 structural equivalence, 352–355 variable binding, 626 constants, 205 type equivalence algorithm and type-checking variable declarations, 33, 163 identifiers, 205 variable-length tokens, 205 keywords, 205 algorithm, 358–359 variables, 9, 48, 105, 297–300 literals, 205 type equivalence algorithms, 331, 360 numbers as, 235–236 type form, 384 bound, 48, 63 principle of longest substring, 205 type inference, 330, 360 bound by quantifier, 106 regular expressions, 206 bound by the lambda, 91 reserved words, 205 Hindley-Milner type checking, 367–370 bound occurrence, 91–92 special symbols, 205 type information, 328–331 box-and-circle diagram, 297 token delimiters, 205 concept of, 48 white space, 205 declarations, 386–388 data types, 9 YACC/Bison, 235 recording, 477 declarations, 32, 356 type names, 349–351, 354 dereferenced, 293, 361 top-down parsers, 230 type parameters, 168–169, 372 free, 63, 91–92, 106 top-down parsing, 224 type recognition functions, 56 Horn clauses, 111 transitivity rule, 550 type rules, 331 instantiated, 114, 128 translation, 259 type variables, 67, 83, 194, 369–370, 375 lambda calculus, 91–92 translation efficiency, 327 l-value, 298 translators, 18–19, 191 U names, 9 reference semantics, 147–148 bindings, 258–259 unary messages, 146 r-value, 298 code inlining, 404 unary operator, 403 schematic representation, 297 compiler options, 589 unconstrained arrays, 342 scope, 62–63 parsing phase, 204 undiscriminated unions, 336 storage class, 296 processors, 589 unification, 111–115, 370 unification, 114 scanning phase, 204 value, 298 type checking, 331 Curry, 133–134 values, 298 validated, 542 equality, 118–119 value semantics, 147 true parallelism, 582 functional languages, 370 visible declaration, 62–63 try-catch blocks, 427–428 Haskell, 120 variant record, 337 tuples, 67, 72, 76, 83, 336 logic programming, 133 vector type, 344 tuple type, 66 ML (MetaLanguage), 120 virtual functions, 186–191 Turing machines, 90 occur-check problem, 127, 375 virtual machines, 18 Turner, David A., 81 Prolog, 118–121 visibility, 266 twos complement notation, 4 uniformity, 31–32 visibility by selection, 267 type checker, 367–370 uninstantiated variables, 119 von Neumann, John, 3 type checking, 330, 359–360, 382–390 unions, 336–339 von Neumann bottleneck, 15, 582 dynamic, 359 unit abstractions, 8–10 von Neumann model, 7, 15 Hindley-Milner type checking, 367–370 units, 14 implicit types, 361–362 universally quantified variables, 110 W multiply-typed values, 362–363 universal quantifier, 106 overlapping types, 362–363 University of Edinburgh, Scotland, 104, 115 waiting, 583 parameters, 459 University of Glasgow, Scotland, 81 weakest assertion, 567 polymorphic, 367–376 UNIX operating system, 20, 26 weakest precondition, 567 shared operations, 363–364 pipes, 591 weakly typed language, 331 static, 359–360 YACC (yet another compiler compiler), 233 while loop, 34–35, 173, 423 translators, 331 unordered collections, 157 while special form, 57 type inference, 360 unsafe programs, 331 while statements unification, 370 unsynchronized methods, 609 type-checking algorithm, 358–359 untyped languages, 331 approximation, 573 type classes, 86–90 USENIX (UNIX users’ association), 37 axiomatic semantics, 571 type class inheritance, 87–88 user-defined data types, 72, 73, 89, 492 Whitehead, A. N., 6 type compatibility, 361, 383 user-defined exceptions, 424 white space, 205 type constructors, 192, 330, 335–349, 351 user-defined functions, 77, 404–405, 492 widening conversions, 365 arrays, 340–345 user-defined operators, 500 wildcard pattern, 416 Cartesian products, 335–336 user-defined polymorphic types, 83 wildcards, 68 classes, 192 user-defined type constructors, 377 WIMP (windows, icons, mouse, pull-down menus) data types, 330 user-defined types, 330–331 functions, 340–345 user interface, 144 union, 336–339 V Wirth, Niklaus, 7, 27, 204, 326 user-defined, 377 writability, 27, 327 type conversion, 364–367 validated, 542 type correctness rules, 361 valuation functions, 557 Y type declaration, 330 value constructors, 73 type definition, 330, 386 values, 54–56, 257 YACC/Bison, 224, 233–235 type descriptors, 383–386, 387–389 Yale University, 81 type equivalence, 352–359, 383 defining, 65–66 yet another compiler compiler. See YACC (yet implicitly pointers or references, 452 literals, 301 another compiler compiler) multiply-typed, 362–363 operations applied to, 329 Z value semantics, 32, 49, 147, 166, 300–301 van Rossum, Guido, 35, 38–40 zero-overhead rule, 36 C7729_index.indd 662 03/01/11 10:47 AM