Warren Abstract Machine

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In 1983, David H. D. Warren designed an abstract machine for the execution of Prolog consisting of a memory architecture and an instruction set.[1][2][3] This design became known as the Warren Abstract Machine (WAM) and has become the de facto standard target for Prolog compilers.


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.

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.

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


Here is a piece of Prolog code:

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

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

 label(1): switch_on_atom([(sally,3),(jane,5)])
 label(2): try_me_else(4)
 label(3): get_atom(sally,0)
 label(4): trust_me_else_fail
 label(5): get_atom(jane,0)

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.


  1. ^ David H. D. Warren (October 1983). An abstract Prolog instruction set (PDF). Menlo Park, CA, USA: Artificial Intelligence Center at SRI International.
  2. ^ Hassan Aït-Kaci (February 18, 1999). Warren's Abstract Machine: A Tutorial Reconstruction (PDF). Archived from the original (PDF) on 2003-02-13.
  3. ^ Hassan Aït-Kaci. "Warren's Abstract Machine: A Tutorial Reconstruction; the book, errata and slides". Retrieved 7 March 2011.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Warren_Abstract_Machine&oldid=820137422"
This content was retrieved from Wikipedia : http://en.wikipedia.org/wiki/Warren_Abstract_Machine
This page is based on the copyrighted Wikipedia article "Warren Abstract Machine"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA