structure Syntax =
struct
  (* SML syntax *)
  datatype etype =
    Tyvar of string
  | Tycon of etype list * string
  | TyTuple of etype list
  | Tyfun of etype * etype

  datatype pat =
    PWild
  | PVar of string
  | PInt of int
  | PTuple of pat list
  | PCon of string list * pat
  | PList of pat list

  datatype identType =
    ITVar
  | ITStruct
  | ITFunctor
  | ITSignature

  fun identTypeOrder ITVar = 0
    | identTypeOrder ITStruct = 1
    | identTypeOrder ITFunctor = 2
    | identTypeOrder ITSignature = 3

  fun compareIdentifiers ((t1, n1) : identType * string, (t2, n2) : identType * string) : order =
    case Int.compare (identTypeOrder t1, identTypeOrder t2) of
      EQUAL => String.compare (n1, n2)
    | ord => ord

  datatype expr =
    EIdent of identType * string
  | EDot of expr * (identType * string)
  | EBuiltin of string
  | EInt of int
  | EStr of string
  | ETuple of expr list
  | EList of expr list
  | EApp of expr * expr
  | ETyped of expr * etype
  | EAndAlso of expr * expr
  | EOrElse of expr * expr
  | ELet of dec list * expr
  | ELambda of pat * expr
  | ECase of expr * (pat * expr) list
  | EStruct of dec list
  | EFunctorApp of expr * expr

  and dec =
    DVal of pat * expr
  | DValRec of pat * expr
  | DFun of string * (pat list * expr) list
  | DDatatype of string list * string * (string * etype option) list
  | DType of string * etype
  | DStruct of string * string option * expr
  | DSig of string * (string * etype) list
  (* Functor? I hardly know 'er! *)
  | DFunctor of string * string * string * expr

  datatype ty =
    TInt
  | TBool
  | TString
  | TVar of int
  | TTuple of ty list
  | TFun of ty * ty
  | TList of ty
  | TDatatype of string list
  | TStruct of ((identType * string) * ty) list
  | TFunctor of ty * ty

  datatype typedPat =
    TPWild
  | TPVar of string
  | TPInt of int
  | TPTuple of (typedPat * ty) list
  | TPCon of string list * (typedPat * ty)
  | TPList of (typedPat * ty) list

  datatype typedExpr =
    TEIdent of identType * string
  | TEDot of (typedExpr * ty) * (identType * string)
  | TEBuiltin of string
  | TEInt of int
  | TEStr of string
  | TETuple of (typedExpr * ty) list
  | TEList of (typedExpr * ty) list
  | TEApp of (typedExpr * ty) * (typedExpr * ty)
  | TEAndAlso of (typedExpr * ty) * (typedExpr * ty)
  | TEOrElse of (typedExpr * ty) * (typedExpr * ty)
  | TELet of typedDec list * (typedExpr * ty)
  | TELambda of (typedPat * ty) * (typedExpr * ty)
  | TECase of (typedExpr * ty) * ((typedPat * ty) * (typedExpr * ty)) list
  | TEStruct of typedDec list
  | TEFunctorApp of (typedExpr * ty) * (typedExpr * ty)

  and typedDec =
    TDVal of (typedPat * ty) * (typedExpr * ty)
  | TDValRec of (typedPat * ty) * (typedExpr * ty)
  | TDFun of string * ((typedPat * ty) list * (typedExpr * ty)) list
  | TDDatatype of string * (string * ty option) list
  | TDStruct of string * (typedExpr * ty)
  | TDFunctor of string * string * ty * (typedExpr * ty)

  (* Lambda language *)
  type var = int

  datatype primop =
    PExit
  | PAdd
  | PSub
  | PMul
  | PDiv
  | PLess
  | PEq
  | PIf
  | PRead
  | PWrite
  | PWriteErr

  datatype lexp =
    LVar of var
  | LFn of var * lexp
  | LFix of (var * var * lexp) list * lexp
  | LApp of lexp * lexp
  | LInt of int
  | LString of string
  | LRecord of lexp list
  | LSelect of int * lexp
  | LPrim of primop
  | LSwitch of lexp * (int * lexp) list * lexp option

  (* CPS *)
  datatype value =
    VVar of var
  | VLabel of var
  | VInt of int

  datatype cexp =
    CRecord of ((value * int list) list * var) list * cexp
  | CSelect of int * value * var * cexp
  | CApp of value * value list
  | CFix of (var * var list * cexp) list * cexp
  | CPrimop of primop * value list * var list * cexp list

  datatype opcode =
    OAlloc of var * value
  | OCall
  | OPoke of int * var * value
  | OPeek of var * int * value
  | OShuf of var * value
  | OExit of value
  | OAdd of var * value * value
  | OSub of var * value * value
  | OMul of var * value * value
  | ODiv of var * value * value
  | OLess of var * value * value
  | OEq of var * value * value
  | OIf of value * var
  | OLabel of var
  | ORead of var * var * value * value
  | OWrite of var * value * value
  | OWriteErr of var * value * value
end