Foundations of programming languages

Preface
	Acknowledgements
	For Teachers
Contents
1 Introduction
	1.1 Historical Perspective
	1.2 Models of Computation
		1.2.1 The Imperative Model
		1.2.2 The Functional Model
		1.2.3 The Logic Model
	1.3 The Origins of a Few Programming Languages
		1.3.1 A Brief History of C and C++
		1.3.2 A Brief History of Java
		1.3.3 A Brief History of Python
		1.3.4 A Brief History of Standard ML
		1.3.5 A Brief History of Prolog
	1.4 Language Implementation
		1.4.1 Compilation
		1.4.2 Interpretation
		1.4.3 Virtual Machines
	1.5 Types and Type Checking
	1.6 Chapter Summary
	1.7 Review Questions
	1.8 Solutions to Practice Problems
		1.8.1 Solution to Practice Problem 1.1
		1.8.2 Solution to Practice Problem 1.2
		1.8.3 Solution to Practice Problem 1.3
		1.8.4 Solution to Practice Problem 1.4
		1.8.5 Solution to Practice Problem 1.5
2 Syntax
	2.1 Terminology
	2.2 Backus Naur Form (BNF)
		2.2.1 BNF Examples
		2.2.2 Extended BNF (EBNF)
	2.3 Context-Free Grammars
		2.3.1 The Infix Expression Grammar
	2.4 Derivations
		2.4.1 A Derivation
		2.4.2 Types of Derivations
		2.4.3 Prefix Expressions
		2.4.4 The Prefix Expression Grammar
	2.5 Parse Trees
	2.6 Abstract Syntax Trees
	2.7 Lexical Analysis
		2.7.1 The Language of Regular Expressions
		2.7.2 Finite State Machines
		2.7.3 Lexer Generators
	2.8 Parsing
	2.9 Top-Down Parsers
		2.9.1 An LL(1) Grammar
		2.9.2 A Non-LL(1) Grammar
		2.9.3 An LL(1) Infix Expression Grammar
	2.10 Bottom-Up Parsers
		2.10.1 Parsing an Infix Expression
	2.11 Ambiguity in Grammars
	2.12 Other Forms of Grammars
	2.13 Limitations of Syntactic Definitions
	2.14 Chapter Summary
	2.15 Review Questions
	2.16 Exercises
	2.17 Solutions to Practice Problems
		2.17.1 Solution to Practice Problem 2.1
		2.17.2 Solution to Practice Problem 2.2
		2.17.3 Solution to Practice Problem 2.3
		2.17.4 Solution to Practice Problem 2.4
		2.17.5 Solution to Practice Problem 2.5
		2.17.6 Solution to Practice Problem 2.6
		2.17.7 Solution to Practice Problem 2.7
		2.17.8 Solution to Practice Problem 2.8
		2.17.9 Solution to Practice Problem 2.9
		2.17.10 Solution to Practice Problem 2.10
		2.17.11 Solution to Practice Problem 2.11
3 Assembly Language
	3.1 Overview of the JCoCo VM
	3.2 Getting Started
	3.3 Input/Output
	3.4 If-Then-Else Statements
		3.4.1 If-Then Statements
	3.5 While Loops
	3.6 Exception Handling
	3.7 List Constants
	3.8 Calling a Method
	3.9 Iterating Over a List
	3.10 Range Objects and Lazy Evaluation
	3.11 Functions and Closures
	3.12 Recursion
	3.13 Support for Classes and Objects
		3.13.1 Inheritance
		3.13.2 Dynamically Created Classes
	3.14 Chapter Summary
	3.15 Review Questions
	3.16 Exercises
	3.17 Solutions to Practice Problems
		3.17.1 Solution to Practice Problem 3.1
		3.17.2 Solution to Practice Problem 3.2
		3.17.3 Solution to Practice Problem 3.3
		3.17.4 Solution to Practice Problem 3.4
		3.17.5 Solution to Practice Problem 3.5
		3.17.6 Solution to Practice Problem 3.6
		3.17.7 Solution to Practice Problem 3.7
		3.17.8 Solution to Practice Problem 3.8
		3.17.9 Solution to Practice Problem 3.9
		3.17.10 Solution to Practice Problem 3.10
		3.17.11 Solution to Practice Problem 3.11
		3.17.12 Solution to Practice Problem 3.12
