Concepts in Programming Languages

Annotation Concepts in Programming Languages elucidates the central concepts used in modern programming languages, such as functions, types, memory management, and control. The book is unique in its comprehensive presentation and comparison of major object-oriented programming languages. Separate chapters examine the history of objects, Simula and Smalltalk, and the prominent languages C++ and Java. The author presents foundational topics, such as lambda calculus and denotational semantics, in an easy-to-read, informal style, focusing on the main insights provided by these theories. Advanced topics include concurrency, concurrent object-oriented programming, program components, and inter-language interoperability. A chapter on logic programming illustrates the importance of specialized programming methods for certain kinds of problems Cover......Page 1 Half-title......Page 3 Title......Page 5 Copyright......Page 6 Contents......Page 7 Preface......Page 11 Acknowledgments......Page 12 PART 1 Functions and Foundations......Page 13 1.1 PROGRAMMING LANGUAGES......Page 15 1.2.1 General Goals......Page 17 1.3 PROGRAMMING LANGUAGE HISTORY......Page 18 1.4 ORGANIZATION: CONCEPTS AND LANGUAGES......Page 20 2.1.1 Expressions, Errors, and Nontermination......Page 22 2.1.2 Partial Functions......Page 24 Computable Functions......Page 25 Noncomputable Functions......Page 26 Applications......Page 27 2.1 Partial and Total Functions......Page 28 2.3 Halting Problem on All Input......Page 29 3.1 LISP HISTORY......Page 30 Program Execution Model......Page 32 Theoretical Foundations......Page 33 S-Expressions and Lists......Page 34 Evaluation of Expressions......Page 35 3.4.1 Statements and Expressions......Page 37 3.4.2 Conditional Expressions......Page 38 Cons Cells......Page 40 Representation of Lists by Cons Cells......Page 42 3.4.4 Programs as Data......Page 43 3.4.5 Function Expressions......Page 44 3.4.6 Recursion......Page 45 3.4.7 Higher-Order Functions......Page 46 3.4.8 Garbage Collection......Page 47 Mark-and-Sweep Garbage Collection......Page 48 3.4.9 Pure Lisp and Side Effects......Page 50 3.5 CHAPTER SUMMARY: CONTRIBUTIONS OF LISP......Page 51 3.2 Conditional Expressions in Lisp......Page 52 3.4 Lisp and Higher-Order Functions......Page 54 3.5 Definition of Garbage......Page 55 3.6 Reference Counting......Page 56 3.8 Concurrency in Lisp......Page 57 4.1.1 Structure of Simple Compiler......Page 60 Lexical Analysis......Page 62 Intermediate Code Generation......Page 63 Grammars......Page 64 Derivations......Page 65 Parse Trees and Ambiguity......Page 66 4.1.3 Parsing and Precedence......Page 67 4.2.1 Functions and Function Expressions......Page 69 Variable Binding......Page 71 Lambda Abstraction in Lisp and Algol......Page 72 Equivalence and Substitution......Page 73 4.2.3 Programming in Lambda Calculus......Page 74 Recursion and Fixed Points......Page 75 4.2.4 Reduction, Confluence, and Normal Forms......Page 77 Confluence......Page 78 4.3 DENOTATIONAL SEMANTICS......Page 79 Compositionality......Page 80 4.3.2 Denotational Semantics of Binary Numbers......Page 81 Expressions with Variables......Page 82 States and Commands......Page 83 Denotational Semantics......Page 84 4.3.4 Perspective and Nonstandard Semantics......Page 86 4.4.1 Imperative and Declarative Sentences......Page 88 4.4.2 Functional versus Imperative Programs......Page 89 Referential Transparency......Page 90 Historical Debate......Page 91 Functional Programming and Concurrency......Page 92 Practical Functional Programming......Page 93 4.5 CHAPTER SUMMARY......Page 94 4.4 Symbolic Evaluation......Page 95 4.7 Order of Evaluation......Page 96 4.10 Semantics of Type Checking......Page 97 4.11 Lazy Evaluation and Parallelism......Page 99 4.12 Single-Assignment Languages......Page 100 4.13 Functional and Imperative Programs......Page 101 4.14 Functional Languages and Concurrency......Page 102 PART 2 Procedures, Types, Memory Management, and Control......Page 103 5.1.1 Algol 60......Page 105 5.1.3 Pascal......Page 109 5.2 THE DEVELOPMENT OF C......Page 111 C Arrays and Pointers......Page 112 5.3 THE LCF SYSTEM AND ML......Page 113 5.4 THE ML PROGRAMMING LANGUAGE......Page 115 Expressions......Page 116 Declarations......Page 117 Bool......Page 119 Integers......Page 120 Real......Page 121 Records......Page 122 Lists......Page 123 Value Declarations......Page 124 Function Declarations......Page 125 5.4.4 ML Data-Type Declaration......Page 127 5.4.5 ML Reference Cells and Assignment......Page 129 Operations on Reference Cells......Page 130 5.5 CHAPTER SUMMARY......Page 133 5.2 Algol 60 Pass-By-Name......Page 134 5.3 Nonlinear Pattern Matching......Page 135 5.4 ML Map for Trees......Page 136 5.7 Disjoint Unions......Page 137 5.8 Lazy Evaluation and Functions......Page 138 6.1 TYPES IN PROGRAMMING......Page 141 6.1.2 Type Errors......Page 142 6.2.1 Type Safety......Page 144 6.2.2 Compile-Time and Run-Time Checking......Page 145 6.3.1 First Examples of Type Inference......Page 147 6.3.2 Type-Inference Algorithm......Page 148 6.4.1 Parametric Polymorphism......Page 157 C++ Function Templates......Page 158 Comparison with ML Polymorphism......Page 159 C++ Implementation......Page 160 ML Implementation......Page 161 6.4.3 Overloading......Page 162 6.5.1 Transparent Type Declarations......Page 163 6.5.3 ML Data-Type Declaration......Page 165 Type Inference......Page 167 6.2 Polymorphic Sorting......Page 168 6.5 Parse Graph......Page 169 6.6 Parse Graph......Page 170 6.9 Polymorphism in C......Page 171 6.11 Dynamic Typing in ML......Page 172 7.1 BLOCK-STRUCTURED LANGUAGES......Page 174 Simplified Machine Model......Page 176 7.2.1 Activation Records and Local Variables......Page 177 Intermediate Results......Page 178 Blocks and Activation Records for ML......Page 179 7.2.2 Global Variables and Control Links......Page 180 7.3.1 Activation Records for Functions......Page 182 7.3.2 Parameter Passing......Page 185 Semantics of Pass-by-Value......Page 186 Semantics of Pass-by-Reference......Page 187 7.3.3 Global Variables (First-Order Case)......Page 188 Access Links are Used to Maintain Static Scope......Page 190 7.3.4 Tail Recursion (First-Order Case)......Page 192 7.4.1 First-Class Functions......Page 194 7.4.2 Passing Functions to Functions......Page 195 Use of Closures......Page 196 7.4.3 Returning Functions from Nested Scope......Page 198 Solution to Storage Management Problem......Page 201 7.5 CHAPTER SUMMARY......Page 202 7.1 Activation Records for In-Line Blocks......Page 203 7.3 Time and Space Requirements......Page 205 7.4 Parameter Passing......Page 206 7.6 Pass-by-Value-Result......Page 207 7.8 Static and Dynamic Scope......Page 208 7.10 Eval and Scope......Page 209 7.12 Function Calls and Memory Management......Page 210 7.13 Function Returns and Memory Management......Page 211 7.14 Recursive Calls and Memory Management......Page 212 7.16 Closures and Tail Recursion......Page 213 7.17 Tail Recursion and Order of Operations......Page 214 8.1.1 Spaghetti Code......Page 216 8.1.2 Structured Control......Page 218 8.2.1 Purpose of an Exception Mechanism......Page 219 8.2.2 ML Exceptions......Page 221 8.2.3 C++ Exceptions......Page 223 8.2.4 More about Exceptions......Page 225 Exceptions for Efficiency......Page 226 Static and Dynamic Scope......Page 227 Typing and Exceptions......Page 228 Exceptions and Resource Allocation......Page 229 8.3.1 A Function Representing “The Rest of the Program”......Page 230 8.3.2 Continuation-Passing Form and Tail Recursion......Page 232 8.4 FUNCTIONS AND EVALUATION ORDER......Page 235 8.5 CHAPTER SUMMARY......Page 239 8.1 Exceptions......Page 240 8.3 Exceptions......Page 241 8.7 Control Flow and Memory Management......Page 242 8.9 Continuations......Page 243 PART 3 Modularity, Abstraction, and Object-Oriented Programming......Page 245 9.1 STRUCTURED PROGRAMMING......Page 247 9.1.1 Data Refinement......Page 250 9.1.2 Modularity......Page 251 Procedural Abstraction......Page 254 9.2.2 Abstract Data Types......Page 255 9.2.3 ML abstype......Page 256 Clu Clusters......Page 259 9.2.4 Representation Independence......Page 260 Partition Operations......Page 261 Induction over Constructors......Page 263 9.3 MODULES......Page 264 9.3.1 Modula and Ada......Page 265 9.3.2 ML Modules......Page 267 Simple Polymorphic Function......Page 271 Operations on Type Parameters......Page 272 Comparison with ML Polymorphism......Page 273 9.4.2 Standard ML Functors......Page 274 9.4.3 C++ Standard Template Library......Page 277 Language Support for Abstraction......Page 281 Modules and Generic Programming......Page 282 9.1 Efficiency vs. Modularity......Page 283 9.2 Equivalence of Abstract Data Types......Page 285 9.4 Modularity of Concrete Data Types......Page 286 9.5 Templates and Polymorphism......Page 288 10.1 OBJECT-ORIENTED DESIGN......Page 289 10.2 FOUR BASIC CONCEPTS IN OBJECT-ORIENTED LANGUAGES......Page 290 10.2.1 Dynamic Lookup......Page 291 10.2.2 Abstraction......Page 294 10.2.3 Subtyping......Page 296 Inheritance and Abstraction......Page 297 10.2.5 Closures as Objects......Page 298 10.2.6 Inheritance Is Not Subtyping......Page 299 10.3 PROGRAM STRUCTURE......Page 300 Comparison of Examples 10.1 and 10.2......Page 301 10.4 DESIGN PATTERNS......Page 302 Sample Code......Page 303 10.5 CHAPTER SUMMARY......Page 304 10.6 LOOKING FORWARD: SIMULA, SMALLTALK, C++, JAVA......Page 305 10.1 Expression Objects......Page 306 10.2 Objects vs. Type Case......Page 308 10.3 Visitor Design Pattern......Page 309 11.1.1 Object and Simulation......Page 312 11.1.2 Main Concepts in Simula......Page 314 11.2.1 Basic Object-Oriented Features in Simula......Page 315 Problem......Page 316 Line......Page 317 11.2.3 Sample Code and Representation of Objects......Page 318 11.3.1 Subclasses and Inheritance......Page 320 11.3.2 Object Types and Subtypes......Page 321 11.4 DEVELOPMENT OF SMALLTALK......Page 322 Dynabook......Page 323 11.5.2 Classes and Objects......Page 324 Run-Time Representation of Objects......Page 326 11.5.3 Inheritance......Page 327 Run-Time Structure to Support Inheritance......Page 328 11.6.1 Dynamic Lookup and Polymorphism......Page 330 11.6.2 Booleans and Blocks......Page 331 11.6.3 Self and Super......Page 332 11.6.4 System Extensibility: The Ingalls Test......Page 333 11.7.1 Interfaces as Object Types......Page 334 11.7.2 Subtyping......Page 335 11.7.3 Subtyping and Inheritance......Page 336 Smalltalk......Page 338 11.1 Simula Inheritance and Access Links......Page 339 11.2 Loophole in Encapsulation......Page 340 11.4 Smalltalk Run-Time Structures......Page 342 11.5 Smalltalk Implementation Decisions......Page 343 11.6 Protocol Conformance......Page 344 11.7 Removing a Method......Page 345 11.8 Subtyping and Binary Methods......Page 346 11.9 Delegation-Based Object-Oriented Languages......Page 347 12.1 DESIGN GOALS AND CONSTRAINTS......Page 349 12.1.1 Compatibility with C......Page 350 12.1.2 Success of C++......Page 351 Type bool......Page 352 Reference Type and Pass-By Reference......Page 353 User-Defined Overloading......Page 354 12.2.2 Object-Oriented Features......Page 355 Problem Areas......Page 356 12.3.1 C++ Classes and Objects......Page 358 12.3.2 C++ Derived Classes (Inheritance)......Page 360 12.3.3 Virtual Functions......Page 361 12.3.4 Why is C++ Lookup Simpler than Smalltalk Lookup?......Page 363 Arguments to Member Functions and this......Page 364 Nonvirtual and Overloaded Functions......Page 365 12.4.1 Subtyping Principles......Page 367 12.4.2 Public Base Classes......Page 368 12.4.3 Specializing Types of Public Members......Page 369 12.4.4 Abstract Base Classes......Page 370 12.5 MULTIPLE INHERITANCE......Page 371 12.5.1 Implementation of Multiple Inheritance......Page 372 Name Clashes......Page 374 Diamond Inheritance......Page 376 Virtual Base Classes......Page 377 12.6 CHAPTER SUMMARY......Page 378 12.1 Assignment and Derived Classes......Page 379 12.2 Function Objects......Page 380 12.4 Subtyping and Public Data......Page 385 12.5 Phantom Members......Page 386 12.6 Subtyping and Visibility......Page 387 12.8 “Like Current” in Eiffel......Page 388 12.9 Subtyping and Specifications......Page 389 12.10 C++ Multiple Inheritance and Casts......Page 391 12.11 Multiple Inheritance and Thunks......Page 392 12.12 Dispatch on State......Page 393 13 Portability and Safety: Java......Page 396 13.1.2 Design Decisions......Page 398 13.2.1 Classes and Objects......Page 401 13.2.2 Packages and Visibility......Page 403 13.2.3 Inheritance......Page 404 13.2.4 Abstract Classes and Interfaces......Page 406 13.3.1 Classification of Types......Page 408 13.3.3 Arrays, Covariance, and Contravariance......Page 409 13.3.4 Java Exception Class Hierarchy......Page 410 13.3.5 Subtype Polymorphism and Generic Programming......Page 413 13.4.1 Java Virtual Machine......Page 416 13.4.2 Class Loader......Page 417 13.4.4 Bytecode Interpreter and Method Lookup......Page 418 Finding a Virtual Method by Class......Page 420 Finding a Virtual Method by Interface......Page 422 13.5 SECURITY FEATURES......Page 424 13.5.1 Buffer Overflow Attack......Page 425 Class Loader......Page 426 The Security Manager......Page 427 13.5.3 Security and Type Safety......Page 428 Objects and Classes......Page 429 Inheritance......Page 430 Security......Page 431 13.3 Subtyping and Exceptions......Page 432 13.5 Array Covariance in Java......Page 433 13.6 Java Bytecode Analysis......Page 434 13.7 Exceptions, Memory Management, and Concurrency......Page 435 13.8 Adding Pointers to Java......Page 436 13.9 Stack Inspection......Page 437 PART4 Concurrency and Logic Programming......Page 441 14 Concurrent and Distributed Programming......Page 443 14.1.1 Execution Order and Nondeterminism......Page 445 14.1.2 Communication, Coordination, and Atomicity......Page 447 14.1.3 Mutual Exclusion and Locking......Page 448 Mutual Exclusion......Page 449 Locks and Busy Waiting......Page 450 Deadlock......Page 451 14.1.4 Semaphores......Page 452 14.2 THE ACTOR MODEL......Page 453 14.3.1 Threads and Channels......Page 457 Functions Using Threads and Channels......Page 459 14.3.2 Selective Communication and Guarded Commands......Page 460 14.3.3 First-Class Synchronous Operations: Events......Page 461 Selective Communication with Events......Page 463 14.4 JAVA CONCURRENCY......Page 466 14.4.1 Threads, Communication, and Synchronization......Page 467 Synchronization Primitives......Page 468 14.4.2 Synchronized Methods......Page 470 Concurrent Garbage Collection......Page 472 Java Memory Model......Page 473 Creating Remote Objects......Page 477 14.5 CHAPTER SUMMARY......Page 478 Actor Systems......Page 479 Distributed Java Programming and Remote Method Invocation......Page 480 14.2 Fairness......Page 481 14.5 CML Events......Page 482 14.6 Concurrent Access to Objects......Page 483 14.7 Java Synchronized Objects......Page 484 14.8 Resources and Java Garbage Collection......Page 485 14.10 Java Memory Model......Page 486 15.1 HISTORY OF LOGIC PROGRAMMING......Page 487 15.2 BRIEF OVERVIEW OF THE LOGIC PROGRAMMING PARADIGM......Page 488 15.2.2 Interactive Programming......Page 489 15.3.1 Terms......Page 490 15.3.2 Substitutions......Page 491 15.3.3 Most General Unifiers......Page 492 MARTELLI–MONTANARI ALGORITHM......Page 493 15.4 CLAUSES AS PARTS OF PROCEDURE DECLARATIONS......Page 494 15.4.2 Computation Process......Page 495 15.4.3 Clauses......Page 497 15.5.1 Multiple Uses of a Single Program......Page 498 A type assignment......Page 500 A Sequence Program......Page 502 Difference lists......Page 503 15.6.2 Arithmetic Comparison Relations......Page 504 15.6.3 Evaluation of Arithmetic Expressions......Page 507 15.7 CONTROL, AMBIVALENT SYNTAX, AND META-VARIABLES......Page 508 15.7.1 Cut......Page 509 15.7.2 Ambivalent Syntax and Meta-variables......Page 510 Disjunction......Page 511 If-then-else......Page 512 15.7.4 Negation as Failure......Page 513 15.7.5 Higher-Order Programming and Meta-Programming in Prolog......Page 514 Program manipulation facilities......Page 515 15.8 ASSESSMENT OF PROLOG......Page 517 Complex Semantics of Various Built-ins......Page 518 15.10 CHAPTER SUMMARY......Page 519 Acknowledgements......Page 520 A.1 PROCEDURAL AND OBJECT-ORIENTED ORGANIZATION......Page 521 A.1.1 Shape Program: Typecase Version......Page 522 A.1.2 Shape Program: Object-Oriented Version......Page 528 Glossary......Page 533 Index......Page 537 For Undergraduate And Beginning Graduate Students, This Textbook Explains And Examines The Central Concepts Used In Modern Programming Languages, Such As Functions, Types, Memory Management, And Control. The Book Is Unique In Its Comprehensive Presentation And Comparison Of Major Object-oriented Programming Languages. Separate Chapters Examine The History Of Objects, Simula And Smalltalk, And The Prominent Languages C++ And Java. The Author Presents Foundational Topics, Such As Lambda Calculus And Denotational Semantics, In An Easy-to-read, Informal Style, Focusing On The Main Insights Provided By These Theories. Advanced Topics Include Concurrency, Concurrent Object-oriented Programming, Program Components, And Inter-language Interoperability. A Chapter On Logic Programming Illustrates The Importance Of Specialized Programming Methods For Certain Kinds Of Problems. This Book Will Give The Reader A Better Understanding Of The Issues And Tradeoffs That Arise In Programming Language Design, And A Better Appreciation Of The Advantages And Pitfalls Of The Programming Languages They Use. Pt. 1. Functions And Foundations -- Introduction -- Computability -- Lisp: Functions, Recursion, And Lists -- Fundamentals -- Pt. 2. Procedures, Types, Memory Management, And Control -- The Algol Family And Ml -- Type Systems And Type Inference -- Scope, Functions, And Storage Management -- Control In Sequential Languages -- Pt. 3. Modularity, Abstraction, And Object-oriented Programming -- Data Abstraction And Modularity -- Concepts In Object-oriented Languages -- History Of Objects: Simula And Smalltalk -- Objects And Run-time Efficiency: C++ -- Portability And Safety: Java -- Pt. 4. Concurrency And Logic Programming -- Concurrent And Distributed Programming -- The Logic Programming Paradigm And Prolog. John C. Mitchell. Includes Index.