package ego

  1. Overview
  2. Docs

The LANGUAGE module type represents the definition of an arbitrary language for use with an EGraph.

type 'a shape

Encodes the "shape" of an expression in the language over sub-expressions of type 'a.

type op

Represents the tags that discriminate the expression constructors of the language.

type t =
  1. | Mk of t shape

Represents concrete terms of the language by "tying-the-knot".

val equal_op : op -> op -> bool

equal_op op1 op2 returns true if the operators op1, op2 are equal.

val pp_shape : (Stdlib.Format.formatter -> 'a -> unit) -> Stdlib.Format.formatter -> 'a shape -> unit

pp_shape f fmt s pretty prints expressions of the language.

val compare_shape : ('a -> 'a -> int) -> 'a shape -> 'a shape -> int

compare cmp a b compares expressions a and b using cmp to compare subexpressions.

val op : 'a shape -> op

op expr retrieves the tag that discriminates the shape of the expression expr.

val children : 'a shape -> 'a list

children exp returns the subexpressions of expression exp.

val map_children : 'a shape -> ('a -> 'b) -> 'b shape

map_children exp f maps the function f over the sub-expressions of the expression exp

val make : op -> 'a list -> 'a shape

make op ls constructs an expression from the tag op and children ls.

Note: If called with invalid arity of arguments for the operator op the function may throw an error.