In 1983,

David H. D. Warren David H. D. Warren is a computer scientist who worked primarily on logic programming and in particular the programming language Prolog in the 1970s and 1980s. Warren wrote the first compiler for Prolog, and the Warren Abstract Machine execution ...

designed an

abstract machine An abstract machine is a computer science theoretical model that allows for a detailed and precise analysis of how a computer system functions. It is analogous to a mathematical function in that it receives inputs and produces outputs based on pre ...

for the execution of

Prolog Prolog is a 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 intended primarily ...

consisting of a

memory Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembered, ...

architecture and an

instruction set In computer science, an instruction set architecture (ISA), also called computer architecture, is an abstract model of a computer. A device that executes instructions described by that ISA, such as a central processing unit (CPU), is called an ' ...

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

compiler In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...

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 compilations to native code are often easier to perform on the more low-level representation. 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 In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recur ...

, and memory reclamation on failure.

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

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 In mathematical logic, a ground term of a formal system is a term that does not contain any variables. Similarly, a ground formula is a formula that does not contain any variables. In first-order logic with identity, the sentence Q(a) \lor P(b) ...

, or a partly instantiated term. The "switch" instructions handle the different cases.

References

{{DEFAULTSORT:Warren Abstract Machine Logic programming Abstract machines Virtual machines SRI International software