Ait-Kaci H.Warren's abstract machine.A tutorial reconstruction.1999
.pdf
WARREN’S ABSTRACT MACHINE
Control instructions
allocate
Allocate a new environment on the stack, setting its continuation environment and continuation point fields to current E and CP, respectively. Continue execution with the following instruction.
if E > B
then newE E + CODE[STACK[E + 1] ; 1] + 2
|
else newE B + STACK[B] + 8 |
STACK[newE] E |
|
STACK[newE + 1] CP |
|
E |
newE |
P |
P + instruction size(P) |
deallocate |
|
|
|
|
|
Remove the environment frame at stack |
CP |
STACK[E + 1] |
|||
location E from the stack by resetting E |
E |
STACK[E] |
|||
to the value of its CE field and the con- |
P |
P + instruction |
|
size(P) |
|
tinuation pointer CP to the value of its |
|
|
|
|
|
CP field. Continue execution with the |
|
|
|
|
|
following instruction. |
|
|
|
|
|
call P N |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
If P is defined, then save the cur- |
if de ned(P) |
|||||||
rent choice point’s address in B0 |
then |
|
|
|
|
|
|
|
and the value of current continua- |
begin |
|
|
|
|
|
|
|
tion in CP, and continue execution |
CP |
|
P + instruction |
|
size(P) |
|||
with instruction labeled P, with N |
num |
|
of |
|
args arity (P) |
|||
|
|
|||||||
stack variables remaining in the cur- |
B0 |
|
B |
|||||
rent environment; otherwise, back- |
P |
@(P) |
||||||
track. |
end |
|
|
|
|
|
|
|
|
|
else backtrack |
||||||
PAGE 106 OF 129 |
Reprinted from MIT Press Copyright c Hassan A¨IT-KACI |
A TUTORIAL RECONSTRUCTION
execute P |
|
|
|
|
|
|
If P s defined, then save the current |
if de ned(P) |
|||||
choice point’s address in B0 and con- |
then |
|
|
|
|
|
tinue execution with instruction labeled |
begin |
|
|
|
|
|
P; otherwise, backtrack. |
num |
|
of |
|
args arity(P) |
|
|
|
B0 |
|
B |
||
|
|
P |
@(P) |
|||
|
|
end |
|
|
|
|
|
|
else backtrack |
||||
proceed
Continue execution at instruction whose P CP address is indicated by the continuation
register CP.
Copyright c Hassan A¨IT-KACI Reprinted from MIT Press |
PAGE 107 OF 129 |
WARREN’S ABSTRACT MACHINE
Choice instructions
try me else L
Allocate a new choice point frame on the stack setting its next clause field to L and the other fields according to the current context, and set B to point to it. Continue execution with following instruction.
if E > B
then newB E + CODE[STACK[E + 1] ; 1] + 2
else newB |
B + STACK[B] + 8 |
||||
STACK[newB] |
num |
|
of |
|
args |
nSTACK[newB]
for i |
1 to n do STACK[newB + i] Ai |
|||
STACK[newB + n + 1] |
E |
|||
STACK[newB + n + 2] |
CP |
|||
STACK[newB + n + 3] |
B |
|||
STACK[newB + n + 4] |
L |
|||
STACK[newB + n + 5] |
TR |
|||
STACK[newB + n + 6] |
H |
|||
STACK[newB + n + 7] |
B0 |
|||
B |
newB |
|
||
HB |
H |
|
||
P |
P + instruction |
|
size(P) |
|
retry |
|
me |
|
else L |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Having backtracked to the cur- |
n |
STACK[B] |
|
|||||||||
rent choice point, reset all the |
for i |
|
1 to n do Ai |
STACK[B + i] |
||||||||
necessary information from it |
E |
STACK[B + n + 1] |
||||||||||
and update its next clause field |
CP |
STACK[B + n + 2] |
||||||||||
to L. Continue execution with |
STACK[B + n + 4] |
L |
||||||||||
following instruction. |
unwind |
|
trail(STACK[B + n + 5] TR) |
|||||||||
|
|
|
|
|
|
TR |
STACK[B + n + 5] |
|||||
|
|
|
|
|
|
H STACK[B + n + 6] |
||||||
|
|
|
|
|
|
HB |
H |
|
||||
|
|
|
|
|
|
P |
P + instruction |
|
size(P) |
|||
PAGE 108 OF 129 |
Reprinted from MIT Press Copyright c Hassan A¨IT-KACI |
A TUTORIAL RECONSTRUCTION
trust |
|
me |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Having backtracked to the cur- |
n |
STACK[B] |
|||||||
rent choice point, reset all the |
for i |
|
1 to n do Ai STACK[B + i] |
||||||
necessary information from it, |
E |
STACK[B + n + 1] |
|||||||
then discard it by resetting B to |
CP |
STACK[B + n + 2] |
|||||||
its predecessor. Continue exe- |
unwind |
|
trail(STACK[B + n + 5] TR) |
||||||
cution with following instruc- |
TR |
STACK[B + n + 5] |
|||||||
tion. |
H |
STACK[B + n + 6] |
|||||||
|
|
|
|
B STACK[B + n + 3] |
|||||
|
|
|
|
HB |
STACK[B + n + 6] |
||||
|
|
|
|
P |
P + instruction |
|
size(P) |
||
try L
Allocate a new choice point frame on the stack setting its next clause field to the following instruction and the other fields according to the current context, and set B to point to it. Continue execution with instruction labeled L.
if E > B
then newB E + CODE[STACK[E + 1] ; 1] + 2
else newB |
B + STACK[B] + 8 |
||||
STACK[newB] |
num |
|
of |
|
args |
nSTACK[newB]
for i |
1 to n do STACK[newB + i] Ai |
|||
STACK[newB + n + 1] |
E |
|||
STACK[newB + n + 2] |
CP |
|||
STACK[newB + n + 3] |
B |
|||
STACK[newB + n + 4] |
P + instruction |
|
size(P) |
|
STACK[newB + n + 5] |
TR |
|||
STACK[newB + n + 6] |
H |
|||
STACK[newB + n + 7] |
B0 |
|||
B |
newB |
|
|
|
HB |
H |
|
|
|
P |
L |
|
|
|
Copyright c Hassan A¨IT-KACI Reprinted from MIT Press |
PAGE 109 OF 129 |
|
|
|
|
|
|
|
|
|
|
|
|
WARREN’S ABSTRACT MACHINE |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
retry L |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
Having |
backtracked |
n |
STACK[B] |
|
|
|
||||||||
|
to the current |
choice |
for i |
|
0 to n ; 1 do Ai |
STACK[B + i] |
|||||||||
|
point, |
reset |
all the |
E |
STACK[B + n + 1] |
|
|
|
|||||||
|
necessary |
information |
CP |
STACK[B + n + 2] |
|
|
|
||||||||
|
from it and update its |
STACK[B + n + 4] P + instruction |
|
size(P) |
|||||||||||
|
next |
clause field to |
unwind |
|
trail (STACK[B + n + 5] TR) |
||||||||||
|
following |
|
instruction. |
TR |
STACK[B + n + 5] |
|
|
|
|||||||
|
Continue |
|
|
execu- |
H |
STACK[B + n + 6] |
|
|
|
||||||
|
tion |
with |
|
instruction |
HB |
H |
|
|
|
|
|
|
|||
|
labeled L. |
|
|
|
P |
L |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
trust L |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Having backtracked to the cur- |
n |
STACK[B] |
|
|
|
|||||||||
|
rent choice point, reset all nec- |
for i |
|
1 to n do Ai |
STACK[B + i] |
||||||||||
|
essary information from it, then |
E STACK[B + n + 1] |
|||||||||||||
|
discard it by resetting B to its |
CP |
STACK[B + n + 2] |
||||||||||||
|
predecessor. Continue execu- |
unwind |
|
trail(STACK[B + n + 5] TR) |
|||||||||||
|
tion with instruction labeled L. |
TR |
STACK[B + n + 5] |
||||||||||||
|
|
|
|
|
|
|
H STACK[B + n + 6] |
||||||||
|
|
|
|
|
|
|
B STACK[B + n + 3] |
||||||||
|
|
|
|
|
|
|
HB |
STACK[B + n + 6] |
|||||||
|
|
|
|
|
|
|
P |
L |
|
|
|
||||
Indexing instructions
switch |
|
on |
|
term V C L S |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jump to the instruction labeled, respec- |
case STORE[deref (A1)] of |
|||||||||||
tively, V , C, L, or S, depending on |
h REF |
|
|
i |
: |
P |
V |
|||||
whether the dereferenced value of argu- |
h CON |
|
|
i |
: |
P |
C |
|||||
ment register A1 is a variable, a constant, |
h LIS |
|
|
i |
: |
P |
L |
|||||
a non-empty list, or a structure, respec- |
h STR |
|
|
i |
: |
P |
S |
|||||
tively. |
endcase |
|
|
|
|
|||||||
PAGE 110 OF 129 |
Reprinted from MIT Press Copyright c Hassan A¨IT-KACI |
A TUTORIAL RECONSTRUCTION
switch on constant N T
The dereferenced value of register A1 being a constant, jump to the instruction associated to it in hashtable T of size N. If the constant found in A1 is not one in the table, backtrack.
switch on structure N T
The dereferenced value of register A1 being a structure, jump to the instruction associated to it in hashtable T of size N. If the functor of the structure found in A1 is not one in the table, backtrack.
h tag val i STORE[deref (A1)]
h found inst i get hash(val T N) if found
then P inst else backtrack
h tag val i STORE[deref (A1)]
h found inst i get hash(val T N) if found
then P inst else backtrack
Cut instructions
neck cut
If there is a choice point after that indicated by B0, discard it and tidy the trail up to that point. Continue execution with following instruction.
get level Yn
if B > B0
then begin
B B0
tidy trail end
P P + instruction size(P)
Set Yn to the current value of B0. Con- |
STACK[E + 2 + n] B0 |
||
tinue execution with following instruc- |
P P + instruction |
|
size(P) |
tion. |
|
|
|
Copyright c Hassan A¨IT-KACI Reprinted from MIT Press |
PAGE 111 OF 129 |
|
|
|
|
WARREN’S ABSTRACT MACHINE |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
cut Yn |
|
|
|
|
|
|
|
Discard all (if any) choice points after |
if B > STACK[E + 2 + n] |
|||||
|
that indicated by Yn, and tidy the trail up |
then |
|||||
|
to that point. Continue execution with |
begin |
|||||
|
following instruction. |
B STACK[E + 2 + n] |
|||||
|
|
|
tidy |
|
trail |
||
|
|
|
|
||||
|
|
|
end |
||||
|
|
|
P P + instruction |
|
size(P) |
||
B.2 WAM ancillary operations
procedure backtrack begin
if B = bottom of stack
then fail and exit program else
begin
B0 STACK[B + STACK[B] + 7]
P STACK[B + STACK[B] + 4]
end endbacktrack
The backtrack operation
PAGE 112 OF 129 |
Reprinted from MIT Press Copyright c Hassan A¨IT-KACI |
A TUTORIAL RECONSTRUCTION
function deref (a : address) : address begin
h tag value i STORE[a]
if (tag = REF) ^ (value 6= a) thenreturn deref (value) elsereturn a
endderef
The deref operation
procedure bind(a1 a2 : address)
h t1 |
|
i STORE[a1] |
h t2 |
|
i STORE[a2] |
|
|
||||
if (t1 = REF) ^ ((t2 =6 |
REF) _ (a2 < a1)) |
||||
then begin
STORE[a1] STORE[a2] trail(a1)
end else
begin
STORE[a2] STORE[a1] trail(a2)
end endbind
The bind operation
Copyright c Hassan A¨IT-KACI Reprinted from MIT Press |
PAGE 113 OF 129 |
WARREN’S ABSTRACT MACHINE
procedure trail (a : address)
if (a < HB) _ ((H < a) ^ (a < B))
then begin
TRAIL[TR] a TR TR + 1
end endtrail
The trail operation
procedure unwind trail(a1 a2 : address) for i a1 to a2 ; 1 do
STORE[TRAIL[i]] h REF TRAIL[i] i endunwind trail
The unwind trail operation
PAGE 114 OF 129 |
Reprinted from MIT Press Copyright c Hassan A¨IT-KACI |
A TUTORIAL RECONSTRUCTION
procedure tidy |
|
trail |
|
||
i STACK[B + STACK[B] + 5] |
||
while i < TR do |
||
if (TRAIL[i] < HB) _ ((H < TRAIL[i]) ^ (TRAIL[i] < B)) |
||
then i |
i + 1 |
|
else |
|
|
begin
TRAIL[i] TRAIL[TR ; 1] TR TR ; 1
end endtidy trail
The tidy trail operation
Copyright c Hassan A¨IT-KACI Reprinted from MIT Press |
PAGE 115 OF 129 |