Module Fix

module type TYPE = sig ... end

A type alone.

module type OrderedType = Map.OrderedType

An ordered type.

module type HashedType = Hashtbl.HashedType

A hashed type.

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

The signature PROPERTY is used by Fix.Make, the least fixed point computation algorithm.

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.

type 'a fix = ('a -> 'a) -> 'a

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

module Make (M : sig ... end) (P : sig ... end) : sig ... end