Implementation of a high-speed Prolog interpreter

ABSTRACT

This paper describes the implementation of a high speed Prolog interpreter on a standard microprocessor (50 KLIPS on a 16 MHz MC68020). The interpreter is based on direct threaded code. By this method an interpreted program achieves the same speed as a compiled program, but uses only a tenth of memory. The first part of this paper describes the implementation of the interpreter. The second part compares the implementation, the runtime and the storage requirements with that of a compiler.

REFERENCES

• 1: /Bruy82/ Maurice Bruynooghe: The Memory Managament of Prolog Implementations; in Logic Programming, Academic Press, 1982.
• 2: W. F. Clocksin , C. S. Mellish, Programming in Prolog, Springer-Verlag New York, Inc., New York, NY, 1987
• 3: /Cloc85/ W. F. Clocksin: Design and Simulation of a Sequential Prolog Machine: in New Generation Computing Vol. 3 No. 1, 1985.
• 4: Y Kaneda , N Tamura , K Wada , H Matsuda , S Kuo, Sequential Prolog machine PEK, New Generation Computing, v.4 n.1, p.51-66, 1986 [doi>10.1007/BF03037382]
• 5: /KuFr85/ Eva Kühn, Thomas Frühwirth: VIP-DBS An Integrated Logic Database System based on Prolog, Technical University of Vienna, TR 1802/4, 1985.
• 6: Hidekazu Matsumoto, A static analysis of prolog programs, ACM SIGPLAN Notices, v.20 n.10, p.48-59, Oct. 1985 [doi>10.1145/382286.382380]
• 7: /Mell82/ C. S. Mellish: An Alternative to Structure Sharing in the Implementation of a Prolog Interpreter; in Logic Programming, Academic Press, 1982.
• 8: R Onai , H Shimizu , K Masuda , M Aso, Analysis of sequential prolog programs, Journal of Logic Programming, v.3 n.2, p.119-141, July 1986 [doi>10.1016/0743-1066(86)90019-1]
• 9: /Oppi85/ Marcus Oppitz, et al.: VIP - A Prolog Programming Environment; Technical University of Vienna, TR 1802/1, 1985.
• 10: /Pich84/ Christian Pichler: Prolog Übersetzer; Technical University of Vienna, Diplomarbeit, Institut für Praktische Informatik, 1984.
• 11: /StSh86/ Leon Sterling, Ehud Shapiro: The Art of Prolog; MIT Press, 1986.
• 12: /TiWa84/ Evan Tick, David H. D. Warren: Towards a Piplined Prolog Processor; in New Generation Computing Vol. 2 No. 4, 1984.
• 13: /Warr77/ David Warren: Implementing Prolog - compiling predicate logic programs; University of Edingburgh, Department of Artificial Intelligence, TR 39, TR 40, 1977.
• 14: /Warr83/ David Warren: An Abstract Prolog Instruction Set; SRI International, TR 309, 1983.
• 15: /Yoko83/ Minoru Yokota, et al.: The Design and Implementation of a Personal Inference Machine: PSI; in New Generation Computing, Vol. 1 No. 2, 1983.

INDEX TERMS

Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Prolog
      D.3.4 Processors
          Subjects: Interpreters; Compilers

General Terms:
Design, Languages, Measurement, Performance