% file:    hw10.pro

% This file can be loaded as is into Prolog. Run test.

% There are two problems, one involving state-puzzle solving, the 
% other involving compilation and a definite-clause grammar (DCG).
% The first one is extra credit.

% Problem 1 [50 points extra credit]
%
% Construct a Prolog program that finds a shortest solution to the
% generalized Towers-of-Hanoi problem.  The generalization is that
% there are T >= 3 spindles, rather than just 3, and N >= 1 disks.
% Use the iterative-deepening method to find the shortest solution.
% Tabulate the length of your solutions for T from 3 to 6, and N from 1 to 6.

% Problem 2 [100 points]
%
% Construct a grammar with semantics for a simple programming language
% to be compiled to the NoRM (No-Register Machine).  We give you the
% grammar without semantics. You need to fill in the code-generation
% part of the grammar.  We also give you the simulator for the NoRM
% in a separate file.  The provided tokenizer contains examples of how 
% to include semantics in a DCG.  The test cases at the end show
% examples of NoRM code generated by a compiler.  (For this simple
% language, you might not use all of the NoRM instruction repertoire.)

% Recommendation: Start with the simplest programs, then work upward.


% The Program grammar

program --> stmt.


% statement

stmt --> assignmentStmt | compoundStmt | conditionalStmt | iterationStmt.


% assignment statement 
%
%    Variable = Expression;

assignmentStmt --> lhsVar, [=], exp, [';'].


% compound statement
%
%    { ... 1 or more statements ... }

compoundStmt --> ['{'], stmt, stmtSequence, ['}'].

compoundStmt --> ['{'], stmt, ['}'].


% statement sequence

stmtSequence --> stmt, stmtSequence.

stmtSequence --> stmt.


% two-sided conditional
%
%    if ( boolean expression ) statement else statement

conditionalStmt --> 
            [if, '('], booleanExp, [')'], 
                stmt,
            [else], 
                stmt.

% one-sided conditional
%
%    if ( boolean expression ) statement

conditionalStmt --> 
            [if, '('], booleanExp, [')'], 
                stmt.

% iteration 
%
%    while ( boolean expression ) statement

iterationStmt --> 
            [while, '('], booleanExp, [')'], 
                stmt.

% Expressions

exp --> sum.

sum --> product, ['+'], sum.

sum --> product.

product --> primary, ['*'], product.

product --> primary.

primary --> ['('], exp, [')'].

primary --> rhsVar.

primary --> [C], {integer(C)}.


% Boolean expressions

booleanExp --> [true].

booleanExp --> [false].

booleanExp --> exp, relop, exp.

relop --> ['<'].

relop --> ['='].


% Right-hand side variables

rhsVar --> variable.


% Left-hand side variables

lhsVar --> variable.

variable --> [V], {isVar(V)}.

isVar(V) :-
    atom(V),
    validStart(V),
    \+reserved(V).

validStart(V) :-
    atom_chars(V, [F | _]),
    member(F, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]).


% Reserved identifiers

reserved(if).
reserved(else).
reserved(while).


% Dynamic predicates for record keeping and such

:- dynamic env/2, lastLoc/1, successes/1, failures/1.

lastLoc(0).
successes(0).
failures(0).

% Base environment compiler, relating variables to locations in data memory

env(u, 1).
env(v, 2).
env(w, 3).
env(x, 4).
env(y, 5).
env(z, 6).


% getLoc returns the location corresponding to a variable.
% If the variable was not allocated yet, it is allocated to
% the next free location.

getLoc(Var, Loc) :-
    env(Var, Loc) 
        -> true 
         ; retract(lastLoc(OldLoc)), 
           Loc is OldLoc + 1, 
           assert(env(Var, Loc)), 
           assert(lastLoc(Loc)).


% Append a list of lists together to get a single list.
% This might be useful.

append([], []).

append([F | R], L) :- append(R, A), append(F, A, L).


checkSyntax(Tokens) :- phrase(program, Tokens).

% Use this when your compiler productions are finished:
% compile(Program, Code) :- phrase(program(Code), Program).

% Test cases, using the NoRM processor definition

:- ensure_loaded('norm.pro').


% Memory load corresponding to variables above

initialMemoryLoad([10,20,30,40,50,60]).


% Test a program against expectations

test(Program, Expectations) :-
    write('Program: '), write(Program), nl,
    tokenize(Program, Tokens),
    write('Tokens: '), write(Tokens), nl,
    write('Expectations: '), write(Expectations), nl,
    (checkSyntax(Tokens) 
        -> (Expectations == success -> record_success ; record_failure(failure))
         ; (Expectations == failure -> record_success ; record_failure(success))
    ),
    nl.

