sig
  type id = string
  module IdMap :
    sig
      type key = id
      type +'a t
      val empty : 'a t
      val is_empty : 'a t -> bool
      val mem : key -> 'a t -> bool
      val add : key -> 'a -> 'a t -> 'a t
      val singleton : key -> 'a -> 'a t
      val remove : key -> 'a t -> 'a t
      val merge :
        (key -> 'a option -> 'b option -> 'c option) -> 'a t -> 'b t -> 'c t
      val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
      val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
      val iter : (key -> 'a -> unit) -> 'a t -> unit
      val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
      val for_all : (key -> 'a -> bool) -> 'a t -> bool
      val exists : (key -> 'a -> bool) -> 'a t -> bool
      val filter : (key -> 'a -> bool) -> 'a t -> 'a t
      val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
      val cardinal : 'a t -> int
      val bindings : 'a t -> (key * 'a) list
      val min_binding : 'a t -> key * 'a
      val max_binding : 'a t -> key * 'a
      val choose : 'a t -> key * 'a
      val split : key -> 'a t -> 'a t * 'a option * 'a t
      val find : key -> 'a t -> 'a
      val map : ('a -> 'b) -> 'a t -> 'b t
      val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
    end
  type constant = Bool of bool | Int of int | Nil | Unit
  type pattern =
      PConstant of Ast.constant
    | PVar of Ast.id
    | PCons of Ast.pattern * Ast.pattern
  type unary_op = Not
  type binary_op =
      Plus
    | Minus
    | Mult
    | Divide
    | Mod
    | And
    | Or
    | Eq
    | Neq
    | Lt
    | Ltq
    | Gt
    | Gtq
  type expr =
      Constant of Ast.constant
    | BinaryOp of Ast.binary_op * Ast.expr * Ast.expr
    | UnaryOp of Ast.unary_op * Ast.expr
    | Var of Ast.id
    | Fun of Ast.id * Ast.expr
    | Cons of Ast.expr * Ast.expr
    | IfThenElse of Ast.expr * Ast.expr * Ast.expr
    | Let of Ast.id * Ast.expr * Ast.expr
    | LetRec of Ast.id * Ast.expr * Ast.expr
    | App of Ast.expr * Ast.expr
    | Match of Ast.expr * (Ast.pattern * Ast.expr) list
  type definition = Ast.id * Ast.expr
  type directive = Env | Reset | Quit | Help | Use of string
  type toplevel_input =
      Definition of Ast.definition
    | Expression of Ast.expr
    | Directive of Ast.directive
  type value =
      VUndef
    | VNil
    | VUnit
    | VBool of bool
    | VInt of int
    | VCons of Ast.value * Ast.value
    | VClosure of Ast.value Pervasives.ref Ast.IdMap.t * Ast.id * Ast.expr
  type typ =
      TBool
    | TInt
    | TUnit
    | TList of Ast.typ
    | TVar of Ast.id
    | Arrow of Ast.typ * Ast.typ
  type environment = Ast.value Pervasives.ref Ast.IdMap.t
  type constr = Ast.typ * Ast.typ
  type substitution = (Ast.id * Ast.typ) list
  type apattern =
      APConstant of Ast.constant * Ast.typ
    | APVar of Ast.id * Ast.typ
    | APCons of Ast.apattern * Ast.apattern * Ast.typ
  type aexpr =
      ABool of bool * Ast.typ
    | AInt of int * Ast.typ
    | ANil of Ast.typ
    | AUnit of Ast.typ
    | ACons of Ast.aexpr * Ast.aexpr * Ast.typ
    | AIfThenElse of Ast.aexpr * Ast.aexpr * Ast.aexpr * Ast.typ
    | ALetRec of Ast.id * Ast.typ * Ast.aexpr * Ast.aexpr * Ast.typ
    | ALet of Ast.id * Ast.typ * Ast.aexpr * Ast.aexpr * Ast.typ
    | ABinaryOp of Ast.binary_op * Ast.aexpr * Ast.aexpr * Ast.typ
    | AUnaryOp of Ast.unary_op * Ast.aexpr * Ast.typ
    | AFun of Ast.id * Ast.aexpr * Ast.typ
    | AApp of Ast.aexpr * Ast.aexpr * Ast.typ
    | AVar of Ast.id * Ast.typ
    | AMatch of Ast.aexpr * (Ast.apattern * Ast.aexpr) list * Ast.typ
end