-- ALP-1
-- Raul Rojas
-- Turing Maschine Simulator

-- computes a single step of the TM

step (q,l,s,r) tabula 
                 | q==0      = (q,l,s,r)
                 | otherwise = (qn,new_l,new_s,new_r)
                   where
                     (qn,o,dir) = find_next (q,s) tabula
                     (new_l,new_s,new_r) 
                                   | dir=='l' = take_left( l,o,r) 
                                   | dir=='r' = take_right(l,o,r)
                                   | dir=='s' = (l,o,r)
                                   
-- finds the next state, output and direction in the table                      
find_next (q,s) ((a,b,qn,out,dir):rest) 
                    | (a==q && b==s)    = (qn,out,dir)
                    | (a==q && b=='#')  = (qn,s,dir)
                    | otherwise          = find_next (q,s) rest                                         
                                                                                                               
empty_tape = '_':empty_tape

-- advances the read/write head to the left
take_left (l,s,r) 
                   | head_l == '_' = error "left margin reached"
                   | otherwise     = (tail l,head_l,s:r)
                     where head_l = head l
-- advances the read/write head to the right                     
take_right(l,s,r) 
                   | head_r == '_' = error "right margin reached"
                   | otherwise     = (s:l,head_r,tail r)
                     where head_r = head r

-- simulates a TM with the table tabula and the history "run"

sim (0,l,s,r) tabula run = run
sim (q,l,s,r) tabula run = sim new tabula (new:run)
                           where new = step (q,l,s,r) tabula

-- start the simulation with the state (q,l,s,r) and table tabula
-- q is the state, l the tape to the left, s the symbol under the read/write head
-- and r the tape to the right

start (q,l,s,r) tabula 
   = putStr(show_states(sim (q1,l1,s1,r1) tabula [(q1,l1,s1,r1)]))
        where (q1,l1,s1,r1) = (q,reverse(l)++empty_tape,s,r++empty_tape)

-- show_states
show_states::[(Int,[Char],Char,[Char])]->[Char]

-- Example tables
-- The program checks balancing of parenthesis

klammer= [(1,'(',2,'X','r'),
          (1,'A',0,'0','s'),
          (1,'#',1,'#','l'),
          (2,')',1,'X','l'),
          (2,'A',3,'A','l'),
          (2,'#',2,'#','r'),
          (3,'(',0,'0','s'),
          (3,'A',0,'1','s'),
          (3,'#',3,'#','l')]

test = start(2,"A",'(',")A") klammer