% Fortolkeren for while-sproget
%
%
% Skrevet af Henning Christiansen, februar 1999 (c)
%

% Oversaetteren er beskrevet i Sprog og abstrakte maskiner, afs. 6.2


:- use_module(library(lists)).

% Abstrakt grammatik for While-sproget
%
%    program::= saetning
%
%    saetning::= tom
%            |  saetning ; saetning
%            |  variabel := udtryk
%            |  if( betingelse, saetning, saetning)
%            |  while( betingelse, saetning)
%
%    udtryk ::= ... heltal med +, -, * og variable
%
%    betingelse ::= sand | falsk
%            | udtryk = udtryk | .. og andre sammenligninger
%            | udtryk /\ udtryk | udtryk \/ udtryk | \+ udtryk 
%         
%    variabel ::= hvad der tilfredsstiller atom(-).

%%%%% Operatorer:

:- op(800,xfx, :=).

% Systemet har allerede op(500, yfx, [/\, \/])
% og op(900, fy, \+), samt de saedvanlige regne-operationer

%%%%% Testeksempel (se ogsaa simplere i slutning af filen)
%
% Euklids algoritme til at finde stoerste faelles
% divisor af to tal, a og b.

% Til slut indeholder baade a og b resultatet.

/*

program( ( a:= 221 ; b:= 493 ;
           while( a =\= b,
                  if( a > b,
                      a:= a-b,
                      b:= b-a))), Lager).

*/

% Vi arbejder ud fra foelgende behagelige antagelser:
% - ingen sideeffekter i udtryk
% - ingen goto's

program(P, Lager) :- saetning(P, [], Lager).

% saetning( saetning, lager-foer, lager-efter)

saetning(tom, L, L).

saetning( (S1 ; S2), L1, L3):-
    saetning(S1, L1, L2),
    saetning(S2, L2, L3).

saetning( (Var := Udtryk), L1, L2):-
    udtryk( Udtryk, L1, Vaerdi),
    erstat( Var,Vaerdi,L1,L2).

saetning( if( Bet, Saetning1, Saetning2), L1, L2):-
    betingelse(Bet, L1, Vaerdi),
    (Vaerdi = sand ->
         saetning(Saetning1, L1, L2)
     ;
       saetning(Saetning2, L1, L2)).
    
saetning( while( Bet, Saetning), L1, L2):-
    betingelse(Bet, L1, Vaerdi),
    (Vaerdi = sand ->
          saetning( (Saetning ; while( Bet, Saetning)), L1, L2)
     ;
       L1 = L2).

% udtryk( udtryk, lager, vaerdi)

udtryk( Tal, _, Tal):- integer(Tal).

udtryk( Variabel, L, V):- atom(Variabel),
    hent(Variabel,V,L).

udtryk( (Udtryk1 + Udtryk2), L, Res):-    % syntaktisk plus
    udtryk( Udtryk1, L, V1),
    udtryk( Udtryk2, L, V2),
    Res is V1 + V2.                      % 'semantisk' plus

udtryk( (Udtryk1 - Udtryk2), L, Res):-    % syntaktisk minus
    udtryk( Udtryk1, L, V1),
    udtryk( Udtryk2, L, V2),
    Res is V1 - V2.                      % 'semantisk' minus

udtryk( (Udtryk1 * Udtryk2), L, Res):-    % syntaktisk gange
    udtryk( Udtryk1, L, V1),
    udtryk( Udtryk2, L, V2),
    Res is V1 * V2.                      % 'semantisk' gange

betingelse( (Udtryk1 = Udtryk2), L, Res):-    % syntaktisk =
    udtryk( Udtryk1, L, V1),
    udtryk( Udtryk2, L, V2),
    (V1 = V2 -> Res = sand                    % 'semantisk' =
      ;
      Res = falsk).


betingelse( (Udtryk1 > Udtryk2), L, Res):-    % syntaktisk >
    udtryk( Udtryk1, L, V1),
    udtryk( Udtryk2, L, V2),
    (V1 > V2 -> Res = sand                    % 'semantisk' >
      ;
      Res = falsk).

betingelse( sand, _, sand).         % syntaktisk sand -> sem. sand

betingelse( falsk, _, falsk).       % syntaktisk falsk -> sem. falsk
 
betingelse( (Udtryk1 >= Udtryk2), L, Res):-    % syntaktisk >=
    udtryk( Udtryk1, L, V1),
    udtryk( Udtryk2, L, V2),
    (V1 >= V2 -> Res = sand                    % 'semantisk' >=
      ;
      Res = falsk).


betingelse( (Udtryk1 < Udtryk2), L, Res):-    % syntaktisk <
    udtryk( Udtryk1, L, V1),
    udtryk( Udtryk2, L, V2),
    (V1 < V2 -> Res = sand                    % 'semantisk' <
      ;
      Res = falsk).


betingelse( (Udtryk1 =< Udtryk2), L, Res):-    % syntaktisk =<
    udtryk( Udtryk1, L, V1),
    udtryk( Udtryk2, L, V2),
    (V1 =< V2 -> Res = sand                    % 'semantisk' =
      ;
      Res = falsk).


betingelse( (Udtryk1 =\= Udtryk2), L, Res):-    % syntaktisk =\=
    udtryk( Udtryk1, L, V1),
    udtryk( Udtryk2, L, V2),
    (V1 =\= V2 -> Res = sand                    % 'semantisk' =\=
      ;
      Res = falsk).


betingelse( (Betingelse1 /\ Betingelse2), L, Res):- 
    betingelse( Betingelse1, L, V1),
    betingelse( Betingelse2, L, V2),
    (V1 = falsk -> Res = falsk
     ;
     V2 = falsk -> Res = falsk
     ;
     Res = sand).


betingelse( (Betingelse1 \/ Betingelse2), L, Res):- 
    betingelse( Betingelse1, L, V1),
    betingelse( Betingelse2, L, V2),
    (V1 = sand -> Res = sand
     ;
     V2 = sand -> Res = sand
     ;
     Res = falsk).


betingelse( (\+ Betingelse), L, Res):- 
    betingelse( Betingelse, L, V),
    (V = sand -> Res = falsk
     ;
     Res = sand).




%%%%%%%%%%%%%%%%%%%%%%%%
% Hjaelpere

% erstat(variabel,vaerdi,lager,nyt-lager)

erstat(V,X,[],[(V=X)]).

erstat(V,X,[(V=_)|L],[(V=X)|L]):- !.

erstat(V,X,[Bind|L0],[Bind|L1]):-
	erstat(V,X,L0,L1).


% hent(variabel, vaerdi,lager)

hent(Var,X,L):-
	member((Var=X),L) -> true
	; 
	X = 0.

%%%%%%%%%% Testforespoergsler

/*

program((x:=7;y:=8),L).

program(if(1=1,x:=1,x:=2),L).

program(if(1=2,x:=1,x:=2),L).

program( (x:=5; while(x>0,y:=y+3)), L). % OBS!

program( (x:=5; while(x>0,(x:=x-1;y:=y+3))), L).

*/