1. Končni simboli (keywords našega programskega jezika: begin, end, print, while, do, :=
2. Primer programa (kot dcg stavek: [begin, a,:=,2, print(a), end]):

begin
  a := 2
  print(a)
end

1. Pomen programa je funkcija, ki slika iz vhoda v izhod.
   • struktura fun(In, Out, Goals) veže skupaj vhodno/izhodno stanje in prologove cilje, ki predstavljajo preslikavo
   • apply(In, Out, fun(In, Out, Goals)) dejansko izvede cilje v Goals
     • ?- F = fun(In, Out, Out is In*In), apply(7, Out, F).
2. Kako predstaviti interno stanje programa?
   • seznam spremenljivk: [a=3,b=4]
   • ob vrhnjem klicu apply je potrebno spremenljivke „deklarirati“
   • posebna spremenljivka printout hrani izpisane vrednosti
     • deklarira jo pravilo za algol
3. Za vsak ukaz definiramo ustrezno funkcijo (zaporedje prologovih ciljev).
   • print
   • assign
     • poseben simbol, ker v nekaterih kontekstih ne moremo uporabiti poljubnega ukaza (npr. za for)
   • cond
   • while
     • loop/4
       • copy_term naredi kopijo cilja s svežimi spremenljivkami (sicer bi v drugi iteraciji imeli fun(…) z že instanciranimi vrednostmi)

?- program(F, [begin, a,:=,2, print(a), print(a+2), end], []), apply([a=0], S, F).

% program
algol(fun(S0,S,apply([printout=[]|S0],S,Minstructs))) -->
  [begin], instructs(Minstructs), [end].

% sequence of instructions
instructs(Minstr) --> instr(Minstr).
instructs(fun(S0,S,
  (apply(S0,S1,Minstr),
   apply(S1,S,Minstructs)))) 
  --> 
  instr(Minstr), instructs(Minstructs).

% assignment statement
instr(Massign) --> assign(Massign).
assign(fun(S0,[X = Value|S1], 
  (apply(S0,Value,Mexpr),
   del(X = _,S0,S1)))) 
  -->
  var(X), [:=], expr(Mexpr).

% print statement
instr(fun(S0,[printout = L1|S1],
  (memb(X = V,S0),
   del(printout = L0,S0,S1),
   conc(L0,[V],L1))))
  -->
  [print(X)].

% while loop statement
instr(fun(S0,S,
  loop(S0,Mcond,Minstructs,S)))
  -->
  [while], cond(Mcond), [do,begin], instructs(Minstructs), [end].

% conditional expression (a < b)
cond(fun(S, TruthVal,
  (apply(S,Val1,ME1),
   apply(S,Val2,ME2),
   (Val1 < Val2, !,
    TruthVal = true
    ;
    TruthVal = false))))
  -->
  expr(ME1), [<], expr(ME2).

% variable
var(X) --> [X], { atom(X) }.

% arithmetic expression
expr(fun(S,Value,eval(Expr,S,Value))) --> [Expr].

% helper predicates
% function call
apply(In, Out, fun(In, Out, Goals)):-
  call(Goals).

% while loop
loop(State0, Mcond, _, State0) :-
  apply(State0, false, Mcond), !. % pogoj neresnicen 
loop(S0, Mcond, MBody, S) :- 
  copy_term(MBody, MBodyCopy),    % kopiraj cilje
  apply(S0, S1, MBody),           % izvedi telo zanke
  loop(S1, Mcond, MBodyCopy, S).  % naslednja iteracija

% evaluate expression
eval(N, _, N) :-
  number(N), !.
eval(X, State, Val) :-  % a program variable
  atom(X), !, 
  memb(X = Val, State). 
eval(E1 + E2, State, Val) :- !,
  eval(E1, State, V1),
  eval(E2, State, V2),
  Val is V1 + V2.
eval(E1 - E2, State, Val) :- !,
  eval(E1, State, V1),
  eval(E2, State, V2),
  Val is V1 - V2.
eval(E1 * E2, State, Val) :- !,
  eval(E1, State, V1),
  eval(E2, State, V2),
  Val is V1 * V2.
eval(E1 / E2, State, Val) :- !,
  eval(E1, State, V1),
  eval(E2, State, V2),
  Val is V1 / V2.

1. Razširitve za osnovno DCG
   • print za splošne izraze
   • stavek if
   • stavek for
2. Predprocesor, ki samodejno vrne začetno stanje z deklaracijami spremenljivk