The RAL Interpreter
			 -------------------

This Haskell program is an interpreter for RAL programs running on 
an abstract Random Access Machine, as described in Chapter 17 of
A.K. Dewdney's "The New Turing Omnibus".

Note: Although the SCRAM (a simple machine that executes RAL programs)
described in Chapter 48 allows code to be interpreted as data (and
vice versa), and therefore makes concrete committments about word size
and op-codes, the presentation in Chapter 17 assumes that the program
sits apart from the data.  We adopt the latter assumption here, which
simplifies the design considerably.  A fun future project would be to
emulate SCRAM more directly.

> module RALInterpreter where
> import List (deleteBy, sort)

Here is a test program demonstrating how to use the interpreter.

Test Program
------------

Detecting duplicates in an array (translated directly from Chapter 17)

> prog0 :: RALProg
> prog0 = [
>   (1, LDI 3), (2, ADD 4), (3, STA 5), (4, LDI 5), (5, JMZ 9), 
>   (6, LDA 3), (7, STA 2), (8, HLT),   (9, LDA 1), (10,STI 5), 
>   (11,LDA 3), (12,SUB 4), (13,JMZ 8), (14,LDA 3), (15,ADD 1), 
>   (16,STA 3), (17,JMP 1) ]

> mem0 :: Memory
> mem0 = [ (0,0), (1,1), (2,0), (3,6), (4,9),
>          (5,0), (6,3), (7,4), (8,2), (9,2),
>          (10,0),(11,0),(12,0),(13,0),(14,0) ]

> test0 = run prog0 (mem0,0,1)  -- AC is 0, PC is 1

Here is a transcript of the test run:

RALInterpreter> test0
Normal halt.
  Accumulator = 9
  Program Counter = 8
  Memory contains: [(0,0), (1,1), (2,9), (3,9), (4,9),
                    (5,11),(6,3), (7,4), (8,2), (9,2),
                    (10,0),(11,1),(12,1),(13,1),(14,0)]

Note that location 2 in the memory contains a 9, which is the location
of the first duplicate (2) in the array.

If all that you want to do is use the interpreter, you need not read
any further!  However, the implementation is really pretty simple
(just 50 lines of Haskell code), so feel free to take a look if you
like.


IMPLEMENTATION
==============

Datatypes
---------

A location is an Int, and a command is an operator paired with its
operand (a location).

> type Loc    = Int
> data RALCmd = LDA Loc  -- load  AC with contents of Loc
>             | LDI Loc  -- load  AC with contents of contents of Loc
>             | STA Loc  -- store AC into contents of Loc
>             | STI Loc  -- store AC into contents of contents of Loc
>             | ADD Loc  -- add      contents of Loc to   AC
>             | SUB Loc  -- subtract contents of Loc from AC
>             | JMP Loc  -- jump to instruction labelled Loc
>             | JMZ Loc  -- jump to instruction labelled Loc if AC=0
>             | HLT      -- halt
>      deriving Show

A label is an Int, and a RAL program is a sequence of labelled RAL
commands. 

> type Label   = Int
> type RALProg = [(Label,RALCmd)]

The data memory is represented as a list of location/content pairs
(each an Int).  The state of a RAM machine running a RAL program
consists of the memory, the accumulator, and the program counter.

> type Memory = [(Int,Int)]
> type State = (Memory,Int,Int)   -- memory, AC, and PC

Memory Operations
-----------------

> readMem :: Int -> Memory -> Int
> readMem loc mem = 
>   case lookup loc mem of
>     Nothing -> 0  -- assume unused memory locations have contents 0
>     Just x  -> x
>
> writeMem :: Int -> Int -> Memory -> Memory
> writeMem loc val mem = 
>   let new = (loc,val)
>   in  new : deleteBy (\x y-> fst x == fst y) new mem

The Interpreter
---------------

The interpreter (called "run") takes a RAL program, a RAM state, and
returns a RAM state.  The contents of the memory in the RAM state at
the end of execution is considered to be the final "answer".

> run :: RALProg -> State -> IO ()
> run prog s@(mem,ac,pc) =
>   case (lookup pc prog) of
>     Nothing -> error ("Abnormal halt: bad instruction location.\n" 
>                       ++ show s)
>     Just (LDA loc) -> let val = readMem loc mem
>                       in run prog (mem, val, pc+1)
>     Just (LDI loc) -> let val = readMem (readMem loc mem) mem
>                       in run prog (mem, val, pc+1)
>     Just (STA loc) -> let mem' = writeMem loc ac mem
>                       in run prog (mem', ac, pc+1)
>     Just (STI loc) -> let mem' = writeMem (readMem loc mem) ac mem
>                       in run prog (mem', ac, pc+1)
>     Just (ADD loc) -> let val = readMem loc mem
>                       in run prog (mem, ac+val, pc+1)
>     Just (SUB loc) -> let val = readMem loc mem
>                       in run prog (mem, ac-val, pc+1)
>     Just (JMP loc) -> run prog (mem, ac, loc)
>     Just (JMZ loc) -> let pc' = if ac==0 then loc else (pc+1)
>                       in run prog (mem, ac, pc')
>     Just  HLT      -> do putStrLn ("Normal halt.")
>                          putStrLn ("  Accumulator = " ++ show ac)
>                          putStrLn ("  Program Counter = " ++ show pc)
>                          putStrLn ("  Memory contents: " 
>                                    ++ show (sort mem))