Extensible interpreter using OCaml 5.0's effect handlers, based on https://gist.github.com/takahisa/e5d3b012a11081302489d29bf417575c

extensible_interpreter_with_ocaml_effect_handlers.ml

module D = Effect.Deep

type 'a expr = ..
type _ Effect.t += Extension : 'a expr -> 'a Effect.t

(* Base Interpreter *)
type 'a expr +=
| Int : int -> int expr
| Add : int expr * int expr -> int expr
| Sub : int expr * int expr -> int expr

let rec eval1 : type a. a expr -> a = function
| Int n1 -> n1
| Add(e1,e2) ->
  let n1 = eval1 e1 in
  let n2 = eval1 e2 in
  n1 + n2
| Sub(e1,e2) ->
  let n1 = eval1 e1 in
  let n2 = eval1 e2 in
  n1 - n2
| e -> Effect.perform (Extension e)

(* Extension 1 *)
type 'a expr +=
| Mul : int expr * int expr -> int expr
| Div : int expr * int expr -> int expr

let rec eval2 : 'a. 'a expr -> 'a = fun e ->
  let handler =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Extension (Mul(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = eval2 e1 in
          let n2 = eval2 e2 in
          D.continue k (n1 * n2))
      | Extension (Div(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = eval2 e1 in
          let n2 = eval2 e2 in
          D.continue k (n1 / n2))
      | _ -> None
  } in
  D.try_with eval1 e handler
  
(* Extension 2 *)
type 'a expr +=
| Bool : bool -> bool expr
| Eq : int expr * int expr -> bool expr
| Gt : int expr * int expr -> bool expr

let rec eval3 : 'a. 'a expr -> 'a = fun e ->
  let handler =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Extension (Bool b1) -> Some (fun (k: (b,_) D.continuation) ->
          D.continue k b1)
      | Extension (Eq(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = eval3 e1 in
          let n2 = eval3 e2 in
          D.continue k (n1 = n2))
      | Extension (Gt(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = eval3 e1 in
          let n2 = eval3 e2 in
          D.continue k (n1 > n2))
      | _ -> None
  } in
  D.try_with eval2 e handler

(* Running the interpreter *)
let _ =
  let e = Gt(Mul(Int 2, Int 3), Add(Int 2, Int 3)) in
  let handler =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Extension _ -> failwith "Unknown syntax"
      | _ -> None
  } in
  let b = D.try_with eval3 e handler in
  print_endline @@ string_of_bool b