package catala

  1. Overview
  2. Docs
package catala
Legend:
Library
Module
Module type
Parameter
Class
Class type

Abstract syntax tree of the default calculus intermediate representation

module Runtime = Runtime_ocaml.Runtime
module StructMap : Stdlib.Map.S with type key = StructName.t
module EnumMap : Stdlib.Map.S with type key = EnumName.t

Abstract syntax tree for the default calculus

Abstract syntax tree

type typ_lit =
  1. | TBool
  2. | TUnit
  3. | TInt
  4. | TRat
  5. | TMoney
  6. | TDate
  7. | TDuration
type marked_typ = typ Utils.Marked.pos
and typ =
  1. | TLit of typ_lit
  2. | TTuple of marked_typ list * StructName.t option
  3. | TEnum of marked_typ list * EnumName.t
  4. | TArrow of marked_typ * marked_typ
  5. | TArray of marked_typ
  6. | TAny
type date = Runtime.date
type duration = Runtime.duration
type lit =
  1. | LBool of bool
  2. | LEmptyError
  3. | LInt of Runtime.integer
  4. | LRat of Runtime.decimal
  5. | LMoney of Runtime.money
  6. | LUnit
  7. | LDate of date
  8. | LDuration of duration
type op_kind =
  1. | KInt
  2. | KRat
  3. | KMoney
  4. | KDate
  5. | KDuration
    (*

    All ops don't have a KDate and KDuration.

    *)
type ternop =
  1. | Fold
type binop =
  1. | And
  2. | Or
  3. | Xor
  4. | Add of op_kind
  5. | Sub of op_kind
  6. | Mult of op_kind
  7. | Div of op_kind
  8. | Lt of op_kind
  9. | Lte of op_kind
  10. | Gt of op_kind
  11. | Gte of op_kind
  12. | Eq
  13. | Neq
  14. | Map
  15. | Concat
  16. | Filter
type log_entry =
  1. | VarDef of typ
    (*

    During code generation, we need to know the type of the variable being logged for embedding

    *)
  2. | BeginCall
  3. | EndCall
  4. | PosRecordIfTrueBool
type unop =
  1. | Not
  2. | Minus of op_kind
  3. | Log of log_entry * Utils.Uid.MarkedString.info list
  4. | Length
  5. | IntToRat
  6. | MoneyToRat
  7. | RatToMoney
  8. | GetDay
  9. | GetMonth
  10. | GetYear
  11. | FirstDayOfMonth
  12. | LastDayOfMonth
  13. | RoundMoney
  14. | RoundDecimal
type operator =
  1. | Ternop of ternop
  2. | Binop of binop
  3. | Unop of unop
module Infer : sig ... end

Contains some structures used for type inference

type untyped = {
  1. pos : Utils.Pos.t;
}
type typed = {
  1. pos : Utils.Pos.t;
  2. ty : marked_typ;
}
type inferring = {
  1. pos : Utils.Pos.t;
  2. uf : Infer.unionfind_typ;
}
type _ mark =
  1. | Untyped : untyped -> untyped mark
  2. | Typed : typed -> typed mark
  3. | Inferring : inferring -> inferring mark

The generic type of AST markings. Using a GADT allows functions to be polymorphic in the marking, but still do transformations on types when appropriate

type ('a, 'm) marked = ('a, 'm mark) Utils.Marked.t
type 'm marked_expr = ('m expr, 'm) marked
and 'm expr =
  1. | EVar of 'm expr Bindlib.var
  2. | ETuple of 'm marked_expr list * StructName.t option
    (*

    The MarkedString.info is the former struct field name

    *)
  3. | ETupleAccess of 'm marked_expr * int * StructName.t option * marked_typ list
    (*

    The MarkedString.info is the former struct field name

    *)
  4. | EInj of 'm marked_expr * int * EnumName.t * marked_typ list
    (*

    The MarkedString.info is the former enum case name

    *)
  5. | EMatch of 'm marked_expr * 'm marked_expr list * EnumName.t
    (*

    The MarkedString.info is the former enum case name

    *)
  6. | EArray of 'm marked_expr list
  7. | ELit of lit
  8. | EAbs of ('m expr, 'm marked_expr) Bindlib.mbinder * marked_typ list
  9. | EApp of 'm marked_expr * 'm marked_expr list
  10. | EAssert of 'm marked_expr
  11. | EOp of operator
  12. | EDefault of 'm marked_expr list * 'm marked_expr * 'm marked_expr
  13. | EIfThenElse of 'm marked_expr * 'm marked_expr * 'm marked_expr
  14. | ErrorOnEmpty of 'm marked_expr

