package fix

Fix: memoization and fixed points made easy

fix is an OCaml library that helps with various constructions that involve memoization and recursion.

Installation

Type opam install fix.

Overview

At the top of an OCaml module, declare open Fix. This gives you access to the following submodules:

• CompactQueue offers a minimalist mutable FIFO queue that is tuned for performance.

• DataFlow performs a forward data flow analysis over a directed graph. Like Fix, it computes the least function of type variable -> property that satisfies a fixed point equation. It is less widely applicable than Fix, but, when it is applicable, it is easier to use and more efficient than Fix. DataFlow.ForCustomMaps is particularly tuned for performance.

• Gensym offers a simple facility for generating fresh integer identifiers.

• Indexing offers a safe API for manipulating indices into fixed-size arrays.

• Memoize offers a number of combinators that help construct possibly recursive memoizing functions, that is, functions that lazily record their input/output graph, so as to avoid repeated computation.

• Tabulate 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 constant time.

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

• GraphNumbering offers a facility for discovering and numbering the reachable vertices in a finite directed graph.

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

• Fix 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. The function thus obtained performs the fixed point computation on demand, in an incremental manner, and is memoizing.

• Prop defines a few common partial orders, including Prop.Boolean, Prop.Option, Prop.Set.

• Glue contains glue code that helps build various implementations of association maps.

The signatures that appear in the above files, such as MEMOIZER, TABULATOR, SOLVER, and so on, are defined here.

The documentation is built by make doc and is then found in the file _build/default/_doc/_html/index.html.

The documentation of the latest released version is also available online.

Demos

A few demos are provided:

• brz sets up a hash-consed representation of regular expressions and shows how to convert a regular expression to a deterministic finite-state automaton by Brzozowski's method. This demo exploits almost all of the submodules listed above, and is accompanied with a commentary.

• cyk presents a CYK-style parsing algorithm as an instance of Fix.

• cfg uses Fix to perform certain static analyses of a context-free grammar; this includes computing nullability information and FIRST sets.

• fib defines Fibonacci's function in several different ways using the fixed-point combinators offered by Memoize and Fix.

• hco sets up simple-minded hash-consed trees using HashCons.