The WAM

The Warren Abstract Machine (1983) is the classic compilation target for Prolog.

The Warren Abstract Machine (1983) is the classic compilation target for Prolog.

38.1 Memory areas

Heap (global stack) terms/structures created during execution Stack (local stack) environments (frames) and choice points addresses of variable bindings to undo on backtracking push-down list used by unification

38.2 Registers

P (program counter), CP (continuation), E (current environment), B (latest choice point), H (heap top), HB (heap backtrack point), TR (trail top), S (structure pointer), argument registers A1..An/X1..Xn.

38.3 Instruction groups

put (build arguments) put_variable, put_value, put_structure, put_constant, put_list get (unify head args)

get_variable, get_value, get_structure, get_constant, get_list unify (structure args)

unify_variable, unify_value, unify_constant, unify_void

call, execute (last call), proceed, allocate, deallocate

try_me_else, retry_me_else, trust_me, try, retry, trust

switch_on_term, switch_on_constant, switch_on_structure neck_cut, get_level, cut

38.4 Example

compiles roughly to:

Reference: Hassan Aït-Kaci, *Warren's Abstract Machine: A Tutorial Reconstruction* (free).

append([], L, L).
append([H|T], L, [H|R]) :- append(T, L, R).

append/3: switch_on_term C1, C1, C2, fail
C1: try_me_else C2
    get_constant [], A1
    get_value A2, A3
    proceed
C2: trust_me
    get_list A1
    unify_variable X4      % H
    unify_variable A1      % T
    get_list A3
    unify_value X4         % H
    unify_variable A3      % R
    execute append/3       % last call optimization