Module Shared_ast.Expr

Box the expression from the outside

For closed expressions, similar to Bindlib.unbox

Rebuild the whole term, re-binding all variables and exposing free variables

Returns an empty mark, using the argument as type witness. Note that the custom part is kept on Custom marks

Adds the given type information only on typed marks

Identity on untyped marks

• raises Invalid_arg

  on custom marks

• raises Invalid_arg

  on custom marks

Returns the corresponding type on a typed expr, or typ (defaulting to TAny) at the current position on an untyped one

Shallow mapping on expressions (non recursive): applies the given function to all sub-terms of the given expression, and rebuilds the node.

This function makes it very concise to transform only certain nodes of the AST. For instance, if you want to remove all errors on empty, you can write

let remove_error_empty e =
  let rec f e =
    match Mark.remove e with
    | EErrorOnEmpty e1 -> Expr.map ~f e1
    | _ -> Expr.map ~f e
  in
  f e

This can even be used to translate between different kinds of ASTs: see Lcalc.Compile_without_exceptions for an example. The structure is like this:

let rec translate = function
  | SpecificCase e -> TargetCase (translate e)
  | (All | Other | Common | Cases) as e -> Expr.map ~f:translate e

The e parameter passed to map here needs to have only the common cases in its shallow type, but can still contain any node from the starting AST deeper inside: this is where the second type parameter to base_gexpr becomes useful.

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.

Applies a function on all sub-terms of the given expression. Does not recurse. It opens binders unless you avoid sending binders to the function like the example below. Useful as helper for recursive calls within traversal functions. This can be used to compute free variables with e.g.:

let rec free_vars = function
  | EVar v, _ -> Var.Set.singleton v
  | EAbs { binder; _ }, _ ->
    let vs, body = Bindlib.unmbind binder in
    Array.fold_right Var.Set.remove vs (free_vars body)
  | e ->
    shallow_fold (fun e -> Var.Set.union (free_vars e)) e Var.Set.empty

Shallow mapping similar to map, but additionally allows to gather an accumulator bottom-up. acc is the accumulator value returned on terminal nodes, and join is used to merge accumulators from the different sub-terms of an expression. acc is assumed to be a neutral element for join. Typically used with a set of variables used in the rewrite:

let rec rewrite e =
  match Mark.remove e with
  | Specific_case -> Var.Set.singleton x, some_rewrite_fun e
  | _ ->
    Expr.map_gather ~acc:Var.Set.empty ~join:Var.Set.union ~f:rewrite e

See Lcalc.closure_conversion for a real-world example.

make_default ?pos exceptions just cons builds a term semantically equivalent to <exceptions | just :- cons> (the EDefault constructor) while avoiding redundant nested constructions. The position is extracted from just by default.

Note that some simplifications take place here, even though all of them return an EDefault term:

• <ex | true :- def>, when def is a default term <j :- c> without exceptions, is collapsed into <ex | def>
• <ex | false :- _>, when ex is a single exception of the form EDefault, is rewritten as ex

Builds a tuple; the mark argument is only used as witness and for position when building 0-uples

Removes surface logging calls and EErrorOnEmpty nodes. Shallow function

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

Simple printing without debug, use Print.expr () instead to follow the command-line debug setting

Determines if two expressions are equal, omitting their position information

Standard comparison function, suitable for e.g. Set.Make. Ignores position information

Used by the optimizer to know when to stop