A while ago, I came across a fascinating blog entry apparently detailing how to embed an ALGOL-like language in Prolog, with a compelling concrete syntax exposed. However, as the comments indicate, his code did not work as is. Changing the “then” and “else” creators to be infix and adhering to the defined convention of “if {Cond} …” (he used “if(Cond) …”) seems to make his code samples work.
Here’s a more friendly guide to getting this awesome code to work. Skip to “code samples” below for awesome examples of this embedded language in action.
My system setup
I am running Ubuntu Hardy with SWI-Prolog 5.6.47; I installed SWI-Prolog straight from the Debian packages (through Synaptic, the usual way). Just get yourself a copy of Ubuntu and install SWI Prolog the sane way and this code should work.
The interpreter
change_member(_, N, [], [N]).
change_member(O, N, [O|XS], [N|XS]).
change_member(O, N, [X|XS], [X|YS]) :- change_member(O, N, XS, YS).
:- op(900, xfy, :=).
:- op(100, fx, [if]).
:- op(125, fx, [while, return]).
:- op(125, yfx, [do, then, else]).
run({Block}, EnvI, O, Ret) :-
run(Block, EnvI, O, Ret).
run((First; Second), EnvI, O, Ret) :-
run(First, EnvI, M, _), run(Second, M, O, Ret).
run(Place := Expr, EnvI, O, void) :-
eval(Expr, Value, EnvI), change_member(Place = _, Place = Value, EnvI, O), !.
run(if {Cond} then {This} else {That}, EnvI, O, Ret) :-
eval(Cond, Value, EnvI),
( Value = true -> Body = This ; Body = That ),
run(Body, EnvI, O, Ret).
run(while(Cond) do {Body}, EnvI, O, Ret) :-
eval(Cond, Value, EnvI),
( Value = true -> run(Body, EnvI, M, _),
run(while(Cond) do {Body}, M, O, Ret)
; O = EnvI, Ret = void
).
run(return Value, EnvI, O, Ret) :-
eval(Value, Ret, EnvI), O = EnvI.
eval(Var, Val, Env) :- member(Var = Val, Env), !.
eval(Num, Num, _ ) :- number(Num), !.
eval(true, true, _ ).
eval(false, false, _ ).
eval(X + Y, Z, Env) :- eval(X, XV, Env), eval(Y, YV, Env), Z is XV + YV.
eval(X - Y, Z, Env) :- eval(X, XV, Env), eval(Y, YV, Env), Z is XV - YV.
eval(X * Y, Z, Env) :- eval(X, XV, Env), eval(Y, YV, Env), Z is XV * YV.
eval(X / Y, Z, Env) :- eval(X, XV, Env), eval(Y, YV, Env), Z is truncate(XV / YV).
eval(X = Y, B, Env) :- eval(X, XV, Env), eval(Y, YV, Env),
( XV = YV -> B = true ; B = false ).
eval(X < Y, B, Env) :- eval(X, XV, Env), eval(Y, YV, Env),
( XV < YV -> B = true ; B = false ).
eval(X > Y, B, Env) :- eval(X, XV, Env), eval(Y, YV, Env),
( XV > YV -> B = true ; B = false ).
eval(not(P), B, Env) :- eval(P, PV, Env),
( PV = true -> B = false ; B = true ).
Language samples
Here are samples of using this little embedded language we’ve built along with the evaluation results in comments.
factorial(N, {i := 1;
n := N;
while(n > 0) do {
i := i * n;
n := n - 1
};
return i}).
%% ?- factorial(5, P), run(P, [], _, X).
%% X = 120
fibonacci(F, {i := 1; a := 1; b := 1;
while(not(i = F)) do {
a := a + b;
b := a - b;
i := i + 1
};
return b}).
%% ?- fibonacci(7, P), run(P, [], _, X).
%% X = 13
pow2(N, {i := N;
n := 1;
while(not(i = 0)) do {
i := i - 1;
n := n * 2
};
return n}).
%% ?- pow2(8, P), run(P, [], _, X).
%% X = 256
gcd(X, Y,
{x := X;
y := Y;
while(not(x = 0)) do {
if {x < y} then {
y := y - x
}
else {
x := x - y
}
};
return y}).
%% ?- A is 2*2*5*7*13, B is 5*13*7*7, gcd(A, B, P), run(P, [], _, X).
%% A = 1820,
%% B = 3185,
%% X = 455
isqrt(N, {q := N; p := (q + N / q) / 2;
while(q > p) do {
q := p;
p := (q + N / q) / 2
};
return p}).
%% ?- isqrt(81, P), run(P, [], _, X).
%% X = 9
Discussion
As best I can tell this actually works. For instance, evaluating our Fibonacci function at 150 gives the correct value, spitting back 9969216677189303386214405760200 as should be the case. Notice how, therefore, we get, among many other things, SWI-Prolog’s built-in arbitrary-precision integers for free — a classic example of why embedded domain-specific languages are such a huge win.
The implementation depends heavily on Prolog’s excellent support for custom symbolic operators and pattern matching abilities, even tolerating added bits of syntactic sugar like the brackets used to delimit boolean conditions in our if-then-else blocks.
Obviously you wouldn’t want to use an interpreter this trivial for serious production/mission-critical stuff, but I think it definitely provides a compelling answer to how far a computer language could conceivably be extended to support new syntax. Languages that claim to support language-oriented programming, but don’t support custom operators with custom fixity and precedence — you’re on notice.
