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 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 eassert : 'm marked_expr Bindlib.box -> 'm mark -> 'm marked_expr Bindlib.box
val eop : operator -> '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