Warren Abstract Machine

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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[bewerken]

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[bewerken]

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[bewerken]

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[bewerken]

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[bewerken]