Exploring Programming Language Architecture in Perl

• Navigation
• prev
• up
• next

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

• 3.1 Example PScheme Structure for (foo ("bar" 10) baz)
• 3.2 PScm::Expr classes
• 3.3 PScm::Expr new() and value() methods
• 3.4 PScm::Expr Eval() Methods
• 3.5 PScm::Expr as_string() methods
• 3.6 PScm::Expr methods

• 4.1 Stacks Destroy Old Environment Frames
• 4.2 Linked Lists Don't Destroy Old Environment Frames
• 4.3 Environment during evaluation of example “let”

• 5.1 Functions extend an environment just like let does
• 5.2 Closures extend the lexical environment
• 5.3 let binds n to 2
• 5.4 Closure Captures the Local Environment
• 5.5 let binds times2 and a
• 5.6 Closure Extends Captured Env

• 6.1 Why recursion doesn't work
• 6.2 Recursive environments

• 7.1 Nested environments

• 8.1 Cons Cell Representation of a nested list (foo ("bar" 10) baz)
• 8.2 The pair (a . b)
• 8.3 The structure (a b . c)

• 9.1 Example mylet internal structure

• 12.1 Notional object structure
• 12.2 Real object structure
• 12.3 Example classes and objects

• 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

• 16.1 Control flow during (list (amb 1 2) (amb 'a 'b))
• 16.2 One possible parse of “Time flies like an arrow”
• 16.3 A parse tree for “Fruit flies like a bannanna”
• 16.4 define installs a failure continuation last

• 17.1 Bach's Family Tree
• 17.2 Unification of ['f', ['g', 'A'], 'A'] with ['f', 'B', 'abc']
• 17.3 A more complex unification example

• Navigation
• prev
• up
• next