An Abstract Prolog Instruction Set

Abstract

This report describes an abstract Prolog instruction set suitable for software, firmware, or hardware implementation. The instruction set is abstract in that certain details of its encoding and implementation are left open, so that it may be realized in a number of different forms. The forms that are contemplated are:

• Translation into a compact bytecode, with emulators written in C (for maximum portability), Progol (a macrolanguage generating machine code, for efficient software implementations as an alternative to direct compilation on machines such as the VAX), and VAX-730 microcode.
• Compilation into the standard instructions of machines such as the VAX or DECsystem-10/20. em Hardware (or firmware) emulation of the instruction set on a specially designed Prolog processor.

The abstract machine described herein (“new Prolog Engine”) is a major revision of the “old Prolog Engine” described in a previous document. The new model overcomes certain difficulties in the old model, which are discussed in a later section. The new model can be considered to be a modification of the old model, where the stack contains compiler-defined goals called environments instead of user-defined goals. The environments correspond to some number of goals forming the tail of a clause. The old model was developed having primarily in mind a VAX-730 microcode implementation. The new model has, in addition, been influenced by hardware implementation considerations, but should remain equally amenable to software or firmware implementation on machines such as the VAX.