| |
| |
| |
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 | |