Editing Warren Abstract Machine

{{Short description|Abstract machine for the execution of Prolog}}
In 1983, [[David H. D. Warren]] designed an [[abstract machine]] for the execution of [[Prolog]] consisting of a [[computer storage|memory]] architecture and an [[instruction set]].<ref>{{cite book | author = David H. D. Warren | title = An abstract Prolog instruction set | publisher = [[Artificial Intelligence Center]] at [[SRI International]] | location = Menlo Park, CA, USA | date = October 1983 | url = https://www.sri.com/wp-content/uploads/2021/12/641.pdf | archive-url = https://web.archive.org/web/20220619231625/https://www.sri.com/wp-content/uploads/2021/12/641.pdf | archive-date = 2022-06-19 | url-status = live }}</ref><ref>{{cite book | author = Hassan Aït-Kaci | title = Warren's Abstract Machine: A Tutorial Reconstruction | date = February 18, 1999 | url = http://www.vanx.org/archive/wam/wambook.pdf | url-status=usurped | archiveurl = https://web.archive.org/web/20030213072337/http://www.vanx.org/archive/wam/wambook.pdf | archivedate = 2003-02-13 }}</ref><ref>{{cite web | author = Hassan Aït-Kaci | title = Warren's Abstract Machine: A Tutorial Reconstruction; the book, errata and slides | url = http://wambook.sourceforge.net/ | accessdate = 7 March 2011 | archive-date = 19 January 2022 | archive-url = https://web.archive.org/web/20220119110941/http://wambook.sourceforge.net/ | url-status = dead }}</ref> This design became known as the '''Warren Abstract Machine''' (WAM) and has become the ''de facto'' standard target for Prolog [[compiler]]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 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]], 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:
<syntaxhighlight lang="prolog">
 girl(sally).
 girl(jane).
 
 boy(B) :- \+ girl(B).
</syntaxhighlight>
A WAM-based Prolog compiler will compile this into WAM instructions similar to the following:
<syntaxhighlight lang="prolog">
 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)])
</syntaxhighlight>
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.

==References==
{{reflist}}

{{DEFAULTSORT:Warren Abstract Machine}}
[[Category:Logic programming]]
[[Category:Abstract machines]]
[[Category:Virtual machines]]
[[Category:SRI International software]]