`Fix`

`module type TYPE = sig ... end`

A type alone.

`module type FINITE_TYPE = sig ... end`

A type whose elements can be enumerated.

`module type PERSISTENT_MAPS = sig ... end`

`PERSISTENT_MAPS`

is a fragment of the standard signature `Map.S`

.

`module type MINIMAL_IMPERATIVE_MAPS = sig ... end`

`module type IMPERATIVE_MAPS = sig ... end`

`module type ARRAY = sig ... end`

An instance of the signature `ARRAY`

represents one mutable map. There is no type `'data t`

and no `create`

operation; there exists just one map. Furthermore, the type `value`

, which corresponds to `'data`

in the previous signatures, is fixed.

`module type PROPERTY = sig ... end`

`module type SEMI_LATTICE = sig ... end`

The signature `SEMI_LATTICE`

offers separate `leq`

and `join`

functions. The functor `Glue.MinimalSemiLattice`

can be used, if necessary, to convert this signature to `MINIMAL_SEMI_LATTICE`

.

`module type MINIMAL_SEMI_LATTICE = sig ... end`

The signature `MINIMAL_SEMI_LATTICE`

is used by `DataFlow.Run`

and friends.

`'a fix`

is the type of a fixed point combinator that constructs a value of type `'a`

.

`module type MEMOIZER = sig ... end`

A memoizer is a higher-order function that constructs memoizing functions.

`module type TABULATOR = sig ... end`

A tabulator is a higher-order function that constructs tabulated functions.

`module type SOLVER = sig ... end`

A solver is a higher-order function that computes the least solution of a monotone system of equations.

`module type SOLUTION = sig ... end`

The signature `SOLUTION`

describes the result of `DataFlow.Run`

and friends.

`module type GRAPH = sig ... end`

The signature `GRAPH`

describes a directed, rooted graph. It is used by `GraphNumbering.Make`

and friends.

`module type DATA_FLOW_GRAPH = sig ... end`

The signature `DATA_FLOW_GRAPH`

describes a data flow analysis problem. It is used by `DataFlow.Run`

and friends.

`module type ONGOING_NUMBERING = sig ... end`

An ongoing numbering of (a subset of) a type `t`

.

`module type NUMBERING = sig ... end`

A fixed numbering of (a subset of) a type `t`

.

`module type TWO_PHASE_NUMBERING = sig ... end`

The signature `TWO_PHASE_NUMBERING`

combines the signatures `ONGOING_NUMBERING`

and `NUMBERING`

. It describes a numbering process that is organized in two phases. During the first phase, the numbering is ongoing: one can encode keys, but not decode. Applying the functor `Done()`

ends the first phase. A fixed numbering then becomes available, which gives access to the total number `n`

of encoded keys and to both `encode`

and `decode`

functions.

`module type INJECTION = sig ... end`

An injection of a type into a type.

`module Glue : sig ... end`

This module contains glue code that helps use the functors provided by other modules. In particular, it helps build various implementations of **association maps**.

`module Memoize : sig ... end`

This module offers facilities for **constructing a (possibly recursive) memoized function**, that is, a function that lazily records its input/output graph, so as to avoid repeated computation.

`module Numbering : sig ... end`

This module offers a facility for **assigning a unique number** to each value in a certain finite set and translating (both ways) between values and their numbers.

`module GraphNumbering : sig ... end`

This module offers a facility for **discovering and numbering the reachable vertices** in a finite directed graph.

`module Indexing : sig ... end`

This module offers **a safe API for manipulating indices into fixed-size arrays**.

`module Tabulate : sig ... end`

This module offers facilities for **tabulating a function**, that is, eagerly evaluating this function at every point in its domain, so as to obtain an equivalent function that can be queried in (near) constant time.

`module Gensym : sig ... end`

This module offers a simple facility for **generating fresh integer identifiers**.

`module HashCons : sig ... end`

This module offers support for **setting up a hash-consed data type**, that is, a data type whose values carry unique integer identifiers.

`module DataFlow : sig ... end`

This module performs a **forward data flow analysis** over a (possibly cyclic) directed graph. Like `Fix.Fix`

, it computes the least function of type `variable -> property`

that satisfies a fixed point equation. It is less widely applicable than `Fix.Fix`

, but, when it is applicable, it can be both easier to use and more efficient. It does not perform dynamic dependency discovery. The submodule `Fix.DataFlow.ForCustomMaps`

is particularly **tuned for performance**.

`module CompactQueue : sig ... end`

This module offers **a minimalist mutable FIFO queue** that is tuned for performance.

`module Enum : sig ... end`

This module offers a few functions that help deal with enumerations.

`module Partition : sig ... end`

This module offers a **partition refinement** data structure.

`module Minimize : sig ... end`

This module offers a **minimization** algorithm for **deterministic finite automata** (DFAs).

`module Prop : sig ... end`

This module defines **a few common partial orders**, each of which satisfies the signature `PROPERTY`

. These include Booleans, options, and sets.

`module Fix : sig ... end`

This module offers support for **computing the least solution of a set of monotone equations**, as described in the unpublished paper Lazy Least Fixed Points in ML. In other words, it allows defining a recursive function of type `variable -> property`

, where **cyclic dependencies** between variables are allowed, and properties must be equipped with a partial order that has finite ascending chains. This function performs the fixed point computation on demand, in an incremental manner, and is memoizing. This is typically used to perform a **backward data flow analysis** over a directed graph. This algorithm performs **dynamic dependency discovery**, so there is no need for the user to explicitly describe dependencies between variables.