Interpreters & Compilers

36.1 An interpreter for a small imperative language

% Program AST: assign(Var, Expr), seq(S1, S2), if(Cond, Then, Else), while(Cond, Body), print(Expr)
exec(assign(V, E), Env0, Env) :- eval(E, Env0, Val), put_assoc(V, Env0, Val, Env).
exec(seq(S1, S2), E0, E) :- exec(S1, E0, E1), exec(S2, E1, E).
exec(if(C, T, F), E0, E) :- ( eval(C, E0, true) -> exec(T, E0, E) ; exec(F, E0, E) ).
exec(while(C, B), E0, E) :-
    (   eval(C, E0, true) -> exec(B, E0, E1), exec(while(C, B), E1, E)
    ;   E = E0 ).
exec(print(Ex), E, E) :- eval(Ex, E, V), writeln(V).

eval(N, _, N) :- number(N).
eval(V, Env, Val) :- atom(V), V \== true, V \== false, get_assoc(V, Env, Val).
eval(A + B, E, V) :- eval(A, E, VA), eval(B, E, VB), V is VA + VB.
eval(A - B, E, V) :- eval(A, E, VA), eval(B, E, VB), V is VA - VB.
eval(A * B, E, V) :- eval(A, E, VA), eval(B, E, VB), V is VA * VB.
eval(A < B, E, T) :- eval(A, E, VA), eval(B, E, VB), ( VA < VB -> T = true ; T = false ).

run(Prog) :- empty_assoc(E), exec(Prog, E, _).

?- run(seq(assign(i, 0), while(i < 3, seq(print(i), assign(i, i + 1))))).

36.2 Pipeline: lexer → parser (DCG) → AST → evaluator/compiler

Lexer: DCG over chars producing tokens.

Parser: DCG over tokens producing ASTs (handle precedence with layered non-terminals).

Type checker: unification-based inference.

Code generation: emit stack-machine instructions with DCGs (output as difference lists).

% Compile expressions to stack code
compile(N) --> { number(N) }, [push(N)].
compile(A + B) --> compile(A), compile(B), [add].
compile(A * B) --> compile(A), compile(B), [mul].

?- phrase(compile(2 + 3 * 4), Code).    % [push(2), push(3), push(4), mul, add]

36.3 Hindley–Milner type inference (sketch)

type(_, N, int) :- integer(N).
type(Env, var(X), T) :- memberchk(X-T0, Env), copy_term(T0, T).   % (simplified generalization)
type(Env, lam(X, B), A -> R) :- type([X-A|Env], B, R).
type(Env, app(F, Arg), R) :- type(Env, F, A -> R), type(Env, Arg, A).

?- type([], lam(x, var(x)), T).          % T = (A -> A)