FixSourceAn ordered type.
A hashed type.
A type whose elements can be enumerated.
PERSISTENT_MAPS is a fragment of the standard signature Map.S.
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.
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.
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.
A memoizer is a higher-order function that constructs memoizing functions.
A tabulator is a higher-order function that constructs tabulated functions.
A solver is a higher-order function that computes the least solution of a monotone system of equations.
The signature SOLUTION describes the result of DataFlow.Run and friends.
The signature GRAPH describes a directed, rooted graph. It is used by GraphNumbering.Make and friends.
The signature DATA_FLOW_GRAPH describes a data flow analysis problem. It is used by DataFlow.Run and friends.
An ongoing numbering of (a subset of) a type t.
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.
This module contains glue code that helps use the functors provided by other modules. In particular, it helps build various implementations of association maps.
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.
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.
This module offers a facility for discovering and numbering the reachable vertices in a finite directed graph.
This module offers a safe API for manipulating indices into fixed-size arrays.
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.
This module offers a simple facility for generating fresh integer identifiers.
This module offers support for setting up a hash-consed data type, that is, a data type whose values carry unique integer identifiers.
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.
This module offers a minimalist mutable FIFO queue that is tuned for performance.
This module defines a few common partial orders, each of which satisfies the signature PROPERTY. These include Booleans, options, and sets.
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.