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:
- get-instructies, corresponderen met de kop van de clause halen en unificeren die met argumenten.
- put-instructies, corresponderen met argumenten meegegeven aan een goal en laden deze in de A registers
- unify-instructies, corresponderen met argumenten van een structure en unificeren deze met bestaande structuren of maken nieuwe structuren aan.
- procedural instructies, dragen zorg voor het overdragen van de besturing en het alloceren en dealloceren van geheugenruimte.
- 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.