| |
| |
| |
| Overview | |
| |
| |
| |
| Principles | |
| |
| |
| |
| Paradigms | |
| |
| |
| |
| Special Topics | |
| |
| |
| |
| A Brief History | |
| |
| |
| |
| On Language Design | |
| |
| |
| |
| Design Constraints | |
| |
| |
| |
| Outcomes and Goals | |
| |
| |
| |
| Compilers and Virtual Machines | |
| |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Syntax | |
| |
| |
| |
| Grammars | |
| |
| |
| |
| Backus-Naur Form (BNF) Grammars | |
| |
| |
| |
| Derivations | |
| |
| |
| |
| Parse Trees | |
| |
| |
| |
| Associativity and Precedence | |
| |
| |
| |
| Ambiguous Grammars | |
| |
| |
| |
| Extended BNF | |
| |
| |
| |
| Syntax of a Small Language: Clite | |
| |
| |
| |
| Lexical Syntax | |
| |
| |
| |
| Concrete Syntax | |
| |
| |
| |
| Compilers and Interpreters | |
| |
| |
| |
| Linking Syntax and Semantics | |
| |
| |
| |
| Abstract Syntax | |
| |
| |
| |
| Abstract Syntax Trees | |
| |
| |
| |
| Abstract Syntax of Clite | |
| |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Lexical and Syntactic Analysis | |
| |
| |
| |
| Chomsky Hierarchy | |
| |
| |
| |
| Lexical Analysis | |
| |
| |
| |
| Regular Expressions | |
| |
| |
| |
| Finite State Automata | |
| |
| |
| |
| From Design to Code | |
| |
| |
| |
| Syntactic Analysis | |
| |
| |
| |
| Preliminary Definitions | |
| |
| |
| |
| Recursive Descent Parsing | |
| |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Names | |
| |
| |
| |
| Syntactic Issues | |
| |
| |
| |
| Variables | |
| |
| |
| |
| Scope | |
| |
| |
| |
| Symbol Table | |
| |
| |
| |
| Resolving References | |
| |
| |
| |
| Dynamic Scoping | |
| |
| |
| |
| Visibility | |
| |
| |
| |
| Overloading | |
| |
| |
| |
| Lifetime | |
| |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Types | |
| |
| |
| |
| Type Errors | |
| |
| |
| |
| Static and Dynamic Typing | |
| |
| |
| |
| Basic Types | |
| |
| |
| |
| Nonbasic Types | |
| |
| |
| |
| Enumerations | |
| |
| |
| |
| Pointers | |
| |
| |
| |
| Arrays and Lists | |
| |
| |
| |
| Strings | |
| |
| |
| |
| Structures | |
| |
| |
| |
| Variant Records and Unions | |
| |
| |
| |
| Recursive Data Types | |
| |
| |
| |
| Functions as Types | |
| |
| |
| |
| Type Equivalence | |
| |
| |
| |
| Subtypes | |
| |
| |
| |
| Polymorphism and Generics | |
| |
| |
| |
| Programmer-Defined Types | |
| |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Type Systems | |
| |
| |
| |
| Type System for Clite | |
| |
| |
| |
| Implicit Type Conversion | |
| |
| |
| |
| Formalizing the Clite Type System | |
| |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Semantics | |
| |
| |
| |
| Motivation | |
| |
| |
| |
| Expression Semantics | |
| |
| |
| |
| Notation | |
| |
| |
| |
| Associativity and Precedence | |
| |
| |
| |
| Short Circuit Evaluation | |
| |
| |
| |
| The Meaning of an Expression | |
| |
| |
| |
| Program State | |
| |
| |
| |
| Assignment Semantics | |
| |
| |
| |
| Multiple Assignment | |
| |
| |
| |
| Assignment Statements vs. Assignment Expressions | |
| |
| |
| |
| Copy vs. Reference Semantics | |
| |
| |
| |
| Control Flow Semantics | |
| |
| |
| |
| Sequence | |
| |
| |
| |
| Conditionals | |
| |
| |
| |
| Loops | |
| |
| |
| |
| Go To Controversy | |
| |
| |
| |
| Input/Output Semantics | |
| |
| |
| |
| Basic Concepts | |
| |
| |
| |
| Random Access Files | |
| |
| |
| |
| I/O Error Handling Semantics | |
| |
| |
| |
| Exception Handling Semantics | |
| |
| |
| |
| Strategies and Design Issues | |
| |
| |
| |
| Exception Handling in Ada, C++, and Java | |
| |
| |
| |
| Exceptions and Assertions | |
| |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Semantic Interpretation | |
| |
| |
| |
| State Transformations and Partial Functions | |
| |
| |
| |
| Semantics of Clite | |
| |
| |
| |
| Meaning of a Program | |
| |
| |
| |
| Statement Semantics | |
| |
| |
| |
| Expression Semantics | |
| |
| |
| |
| Expressions with Side Effects | |
| |
| |
| |
| Semantics with Dynamic Typing | |
| |
| |
| |
| A Formal Treatment of Semantics | |
| |
| |
| |
| State and State Transformation | |
| |
| |
| |
| Denotational Semantics of a Program | |
| |
| |
| |
| Denotational Semantics of Statements | |
| |
| |
| |
| Denotational Semantics of Expressions | |
| |
| |
| |
| Limits of Formal Semantic Models | |
| |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Functions | |
| |
| |
| |
| Basic Terminology | |
| |
| |
| |
| Function Call and Return | |
| |
| |
| |
| Parameters | |
| |
| |
| |
| Parameter Passing Mechanisms | |
| |
| |
| |
| Pass by Value | |
| |
| |
| |
| Pass by Reference | |
| |
| |
| |
| Pass by Value-Result and Result | |
| |
| |
| |
| Pass by Name | |
| |
| |
| |
| Parameter Passing in Ada | |
| |
| |
| |
| Activation Records | |
| |
| |
| |
| Recursive Functions | |
| |
| |
| |
| Run-Time Stack | |
| |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Function Implementation | |
| |
| |
| |
| Function Declaration and Call in Clite | |
| |
| |
| |
| Concrete Syntax | |
| |
| |
| |
| Abstract Syntax | |
| |
| |
| |
| Completing the Clite Type System | |
| |
| |
| |
| Semantics of Function Call and Return | |
| |
| |
| |
| Non-Void Functions | |
| |
| |
| |
| Side Effects Revisited | |
| |
| |
| |
| Formal Treatment of Types and Semantics | |
| |
| |
| |
| Type Maps for Clite | |
| |
| |
| |
| Formalizing the Type Rules for Clite | |
| |
| |
| |
| Formalizing the Semantics of Clite | |
| |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Memory Management | |
| |
| |
| |
| The Heap | |
| |
| |
| |
| Implementation of Dynamic Arrays | |
| |
| |
| |
| Heap Management Problems: Garbage | |
| |
| |
| |
| Garbage Collection | |
| |
| |
| |
| Reference Counting | |
| |
| |
| |
| Mark-Sweep | |
| |
| |
| |
| Copy Collection | |
| |
| |
| |
| Comparison of Strategies | |
| |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Imperative Programming | |
| |
| |
| |
| What Makes a Language Imperative? | |
| |
| |
| |
| Procedural Abstraction | |
| |
| |
| |
| Expressions and Assignment | |
| |
| |
| |
| Library Support for Data Structures | |
| |
| |
| |
| Imperative Programming and C | |
| |
| |
| |
| General Characteristics | |
| |
| |
| |
| Example: Grep | |
| |
| |
| |
| Example: Average | |
| |
| |
| |
| Example: Symbolic Differentiation | |
| |
| |
| |
| Imperative Programming and ADA | |
| |
| |
| |
| General Characteristics | |
| |
| |
| |
| Example: Average | |
| |
| |
| |
| Example: Matrix Multiplication | |
| |
| |
| |
| Imperative Programming and Perl | |
| |
| |
| |
| General Characteristics | |
| |
| |
| |
| Example: Grep | |
| |
| |
| |
| Example: Mailing Grades | |
| |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Object-Oriented Programming | |
| |
| |
| |
| Prelude: Abstract Data Types | |
| |
| |
| |
| The Object Model | |
| |
| |
| |
| Classes | |
| |
| |
| |
| Visibility and Information Hiding | |
| |
| |
| |
| Inheritance | |
| |
| |
| |
| Multiple Inheritance | |
| |
| |
| |
| Polymorphism | |
| |
| |
| |
| Templates | |
| |
| |
| |
| Abstract Classes | |
| |
| |
| |
| Interfaces | |
| |
| |
| |
| Virtual Method Table | |
| |
| |
| |
| Run-Time Type Identification | |
| |
| |
| |
| Reflection | |
| |
| |
| |
| Smalltalk | |
| |
| |
| |
| General Characteristics | |
| |
| |
| |
| Example: Polynomials | |
| |
| |
| |
| Example: Complex Numbers | |
| |
| |
| |
| Example: Bank Account | |
| |
| |
| |
| Java | |
| |
| |
| |
| Example: Symbolic Differentiation | |
| |
| |
| |
| Example: Backtracking | |
| |
| |
| |
| Python | |
| |
| |
| |
| General Characteristics | |
| |
| |
| |
| Example: Polynomials | |
| |
| |
| |
| Example: Fractions | |
| |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Functional Programming | |
| |
| |
| |
| Functions and the Lambda Calculus | |
| |
| |
| |
| Scheme | |
| |
| |
| |
| Expressions | |
| |
| |
| |
| Expression Evaluation | |
| |
| |
| |
| Lists | |
| |
| |
| |
| Elementary Values | |
| |
| |
| |
| Control Flow | |
| |
| |
| |
| Defining Functions | |
| |
| |
| |
| Let Expressions | |
| |
| |
| |
| Example: Semantics of Clite | |
| |
| |
| |
| Example: Symbolic Differentiation | |
| |
| |
| |
| Example: Eight Queens | |
| |
| |
| |
| Haskell | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Expressions | |
| |
| |
| |
| Lists and List Comprehensions | |
| |
| |
| |
| Elementary Types and Values | |
| |
| |
| |
| Control Flow | |
| |
| |
| |
| Defining Functions | |
| |
| |
| |
| Tuples | |
| |
| |
| |
| Example: Semantics of Clite | |
| |
| |
| |
| Example: Symbolic Differentiation | |
| |
| |
| |
| Example: Eight Queens | |
| |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Logic Programming | |
| |
| |
| |
| Logic and Horn Clauses | |
| |
| |
| |
| Resolution and Unification | |
| |
| |
| |
| Logic Programming in Prolog | |
| |
| |
| |
| Prolog Program Elements | |
| |
| |
| |
| Practical Aspects of Prolog | |
| |
| |
| |
| Prolog Examples | |
| |
| |
| |
| Symbolic Differentiation | |
| |
| |
| |
| Solving Word Puzzles | |
| |
| |
| |
| Natural Language Processing | |
| |
| |
| |
| Semantics of Clite | |
| |
| |
| |
| Eight Queens Problem | |
| |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Event-Driven Programming | |
| |
| |
| |
| Event-Driven Control | |
| |
| |
| |
| Model-View-Controller | |
| |
| |
| |
| Events in Java | |
| |
| |
| |
| Java GUI Applications | |
| |
| |
| |
| Event Handling | |
| |
| |
| |
| Mouse Clicks | |
| |
| |
| |
| Mouse Motion | |
| |
| |
| |
| Buttons | |
| |
| |
| |
| Labels, TextAreas, and TextFields | |
| |
| |
| |
| Combo Boxes | |
| |
| |
| |
| Three Examples | |
| |
| |
| |
| A Simple GUI Interface | |
| |
| |
| |
| Designing a Java Applet | |
| |
| |
| |
| Event-Driven Interactive Games | |
| |
| |
| |
| Other Event-Driven Applications | |
| |
| |
| |
| ATM Machine | |
| |
| |
| |
| Home Security System | |
| |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Concurrent Programming | |
| |
| |
| |
| Concurrency Concepts | |
| |
| |
| |
| History and Definitions | |
| |
| |
| |
| Thread Control and Communication | |
| |
| |
| |
| Races and Deadlocks | |
| |
| |
| |
| Synchronization Strategies | |
| |
| |
| |
| Semaphores | |
| |
| |
| |
| Monitors | |
| |
| |
| |
| Synchronization in Java | |
| |
| |
| |
| Java Threads | |
| |
| |
| |
| Examples | |
| |
| |
| |
| Interprocess Communication | |
| |
| |
| |
| IP Addresses, Ports, and Sockets | |
| |
| |
| |
| A Client-Server Example | |
| |
| |
| |
| Concurrency in Other Languages | |
| |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Program Correctness | |
| |
| |
| |
| Axiomatic Semantics | |
| |
| |
| |
| Fundamental Concepts | |
| |
| |
| |
| The Assignment Rule | |
| |
| |
| |
| Rules of Consequence | |
| |
| |
| |
| Correctness of the Max Function | |
| |
| |
| |
| Correctness of Programs with Loops | |
| |
| |
| |
| Perspectives on Formal Methods | |
| |
| |
| |
| Formal Methods Tools: JML | |
| |
| |
| |
| JML Exception Handling | |
| |
| |
| |
| Correctness of Object-Oriented Programs | |
| |
| |
| |
| Design By Contract | |
| |
| |
| |
| The Class Invariant | |
| |
| |
| |
| Example: Correctness of a Stack Application | |
| |
| |
| |
| Final Observations | |
| |
| |
| |
| Correctness of Functional Programs | |
| |
| |
| |
| Recursion and Induction | |
| |
| |
| |
| Examples of Structural Induction | |
| |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Definition of Clite | |
| |
| |
| |
| Lexical and Concrete Syntax of Clite | |
| |
| |
| |
| Abstract Syntax of Clite | |
| |
| |
| |
| Type System of Clite | |
| |
| |
| |
| Semantics of Clite | |
| |
| |
| |
| Adding Functions to Clite | |
| |
| |
| |
| Lexical and Concrete Syntax | |
| |
| |
| |
| Abstract Syntax | |
| |
| |
| |
| Type System | |
| |
| |
| |
| Semantics | |
| |
| |
| |
| Discrete Math Review | |
| |
| |
| |
| Sets and Relations | |
| |
| |
| |
| Graphs | |
| |
| |
| |
| Logic | |
| |
| |
| |
| Inference Rules and Direct Proof | |
| |
| |
| |
| Proof by Induction | |
| |
| |
| Glossary | |
| |
| |
| Bibliography | |
| |
| |
| Index | |