Can Logic Programming Execute as Fast as Imperative Programming?

Peter Lodewijk Van Roy

Ph.D. Dissertation, Technical Report UCB/CSD 90/600, Computer Science Division, UC Berkeley, December 1990.

Packaged Version

• Main text and references (648K)
• Appendixes (which include full commented source code) (579K)

Related Documentation

• Aquarius Prolog Release 1.0
• Ready-to-Run Source Code of the Aquarius Prolog Compiler (September 1991 Version) (360K)

Original Version

Introduction

• Abstract
• Copyright
• Acknowledgment
• Table of Contents

Main Text

• Chapter 1: Introduction
• Chapter 2: Prolog and Its High Performance Execution
• Chapter 3: The Two Representation Languages
• Chapter 4: Kernel Transformations
• Chapter 5: Compiling Kernel Prolog to BAM Code
• Chapter 6: BAM Transformations
• Chapter 7: Evaluation of the Aquarius System
• Chapter 8: Concluding Remarks and Further Work

Figures

• Figure 1.1: Structure of the Compiler and the Dissertation
• Figure 2.1: An Example of Unification
• Figure 2.4: Mapping Between Prolog and an Imperative Language (according to WAM)
• Figure 2.5: Representation of Prolog Terms in WAM and BAM
• Figure 2.6: Data Structures of WAM and BAM
• Figure 2.8: Compiling Prolog Into WAM
• Figure 2.9: Three Categories of Unbound Variables
• Figure 3.4: Decomposition of Unification
• Figure 4.4: The Argument Lattice
• Figure 4.9: Integrating Analysis Into the Compiler
• Figure 4.10: Some Examples of Test Sets
• Figure 5.1: Structure of the Clause Compiler
• Figure 5.6: Example of a Modal Entry Tree for Entry Specialization
• Figure 5.7: The Need for the Dereference Chain Transformation
• Figure 6.1: BAM Transformations
• Figure 7.1: The Effectiveness of Determinism Extraction

References and Appendixes

• References
• Appendix A: User Manual for the Aquarius Prolog Compiler
• Appendix B: Formal Specification of the Berkeley Abstract Machine Syntax
• Appendix C: Formal Specification of the Berkeley Abstract Machine Semantics
• Appendix D: Semantics of the Berkeley Abstract Machine
• Appendix E1: Extended DCG Notation: A Tool for Applicative Programming in Prolog
• Appendix E2: Extended DCG Notation: User Manual
• Appendix F: Source Code of the C and Prolog Benchmarks
• Appendix G: Source Code of the Aquarius Prolog Compiler (part 1)
• Appendix G: Source Code of the Aquarius Prolog Compiler (part 2)