README.md 2.86 KB
Newer Older
POTTIER Francois's avatar
README.  
POTTIER Francois committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 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`](src/Gensym.mli) offers a simple facility
  for **generating fresh integer identifiers**.

* [`Memoize`](src/Memoize.mli) 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`](src/Tabulate.mli) 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.

* [`Number`](src/Number.mli) offers a facility for
  **discovering and numbering the reachable vertices** in a directed graph.

* [`HashCons`](src/HashCons.mli) offers support for
  **setting up a hash-consed data type**, that is, a data type whose
  values carry unique integer identifiers.

* [`Fix`](src/Core.mli) 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](http://gallium.inria.fr/~fpottier/publis/fpottier-fix.pdf).
  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.
POTTIER Francois's avatar
README.    
POTTIER Francois committed
43
44
45
  The function thus obtained performs the fixed point
  computation on demand, in an incremental manner,
  and is memoizing.
POTTIER Francois's avatar
README.  
POTTIER Francois committed
46
47
48
49
50
51
52
53
54
55
56
57
58

* `Prop` defines a few common partial orders, including
  [`Prop.Boolean`](src/Boolean.mli),
  [`Prop.Option`](src/Option.mli),
  [`Prop.Set`](src/Set.mli).

* [`Glue`](src/Glue.mli) 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](src/Sigs.ml).

POTTIER Francois's avatar
README.    
POTTIER Francois committed
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
## Demos

A few demos are provided:

* [`brz`](demos/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 all of the
  submodules listed above!

* [`cyk`](demos/cyk) presents a CYK-style parsing algorithm as an instance of
  `Fix`.

* [`cfg`](demos/cfg) uses `Fix` to perform certain static analyses of a
  context-free grammar; this includes computing nullability information and
  FIRST sets.

* [`fib`](demos/fib) defines Fibonacci's function in several different ways
  using the fixed-point combinators offered by `Memoize` and `Fix`.

* [`hco`](demos/hco) sets up simple-minded hash-consed trees
  using `HashCons`.