% file:          norm.pro
% last revision: 9 April 2008, 1:53 p.m.
% author:        Robert Keller
% purpose:       Execution model for NoRM (No-Register Machine)

% run runs a given instruction sequence with a memmory initialized by
% successive location contents (starting at location 1), returning
% the final state (Stack, Location, Instruction Memory, Data Memory)

run(InstructionSequence, InitialDataSequence, FinalState) :-
    run(InstructionSequence, InitialDataSequence, FinalState, 0).

% option with non-zero trace level

run(InstructionSequence, InitialDataSequence, FinalState, TraceLevel) :-
    StartLocation = 1,
    InstructionMemory =.. [instructions | InstructionSequence],
    DataMemory =.. [data | InitialDataSequence],
    InitialStack = [],
    InitialState = state(InitialStack, StartLocation, InstructionMemory, DataMemory),
    StartStep = 1,
    norm(InitialState, FinalState, StartStep, TraceLevel).
    

% norm is iterates the basic cycle of the NoRM
% If cycle execution fails (as it will for the halt instruction, for example)
% norm stops and returns the current state

norm(State, FinalState, Step, TraceLevel) :-
    (TraceLevel > 0 -> showState(Step, State) ; true),
    (
     cycle(State, NewState)
     -> (Step1 is Step + 1, norm(NewState, FinalState, Step1, TraceLevel))
      ; FinalState = State
    ).

% Note: DataMemory is updated destructively for efficiency purposes
% While this is not routinely advisable nor necessary, we do it anyway.


% cycle does one execution cycle:
% It fetches the instruction at Location from Instruction Memory
% then executes the instruction.  It also returns the next instruction's
% location.  The latter is normally the next location in instruction memory,
% but it may be altered by a jump instruction.

cycle(state(   Stack,    Location, InstructionMemory, DataMemory),
      state(NewStack, NewLocation, InstructionMemory, DataMemory)) :-
    fetch(Location, InstructionMemory, Instruction),
    next(Location, NextLocation),
    execute(Instruction, Stack, NewStack, NextLocation, NewLocation, DataMemory).

showState(Step, State) :-
    write('step '), write(Step), write(': '), nl,
    State = state(Stack, Location, InstructionMemory, DataMemory),
    write('stack '), write(Stack), nl,
    write('memory '), write(DataMemory), nl,
    write('memory '), write(InstructionMemory), nl,
    fetch(Location, InstructionMemory, Instruction),
    write('instruction '), write(Location), write(': '), write(Instruction), nl, nl.

% execute executes the various NoRM instructions.

% The push instruction pushes a constant (number) onto the stack.

execute(push(Constant), Stack, [Constant | Stack], Location, Location, _).


% The pop instruction removes the top of the stack and discards it.

execute(pop, [_ | Stack], Stack, Location, Location, _) .


% The rep instruction replicates the top element of the stack.

execute(rep, [V | Stack], [V, V | Stack], Location, Location, _) .


% The flip instruction flips the top two stack elements.

execute(flip, [V1, V2 | Stack], [V2, V1 | Stack], Location, Location, _) .


% The add instruction pops the top two stack elements and pushes the sum.

execute(add, [V1, V2 | Stack], [V3 | Stack], Location, Location, _) :-
    V3 is V1 + V2.


% The subtract instruction pops the top two stack elements and pushes the
% top minus the second.

execute(subtract, [V1, V2 | Stack], [V3 | Stack], Location, Location, _) :-
    V3 is V1 - V2.


% The multiply instruction pops the top two stack elements and pushes the product.

execute(multiply, [V1, V2 | Stack], [V3 | Stack], Location, Location, _) :-
    V3 is V1 * V2.


% The divide instruction pops the top two stack elements and pushes the
% quotient of the top divided by the second (integer division).

execute(divide, [V1, V2 | Stack], [V3 | Stack], Location, Location, _) :-
    V3 is V1 // V2.


% The mod instruction pops the top two stack elements and pushes the
% remainder of the top divided by the second (integer division).

execute(mod, [V1, V2 | Stack], [V3 | Stack], Location, Location, _) :-
    V3 is V1 mod V2.


% The equal instruction tests the top two elements for equality.
% The elements are left on the stack. A 1 is pushed if the values are equal,
% and a 0 is pushed otherwise.

execute(equal, [V1, V2 | Stack], [V3, V1, V2 | Stack], Location, Location, _) :-
    V1 == V2 -> V3 = 1 ; V3 = 0.


% The less instruction tests the top two elements for inequality
% The elements are left on the stack. A 1 is pushed if the top value is less
% than the second, and a 0 is pushed otherwise.

execute(less, [V1, V2 | Stack], [V3 | Stack], Location, Location, _) :-
    V1 < V2 -> V3 = 1 ; V3 = 0.


% The 'not' instruction replaces the top value on the stack by 1 if it is 0,
% and by 0 otherwise.

execute(not, [V1 | Stack], [V2 | Stack], Location, Location, _) :-
    V1 == 0 -> V2 = 1 ; V2 = 0.


% The jump instruction, with argument Offset, pops the top value on the stack.  
% If that value was 0 then the next instruction is taken from the instruction location 
% that is Offset away from the current instruction.  Otherwise the next instruction is 
% from the next location as normal.

execute(jump(Offset), [Value | Stack], Stack, Location, NewLocation, _) :-
    Value == 0
        -> NewLocation is Location + Offset - 1    % zero:     jump taken
         ; NewLocation is Location.                % non-zero: jump not taken


% The fetch instruction pushes the contents of the addressed data memory location
% onto the stack.

execute(fetch(Address), Stack, [Value | Stack], Location, Location, Memory) :-
    fetch(Address, Memory, Value).


% The store instruction stores into the addressed data memory location
% the top value on the stack (which stays there).

execute(store(Address), [Value | Stack], [Value | Stack], Location, Location, Memory) :-
    store(Address, Memory, Value).


% The halt instruction produces a failure, so that cycling stops.

execute(halt, Stack, Stack, Location, Location, _) :- !, fail.


% Any other instruction also causes failure, and an error message.

execute(Other, Stack, Stack, Location, Location, _) :- 
    write('*** Unidentified operation: '),
    write(Other),
    nl,
    fail.


% Get the contents of a memory location, where the entire memory is
% represented by a single Prolog term (treated as an array).

fetch(Location, MemoryTerm, Value) :-
    arg(Location, MemoryTerm, Value)
        -> true 
         ; write('*** Memory fetch of address '), 
           write(Location),
           write(' failed for memory '),
           write(MemoryTerm),
           nl,
           fail.

% Store a value in the specified memory location.
% Caution: Updating is destructive, using setarg.

store(Location, MemoryTerm, Value) :-
    setarg(Location, MemoryTerm, Value)
        -> true 
         ; write('*** Memory store of address '), 
           write(Location),
           write(' failed for memory '),
           write(MemoryTerm),
           nl,
           fail.


% Compute the location of the next instruction.

next(Location, NextLocation) :-
    NextLocation is Location + 1.