Module Core_lambdae.Ast

Syntax and runtime values of the explicit-environment core calculus.

type typ =
  1. | TInt
  2. | TBool
  3. | TString
  4. | TTop
  5. | TArr of typ * typ
  6. | TAnd of typ * typ
  7. | TOr of typ * typ
  8. | TRcd of string * typ
  9. | TVar of int
  10. | TMu of typ

Recursive type variables use de Bruijn indices: TVar 0 denotes the nearest enclosing TMu. Whole types should be closed; Fold stores only a mu body.

type lit =
  1. | Int of int
  2. | Bool of bool
  3. | String of string
type binop =
  1. | Add
  2. | Sub
  3. | Mul
  4. | Div
  5. | Mod
  6. | Lt
  7. | Le
  8. | Gt
  9. | Ge
  10. | Eq
  11. | Ne
  12. | Cat

Equality accepts matching primitive types; arithmetic and ordering use integers, and Cat concatenates strings.

type exp =
  1. | Query
  2. | Proj of exp * int
  3. | Lit of lit
  4. | Unit
  5. | Lam of typ * exp
    (*

    The body runs with the argument appended to the captured environment.

    *)
  6. | Box of exp * exp
    (*

    Evaluate the second expression under the first expression's value.

    *)
  7. | Clos of exp * typ * exp
    (*

    Captured environment, argument type, body; the environment is a value.

    *)
  8. | App of exp * exp
  9. | Mrg of exp * exp
    (*

    The right operand sees the left operand's value appended to its ambient environment.

    *)
  10. | Lrec of string * exp
  11. | Rproj of exp * string
  12. | Binop of binop * exp * exp
  13. | If of exp * exp * exp
  14. | Inl of typ * exp
    (*

    Inl (b, e) supplies the other summand b.

    *)
  15. | Inr of typ * exp
    (*

    Inr (a, e) supplies the other summand a.

    *)
  16. | Case of exp * exp * exp
    (*

    Each branch receives the injection payload at index zero.

    *)
  17. | Flam of typ * typ * exp
    (*

    Argument type, result type, body. The body sees its argument at index zero and the recursive function at index one.

    *)
  18. | Fclos of exp * typ * typ * exp
    (*

    Recursive closure with a captured value environment.

    *)
  19. | Fold of typ * exp
    (*

    Fold (body, e) has type TMu body; the annotation is the mu body.

    *)
  20. | Unfold of exp
  21. | Hostfn of string * typ * typ
    (*

    Host capability name, argument type, result type. Application uses Eval.host_dispatch; the annotation does not validate the host code.

    *)

Environments are values, conventionally a left-associated Mrg chain rooted at Unit. Query denotes the whole environment. Positional index zero selects the right component of a merge; further indices follow its left spine, never selecting the terminal base itself.

val is_value : exp -> bool

The runtime value predicate, including recursively valued environments and payloads. It does not check types or closure bodies.