4 Object-Oriented Programming
	4.1 The Java Environment
	4.2 The C++ Environment
		4.2.1 The Macro Processor
		4.2.2 The Make Tool
	4.3 Namespaces
	4.4 Dynamic Linking
	4.5 Defining the Main Function
	4.6 I/O Streams
	4.7 Garbage Collection
	4.8 Threading
	4.9 The PyToken Class
		4.9.1 The C++ PyToken Class
	4.10 Inheritance and Polymorphism
	4.11 Interfaces and Adapters
	4.12 Functions as Values
	4.13 Anonymous Inner Classes
	4.14 Type Casting and Generics
	4.15 Auto-Boxing and Unboxing
	4.16 Exception Handling in Java and C++
	4.17 Signals
	4.18 JCoCo in Depth
	4.19 The Scanner
	4.20 The Parser
	4.21 The Assembler
	4.22 ByteCode
	4.23 JCoCo\'s Class and Interface Type Hierarchy
	4.24 Code
	4.25 Functions
	4.26 Classes
	4.27 Methods
	4.28 JCoCo Exceptions and Tracebacks
	4.29 Magic Methods
	4.30 Dictionaries
		4.30.1 Two New Classes
		4.30.2 Two New Types
		4.30.3 Two New Instructions
	4.31 Chapter Summary
	4.32 Review Questions
	4.33 Exercises
	4.34 Solutions to Practice Problems
		4.34.1 Solution to Practice Problem 4.1
		4.34.2 Solution to Practice Problem 4.2
		4.34.3 Solution to Practice Problem 4.3
		4.34.4 Solution to Practice Problem 4.4
		4.34.5 Solution to Practice Problem 4.5
		4.34.6 Solution to Practice Problem 4.6
		4.34.7 Solution to Practice Problem 4.7
		4.34.8 Solution to Practice Problem 4.8
		4.34.9 Solution to Practice Problem 4.9
5 Functional Programming
	5.1 Imperative Versus Functional Programming
	5.2 The Lambda Calculus
		5.2.1 Normal Form
		5.2.2 Problems with Applicative Order Reduction
	5.3 Getting Started with Standard ML
	5.4 Expressions, Types, Structures, and Functions
	5.5 Recursive Functions
	5.6 Characters, Strings, and Lists
	5.7 Pattern Matching
	5.8 Tuples
	5.9 Let Expressions and Scope
	5.10 Datatypes
	5.11 Parameter Passing in Standard ML
	5.12 Efficiency of Recursion
	5.13 Tail Recursion
	5.14 Currying
	5.15 Anonymous Functions
	5.16 Higher-Order Functions
		5.16.1 Composition
		5.16.2 Map
		5.16.3 Reduce or Foldright
		5.16.4 Filter
	5.17 Continuation Passing Style
	5.18 Input and Output
	5.19 Programming with Side-effects
		5.19.1 Variables in Standard ML
		5.19.2 Sequential Execution
		5.19.3 Iteration
	5.20 Exception Handling
	5.21 Encapsulation in ML
		5.21.1 Signatures
		5.21.2 Implementing a Signature
	5.22 Type Inference
	5.23 Building a Prefix Calculator Interpreter
		5.23.1 The Prefix Calc Parser
		5.23.2 The AST Evaluator
		5.23.3 Imperative Programming Observations
	5.24 Chapter Summary
	5.25 Exercises
	5.26 Solutions to Practice Problems
		5.26.1 Solution to Practice Problem 5.1
		5.26.2 Solution to Practice Problem 5.2
		5.26.3 Solution to Practice Problem 5.3
		5.26.4 Solution to Practice Problem 5.4
		5.26.5 Solution to Practice Problem 5.5
		5.26.6 Solution to Practice Problem 5.6
		5.26.7 Solution to Practice Problem 5.7
		5.26.8 Solution to Practice Problem 5.8
		5.26.9 Solution to Practice Problem 5.9
		5.26.10 Solution to Practice Problem 5.10
		5.26.11 Solution to Practice Problem 5.11
		5.26.12 Solution to Practice Problem 5.12
		5.26.13 Solution to Practice Problem 5.13
		5.26.14 Solution to Practice Problem 5.14
		5.26.15 Solution to Practice Problem 5.15
		5.26.16 Solution to Practice Problem 5.16, see Fig.5.27
		5.26.17 Solution to Practice Problem 5.17
		5.26.18 Solution to Practice Problem 5.18
		5.26.19 Solution to Practice Problem 5.19
		5.26.20 Solution to Practice Problem 5.20
		5.26.21 Solution to Practice Problem 5.21
		5.26.22 Solution to Practice Problem 5.22
		5.26.23 Solution to Practice Problem 5.23
		5.26.24 Solution to Practice Problem 5.24