The expressions use the Bindlib library, based on higher-order abstract syntax

Expression annotations (Marked.t)

type typed_expr = typed marked_expr
type struct_ctx = (StructFieldName.t * marked_typ) list StructMap.t
type enum_ctx = (EnumConstructor.t * marked_typ) list EnumMap.t
type decl_ctx = {
  1. ctx_enums : enum_ctx;
  2. ctx_structs : struct_ctx;
}
type 'm binder = ('m expr, 'm marked_expr) Bindlib.binder
type scope_let_kind =
  1. | DestructuringInputStruct
    (*

    let x = input.field

    *)
  2. | ScopeVarDefinition
    (*

    let x = error_on_empty e

    *)
  3. | SubScopeVarDefinition
    (*

    let s.x = fun _ -> e or let s.x = error_on_empty e for input-only subscope variables.

    *)
  4. | CallingSubScope
    (*

    let result = s ({ x = s.x; y = s.x; ...})

    *)
  5. | DestructuringSubScopeResults
    (*

    let s.x = result.x *

    *)
  6. | Assertion
    (*

    let _ = assert e

    *)

This kind annotation signals that the let-binding respects a structural invariant. These invariants concern the shape of the expression in the let-binding, and are documented below.

type ('expr, 'm) scope_let = {
  1. scope_let_kind : scope_let_kind;
  2. scope_let_typ : marked_typ;
  3. scope_let_expr : ('expr, 'm) marked;
  4. scope_let_next : ('expr, ('expr, 'm) scope_body_expr) Bindlib.binder;
  5. scope_let_pos : Utils.Pos.t;
}

This type is parametrized by the expression type so it can be reused in later intermediate representations.

and ('expr, 'm) scope_body_expr =
  1. | Result of ('expr, 'm) marked
  2. | ScopeLet of ('expr, 'm) scope_let

A scope let-binding has all the information necessary to make a proper let-binding expression, plus an annotation for the kind of the let-binding that comes from the compilation of a Scopelang.Ast statement.

type ('expr, 'm) scope_body = {
  1. scope_body_input_struct : StructName.t;
  2. scope_body_output_struct : StructName.t;
  3. scope_body_expr : ('expr, ('expr, 'm) scope_body_expr) Bindlib.binder;
}

Instead of being a single expression, we give a little more ad-hoc structure to the scope body by decomposing it in an ordered list of let-bindings, and a result expression that uses the let-binded variables. The first binder is the argument of type scope_body_input_struct.

type ('expr, 'm) scope_def = {
  1. scope_name : ScopeName.t;
  2. scope_body : ('expr, 'm) scope_body;
  3. scope_next : ('expr, ('expr, 'm) scopes) Bindlib.binder;
}
and ('expr, 'm) scopes =
  1. | Nil
  2. | ScopeDef of ('expr, 'm) scope_def

Finally, we do the same transformation for the whole program for the kinded lets. This permit us to use bindlib variables for scopes names.

type ('expr, 'm) program_generic = {
  1. decl_ctx : decl_ctx;
  2. scopes : ('expr, 'm) scopes;
}
type 'm program = ('m expr, 'm) program_generic

Helpers

Manipulation of marks

val no_mark : 'm mark -> 'm mark
val mark_pos : 'm mark -> Utils.Pos.t
val pos : ('a, 'm) marked -> Utils.Pos.t
val ty : ('a, typed) marked -> marked_typ
val with_ty : marked_typ -> ('a, 'm) marked -> ('a, typed) marked

All the following functions will resolve the types if called on an Inferring type

val map_mark : (Utils.Pos.t -> Utils.Pos.t) -> (marked_typ -> marked_typ) -> 'm mark -> 'm mark
val map_mark2 : (Utils.Pos.t -> Utils.Pos.t -> Utils.Pos.t) -> (typed -> typed -> marked_typ) -> 'm mark -> 'm mark -> 'm mark
val fold_marks : (Utils.Pos.t list -> Utils.Pos.t) -> (typed list -> marked_typ) -> 'm mark list -> 'm mark
val get_scope_body_mark : ('expr, 'm) scope_body -> 'm mark
val untype_expr : 'm marked_expr -> untyped marked_expr Bindlib.box
val untype_program : 'm program -> untyped program

Boxed constructors

val evar : 'm expr Bindlib.var -> 'm mark -> 'm marked_expr Bindlib.box
val etuple : 'm marked_expr Bindlib.box list -> StructName.t option -> 'm mark -> 'm marked_expr Bindlib.box
val etupleaccess : 'm marked_expr Bindlib.box -> int -> StructName.t option -> marked_typ list -> 'm mark -> 'm marked_expr Bindlib.box
val einj : 'm marked_expr Bindlib.box -> int -> EnumName.t -> marked_typ list -> 'm mark -> 'm marked_expr Bindlib.box
val ematch : 'm marked_expr Bindlib.box -> 'm marked_expr Bindlib.box list -> EnumName.t -> 'm mark -> 'm marked_expr Bindlib.box
val earray : 'm marked_expr Bindlib.box list -> 'm mark -> 'm marked_expr Bindlib.box
val elit : lit -> 'm mark -> 'm marked_expr Bindlib.box
val eabs : ('m expr, 'm marked_expr) Bindlib.mbinder Bindlib.box -> marked_typ list -> 'm mark -> 'm marked_expr Bindlib.box
val eapp : 'm marked_expr Bindlib.box -> 'm marked_expr Bindlib.box list -> 'm mark -> 'm marked_expr Bindlib.box
val eassert : 'm marked_expr Bindlib.box -> 'm mark -> 'm marked_expr Bindlib.box
val eop : operator -> 'm mark -> 'm marked_expr Bindlib.box
val edefault : 'm marked_expr Bindlib.box list -> 'm marked_expr Bindlib.box -> 'm marked_expr Bindlib.box -> 'm mark -> 'm marked_expr Bindlib.box
val eifthenelse : 'm marked_expr Bindlib.box -> 'm marked_expr Bindlib.box -> 'm marked_expr Bindlib.box -> 'm mark -> 'm marked_expr Bindlib.box
val eerroronempty : 'm marked_expr Bindlib.box -> 'm mark -> 'm marked_expr Bindlib.box
type ('expr, 'm) box_expr_sig = ('expr, 'm) marked -> ('expr, 'm) marked Bindlib.box
val box_expr : ('m expr, 'm) box_expr_sig

Program traversal

Be careful when using these traversal functions, as the bound variables they open will be different at each traversal.

val map_expr : 'a -> f:('a -> 'm1 marked_expr -> 'm2 marked_expr Bindlib.box) -> ('m1 expr, 'm2 mark) Utils.Marked.t -> 'm2 marked_expr Bindlib.box

If you want to apply a map transform to an expression, you can save up writing a painful match over all the cases of the AST. For instance, if you want to remove all errors on empty, you can write

let remove_error_empty =
  let rec f () e =
    match Marked.unmark e with
    | ErrorOnEmpty e1 -> map_expr () f e1
    | _ -> map_expr () f e
  in
  f () e

The first argument of map_expr is an optional context that you can carry around during your map traversal.

val map_expr_top_down : f:('m1 marked_expr -> ('m1 expr, 'm2 mark) Utils.Marked.t) -> 'm1 marked_expr -> 'm2 marked_expr Bindlib.box

Recursively applies f to the nodes of the expression tree. The type returned by f is hybrid since the mark at top-level has been rewritten, but not yet the marks in the subtrees.

val map_expr_marks : f:('m1 mark -> 'm2 mark) -> 'm1 marked_expr -> 'm2 marked_expr Bindlib.box
val fold_left_scope_lets : f:('a -> ('expr, 'm) scope_let -> 'expr Bindlib.var -> 'a) -> init:'a -> ('expr, 'm) scope_body_expr -> 'a

Usage: fold_left_scope_lets ~f:(fun acc scope_let scope_let_var -> ...) ~init scope_lets, where scope_let_var is the variable bound to the scope let in the next scope lets to be examined.

val fold_right_scope_lets : f:(('expr1, 'm1) scope_let -> 'expr1 Bindlib.var -> 'a -> 'a) -> init:(('expr1, 'm1) marked -> 'a) -> ('expr1, 'm1) scope_body_expr -> 'a

Usage: fold_right_scope_lets ~f:(fun scope_let scope_let_var acc -> ...) ~init scope_lets, where scope_let_var is the variable bound to the scope let in the next scope lets to be examined (which are before in the program order).

val map_exprs_in_scope_lets : f:(('expr1, 'm1) marked -> ('expr2, 'm2) marked Bindlib.box) -> varf:('expr1 Bindlib.var -> 'expr2 Bindlib.var) -> ('expr1, 'm1) scope_body_expr -> ('expr2, 'm2) scope_body_expr Bindlib.box
val fold_left_scope_defs : f:('a -> ('expr1, 'm1) scope_def -> 'expr1 Bindlib.var -> 'a) -> init:'a -> ('expr1, 'm1) scopes -> 'a

Usage: fold_left_scope_defs ~f:(fun acc scope_def scope_var -> ...) ~init scope_def, where scope_var is the variable bound to the scope in the next scopes to be examined.

val fold_right_scope_defs : f:(('expr1, 'm1) scope_def -> 'expr1 Bindlib.var -> 'a -> 'a) -> init:'a -> ('expr1, 'm1) scopes -> 'a

Usage: fold_right_scope_defs ~f:(fun scope_def scope_var acc -> ...) ~init scope_def, where scope_var is the variable bound to the scope in the next scopes to be examined (which are before in the program order).

val map_scope_defs : f:(('expr, 'm) scope_def -> ('expr, 'm) scope_def Bindlib.box) -> ('expr, 'm) scopes -> ('expr, 'm) scopes Bindlib.box
val map_exprs_in_scopes : f:(('expr1, 'm1) marked -> ('expr2, 'm2) marked Bindlib.box) -> varf:('expr1 Bindlib.var -> 'expr2 Bindlib.var) -> ('expr1, 'm1) scopes -> ('expr2, 'm2) scopes Bindlib.box

This is the main map visitor for all the expressions inside all the scopes of the program.

Variables

type 'm var = 'm expr Bindlib.var
val new_var : string -> 'm var
val translate_var : 'm1 var -> 'm2 var

used to convert between e.g. untyped expr var into a typed expr var

module Var : sig ... end
module VarMap : Stdlib.Map.S with type key = Var.t
module VarSet : Stdlib.Set.S with type elt = Var.t
val free_vars_expr : 'm marked_expr -> VarSet.t
val free_vars_scope_body_expr : ('m expr, 'm) scope_body_expr -> VarSet.t
val free_vars_scope_body : ('m expr, 'm) scope_body -> VarSet.t
val free_vars_scopes : ('m expr, 'm) scopes -> VarSet.t
val make_var : ('m var, 'm) marked -> 'm marked_expr Bindlib.box

Boxed term constructors

type ('e, 'm) make_abs_sig = 'e Bindlib.mvar -> ('e, 'm) marked Bindlib.box -> marked_typ list -> 'm mark -> ('e, 'm) marked Bindlib.box
val make_abs : ('m expr, 'm) make_abs_sig
val make_app : 'm marked_expr Bindlib.box -> 'm marked_expr Bindlib.box list -> 'm mark -> 'm marked_expr Bindlib.box
type ('expr, 'm) make_let_in_sig = 'expr Bindlib.var -> marked_typ -> ('expr, 'm) marked Bindlib.box -> ('expr, 'm) marked Bindlib.box -> Utils.Pos.t -> ('expr, 'm) marked Bindlib.box
val make_let_in : ('m expr, 'm) make_let_in_sig

Other

val empty_thunked_term : 'm mark -> 'm marked_expr
val is_value : 'm marked_expr -> bool
val equal_exprs : 'm marked_expr -> 'm marked_expr -> bool

Determines if two expressions are equal, omitting their position information

AST manipulation helpers

val build_whole_scope_expr : box_expr:('expr, 'm) box_expr_sig -> make_abs:('expr, 'm) make_abs_sig -> make_let_in:('expr, 'm) make_let_in_sig -> decl_ctx -> ('expr, 'm) scope_body -> 'm mark -> ('expr, 'm) marked Bindlib.box

Usage: build_whole_scope_expr ctx body scope_position where scope_position corresponds to the line of the scope declaration for instance.

type 'expr scope_name_or_var =
  1. | ScopeName of ScopeName.t
  2. | ScopeVar of 'expr Bindlib.var
val unfold_scopes : box_expr:('expr, 'm) box_expr_sig -> make_abs:('expr, 'm) make_abs_sig -> make_let_in:('expr, 'm) make_let_in_sig -> decl_ctx -> ('expr, 'm) scopes -> 'm mark -> 'expr scope_name_or_var -> ('expr, 'm) marked Bindlib.box
val build_whole_program_expr : box_expr:('expr, 'm) box_expr_sig -> make_abs:('expr, 'm) make_abs_sig -> make_let_in:('expr, 'm) make_let_in_sig -> ('expr, 'm) program_generic -> ScopeName.t -> ('expr, 'm) marked Bindlib.box

Usage: build_whole_program_expr program main_scope builds an expression corresponding to the main program and returning the main scope as a function.

val expr_size : 'm marked_expr -> int

Used by the optimizer to know when to stop

val remove_logging_calls : 'm marked_expr -> 'm marked_expr Bindlib.box

Removes all calls to Log unary operators in the AST, replacing them by their argument.

val build_scope_typ_from_sig : decl_ctx -> StructName.t -> StructName.t -> Utils.Pos.t -> typ Utils.Marked.pos

build_scope_typ_from_sig ctx in_struct out_struct pos builds the arrow type for the specified scope

OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct