Abstract Machines

The execution of programming languages in general can be performed in three different ways:

1. by interpreting the source code,
2. by compiling the source code into native machine code, or
3. by compiling it into an abstract machine code and then emulating it.

Interpretation is used for the definition of the operational semantics and in prototypical implementations of all kinds of programming languages. In order to obtain efficiency, compilation is needed. Programming languages complying with the imperative programming style imposed by the von Neumann architecture are usually compiled into native machine code.

For a language like PROLOG which cannot be easily mapped into the imperative programming paradigm, the compilation into an abstract machine especially designed for it is usually a good compromise w.r.t. efficiency and development costs. The machine code for such an abstract machine is interpreted by an ordinary (but of course highly optimized) imperative program in contrast to the execution of native machine code with a hardware-encoded interpreter (a processor).

In case of relational programming languages, for quite some time only interpreters existed. In 1967, Absys (Aberdeen System), an interpreter for (a predecessor of) pure PROLOG, was developed at the University of Aberdeen. In 1977, David H. D. Warren et. al. developed DEC-10 PROLOG, the first PROLOG compiler, and in 1983, he designed the WAM [\protect\citeauthoryearWarren1983], the abstract machine that has become the de facto standard implementation technique for relational languages [\protect\citeauthoryearVan Roy1994].

The WAM can be characterized as follows:

Since the coupling of the WAM and the LLAMA is loose, a deep understanding of the WAM will not be required. Only

• the WAM heap (holding lists and structures, the compound data terms of PROLOG and RELFUN/REL),
• the local stack (holding environments, which contain local variables, and choice points), and
• some of the WAM registers (the program counter and the stack and heap pointers)