type id = string

type table = (id * int) list

datatype binop = Plus | Minus | Times | Div

datatype stm = CompoundStm of stm * stm
             | AssignStm of id * exp
             | PrintStm of exp list
     and exp = IdExp of id
             | NumExp of int
             | OpExp of exp * binop * exp
             | EseqExp of stm * exp


val prog =
    CompoundStm ( AssignStm ( "a",
                              OpExp ( NumExp 5, Plus, NumExp 3 ) ),
                  CompoundStm ( AssignStm ( "b",
                                            EseqExp ( PrintStm [ IdExp "a",
                                                                 OpExp ( IdExp "a",
                                                                         Minus,
                                                                         NumExp 1 ) ],
                                                      OpExp ( NumExp 10,
                                                              Times,
                                                              IdExp "a" ))),
                                PrintStm [ IdExp "b" ]))

fun maxoflist [] = 0
  | maxoflist (x::xs) = Int.max (x, maxoflist xs)

fun maxargs s =
  let fun maxargs_exp e =
        case e of
            IdExp _           => 0
          | NumExp _          => 0
          | OpExp (e1, _, e2) => Int.max (maxargs_exp e1, maxargs_exp e2)
          | EseqExp (s, e1)   => Int.max (maxargs s,      maxargs_exp e1)
  in 
      case s of
          PrintStm l           => Int.max (List.length l, maxoflist (map maxargs_exp l))
        | AssignStm (_, e)     => maxargs_exp e
        | CompoundStm (s1, s2) => Int.max (maxargs s1, maxargs s2)
  end

fun fst (a,_) = a

fun snd (_,b) = b

fun lookup (k:id) ([]:table) = 0
  | lookup k ((i,v)::ts)     = if k = i
                               then v
                               else lookup k ts

fun update (t:table) (i:id,v) = (i,v)::t


fun interpStm (t:table) (CompoundStm (s1, s2)) = interpStm (interpStm t s1) s2
  | interpStm t         (PrintStm l)           = (print (String.concatWith " " (map (expAsStr t) l));
                                                  print "\n";
                                                  t)
  | interpStm t         (AssignStm (i, e))     =
    let 
        val (t1,v1) = interpExp t e
    in
        update t1 (i, v1)
    end
and interpExp (t:table) (NumExp x)             = (t, x)
  | interpExp t         (IdExp k)              = (t, lookup k t)
  | interpExp t         (EseqExp (s,e))        = (interpExp (interpStm t s) e)
  | interpExp t         (OpExp (a1,oper,a2))   =
    let
        val (t1,v1) = interpExp t a1
        val (t2,v2) = interpExp t1 a2
    in case oper of
           Plus  => (t2, (v1 + v2))
         | Minus => (t2, (v1 - v2))
         | Times => (t2, (v1 * v2))
         | Div   => (t2, Int.div (v1, v2))
    end
and expAsStr t (NumExp x)      = Int.toString x
  | expAsStr t (IdExp a)       = Int.toString (lookup a t)
  | expAsStr t (OpExp x)       =
    let 
        val (t1,v1) = interpExp t (OpExp x)
    in
        Int.toString v1
    end
  | expAsStr t (EseqExp (s,e)) = expAsStr (interpStm t s) e


fun interp s = interpStm [] s