Fix.Fix
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.
Make
constructs a solver for a type key
that is equipped with an implementation of imperative maps and a type property
that is equipped with bottom
, equal
, and is_maximal
functions.
module ForOrderedType (T : sig ... end) (P : sig ... end) : sig ... end
ForOrderedType
is a special case of Make
where it suffices to pass an ordered type T
as an argument. A reference to a persistent map is used to hold the memoization table.
module ForHashedType (T : sig ... end) (P : sig ... end) : sig ... end
ForHashedType
is a special case of Make
where it suffices to pass a hashed type T
as an argument. A hash table is used to hold the memoization table.