% Oversaetter fra while-sproget til
% Mini-Stak-og-variabel-maskinens sprog
%
%
% Skrevet af Henning Christiansen, februar 1999 (c)
%

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


:- 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

:- op(700, xfx, <-). % svarende til 'is'

%%%%% Testeksempel
%
% Euklids algoritme til at finde stoerste faelles
% divisor af to tal, a og b.

% Til slut indeholder baade a og b resultatet.

% Nedenfor oversaetter vi og sender videre til
% Mini-stak-og-variabel-maskinens fortolker (som skal vaere consultet).
/*

program( ( a:= 221 ; b:= 493 ;
           while( a =\= b,
                  if( a > b,
                      a:= a-b,
                      b:= b-a))), K),
write(K),nl,
prog( K, S, L).

*/

program(P, K):- saetning(P, K).

saetning(tom, []).


saetning( (S1 ; S2), K):-
    saetning(S1, K1),
    saetning(S2, K2),
    K <- K1 + K2.


saetning( (Var := Udtryk), K):-
    udtryk( Udtryk, K1),
    K <- K1 + gem(Var).


saetning( if( Bet, Saetning1, Saetning2), K):-
    betingelse(Bet, Kbet),
    saetning(Saetning1, K1),
    saetning(Saetning2, K2),
    ny_etikette(E2), ny_etikette(Eslut),
    K <-    Kbet +
            n_hop(E2) +
            K1 +
            hop(Eslut) +
       E2 + K2 +
       Eslut.

    
saetning( while( Bet, Saetning), K):-
    betingelse(Bet, Kbet),
    saetning( Saetning, K1),
    ny_etikette(Estart), ny_etikette(Eslut),
    K <-  Estart + Kbet +
                   n_hop(Eslut) +
                   K1 +
                   hop(Estart) +
          Eslut.


udtryk( Tal, K):- 
    integer(Tal),
    K <- stak(Tal).


udtryk( Variabel, K):-
   atom(Variabel),
   K <- hent(Variabel).


udtryk( (Udtryk1 + Udtryk2), K):-
    udtryk( Udtryk1, K1),
    udtryk( Udtryk2, K2),
    K <- K1 + K2 + udregn(+).


udtryk( (Udtryk1 - Udtryk2), K):-
    udtryk( Udtryk1, K1),
    udtryk( Udtryk2, K2),
    K <- K1 + K2 + udregn(-).


udtryk( (Udtryk1 * Udtryk2), K):-
    udtryk( Udtryk1, K1),
    udtryk( Udtryk2, K2),
    K <- K1 + K2 + udregn(*).


betingelse( sand,  stak(ja)).

betingelse( falsk, stak(nej)).


betingelse( (Udtryk1 = Udtryk2), K):-
    udtryk( Udtryk1, K1),
    udtryk( Udtryk2, K2),
    K <- K1 + K2 + udregn(=).


betingelse( (Udtryk1 > Udtryk2), K):-
    udtryk( Udtryk1, K1),
    udtryk( Udtryk2, K2),
    K <- K1 + K2 + udregn(>).


betingelse( (Udtryk1 >= Udtryk2), K):-
    udtryk( Udtryk1, K1),
    udtryk( Udtryk2, K2),
    K <- K1 + K2 + udregn(>=).


betingelse( (Udtryk1 < Udtryk2), K):-
    udtryk( Udtryk1, K1),
    udtryk( Udtryk2, K2),
    K <- K1 + K2 + udregn(<).


betingelse( (Udtryk1 =< Udtryk2), K):-
    udtryk( Udtryk1, K1),
    udtryk( Udtryk2, K2),
    K <- K1 + K2 + udregn(=<).


betingelse( (Udtryk1 =\= Udtryk2), K):-
    udtryk( Udtryk1, K1),
    udtryk( Udtryk2, K2),
    K <- K1 + K2 + udregn(=\=).


betingelse( (Betingelse1 /\ Betingelse2), K):-
    betingelse( Betingelse1, K1),
    betingelse( Betingelse2, K2),
    K <- K1 + K2 + udregn(/\).


betingelse( (Betingelse1 \/ Betingelse2), K):- 
    betingelse( Betingelse1, K1),
    betingelse( Betingelse2, K2),
    K <- K1 + K2 + udregn(\/).


betingelse( (Betingelse1 \/ Betingelse2), K):- 
    betingelse( Betingelse1, K1),
    betingelse( Betingelse2, K2),
    K <- K1 + K2 + udregn(\/).


betingelse( (\+ Betingelse), K):- 
    betingelse( Betingelse, K1),
    ny_etikette(L), ny_etikette(L),
    K <- K1 + [     n_hop(L),
                    stak(nej),
                    hop(Slut),
                 L, stak(ja),
                 Slut
              ].




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

% Hjaelpepraedikat til beskrivelse af oversaettelse
% - skrevet ved en infix-operator <-
% - oversaettelsen komponeres vha. + operatoren,
%
%
%
% Variabel <- nul eller flere lister eller andre-objekter
%             adskilt med +,
%
% Variabel instantieres til en liste, som indeholder
% de omtale listers elementer og andre-objekter i den
% raekkefoelge, de forekommer.


:- op(700, xfx, <-). % svarende til 'is'

[] <- []:- !.

Sekvens <- Et + To :-
    !, Sekvens <- [Et | To].

Sekvens <- [Ho | Ha] :-
    !,
    HoSekvens <- Ho,
    HaSekvens <- Ha,
    append(HoSekvens, HaSekvens, Sekvens).

[NonList] <- NonList.

%%%%%%%%%%%%%%%%%%%%%%%%%

ny_etikette(N):-
    retract( naeste(N) ),
    N1 is N+1,
    asserta( naeste(N1)).  

:- dynamic naeste/1.

naeste(0).