structure Tiny = 
struct
datatype Program = op := of  string * IntExp
                 | Seq   of Program * Program
                 | If    of BoolExp * Program
                 | While of BoolExp * Program

and IntExp  = Const of int
            | Value of string
            | ++ of IntExp * IntExp

and BoolExp = Bool of bool
            | << of IntExp * IntExp
            | == of IntExp * IntExp
;

infix ++ << == ;
	 
type Memory = (string * int) list ;
    
fun lookup  s [] = 
    error ("Memory " ^ s ^ " used but not declared.\n")
|   lookup  s (( s', v ) ::t) = 
                   if s = s' then v 
		   else lookup  s t ;
		       
fun add initial m = initial :: m (* needs error *);

fun update (new as ( s, v )) ((old as ( s',_)) ::t) = 
                   if s = s' then (new ::t) 
		   else  add old (update new t) 
|   update _ [] = error "Nothing to update" ;


fun evalIntExp (Const n)   m = n
|   evalIntExp (Value l) m = lookup l m
|   evalIntExp (a ++ b)  m = evalIntExp a m + evalIntExp b m

and evalBoolExp (Bool b) m = b
|   evalBoolExp (a << b) m = evalIntExp a m < evalIntExp b m 
|   evalBoolExp (a == b) m = evalIntExp a m = evalIntExp b m 

and eval (l := a)          m = update (l,evalIntExp a m) m
|   eval (Seq (e,f))       m = eval f (eval e m)
|   eval (If  (b,e))       m = if evalBoolExp b m then eval e m else m
|   eval (s as While (b,e))m = if evalBoolExp b m then eval s (eval e m) 
                                                  else m ;
      
      
fun print indent ( v := e ) = 
          indent ^ v ^ " := " ^ printIntExp e

|   print indent (Seq ( e,f)) = 
          print indent e ^ "; \n" ^ print indent f

|   print indent (If (b,e)) = 
          indent ^ "if " ^ printBoolExp b ^ " then\n" ^
                           print ("  " ^ indent) e

|   print indent (While(b,e)) = 
          indent ^ "while " ^ printBoolExp b ^ " do\n" ^   
                              print ("  " ^ indent) e 
      

and printIntExp (Const n) = printInt n

|   printIntExp (Value l) = l

|   printIntExp (a ++ b)  = printIntExp a ^ " + " ^ printIntExp b

and printBoolExp (Bool b) = if b then " true " else " false "

|   printBoolExp (n << m) = printIntExp n ^ " < " ^ printIntExp m
|   printBoolExp (n == m) = printIntExp n ^ " = " ^ printIntExp m

and printInt n = if n < 0 then "~" ^ printInt (~ n)
                 else (case n div 10 of 0 => "" | x => printInt x)
                    ^ printDigit (n mod 10)

and printDigit x = chr (x + ord "0") ;

end ;