Warren abstract machine


Warren abstract machine

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

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 different 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.

References

* [War83] David H. D. Warren. [http://www.ai.sri.com/pubs/files/641.pdf "An abstract Prolog instruction set"] . Technical Note 309, SRI International, Menlo Park, CA, October 1983.

* [2] Hassan Aït-Kaci. [http://web.archive.org/web/20030213072337/http://www.vanx.org/archive/wam/wam.html "Warren's Abstract Machine: A Tutorial Reconstruction"] . The book is out of print. The author has made it available online and free to use for non-commercial purposes.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Warren Abstract Machine — Warren s Abstract Machine La Warren s Abstract Machine (Machine abstraite de Warren) est une machine virtuelle permettant d implémenter le langage Prolog. Cette machine est composée d un jeu d instructions spécial ainsi que d une mémoire. Elle a… …   Wikipédia en Français

  • 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. Abstraction of computing processes is used in both the computer science and computer engineering… …   Wikipedia

  • Warren's Abstract Machine — Warren’s Abstract Machine (WAM) bezeichnet in der Informatik einen 1983 von David H. D. Warren spezifizierten idealen Prozessor, dessen Maschinensprache als Zielsprache für Prolog Übersetzer oder Interpreter dient. Man spricht auch von einer… …   Deutsch Wikipedia

  • Warren’s Abstract Machine — (WAM) bezeichnet in der Informatik einen 1983 von David H. D. Warren spezifizierten idealen Prozessor, dessen Maschinensprache als Zielsprache für Prolog Übersetzer oder Interpreter dient. Man spricht auch von einer virtuellen Maschine, da es den …   Deutsch Wikipedia

  • Warren's Abstract Machine — La Warren s Abstract Machine (Machine abstraite de Warren) est une machine virtuelle permettant d implémenter le langage Prolog. Cette machine est composée d un jeu d instructions spécial ainsi que d une mémoire. Elle a été définie par David H. D …   Wikipédia en Français

  • Warren — may refer to:Animal husbandry and relatedForest law*Warren (free) ( Free warren ), a type of hunting franchise under the Anglo Norman Forest law Animal husbandry*Warren (domestic), a rabbitry or fixed establishment of cuniculture *The domestic… …   Wikipedia

  • Machine abstraite de Warren — Warren s Abstract Machine La Warren s Abstract Machine (Machine abstraite de Warren) est une machine virtuelle permettant d implémenter le langage Prolog. Cette machine est composée d un jeu d instructions spécial ainsi que d une mémoire. Elle a… …   Wikipédia en Français

  • Virtual machine — A virtual machine (VM) is a completely isolated guest operating system installation within a normal host operating system .[1] Modern virtual machines are implemented with either software emulation or hardware virtualization or (in the most… …   Wikipedia

  • David H. D. Warren — is a computer scientist (Ph.D. artificial intelligence, University of Edinburgh 1977). 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.… …   Wikipedia

  • David H. D. Warren — Pour les articles homonymes, voir Warren. David H.D. Warren est un spécialiste de l intelligence artificielle. Il a écrit le premier compilateur pour le langage Prolog. On lui doit la Warren s Abstract Machine qui est une machine pour l exécution …   Wikipédia en Français


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.