let rec subst e x t =
    match e with
    | ID s          -> if s = x then t else ID s
    | BOOL b        -> BOOL b
    | ERROR s       -> ERROR s
    | ISZERO        -> ISZERO
    | NUM n         -> NUM n
    | PRED          -> PRED
    | SUCC          -> SUCC
    | APP (e1, e2)  -> APP (subst e1 x t, subst e2 x t)
    | IF (b, e1, e2)-> IF (subst b x t, subst e1 x t, subst e2 x t)
    | FUN (s, t2)   -> if s = x then FUN (s, t2) else FUN (s, subst t2 x t)
    | REC (s, t2)   -> if s = x then REC (s, subst t2 x t) else REC (s, t2) //ERROR "AT REC SUB"

//if s != x then do fun (s, subst t2 x t) else return fun (s, t2) .. same for rec

let rec interp = function
    | NUM n             -> NUM n                // Rule (1)
    | BOOL true         -> BOOL true            // Rule (2)
    | BOOL false        -> BOOL false           // Rule (2)
    | SUCC              -> SUCC                 // Rule (3)
    | PRED              -> PRED                 // Rule (3)
    | ISZERO            -> ISZERO               // Rule (3)
    | ERROR s           -> ERROR s
    | ID s              -> ERROR (sprintf "unbound identifier ID \"%A\" (stuck)" s)
    | FUN (s, t)        -> FUN (s, t)           // Rule (9)
    | REC (s, t)        -> interp (subst t s t) // Rule (11)
    | IF (b, e1, e2)    ->
        match interp b with
        | BOOL true     -> interp e1            // Rule (4)
        | BOOL false    -> interp e2            // Rule (5)
        | _             -> ERROR (sprintf "'if' statement must evaluate to a BOOL val of true or
                                            false (stuck), current value is '%A'" (interp b))
    | APP (e1, e2)      ->
        match (interp e1, interp e2) with
        | (ERROR s, _)      -> ERROR s
        | (_, ERROR s)      -> ERROR s
        | (SUCC, NUM n)     -> NUM (n+1)        // Rule (6)
        | (SUCC, v)         -> ERROR (sprintf "'succ' needs int argument, not '%A'" v)
        | (PRED, NUM n)     -> if n = 0 then NUM 0 else NUM (n-1)       // Rule (7)
        | (PRED, v)         -> ERROR (sprintf "'pred' needs int argument, not '%A'" v)
        | (ISZERO, NUM n)   -> if n = 0 then BOOL true else BOOL false  // Rule (8)
        | (ISZERO, v)       -> ERROR (sprintf "'iszero' needs int argument, not '%A'" v)
        | (FUN (s, t), v)   -> interp (subst t s v) // Rule (10)
        | (_, _)            -> ERROR "invalid 'app' operation"

interp (parsestr "(rec d -> fun n -> if iszero n thn 0 else succ (succ (d (pred n)))) #37")

produces -->

val it : term =
  FUN
    ("n",
     IF
       (APP (ISZERO,ID "n"),NUM 0,
        APP
          (SUCC,
           APP
             (SUCC,
              APP
                (FUN
                   ("n",
                    IF
                      (APP (ISZERO,ID "n"),NUM 0,
                       APP (SUCC,APP (SUCC,APP (ID "d",APP (PRED,ID "n")))))),
                 APP (PRED,ID "n"))))))