Contents

• Chapter 1  Introduction
  • 1.1  Purpose of program transformations
  • 1.2  Why transform functional programs?
  • 1.3  Difficulties
    • 1.3.1  Semantic complications
    • 1.3.2  Complexity of search
  • 1.4  Goals and structure of this work
• Chapter 2  A Simple Functional Language with Call-by-Value Semantics
  • 2.1  Description of types, values and informal semantics
    • 2.1.1  Unit type
    • 2.1.2  Product type
    • 2.1.3  Sum type
    • 2.1.4  Function type
    • 2.1.5  Type of recursively defined functions
    • 2.1.6  Recursive types
  • 2.2  Abstract syntax
  • 2.3  Formal typing rules
  • 2.4  Operational semantics
    • 2.4.1  Values
    • 2.4.2  Structural operational semantics
  • 2.5  Denotational semantics
• Chapter 3  Automated Transformations
  • 3.1  Partial evaluation
    • 3.1.1  Example
    • 3.1.2  Properties of partial evaluation
  • 3.2  Fold/Unfold method
    • 3.2.1  Deforestation
    • 3.2.2  Tupling transformation
  • 3.3  Bird/Meertens formalism
• Chapter 4  Correctness of Transformations
  • 4.1  Preserving termination behaviour
    • 4.1.1  Correctness of partial evaluation
    • 4.1.2  Correctness of Fold/Unfold transformations
  • 4.2  Other side effects
  • 4.3  Practical correctness issues
• Chapter 5  Controlling Transformations
  • 5.1  Reducing the number of choice points
    • 5.1.1  Partial evaluation
    • 5.1.2  An advanced technique for guiding search — rippling
  • 5.2  Giving priority to choices
  • 5.3  Control and completeness
  • 5.4  Examples of control heuristics
    • 5.4.1  A classic control strategy
    • 5.4.2  A control strategy with partial evaluation
• Chapter 6  Implementing Transformations
  • 6.1  Implementation in LambdaProlog
    • 6.1.1  Higher-order logic
  • 6.2  Structuring partial evaluation using monads
    • 6.2.1  What are monads?
    • 6.2.2  Using monads to hide side effects
    • 6.2.3  Partial evaluation and monads
    • 6.2.4  Extensibility and monads
    • 6.2.5  Theoretical aspects of monads and partial evaluation
    • 6.2.6  Final remarks on the use of monads
  • 6.3  Maintaining types during partial evaluation
• Chapter 7  System Evaluation
  • 7.1  Type inference
  • 7.2  Evaluation
  • 7.3  Partial evaluation
  • 7.4  Common sub-expression elimination
  • 7.5  Inlining
• Chapter 8  Conclusion
  • 8.1  A better partial evaluator?
  • 8.2  Correctness issues
  • 8.3  Control issues
  • 8.4  New ways of implementation
  • 8.5  Future work
  • 8.6  Completely different ways
• Appendices
• Appendix A  Miscellaneous Examples
  • A.1  Fibonacci in O(log_n) — Haskell code
• Appendix B  Components of the system
• Appendix C  Examples of System Code
  • C.1  Code of effect monad
    • C.1.1  Signature of effect monad
    • C.1.2  Implementation of effect monad
  • C.2  Code of monadic partial evaluator
    • C.2.1  Signature of monadic partial evaluator
    • C.2.2  Implementation of monadic partial evaluator