Exploring Programming Language Architecture in Perl

Table of Contents

Part 1 Implementing a Scheme-Like Interpreter
- Chapter 1 Introduction
  - 1.1 Why Perl?
  - 1.2 Why Scheme?
  - 1.3 References
  - 1.4 Typography
  - 1.5 A Note on the Interpreter Versions
- Chapter 2 An Introduction to PScheme
  - 2.1 PScheme Syntax
  - 2.2 Simple Expressions
  - 2.3 Conditionals
  - 2.4 Global Variables
  - 2.5 Functions
  - 2.6 Local Variables
- Chapter 3 Interpreter Version 0.0.0
  - 3.1 The Read-Eval-Print Loop
  - 3.2 The Environment
  - 3.3 The Reader
  - 3.4 PScheme Expressions
  - 3.5 Evaluation
    - 3.5.1 Evaluation of Literals
    - 3.5.2 Evaluation of Symbols
    - 3.5.3 Evaluation of Lists
  - 3.6 Primitive Operations
  - 3.7 Special Forms
  - 3.8 Output
  - 3.9 Summary
  - 3.10 Tests
- Chapter 4 Implementing let
  - 4.1 The Environment
    - 4.1.1 A Stack-based Environment
    - 4.1.2 A Linked List Environment
  - 4.2 Global Environments have a Problem
  - 4.3 Environment Passing
  - 4.4 let Itself
  - 4.5 Summary
  - 4.6 Tests
- Chapter 5 Implementing lambda
  - 5.1 lambda
  - 5.2 Evaluating a Closure
  - 5.3 Printing a Closure
  - 5.4 Summary
  - 5.5 Tests
- Chapter 6 Recursion and letrec
  - 6.1 letrec
    - 6.1.1 Assignment
    - 6.1.2 PSCM::LetRec itself
  - 6.2 Summary
  - 6.3 Tests
- Chapter 7 Another Variation on let
  - 7.1 Sequential Binding
  - 7.2 let*
  - 7.3 Summary
  - 7.4 Tests
- Chapter 8 List Processing
  - 8.1 quote
  - 8.2 list
  - 8.3 car and cdr
  - 8.4 cons
    - 8.4.1 Dot Notation
  - 8.5 Implementation
    - 8.5.1 Changes to Expressions
    - 8.5.2 Changes to Primitives and Special Forms
    - 8.5.3 Changes to Closures
    - 8.5.4 Changes to the Environment
    - 8.5.5 Changes to the Reader
  - 8.6 Summary
  - 8.7 Tests
- Chapter 9 Macros
  - 9.1 macro
  - 9.2 Evaluating Macros
    - 9.2.1 Trying it out
    - 9.2.2 An Improvement
    - 9.2.3 One Last Addition
  - 9.3 Summary
  - 9.4 Tests
- Chapter 10 Side Effects
  - 10.1 The Beauty of Functional Languages
  - 10.2 Variable Assignment
  - 10.3 Sequences
  - 10.4 Summary
  - 10.5 Tests
- Chapter 11 define
  - 11.1 Environment Changes
  - 11.2 The define Special Form
  - 11.3 Persistant Environments
  - 11.4 Tests
- Chapter 12 Classes and Objects
  - 12.1 Features of this implementation
    - 12.1.1 Inheritance
    - 12.1.2 Class Variables and Methods
    - 12.1.3 super Calls
    - 12.1.4 Feature Summary
  - 12.2 Implementation
    - 12.2.1 Class Creation with make-class
    - 12.2.2 Object Creation
    - 12.2.3 init Method Invocation
    - 12.2.4 General Method Invocation
    - 12.2.5 super Method Invocation
    - 12.2.6 Wiring it up
  - 12.3 Summary and Variations
  - 12.4 Tests
- Chapter 13 Continuations
  - 13.1 Tail Recursion and Tail Call Optimization
  - 13.2 Continuation Passing Style
  - 13.3 Example CPS Transformations
  - 13.4 The Trampoline
  - 13.5 Using CPS
  - 13.6 Implementation
    - 13.6.1 Our Trampoline Implementation
    - 13.6.2 CPS let and lambda
    - 13.6.3 CPS letrec
    - 13.6.4 CPS let*
    - 13.6.5 CPS List Processing
    - 13.6.6 CPS macro and unquote
    - 13.6.7 CPS Sequences and Assignment
    - 13.6.8 CPS define
    - 13.6.9 CPS OOP
  - 13.7 CPS Without Closures
  - 13.8 CPS Fun
    - 13.8.1 An error Handler
    - 13.8.2 yield
  - 13.9 Summary
- Chapter 14 Threads
  - 14.1 Variations
  - 14.2 Tests
- Chapter 15 Better Error Handling
  - 15.1 The Built in error Primitive
  - 15.2 Using the error Builtin for Internal Errors
  - 15.3 Tests
- Chapter 16 Chronological Backtracking
  - 16.1 Introducing amb
  - 16.2 Examples of amb in Action
    - 16.2.1 The “Liars” Puzzle
    - 16.2.2 Barrels of Fun
    - 16.2.3 Pythagorean Triples
    - 16.2.4 Parsing Natural Language
  - 16.3 Implementing amb
    - 16.3.1 Changes to Continuations
    - 16.3.2 Mechanical Transformations of the Interpreter
    - 16.3.3 Remaining Continuation Changes
    - 16.3.4 amb Itself
    - 16.3.5 Changes to define
    - 16.3.6 Changes to set!
    - 16.3.7 Changes to repl()
    - 16.3.8 Additional Changes
  - 16.4 Support for Testing amb
    - 16.4.1 and and or
    - 16.4.2 Numeric Inequality Tests
    - 16.4.3 eq?
    - 16.4.4 Wiring it up
  - 16.5 Summary and Directions
    - 16.5.1 An Alternative Implementation
  - 16.6 Tests
- Chapter 17 Unification and Logic Programming
  - 17.1 Logic Programming Examples
    - 17.1.1 Mary and John
    - 17.1.2 J. S. Bach and Family
    - 17.1.3 Appending Lists
    - 17.1.4 Factorial Again
    - 17.1.5 Symbolic Differentiation
  - 17.2 Pattern Matching
    - 17.2.1 A Perl Pattern Matcher
  - 17.3 Unification
    - 17.3.1 A Perl Unifier
    - 17.3.2 Implementing unify in PScheme
  - 17.4 Logic Programming
  - 17.5 More Logic Programming Examples
    - 17.5.1 Parsing (again)
    - 17.5.2 Simplifying Algebraic Expressions
  - 17.6 Summary, Shortcomings and Short-cuts
    - 17.6.1 Functors and Arity
    - 17.6.2 The Cut
    - 17.6.3 Backtracking Efficiency
  - 17.7 Tests
- Chapter 18 Summary
Bibliography
Index

List of Figures

6.1 Why recursion doesn't work
6.2 Recursive environments

7.1 Nested environments

9.1 Example mylet internal structure

13.1 Producer/consumer pair
13.2 Tail call without TCO
13.3 Tail call with TCO
13.4 Control flow for the simple script
13.5 Control flow with continuations
13.6 Continuations are just (anonymous) subroutines
13.7 Continuations really are just subroutines

Last updated Sun Mar 14 10:43:08 2010 UST