/*
    Use this code instead for the compiler version:

    compile(Tokens, Code),
    write('NoRM Code: '), write(Code), nl,
    initialMemoryLoad(MemoryLoad),
    run(Code, MemoryLoad, FinalState),
    FinalState = state(Stack, Location, _, DataMemory),
    write('Final Location: '), write(Location), nl,
    write('Final Stack: '), write(Stack), nl,
    write('Final Data Memory: '), write(DataMemory), nl,
    write('Expectations: '), write(Expectations), nl,
    checkExpectations(Expectations, DataMemory),
    nl.
*/

% Get variable value for test purposes.

getVarValue(Var, Memory, Value) :-
    env(Var, Location),
    fetch(Location, Memory, Value).

% Check expectation

checkExpectations([], _).

checkExpectations([[Var, Value] | More], Memory) :-
    checkExpectation(Var, Value, Memory),
    checkExpectations(More, Memory).

checkExpectation(Var, Expected, Memory) :-
    write('Expectation '), write(Var), write(' = '), write(Expected),
    getVarValue(Var, Memory, Actual),
    (
    Expected == Actual
        -> record_success
         ; record_failure(Actual)
    ).

record_success :-
    write(' succeeded '), nl,
    increment(successes(_)).

record_failure(Actual) :-
    write(' failed, actual is '), write(Actual), write(' <<<<<< test failed '), nl,
    increment(failures(_)).

increment(Term) :-
    retract(Term),
    Term =.. [Functor, Arg],
    Arg1 is Arg + 1,
    NewTerm =.. [Functor, Arg1],
    assert(NewTerm).

report :-
    write('Test summary: '),
    successes(S), write(S), write(' successes, '),
    failures(F), write(F), write(' failures.').


% Tokenizer for our language. Use as is.

tokenize(Program, Tokens) :-
    atom_chars(Program, Chars),	% convert a single atom ("string") to char list
    phrase(tokens(Tokens), Chars). % parse the chars to a list of tokens


% Tokenizer productions in DCG Notation

% Produce a list of tokens.

tokens(Tokens) --> whitespace, {!}, tokens(Tokens).
tokens([Token | Tokens]) --> token(Token), {!}, tokens(Tokens).
tokens([]) --> [].

% Note that {!} (called "cut") intentionally prevents backtracking.


% Produce a single token, one of three types.

token(Token) --> numeric(Token) | identifier(Token) | specialChar(Token).


% An identifier is defined to be a letter (the "head") 
% followed by 0 or more letters and digits (the "tail").

identifier(Token) --> identifierHead(H), {!}, identifierTail(T), {atom_chars(Token, [H | T])}.

identifierHead(C) --> [C], {atom_chars('abcdefghijklmnopqrstuvwxyz', L), member(C, L)}.

identifierTail([C | T]) --> identifierChar(C), {!}, identifierTail(T).
identifierTail([]) --> [].

identifierChar(C) --> [C], {atom_chars('abcdefghijklmnopqrstuvwxyz0123456789', L), member(C, L)}.


% A 'numeric' is essentially a numeral, but we convert the numeral from an atom 
% to a Prolog number so that we can do arithmetic on it at a later time.

numeric(N) --> numeral(L), {atom_chars(A, L), safe_atom_number(A, N)}.

numeral([S | L]) --> sign(S), unsigned(L).
numeral(L) --> unsigned(L).

unsigned([D | L]) --> digit(D), unsigned(L).
unsigned([D]) --> digit(D).

