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 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.