Programming Languages Concepts and Implementation
Title Page
Copyright
Dedication
Contents
Preface
About the Author
List of Figures
List of Tables
Part I Fundamentals
1 Introduction
1.1 Text Objectives
1.2 Chapter Objectives
1.3 The World of Programming Languages
1.3.1 Fundamental Questions
1.3.2 Bindings: Static and Dynamic
1.3.3 Programming Language Concepts
1.4 Styles of Programming
1.4.1 Imperative Programming
1.4.2 Functional Programming
1.4.3 Object-Oriented Programming
1.4.4 Logic/Declarative Programming
1.4.5 Bottom-up 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.7 What You Will Learn
1.8 Learning Outcomes
1.9 Thematic Takeaways
1.10 Chapter Summary
1.11 Notes and Further Reading
2 Formal Languages and Grammars
2.1 Chapter Objectives
2.2 Introduction to Formal Languages
2.3 Regular Expressions and Regular Languages
2.3.1 Regular Expressions
2.3.2 Finite-State Automata
2.3.3 Regular Languages
2.4 Grammars and BackusβNaur Form
2.4.1 Regular Grammars
2.5 Context-Free Languages and Grammars
2.6 Language Generation: Sentence Derivations
2.7 Language Recognition: Parsing
2.8 Syntactic Ambiguity
2.8.1 Modeling Some Semantics in Syntax
2.8.2 Parse Trees
2.9 Grammar Disambiguation
2.9.1 Operator Precedence
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.12 Thematic Take aways
2.13 Chapter Summary
2.14 Notes and Further Reading
3 Scanning and Parsing
3.1 Chapter Objectives
3.2 Scanning
3.3 Parsing
3.4 Recursive-Descent Parsing
3.4.1 A Complete Recursive-Descent Parser
3.4.2 A Language Generator
3.5 Bottom-up, Shift-Reduce Parsing and Parser Generators
3.5.1 A Complete Example in lex and yacc
3.6 PLY: Python Lex-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.8 Thematic Takeaways
3.9 Chapter Summary
3.10 Notes and Further Reading
4 Programming Language Implementation
4.1 Chapter Objectives
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
4.6 Thematic Takeaways
4.7 Chapter Summary
4.8 Notes and Further Reading
5 Functional Programming in Scheme
5.1 Chapter Objectives
5.2 Introduction to Functional Programming
5.2.1 Hallmarks of Functional Programming
5.2.2 Lambda Calculus
5.2.3 Lists in Functional Programming
5.3 Lisp
5.3.1 Introduction
5.3.2 Lists in Lisp
5.4 Scheme
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.5.1 List Representation
5.5.2 List-Box Diagrams
5.6 Functions on Lists
5.6.1 A List length Function
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.2 The letrec Expression
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 Advanced Techniques
5.10.1 More List Functions
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.13 Concurrency
5.14 Programming Project for Chapter 5
5.15 Thematic Takeaways
5.16 Chapter Summary
5.17 Notes and Further Reading
6 Binding and Scope
6.1 Chapter Objectives
6.2 Preliminaries
6.2.1 What Is a Closure?
6.2.2 Static Vis-Γ -Vis Dynamic Properties
6.3 Introduction
6.4 Static Scoping
6.4.1 Lexical Scoping
6.5 Lexical Addressing
6.6 Free or Bound Variables
6.7 Dynamic Scoping
6.8 Comparison of Static and Dynamic Scoping
6.9 Mixing Lexically and Dynamically Scoped Variables
6.10 The FUNARG Problem
6.10.1 The Downward FUNARG Problem
6.10.2 The Upward FUNARG Problem
6.10.3 Relationship Between Closures and Scope
6.10.4 Uses of Closures
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.11.1 Deep Binding
6.11.2 Shallow Binding
6.11.3 Ad Hoc Binding
6.12 Thematic Takeaways
6.13 Chapter Summary
6.14 Notes and Further Reading
Part II Types
7 Type Systems
7.1 Chapter Objectives
7.2 Introduction
7.3 Type Checking
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.5 Parametric Polymorphism
7.6 Operator/Function Overloading
7.7 Function Overriding
7.8 Static/Dynamic Typing Vis-Γ -Vis Explicit/Implicit Typing
7.9 Type Inference
7.10 Variable-Length Argument Lists in Scheme
7.11 Thematic Takeaways
7.12 Chapter Summary
7.13 Notes and Further Reading
8 Currying and Higher-Order Functions
8.1 Chapter Objectives
8.2 Partial Function Application
8.3 Currying
8.3.1 Curried Form
8.3.2 Currying and Uncurrying
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.3.7 ML Analogs
8.4 Putting It All Together: Higher-Order Functions
8.4.1 Functional Mapping
8.4.2 Functional Composition
8.4.3 Sections in Haskell
8.4.4 Folding Lists
8.4.5 Crafting Cleverly Conceived Functions with Curried HOFs
8.5 Analysis
8.6 Thematic Takeaways
8.7 Chapter Summary
8.8 Notes and Further Reading
9 Data Abstraction
9.1 Chapter Objectives
9.2 Aggregate Data Types
9.2.1 Arrays
9.2.2 Records
9.2.3 Undiscriminated Unions
9.2.4 Discriminated Unions
9.3 Inductive Data Types
9.4 Variant Records
9.4.1 Variant Records in Haskell
9.4.2 Variant Records in Scheme: (define-datatype ...) and (cases ...)
9.5 Abstract Syntax
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.7 Data Abstraction
9.8 Case Study: Environments
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.1 ML Summary
9.9.2 Haskell Summary
9.9.3 Comparison of ML and Haskell
9.9.4 Applications
9.9.5 Analysis
9.10 Thematic Takeaways
9.11 Chapter Summary
9.12 Notes and Further Reading
Part III Interpreter Implementation
10 Local Binding and Conditional Evaluation
10.1 Chapter Objectives
10.2 Checkpoint
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.1 Front End for Camille
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.7 Local Binding
10.8 Conditional Evaluation
10.9 Putting It All Together
10.10 Thematic Takeaways
10.11 Chapter Summary
10.12 Notes and Further Reading
11 Functions and Closures
11.1 Chapter Objectives
11.2 Non-recursive Functions
11.2.1 Adding Support for User-Defined Functions to Camille
11.2.2 Closures
11.2.3 Augmenting the evaluate_expr Function
11.2.4 A Simple Stack Object
11.3 Recursive Functions
11.3.1 Adding Support for Recursion in Camille
11.3.2 Recursive Environment
11.3.3 Augmenting evaluate_expr with New Variants
11.4 Thematic Takeaways
11.5 Chapter Summary
11.6 Notes and Further Reading
12 Parameter Passing
12.1 Chapter Objectives
12.2 Assignment Statement
12.2.1 Use of Nested lets to Simulate Sequential Evaluation
12.2.2 Illustration of Pass-by-Value in Camille
12.2.3 Reference Data Type
12.2.4 Environment Revisited
12.2.5 Stack Object Revisited
12.3 Survey of Parameter-Passing Mechanisms
12.3.1 Pass-by-Value
12.3.2 Pass-by-Reference
12.3.3 Pass-by-Result
12.3.4 Pass-by-Value-Result
12.3.5 Summary
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 Lazy Evaluation
12.5.1 Introduction
12.5.2 Γ-Reduction
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.5.9 Purity and Consistency
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.10 Thematic Takeaways
12.11 Chapter Summary
12.12 Notes and Further Reading
Part IV Other Styles of Programming
13 Control and Exception Handling
13.1 Chapter Objectives
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.1 Nonlocal Exits
13.3.2 Breakpoints
13.3.3 First-Class Continuations in Ruby
13.4 Other Mechanisms for Global Transfer of Control
13.4.1 The goto Statement
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.1 Function Calls
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 Control Abstraction
13.6.1 Coroutines
13.6.2 Applications of First-Class Continuations
13.6.3 The Power of First-Class Continuations
13.7 Tail Recursion
13.7.1 Recursive Control Behavior
13.7.2 Iterative Control Behavior
13.7.3 Tail-Call Optimization
13.7.4 Space Complexity and Lazy Evaluation
13.8 Continuation-Passing Style
13.8.1 Introduction
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.8.5 call/cc Vis-Γ -Vis CPS
13.9 Callbacks
13.10 CPS Transformation
13.10.1 Defining call/cc in Continuation-Passing Style
13.11 Thematic Takeaways
13.12 Chapter Summary
13.13 Notes and Further Reading
14 Logic Programming
14.1 Chapter Objectives
14.2 Propositional Calculus
14.3 First-Order Predicate Calculus
14.3.1 Representing Knowledge as Predicates
14.3.2 Conjunctive Normal Form
14.4 Resolution
14.4.1 Resolution in Propositional Calculus
14.4.2 Resolution in Predicate Calculus
14.5 From Predicate Calculus to Logic Programming
14.5.1 Clausal Form
14.5.2 Horn Clauses
14.5.3 Conversion Examples
14.5.4 Motif of Logic Programming
14.5.5 Resolution with Propositions in Clausal Form
14.5.6 Formalism Gone Awry
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 Going Further in Prolog
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.6 Arithmetic in Prolog
14.7.7 Negationas Failure in Prolog
14.7.8 Graphs
14.7.9 Analogs Between Prolog and an RDBMS
14.8 Imparting More Control in Prolog: Cut
14.9 Analysis of Prolog
14.9.1 Prolog Vis-Γ -Vis Predicate Calculus
14.9.2 Reflection in Prolog
14.9.3 Metacircular Prolog Interpreter and WAM
14.10 The CLIPS Programming Language
14.10.1 Asserting Facts and Rules
14.10.2 Variables
14.10.3 Templates
14.10.4 Conditional Facts in Rules
14.11 Applications of Logic Programming
14.11.1 Natural Language Processing
14.11.2 Decision Trees
14.12 Thematic Takeaways
14.13 Chapter Summary
14.14 Notes and Further Reading
15 Conclusion
15.1 Language Themes Revisited
15.2 Relationship of Concepts
15.3 More Advanced Concepts
15.4 Bottom-up Programming
15.5 Further Reading
Appendix A Python Primer
A.1 Appendix Objective
A.2 Introduction
A.3 Data Types
A.4 Essential Operators and Expressions
A.5 Lists
A.6 Tuples
A.7 User-Defined Functions
A.7.1 Simple User-Defined Functions
A.7.2 Positional Vis-Γ -Vis Keyword Arguments
A.7.3 Lambda Functions
A.7.4 Lexical Closures
A.7.5 More User-Defined Functions
A.7.6 Local Binding and Nested Functions
A.7.7 Mutual Recursion
A.7.8 Putting It All Together: Mergesort
A.8 Object-Oriented Programming in Python
A.9 Exception Handling
A.10 Thematic Takeaway
A.11 Appendix Summary
A.12 Notes and Further Reading
Appendix B Introduction to ML (Online)
B.1 Appendix Objective
B.2 Introduction
B.3 Primitive Types
B.4 Essential Operators and Expressions
B.5 Running an ML Program
B.6 Lists
B.7 Tuples
B.8 User-Defined Functions
B.8.1 Simple User-Defined Functions
B.8.2 Lambda Functions
B.8.3 Pattern-Directed Invocation
B.8.4 Local Binding and Nested Functions: let Expressions
B.8.5 Mutual Recursion
B.8.6 Putting It All Together: Mergesort
B.9 Declaring Types
B.9.1 Inferredor Deduced
B.9.2 Explicitly Declared
B.10 Structures
B.11 Exceptions
B.12 Input and Output
B.12.1 Input
B.12.2 Parsing an Input File
B.12.3 Output
B.13 Thematic Takeaways
B.14 Appendix Summary
B.15 Notes and Further Reading
Appendix C Introduction to Haskell (Online)
C.1 Appendix Objective
C.2 Introduction
C.3 Primitive Types
C.4 Type Variables, Type Classes, and Qualified Types
C.5 Essential Operators and Expressions
C.6 Running a Haskell Program
C.7 Lists
C.8 Tuples
C.9 User-Defined Functions
C.9.1 Simple User-Defined Functions
C.9.2 Lambda Functions
C.9.3 Pattern-Directed Invocation
C.9.4 Local Binding and Nested Functions: let Expressions
C.9.5 Mutual Recursion
C.9.6 Putting It All Together: Mergesort
C.10 Declaring Types
C.10.1 Inferredor Deduced
C.10.2 Explicitly Declared
C.11 Thematic Takeaways
C.12 Appendix Summary
C.13 Notes and Further Reading
Appendix D Getting Started with the Camille Programming Language (Online)
D.1 Appendix Objective
D.2 Grammar
D.3 Installation
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.5.5 Chapter 12 Modules: Advanced (Parameter Passing, Including Lazy Evaluation) and Imperative (Statements and Sequential Evaluation)
D.6 Example Usage: Non-interactively and Interactively (CLI)
D.7 Solutions to Programming Exercises in Chapters 10β12
D.8 Notes and Further Reading
Appendix E Camille Grammar and Language (Online)
E.1 Appendix Objective
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
E.6 Camille 4.X: Sequential Execution
Bibliography
Index