6 Compiling Standard ML
	6.1 ML-lex
	6.2 The Small AST Definition
	6.3 Using ML-yacc
	6.4 Compiling and Running the Compiler
	6.5 Function Calls
	6.6 Let Expressions
	6.7 Unary Negation
	6.8 If-Then-Else Expressions
	6.9 Short-Circuit Logic
	6.10 Defining Functions
		6.10.1 Curried Functions
		6.10.2 Mutually Recursive Functions
	6.11 Reference Variables
	6.12 Chapter Summary
	6.13 Review Questions
	6.14 Exercises
	6.15 Solutions to Practice Problems
		6.15.1 Solution to Practice Problem 6.1
		6.15.2 Solution to Practice Problem 6.2
		6.15.3 Solution to Practice Problem 6.3
7 Logic Programming
	7.1 Getting Started with Prolog
	7.2 Fundamentals
	7.3 The Prolog Program
	7.4 Lists
	7.5 The Accumulator Pattern
	7.6 Built-In Predicates
	7.7 Unification and Arithmetic
	7.8 Input and Output
	7.9 Structures
	7.10 Parsing in Prolog
		7.10.1 Difference Lists
	7.11 Prolog Grammar Rules
	7.12 Building an AST
	7.13 Attribute Grammars
		7.13.1 Synthesized Versus Inherited
	7.14 Chapter Summary
	7.15 Review Questions
	7.16 Exercises
	7.17 Solutions to Practice Problems
		7.17.1 Solution to Practice Problem 7.1
		7.17.2 Solution to Practice Problem 7.2
		7.17.3 Solution to Practice Problem 7.3
		7.17.4 Solution to Practice Problem 7.4
		7.17.5 Solution to Practice Problem 7.5
		7.17.6 Solution to Practice Problem 7.6
		7.17.7 Solution to Practice Problem 7.7
		7.17.8 Solution to Practice Problem 7.8
		7.17.9 Solution to Practice Problem 7.9
		7.17.10 Solution to Practice Problem 7.10
		7.17.11 Solution to Practice Problem 7.11 (See Fig.7.13)
		7.17.12 Solution to Practice Problem 7.12
8 Standard ML Type Inference
	8.1 Why Static Type Inference?
		8.1.1 Exception Program
		8.1.2 A Bad Function Call
	8.2 Type Inference Rules
	8.3 Using Prolog
	8.4 The Type Environment
	8.5 Integers, Strings, and Boolean Constants
	8.6 List and Tuple Constants
	8.7 Identifiers
	8.8 Function Application
		8.8.1 Instantiation
	8.9 Let Expressions
	8.10 Patterns
	8.11 Matches
	8.12 Anonymous Functions
	8.13 Sequential Execution
	8.14 If-Then and While-Do
	8.15 Exception Handling
	8.16 Chapter Summary
	8.17 Review Questions
	8.18 Exercises
	8.19 Solutions to Practice Problems
		8.19.1 Solution to Practice Problem 8.1
		8.19.2 Solution to Practice Problem 8.2
		8.19.3 Solution to Practice Problem 8.3
9 Appendix A:  The JCoCo Virtual Machine Specification
	9.1 Types
	9.2 JCoCo Magic and Attr Methods
	9.3 Global Built-In Functions
	9.4 Virtual Machine Instructions
	9.5 Arithmetic Instructions
	9.6 Load and Store Instructions
	9.7 List, Tuple, and Dictionary Instructions
	9.8 Stack Manipulation Instructions
	9.9 Conditional and Iterative Execution Instructions
	9.10 Function Execution Instructions
	9.11 Special Instructions
10 Appendix B: The Standard ML Basis Library
	10.1 The Bool Structure
	10.2 The Int Structure
	10.3 The Real Structure
	10.4 The Char Structure
	10.5 The String Structure
	10.6 The List Structure
	10.7 The Array Structure
	10.8 The TextIO Structure
Bibliography