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:

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

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

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.