Welcome!

Welcome to Foundations of Programming Languages Second Edition by Kent D. Lee. If you are looking for the First Edition website, please go to the address https://kentdlee.github.io/PL1. This text, available from Springer, covers material on the design and implementation of programming languages, focusing on the three paradigms of prorgramming: imperative, functional, and logic programming.

Concepts covered in the text include syntax specification, lexical analysis, parsing, abstract syntax, compilation, disassembly, interpretation, functional programming, logic programming, type inference, and type inference rules. The text covers several programming languages including assembly language programming, C++, Standard ML, and Prolog.

This text uses and extends the JCoCo Virtual Machine. JCoCo is based on the Python Virtual Machine version 3.2. JCoCo, and its Python disassember, were written to illustrate assembly language programming on a virtual machine. The text both uses JCoCo so students can learn about assembly language programming, and extends JCoCo so students can learn about virtual machine implementations. The JCoCo website describes the JCoCo virtual machine and the Github website http://github.com/kentdlee/JCoCo provides the source code for JCoCo.

An older C++ version of the CoCo code is available at https://kentdlee.github.io/CoCoPages.

In addition, this text uses JCoCo/CoCo as a target language for implementing a compiler of Standard ML. The code for this project is available on Github at http://github.com/kentdlee/MLComp. The text extends the MLComp compiler to compile a robust subset of Standard ML.

The final chapter of this text covers type inference in Standard ML and provides the description and partial implementation of the Standard ML type inference system written in Prolog. This code is included in the MLComp Github project. The text extends the type checker to cover a more complete subset of the language.

Solutions to JCoCo and MLComp can be provided to instructors of qualified universities or colleges. These solutions cover chapters 4, 6, and 8 of the text. In addition, solutions to exercises from chapters 1, 2, 3, 5 and 7 can be provided to teachers upon request. Teachers must provide proof that they are teaching at a university or college.

This website provides access to figures and example code from the text as well as practice problems, review questions, and exercises.

Errata

Unfortunately there are several errata in the second edition. Most are minor and were introduced when removing some formatting from the first edition. Here they are in order of the textbook

• Page 230, Solution to Practice Problem 5.8 is correct on these web pages.
• Page 231, Solution to Practice Problem 5.10 is correct on these web pages.
• Page 242, fig. 6.5 is correct on these web pages.
• Page 268, fig. 6.34 caption should read “test7.sml”.
• Page 271, figure 6.40 should be as given on these web pages.
• Page 271, figure 6.41 should be as given on these web pages.
• Page 275, exercise 7, the example code is correct on these web pages and in test20.sml.
• Page 329, review question 8, the example code is correct on these web pages.
• Page 330, exercise 1, the sample program is correct on these web pages and in test20.sml.
• Page 331, exercise 3, the sample program is correct on these web pages and in test12.sml.

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 Python
    • 1.3.3. A Brief History of Java
    • 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. PDA
    • 2.10.2. 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.2.1. Running the Disassembler
    • 3.2.2. Running JCoCo
  • 3.3. Input/Output
    • 3.3.1. Python I/O
    • 3.3.2. CoCo I/O
  • 3.4. If-Then-Else Statements
    • 3.4.1. Assembled CoCo
    • 3.4.2. If-Then Statements
    • 3.4.3. CoCo If-Then Assembly
  • 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.11.1. Nested Functions Assembly
    • 3.11.2. Nested Function
  • 3.12. Recursion
    • 3.12.1. CoCo Recursion Assembly
  • 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. Example 4.1
    • 4.2.2. The Macro Processor
    • 4.2.3. The Make Tool
  • 4.3. Namespaces
    • 4.3.1. Example 4.2
  • 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.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. Standard ML
  • 5.1. Imperative vs 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. Variable Declarations
    • 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 Caclculator 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
    • 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.1.1. Example 6.1
  • 6.2. The Small AST Definition
  • 6.3. Using ML-yacc
    • 6.3.1. Example 6.3
    • 6.3.2. Example 6.4
  • 6.4. Compiling and Running the Compiler
    • 6.4.1. Example 6.5
    • 6.4.2. Example 6.6
  • 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. Prolog
  • 7.1. Getting Started with Prolog
    • 7.1.1. Example 7.2
  • 7.2. Fundamentals
    • 7.2.1. Example 7.3
    • 7.2.2. Example 7.4
  • 7.3. The Prolog Program
    • 7.3.1. Example 7.5
  • 7.4. Lists
    • 7.4.1. Example 7.6
    • 7.4.2. Example 7.7
  • 7.5. The Accumulator Pattern
  • 7.6. Built-in Predicates
  • 7.7. Unification and Arithmetic
  • 7.8. Input and Output
    • 7.8.1. Example 7.8
    • 7.8.2. Example 7.9
  • 7.9. Structures
    • 7.9.1. Example 7.10
  • 7.10. Parsing in Prolog
    • 7.10.1. Example 7.11
    • 7.10.2. Example 7.12
    • 7.10.3. Example 7.13
    • 7.10.4. Example 7.14
    • 7.10.5. Difference Lists
    • 7.10.6. Example 7.15
    • 7.10.7. Example 7.16
  • 7.11. Prolog Grammar Rules
    • 7.11.1. Example 7.17
  • 7.12. Building an AST
    • 7.12.1. Example 7.18
  • 7.13. Attribute Grammars
    • 7.13.1. Example 7.19
    • 7.13.2. Synthesized vs 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
    • 7.17.12. Solution to Practice Problem 7.12
• 8. Type Inference
  • 8.1. Why Static Type Inference?
  • 8.2. Type Inference Rules
  • 8.3. Using Prolog
  • 8.4. The Type Environment
  • 8.5. Integers, Strings, and Boolean Constants
    • 8.5.1. Example 8.1
  • 8.6. List and Tuple Constants
    • 8.6.1. Example 8.2
  • 8.7. Identifiers
    • 8.7.1. Example 8.3
  • 8.8. Function Application
    • 8.8.1. Instantiation
    • 8.8.2. Example 8.4
  • 8.9. Let Expressions
    • 8.9.1. Example 8.5
  • 8.10. Patterns
    • 8.10.1. Example 8.6
  • 8.11. Matches
    • 8.11.1. Example 8.7
  • 8.12. Anonymous Functions
    • 8.12.1. Example 8.8
  • 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