type expr = 
  | Const of int
  | Add of expr * expr
  | Mul of expr * expr

type instr = Push | Addint | Mulint | Value of int

exception Bad_code

(* 5(a) *)
let rec compile = function
  | Const n -> [Push; Value n]
  | Add (e1, e2) -> compile e1 @ compile e2 @ [Addint]
  | Mul (e1, e2) -> compile e1 @ compile e2 @ [Mulint]

let expr = Mul (Const 10, Add (Const 20, Const 30))

let code = compile expr

(* 5(b) *)
let val_int = function
  | Value n -> n
  | _ -> raise Bad_code

let rec interpret1 code (pc, stack) =
  match List.nth code pc, stack with
  | Push, s -> (pc + 2, val_int (List.nth code (pc + 1)) :: s)
  | Addint, x :: y :: s -> (pc + 1, (x + y) :: s)
  | Mulint, x :: y :: s -> (pc + 1, (x * y) :: s)
  | _, _ -> raise Bad_code

let rec interpret' code (pc, stack) =
  if pc = List.length code then
    List.hd stack
  else
    interpret' code (interpret1 code (pc,stack))

let interpret code = interpret' code (0, []);;

assert (500 = interpret code);;