Warren Abstract Machine

Een Warren Abstract Machine ofwel WAM is een virtuele machine gericht op de taal Prolog en bestaat uit een geheugenmodel en een instructieset. Momenteel is het een de-facto standaard voor Prolog-compilers. Omdat deze architectuur de mogelijkheid biedt Prologprogramma's naar een low-level bytecode of machinetaal te compileren helpt het de Prolog-code efficiënter uit te voeren en maakt het echte Prologcompilers mogelijk. Warren voorziet in zijn publicatie zelfs een gespecialiseerde Prolog-processor.

Representatie van Prolog-terms

Een Prologterm wordt in een WAM gerepresenteerd door een tag gevolgd door een waarde. De tag wordt gebruikt om het type van de term te identificeren. Types zijn normaliter:

• Reference, een verwijzing naar een gebonden of ongebonden variabele
• Structures, voor Prologstructuren,
• Lists,
• Constants, getallen, maar ook Prolog-atoms.

Structuren en lijsten worden hierbij niet gedeeld, maar in hun geheel gekopieerd.

Geheugenmodel

De Warren Abstract Machine verdeelt de beschikbare geheugenruimte op in vier delen:

• De code space, waarin instructies worden opgeslagen,
• De local stack, Bevat environments, waarin gegevens omtrent het huidige goal wordt bijgehouden en keuzepunten met hun voortzettingen.
• De global stack or heap, bevat alle structuren en lijsten die worden aangemaakt door unificatie en die moeten worden vrijgegeven bij het backtracken.
• De trail, waarin wordt bijgehouden welke gebonden variabelen moeten worden vrijgegeven bij het backtracken

Registers

De huidige toestand van het Prolog-programma wordt weergegeven in een aantal registers:

Register	doel	wijst naar
P	Programmateller	Code ruimte
CP	Voortzetting (continuation)	Code ruimte
E	Laatste omgeving (environment)	local stack
B	Laatste keuzepunt (backtracking)	local stack
A	Top van de lokale stack
TR	Top van de trail-stack
H	Top van de heap
HB	Top van de heap voor het laatste keuzepunt
S	Structure Pointer
A1, A2 .. An	Argumenten	heap
X1, X2 .. Xn	Lokale variabelen

Instructieset

De instructieset van de WAM kan worden onderverdeeld in vijf categorieën:

1. get-instructies, corresponderen met de kop van de clause halen en unificeren die met argumenten.
2. put-instructies, corresponderen met argumenten meegegeven aan een goal en laden deze in de A registers
3. unify-instructies, corresponderen met argumenten van een structure en unificeren deze met bestaande structuren of maken nieuwe structuren aan.
4. procedural instructies, dragen zorg voor het overdragen van de besturing en het alloceren en dealloceren van geheugenruimte.
5. indexing instructies, filteren de clauses die overeenkomen met een goal en laten alleen die clauses over die mogelijk geëvalueerd worden.

Instructies bestaan uit een opcode gevolgd door 0, 1 of 2 argumenten. Een argument kan 1, 2 of 4 bytes lang zijn.

Bronnen

• David H. D. Warren. "An abstract Prolog instruction set". Technical Note 309, SRI International, Menlo Park, CA, October 1983.

• Hassan Aït-Kaci. "Warren's Abstract Machine: A Tutorial Reconstruction". Het boek wordt niet meer gedrukt. De auteur heeft de tekst vrijgegeven voor niet-commercieel gebruik. Deze is online beschikbaar.