package catala

You can search for identifiers within the package.

in-package search v0.2.0

On This Page

Types and unification
Double-directed typing
API

catala
- Catala
  - Driver
catala.dcalc
- Dcalc
  - Ast
    
    Var
    
    VarMap
  - Interpreter
  - Print
  - Typing
catala.desugared
- Desugared
  - Ast
    
    RuleName
    
    ScopeDef
  - Dependency
    
    Edge
    
    SCC
    
    ScopeDependencies
    
    E
    
    V
    
    TopologicalTraversal
    
    Vertex
  - Desugared_to_scope
catala.literate
- Literate
  - Html
  - Latex
catala.scopelang
- Scopelang
  - Ast
    
    EnumConstructor
    
    EnumName
    
    ScopeName
    
    ScopeVar
    
    StructFieldName
    
    StructName
    
    SubScopeName
    
    Var
    
    VarMap
  - Dependency
    
    SDependencies
    
    E
    
    V
    
    SEdge
    
    SSCC
    
    STopologicalTraversal
    
    SVertex
    
    TDependencies
    
    E
    
    V
    
    TEdge
    
    TSCC
    
    TTopologicalTraversal
    
    TVertex
    
    TVertexSet
  - Print
  - Scope_to_dcalc
catala.surface
- Surface
catala.utils
- Utils
  - Cli
  - Errors
  - Pos
  - Uid
    
    Id
    
    Info
    
    Make
    
    X
    
    MarkedString

Legend:
Library
Module
Module type
Parameter
Class
Class type

Typing for the default calculus. Because of the error terms, we perform type inference using the classical W algorithm with union-find unification.

module Pos = Utils.Pos

module Errors = Utils.Errors

module A = Ast

module Cli = Utils.Cli

Types and unification

type typ =

| TLit of A.typ_lit
| TArrow of typ Pos.marked UnionFind.elem * typ Pos.marked UnionFind.elem
| TTuple of typ Pos.marked UnionFind.elem list
| TEnum of typ Pos.marked UnionFind.elem list
| TAny

We do not reuse Dcalc.Ast.typ because we have to include a new TAny variant. Indeed, error terms can have any type and this has to be captured by the type sytem.

val format_typ : 
  Stdlib.Format.formatter ->
  typ Pos.marked UnionFind.elem ->
  unit

val unify : 
  typ Pos.marked UnionFind.elem ->
  typ Pos.marked UnionFind.elem ->
  unit

Raises an error if unification cannot be performed

val op_type : A.operator Pos.marked -> typ Pos.marked UnionFind.elem

Operators have a single type, instead of being polymorphic with constraints. This allows us to have a simpler type system, while we argue the syntactic burden of operator annotations helps the programmer visualize the type flow in the code.

val ast_to_typ : A.typ -> typ

val typ_to_ast : typ Pos.marked UnionFind.elem -> A.typ Pos.marked

Double-directed typing

type env = typ Pos.marked A.VarMap.t

val typecheck_expr_bottom_up : 
  env ->
  A.expr Pos.marked ->
  typ Pos.marked UnionFind.elem

Infers the most permissive type from an expression

val typecheck_expr_top_down : 
  env ->
  A.expr A.Pos.marked ->
  typ Pos.marked UnionFind.elem ->
  unit

Checks whether the expression can be typed with the provided type

API

val infer_type : A.expr Pos.marked -> A.typ Pos.marked

val check_type : A.expr Pos.marked -> A.typ Pos.marked -> unit

Typechecks an expression given an expected type