digit(D) --> [D], {member(D, ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'])}.

sign(S) --> [S], {member(S, ['+', '-'])}.


specialChar(C) --> [C], {member(C, ['{', '}', '(', ')', ';', '+', '*', '=', '<'])}.


% Whitespace can appear at various places in a valid string.

whitespace --> whitespaceChar.
whitespace --> whitespaceChar, whitespace.

whitespaceChar --> [C], {member(C, [' '])}.


% convert atoms that are numeric into numbers, if possible

safe_atom_number(Atom, N) :-
    catch(atom_number(Atom, N), _, fail) -> true ; N = Atom.


/* Tests for the syntax-checking only version */

test :-
    test('x = 5 ;', success),
    test('x ;', failure),
    test('x = + ;', failure),
    test('x = z ;', success),
    test('x = y + z ;', success),
    test('x = y z ;', failure),
    test('x = u + v + w ;', success),
    test('x = u + v * w ;', success),
    test('x = u * v + w ;', success),
    test('x = u * v + + w ;', failure),
    test('x = u * v * w ;', success),
    test('x = ( u + v ) * w ;', success),
    test('x = u * ( v + w ) ;', success),
    test('x = u * v + w ) ;', failure),
    test('x = ( u + y ) * ( v + w ) ;', success),
    test('x = ( u * y ) +  v * w ) ;', failure),
    test('x = u * y + ( v * w ) ;', success),
    test('x = u * 9 + ( 8 * w ) ;', success),
    test('{ x = 5 ; y = 10 ; }', success),
    test('{ x = 5 ; y = x ; }', success),
    test('if ( y < 60 ) x = 5 ;', success),
    test('if ( y = 50 ) x = 5 ;', success),
    test('if ( y = 50 ) { x = 5 ;', failure),
    test('if ( y = 55 ) x = 5 ;', success),
    test('{ x = 0 ; while ( x < 5 ) x = x + 1 ; }', success),
    test('{ x = 0 ; y = 0 ; while ( x < 5 ) { x = x + 1 ; y = y + 5 ; } }', success),
    report.


/* Tests for the compile and execute version

test :-
    test('x = 5 ;', [[x, 5]]),
    test('x = z ;', [[x, 60]]),
    test('x = y + z ;', [[x, 110]]),
    test('x = u + v + w ;', [[x, 60]]),
    test('x = u + v * w ;', [[x, 610]]),
    test('x = u * v + w ;', [[x, 230]]),
    test('x = u * v * w ;', [[x, 6000]]),
    test('x = ( u + v ) * w ;', [[x, 900]]),
    test('x = u * ( v + w ) ;', [[x, 500]]),
    test('x = ( u + y ) * ( v + w ) ;', [[x, 3000]]),    
    test('x = ( u * y ) + ( v * w ) ;', [[x, 1100]]),
    test('x = u * y + ( v * w ) ;', [[x, 1100]]),    
    test('x = u * 9 + ( 8 * w ) ;', [[x, 330]]),    
    test('{ x = 5 ; y = 10 ; }', [[x, 5], [y, 10]]),
    test('{ x = 5 ; y = x ; }', [[x, 5], [y, 5]]),
    test('if ( y < 60 ) x = 5 ;', [[x, 5]]),
    test('if ( y = 50 ) x = 5 ;', [[x, 5]]),
    test('if ( y = 55 ) x = 5 ;', [[x, 40]]),
    test('{ x = 0 ; while ( x < 5 ) x = x + 1 ; }', [[x, 5]]),
    test('{ x = 0 ; y = 0 ; while ( x < 5 ) { x = x + 1 ; y = y + 5 ; } }', [[x, 5], [y, 25]]),
    test('{ x = 0 ; z = 0; while ( x < 5 ) { y = 0 ; while( y < x ) y = y + 5 ; z = z + y; x = x + 1 ; } }', 
          [[x, 5], [y, 5], [z, 20]]),
    test('{ x = 1 ; y = 15; z = 0; while ( x < y ) { x = 2 * x; z = z + 1;}}', [[x, 16], [z, 4]]),
    report.
*/

/* Output from the tests above, which show examples of NoRM code:
   Note that the env assertions earlier, which give that variables u, v, w, x, y, z
   are stored in locations 1, 2, 3, 4, 5, 6, respectively.

Program: x = 5 ;
Tokens: [x, =, 5, (;)]
NoRM Code: [push(5), store(4), pop, halt]
Final Location: 4
Final Stack: []
Final Data Memory: data(10, 20, 30, 5, 50, 60)
Expectations: [[x, 5]]
Expectation x = 5 met 

Program: x = z ;
Tokens: [x, =, z, (;)]
NoRM Code: [fetch(6), store(4), pop, halt]
Final Location: 4
Final Stack: []
Final Data Memory: data(10, 20, 30, 60, 50, 60)
Expectations: [[x, 60]]
Expectation x = 60 met 

Program: x = y + z ;
Tokens: [x, =, y, +, z, (;)]
NoRM Code: [fetch(5), fetch(6), add, store(4), pop, halt]
Final Location: 6
Final Stack: []
Final Data Memory: data(10, 20, 30, 110, 50, 60)
Expectations: [[x, 110]]
Expectation x = 110 met 

Program: x = u + v + w ;
Tokens: [x, =, u, +, v, +, w, (;)]
NoRM Code: [fetch(1), fetch(2), add, fetch(3), add, store(4), pop, halt]
Final Location: 8
Final Stack: []
Final Data Memory: data(10, 20, 30, 60, 50, 60)
Expectations: [[x, 60]]
Expectation x = 60 met 

Program: x = u + v * w ;
Tokens: [x, =, u, +, v, *, w, (;)]
NoRM Code: [fetch(1), fetch(2), fetch(3), multiply, add, store(4), pop, halt]
Final Location: 8
Final Stack: []
Final Data Memory: data(10, 20, 30, 610, 50, 60)
Expectations: [[x, 610]]
Expectation x = 610 met 

Program: x = u * v + w ;
Tokens: [x, =, u, *, v, +, w, (;)]
NoRM Code: [fetch(1), fetch(2), multiply, fetch(3), add, store(4), pop, halt]
Final Location: 8
Final Stack: []
Final Data Memory: data(10, 20, 30, 230, 50, 60)
Expectations: [[x, 230]]
Expectation x = 230 met 

Program: x = u * v * w ;
Tokens: [x, =, u, *, v, *, w, (;)]
NoRM Code: [fetch(1), fetch(2), fetch(3), multiply, multiply, store(4), pop, halt]
Final Location: 8
Final Stack: []
Final Data Memory: data(10, 20, 30, 6000, 50, 60)
Expectations: [[x, 6000]]
Expectation x = 6000 met 

Program: x = ( u + v ) * w ;
Tokens: [x, =, (, u, +, v, ), *, w, (;)]
NoRM Code: [fetch(1), fetch(2), add, fetch(3), multiply, store(4), pop, halt]
Final Location: 8
Final Stack: []
Final Data Memory: data(10, 20, 30, 900, 50, 60)
Expectations: [[x, 900]]
Expectation x = 900 met 

Program: x = u * ( v + w ) ;
Tokens: [x, =, u, *, (, v, +, w, ), (;)]
NoRM Code: [fetch(1), fetch(2), fetch(3), add, multiply, store(4), pop, halt]
Final Location: 8
Final Stack: []
Final Data Memory: data(10, 20, 30, 500, 50, 60)
Expectations: [[x, 500]]
Expectation x = 500 met 

Program: x = ( u + y ) * ( v + w ) ;
Tokens: [x, =, (, u, +, y, ), *, (, v, +, w, ), (;)]
NoRM Code: [fetch(1), fetch(5), add, fetch(2), fetch(3), add, multiply, store(4), pop, halt]
Final Location: 10
Final Stack: []
Final Data Memory: data(10, 20, 30, 3000, 50, 60)
Expectations: [[x, 3000]]
Expectation x = 3000 met 

Program: x = ( u * y ) + ( v * w ) ;
Tokens: [x, =, (, u, *, y, ), +, (, v, *, w, ), (;)]
NoRM Code: [fetch(1), fetch(5), multiply, fetch(2), fetch(3), multiply, add, store(4), pop, halt]
Final Location: 10
Final Stack: []
Final Data Memory: data(10, 20, 30, 1100, 50, 60)
Expectations: [[x, 1100]]
Expectation x = 1100 met 

Program: x = u * y + ( v * w ) ;
Tokens: [x, =, u, *, y, +, (, v, *, w, ), (;)]
NoRM Code: [fetch(1), fetch(5), multiply, fetch(2), fetch(3), multiply, add, store(4), pop, halt]
Final Location: 10
Final Stack: []
Final Data Memory: data(10, 20, 30, 1100, 50, 60)
Expectations: [[x, 1100]]
Expectation x = 1100 met 

Program: x = u * 9 + ( 8 * w ) ;
Tokens: [x, =, u, *, 9, +, (, 8, *, w, ), (;)]
NoRM Code: [fetch(1), push(9), multiply, push(8), fetch(3), multiply, add, store(4), pop, halt]
Final Location: 10
Final Stack: []
Final Data Memory: data(10, 20, 30, 330, 50, 60)
Expectations: [[x, 330]]
Expectation x = 330 met 

Program: { x = 5 ; y = 10 ; }
Tokens: [{, x, =, 5, (;), y, =, 10, (;), }]
NoRM Code: [push(5), store(4), pop, push(10), store(5), pop, halt]
Final Location: 7
Final Stack: []
Final Data Memory: data(10, 20, 30, 5, 10, 60)
Expectations: [[x, 5], [y, 10]]
Expectation x = 5 met 
Expectation y = 10 met 

Program: { x = 5 ; y = x ; }
Tokens: [{, x, =, 5, (;), y, =, x, (;), }]
NoRM Code: [push(5), store(4), pop, fetch(4), store(5), pop, halt]
Final Location: 7
Final Stack: []
Final Data Memory: data(10, 20, 30, 5, 5, 60)
Expectations: [[x, 5], [y, 5]]
Expectation x = 5 met 
Expectation y = 5 met 

Program: if ( y < 60 ) x = 5 ;
Tokens: [if, (, y, <, 60, ), x, =, 5, (;)]
NoRM Code: [push(60), fetch(5), less, jump(4), push(5), store(4), pop, halt]
Final Location: 8
Final Stack: []
Final Data Memory: data(10, 20, 30, 5, 50, 60)
Expectations: [[x, 5]]
Expectation x = 5 met 

Program: if ( y = 50 ) x = 5 ;
Tokens: [if, (, y, =, 50, ), x, =, 5, (;)]
NoRM Code: [push(50), fetch(5), equal, jump(4), push(5), store(4), pop, halt]
Final Location: 8
Final Stack: [50, 50]
Final Data Memory: data(10, 20, 30, 5, 50, 60)
Expectations: [[x, 5]]
Expectation x = 5 met 

Program: if ( y = 55 ) x = 5 ;
Tokens: [if, (, y, =, 55, ), x, =, 5, (;)]
NoRM Code: [push(55), fetch(5), equal, jump(4), push(5), store(4), pop, halt]
Final Location: 8
Final Stack: [50, 55]
Final Data Memory: data(10, 20, 30, 40, 50, 60)
Expectations: [[x, 40]]
Expectation x = 40 met 

Program: { x = 0 ; while ( x < 5 ) x = x + 1 ; }
Tokens: [{, x, =, 0, (;), while, (, x, <, 5, ), x, =, x, +, 1, (;), }]
NoRM Code: [push(0), store(4), pop, push(5), fetch(4), less, jump(8), fetch(4), push(1), add, store(4), pop, push(0), jump(-10), halt]
Final Location: 15
Final Stack: []
Final Data Memory: data(10, 20, 30, 5, 50, 60)
Expectations: [[x, 5]]
Expectation x = 5 met 

Program: { x = 0 ; y = 0 ; while ( x < 5 ) { x = x + 1 ; y = y + 5 ; } }
Tokens: [{, x, =, 0, (;), y, =, 0, (;), while, (, x, <, 5, ), {, x, =, x, +, 1, (;), y, =, y, +, 5, (;), }, }]
NoRM Code: [push(0), store(4), pop, push(0), store(5), pop, push(5), fetch(4), less, jump(13), fetch(4), push(1), add, store(4), pop, fetch(5), push(5), add, store(5), pop, push(0), jump(-15), halt]
Final Location: 23
Final Stack: []
Final Data Memory: data(10, 20, 30, 5, 25, 60)
Expectations: [[x, 5], [y, 25]]
Expectation x = 5 met 
Expectation y = 25 met 

Program: { x = 0 ; z = 0; while ( x < 5 ) { y = 0 ; while( y < x ) y = y + 5 ; z = z + y; x = x + 1 ; } }
Tokens: [{, x, =, 0, (;), z, =, 0, (;), while, (, x, <, 5, ), {, y, =, 0, (;), while, (, y, <, x, ), y, =, y, +, 5, (;), z, =, z, +, y, (;), x, =, x, +, 1, (;), }, }]
NoRM Code: [push(0), store(4), pop, push(0), store(6), pop, push(5), fetch(4), less, jump(27), push(0), store(5), pop, fetch(4), fetch(5), less, jump(8), fetch(5), push(5), add, store(5), pop, push(0), jump(-10), fetch(6), fetch(5), add, store(6), pop, fetch(4), push(1), add, store(4), pop, push(0), jump(-29), halt]
Final Location: 37
Final Stack: []
Final Data Memory: data(10, 20, 30, 5, 5, 20)
Expectations: [[x, 5], [y, 5], [z, 20]]
Expectation x = 5 met 
Expectation y = 5 met 
Expectation z = 20 met 

Program: { x = 1 ; y = 15; z = 0; while ( x < y ) { x = 2 * x; z = z + 1;}}
Tokens: [{, x, =, 1, (;), y, =, 15, (;), z, =, 0, (;), while, (, x, <, y, ), {, x, =, 2, *, x, (;), z, =, z, +, 1, (;), }, }]
NoRM Code: [push(1), store(4), pop, push(15), store(5), pop, push(0), store(6), pop, fetch(5), fetch(4), less, jump(13), push(2), fetch(4), multiply, store(4), pop, fetch(6), push(1), add, store(6), pop, push(0), jump(-15), halt]
Final Location: 26
Final Stack: []
Final Data Memory: data(10, 20, 30, 16, 15, 4)
Expectations: [[x, 16], [z, 4]]
Expectation x = 16 met 
Expectation z = 4 met 

Test summary: 28 successes, 0 failures.

*/