zbMATH — the first resource for mathematics

How to invent a Prolog machine. (English) Zbl 0614.68020
In this paper we study the compilation of Prolog by making visible hidden operations (especially unification), and then optimizing them using well- known partial evaluation techniques. Inspection of straightforward partially evaluated unification algorithms gives an idea how to design special abstract machine instructions which later form the target language of our compilation. We handle typical compiler problems like representation of terms explicitly. This work gives a logical reconstruction of abstract Prolog machine code, and represents an approach of constructing a correct compiler from Prolog to such a code. As an example, we are explaining the unification principles of Warren’s new Prolog engine within our framework.

68N25 Theory of operating systems
Full Text: DOI
[1] Bowen, D. L. and Byrd, L. M., ”A Portable Prolog COmpiler,”Proc. of the Logic Programming Workshop, Portugal 74–83, 1983.
[2] Clocksin, W. F. and Mellish, C. S.,Programming in Prolog, 2nd Ed., Springer, 1984. · Zbl 0466.68009
[3] Clocksin, W. F., ”Design and Simulation of a Sequential Prolog Machine,”New Generation Computing, 3, pp. 101–120, 1985.
[4] Ershov, A. P., ”On the Partial Evaluation Principle,”Information Processing Letters, Vol. 6, No. 2, pp. 38–41, 1977. · Zbl 0384.68006
[5] Ershov, A. P., ”Mixed Computation: Potential Applications and Problems for Study,”Theor. Comp. Sci., 18, pp. 41–67, 1982. · Zbl 0495.68011
[6] Futamura, Y., ”Partial Evaluation of Computation Process_– An Approach to a Compiler-Compiler,”Systems, Computers, Controls, Vol. 2, 5, pp. 45–50, 1971.
[7] Heck, N. and Avenhaus, J., ”Automatic Implementation of Abstract Data Types Specified by the Logic Programming Language”Proc. of the International Conference on Fifth Generation Computer Systems 1984, ICOT, pp. 210–219, 1984.
[8] Hsiang, J. and Srivas, M. K. ”A Prolog Environment for Developing and Reasoning about Data Types,” inFormal Methods and Software Development, Vol. 2 (H. Ehrig et al., eds.), LNCS, 186, pp. 276–293, 1985.
[9] Jones, N. D., Sestoft, P. and Søndergaard, H., ”An Experiment in Partial Evaluation: The Generation of a Compiler Generator,”1st Int. Conf. on Rewriting Techniques and Applications, Dijon, LNCS, 202, pp. 124–140, 1985.
[10] Kahn, K. M. and Carlsson, M., ”The Compilation of Prolog Programs without the Use of a Prolog Compiler,”Proc. of the International Conference on Fifth Generation Computer Systems 1984, ICOT, pp. 348–355, 1984.
[11] Mellish, C. S., ”Some Global Optimizations for a Prolog Compiler,”Journal of Logic Programming, 1, pp. 43–66, 1985. · Zbl 0575.68003
[12] Neidecker, B., ”KAP-Maschine: Maschinenmodell und Instruktionssatz,”internal report 19/86, University of Karlsruhe, 1986 [in German].
[13] Tick, E. and Warren, D. H. D., ”Towards a Pipelined Prolog Processor,”New Generation Computing, 2, pp. 323–345, 1984.
[14] Venken, R., A Prolog Meta-Interpreter for Partial Evaluation and its Application to Source to Source Transformation and Query-Optimisation, ECAI 84, Elsevier Sc. Publ., North-Holland, pp. 91–104, 1984.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.