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
Copyright © 2000 Markus Mottl ⟨
markus.mottl@gmail.com⟩