Contents
1.3 The World of Programming Languages
1.3.2 Bindings: Static and Dynamic
1.3.3 Programming Language Concepts
1.4.3 Object-Oriented Programming
1.4.4 Logic/Declarative Programming
1.4.6 Synthesis: Beyond Paradigms
1.4.7 Language Evaluation Criteria
1.4.8 Thought Process for Problem Solving
1.5 Factors Influencing Language Development
1.6 Recurring Themes in the Study of Languages
1.11 Notes and Further Reading
2 Formal Languages and Grammars
2.2 Introduction to Formal Languages
2.3 Regular Expressions and Regular Languages
2.4 Grammars and Backus–Naur Form
2.5 Context-Free Languages and Grammars
2.6 Language Generation: Sentence Derivations
2.7 Language Recognition: Parsing
2.8.1 Modeling Some Semantics in Syntax
2.9.2 Associativity of Operators
2.9.3 The Classical Dangling else Problem
2.10 Extended Backus–Naur Form
2.11 Context-Sensitivity and Semantics
2.14 Notes and Further Reading
3.4.1 A Complete Recursive-Descent Parser
3.5 Bottom-up, Shift-Reduce Parsing and Parser Generators
3.5.1 A Complete Example in lex and yacc
3.6.1 A Complete Example in PLY
3.6.2 Camille Scanner and Parser Generators in PLY
3.7 Top-down Vis-à-Vis Bottom-up Parsing
3.10 Notes and Further Reading
4 Programming Language Implementation
4.2 Interpretation Vis-à-Vis Compilation
4.3 Run-Time Systems: Methods of Executions
4.4 Comparison of Interpreters and Compilers
4.5 Influence of Language Goals on Implementation
5 Functional Programming in Scheme
5.2 Introduction to Functional Programming
5.2.1 Hallmarks of Functional Programming
5.2.3 Lists in Functional Programming
5.4.1 An Interactive and Illustrative Session with Scheme
5.4.2 Homoiconicity: No Distinction Between Program Code and Data
5.5 cons Cells: Building Blocks of Dynamic Memory Structures
5.6.2 Run-Time Complexity: append and reverse
5.6.3 The Difference Lists Technique
5.7 Constructing Additional Data Structures
5.7.1 A Binary Tree Abstraction
5.7.2 A Binary Search Tree Abstraction
5.8 Scheme Predicates as Recursive-Descent Parsers
5.8.1 atom?, list-of-atoms?, and list-of-numbers?
5.8.2 Factoring out the list-of Pattern
5.9 Local Binding: let, let*, and letrec
5.9.1 The let and let* Expressions
5.9.3 Using let and letrec to Define a Local Function
5.9.4 Other Languages Supporting Functional Programming: ML and Haskell
5.10.2 Eliminating Expression Recomputation
5.10.3 Avoiding Repassing Constant Arguments Across Recursive Calls
5.11 Languages and Software Engineering
5.11.1 Building Blocks as Abstractions
5.11.2 Language Flexibility Supports Program Modification
5.11.3 Malleable Program Design
5.11.4 From Prototype to Product
5.12 Layers of Functional Programming
5.14 Programming Project for Chapter 5
5.17 Notes and Further Reading
6.2.2 Static Vis-à-Vis Dynamic Properties
6.8 Comparison of Static and Dynamic Scoping
6.9 Mixing Lexically and Dynamically Scoped Variables
6.10.1 The Downward FUNARG Problem
6.10.2 The Upward FUNARG Problem
6.10.3 Relationship Between Closures and Scope
6.10.5 The Upward and Downward FUNARG Problem in a Single Function
6.10.6 Addressing the FUNARG Problem
6.11 Deep, Shallow, and Ad Hoc Binding
6.14 Notes and Further Reading
7.4 Type Conversion, Coercion, and Casting
7.4.1 Type Coercion: Implicit Conversion
7.4.2 Type Casting: Explicit Conversion
7.4.3 Type Conversion Functions: Explicit Conversion
7.6 Operator/Function Overloading
7.8 Static/Dynamic Typing Vis-à-Vis Explicit/Implicit Typing
7.10 Variable-Length Argument Lists in Scheme
7.13 Notes and Further Reading
8 Currying and Higher-Order Functions
8.2 Partial Function Application
8.3.3 The curry and uncurry Functions in Haskell
8.3.4 Flexibility in Curried Functions
8.3.5 All Built-in Functions in Haskell Are Curried
8.3.6 Supporting Curried Form Through First-Class Closures
8.4 Putting It All Together: Higher-Order Functions
8.4.5 Crafting Cleverly Conceived Functions with Curried HOFs
9.4.1 Variant Records in Haskell
9.4.2 Variant Records in Scheme: (define-datatype ...) and (cases ...)
9.6 Abstract-Syntax Tree for Camille
9.6.1 Camille Abstract-Syntax Tree Data Type: TreeNode
9.6.2 Camille Parser Generator with Tree Builder
9.8.1 Choices of Representation
9.8.2 Closure Representation in Scheme
9.8.3 Closure Representation in Python
9.8.4 Abstract-Syntax Representation in Python
9.9 ML and Haskell: Summaries, Comparison, Applications, and Analysis
9.9.3 Comparison of ML and Haskell
9.12 Notes and Further Reading
Part III Interpreter Implementation
10 Local Binding and Conditional Evaluation
10.3 Overview: Learning Language Concepts Through Interpreters
10.4 Preliminaries: Interpreter Essentials
10.4.1 Expressed Values Vis-à-Vis Denoted Values
10.4.2 Defined Language Vis-à-Vis Defining Language
10.5 The Camille Grammar and Language
10.6 A First Camille Interpreter
10.6.2 Simple Interpreter for Camille
10.6.3 Abstract-Syntax Trees for Arguments Lists
10.6.4 REPL: Read-Eval-Print Loop
10.6.5 Connecting the Components
10.6.6 How to Run a Camille Program
10.12 Notes and Further Reading
11.2.1 Adding Support for User-Defined Functions to Camille
11.2.3 Augmenting the evaluate_expr Function
11.3.1 Adding Support for Recursion in Camille
11.3.3 Augmenting evaluate_expr with New Variants
11.6 Notes and Further Reading
12.2.1 Use of Nested lets to Simulate Sequential Evaluation
12.2.2 Illustration of Pass-by-Value in Camille
12.3 Survey of Parameter-Passing Mechanisms
12.4 Implementing Pass-by-Reference in the Camille Interpreter
12.4.1 Revised Implementation of References
12.4.2 Reimplementation of the evaluate_operand Function
12.5.3 C Macros to Demonstrate Pass-by-Name: β-Reduction Examples
12.5.4 Two Implementations of Lazy Evaluation
12.5.5 Implementing Lazy Evaluation: Thunks
12.5.6 Lazy Evaluation Enables List Comprehensions
12.5.7 Applications of Lazy Evaluation
12.5.8 Analysis of Lazy Evaluation
12.6 Implementing Pass-by-Name/Need in Camille: Lazy Camille
12.7 Sequential Execution in Camille
12.8 Camille Interpreters: A Retrospective
12.9 Metacircular Interpreters
12.12 Notes and Further Reading
Part IV Other Styles of Programming
13 Control and Exception Handling
13.2 First-Class Continuations
13.2.1 The Concept of a Continuation
13.2.2 Capturing First-Class Continuations: call/cc
13.3 Global Transfer of Control with Continuations
13.3.3 First-Class Continuations in Ruby
13.4 Other Mechanisms for Global Transfer of Control
13.4.2 Capturing and Restoring Control Context in C: setjmp and longjmp
13.5 Levels of Exception Handling in Programming Languages: A Summary
13.5.2 Lexically Scoped Exceptions: break and continue
13.5.3 Stack Unwinding/Crawling
13.5.4 Dynamically Scoped Exceptions: Exception-Handling Systems
13.5.5 First-Class Continuations
13.6.2 Applications of First-Class Continuations
13.6.3 The Power of First-Class Continuations
13.7.1 Recursive Control Behavior
13.7.2 Iterative Control Behavior
13.7.4 Space Complexity and Lazy Evaluation
13.8 Continuation-Passing Style
13.8.2 A Growing Stack or a Growing Continuation
13.8.3 An All-or-Nothing Proposition
13.8.4 Trade-off Between Time and Space Complexity
13.10.1 Defining call/cc in Continuation-Passing Style
13.13 Notes and Further Reading
14.3 First-Order Predicate Calculus
14.3.1 Representing Knowledge as Predicates
14.3.2 Conjunctive Normal Form
14.4.1 Resolution in Propositional Calculus
14.4.2 Resolution in Predicate Calculus
14.5 From Predicate Calculus to Logic Programming
14.5.4 Motif of Logic Programming
14.5.5 Resolution with Propositions in Clausal Form
14.6 The Prolog Programming Language
14.6.1 Essential Prolog: Asserting Facts and Rules
14.6.2 Casting Horn Clauses in Prolog Syntax
14.6.3 Running and Interacting with a Prolog Program
14.6.4 Resolution, Unification, and Instantiation
14.7.1 Program Control in Prolog: A Binary Tree Example
14.7.2 Lists and Pattern Matching in Prolog
14.7.3 List Predicates in Prolog
14.7.4 Primitive Nature of append
14.7.5 Tracing the Resolution Process
14.7.7 Negation as Failure in Prolog
14.7.9 Analogs Between Prolog and an RDBMS
14.8 Imparting More Control in Prolog: Cut
14.9.1 Prolog Vis-à-Vis Predicate Calculus
14.9.3 Metacircular Prolog Interpreter and WAM
14.10 The CLIPS Programming Language
14.10.1 Asserting Facts and Rules
14.10.4 Conditional Facts in Rules
14.11 Applications of Logic Programming
14.11.1 Natural Language Processing
14.14 Notes and Further Reading
15.1 Language Themes Revisited
A.4 Essential Operators and Expressions
A.7.1 Simple User-Defined Functions
A.7.2 Positional Vis-à-Vis Keyword Arguments
A.7.5 More User-Defined Functions
A.7.6 Local Binding and Nested Functions
A.7.8 Putting It All Together: Mergesort
A.8 Object-Oriented Programming in Python
A.12 Notes and Further Reading
Appendix B Introduction to ML (Online)
B.4 Essential Operators and Expressions
B.8.1 Simple User-Defined Functions
B.8.3 Pattern-Directed Invocation
B.8.4 Local Binding and Nested Functions: let Expressions
B.8.6 Putting It All Together: Mergesort
B.15 Notes and Further Reading
Appendix C Introduction to Haskell (Online)
C.4 Type Variables, Type Classes, and Qualified Types
C.5 Essential Operators and Expressions
C.9.1 Simple User-Defined Functions
C.9.3 Pattern-Directed Invocation
C.9.4 Local Binding and Nested Functions: let Expressions
C.9.6 Putting It All Together: Mergesort
C.13 Notes and Further Reading
Appendix D Getting Started with the Camille Programming Language (Online)
D.4 Git Repository Structure and Setup
D.5 How to Use Camille in a Programming Languages Course
D.5.1 Module 0: Front End (Scanner and Parser)
D.5.2 Chapter 10 Module: Introduction (Local Binding and Conditionals)
D.5.3 Configuring the Language
D.5.4 Chapter 11 Module: Intermediate (Functions and Closures)
D.6 Example Usage: Non-interactively and Interactively (CLI)
D.7 Solutions to Programming Exercises in Chapters 10–12
Appendix E Camille Grammar and Language (Online)
E.2 Camille 0.1: Numbers and Primitives
E.3 Camille 1.x: Local Binding and Conditional Evaluation
E.4 Camille 2.x: Non-recursive and Recursive Functions
E.5 Camille 3.x: Variable Assignment and Support for Arrays