In 1983, David H. D. Warren

David H. D. Warren

David H. D. Warren is a computer scientist .In the 1970s and 1980s he worked primarily on logic programming and in particular the programming language Prolog. Warren wrote the first compiler for Prolog...

 designed an abstract machine

Abstract machine

An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory...

 for the execution of Prolog

Prolog

Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...

 consisting of a memory

Computer storage

Computer data storage, often called storage or memory, refers to computer components and recording media that retain digital data. Data storage is one of the core functions and fundamental components of computers....

 architecture and an instruction set

Instruction set

An instruction set, or instruction set architecture , is the part of the computer architecture related to programming, including the native data types, instructions, registers, addressing modes, memory architecture, interrupt and exception handling, and external I/O...

.
This design became known as the Warren Abstract Machine (WAM) and has become the de facto standard target for Prolog compiler

Compiler

A compiler is a computer program that transforms source code written in a programming language into another computer language...

s.

Purpose

The purpose of compiling Prolog code to the more low-level WAM code is to make subsequent interpretation of the Prolog program more efficient. Prolog code is reasonably easy to translate to WAM instructions which can be more efficiently interpreted. Also, subsequent code improvements and compilation to native code are often easier to perform on the more low-level representation.

Memory areas

The WAM has the following memory areas:

• The global stack or heap, used to store compound terms
• The local stack for environment frames and choice-points
• The trail to record which variables bindings ought to be undone on backtracking

Relevance for Prolog users

In order to write efficient Prolog programs, a basic understanding of how the WAM works can be advantageous. Some of the most important WAM concepts are first argument indexing and its relation to choice-points, tail call optimization and memory reclamation on failure.

Example

Here is a piece of Prolog code:

girl(sally).
girl(jane).

boy(B) :- \+ girl(B).

A WAM-based Prolog compiler will compile this into WAM instructions similar to the following:

predicate(girl/1):
switch_on_term(2,1,fail,fail,fail),
label(1): switch_on_atom([(sally,3),(jane,5)])
label(2): try_me_else(4)
label(3): get_atom(sally,0)
proceed
label(4): trust_me_else_fail
label(5): get_atom(jane,0)
proceed

predicate(boy/1):
get_variable(x(1),0)
put_structure(girl/1,0)
unify_local_value(x(1))
execute((\+)/1)])

An important characteristic of this code is its ability to cope with the various modes in which the predicates can be evoked: Any argument might be a variable, a ground term, or a partly instantiated term. The "switch" instructions handle the different cases.