README.md 1.11 KB
Newer Older
POTTIER Francois's avatar
README.  
POTTIER Francois committed
1
2
# Fix: memoization and fixed points made easy

3
4
`fix` is an OCaml library that helps with various algorithmic
constructions that involve memoization, recursion, and numbering.
POTTIER Francois's avatar
README.  
POTTIER Francois committed
5

6
## Documentation
POTTIER Francois's avatar
README.  
POTTIER Francois committed
7

8
See the [documentation of the latest released
POTTIER Francois's avatar
POTTIER Francois committed
9
version](http://cambium.inria.fr/~fpottier/fix/doc/fix/index.html).
10

POTTIER Francois's avatar
README.    
POTTIER Francois committed
11
12
13
14
15
16
## 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
17
  finite-state automaton by Brzozowski's method. This demo exploits many
POTTIER Francois's avatar
README.    
POTTIER Francois committed
18
19
  of the submodules listed above, and is accompanied with
  [a commentary](misc/post.md).
POTTIER Francois's avatar
README.    
POTTIER Francois committed
20
21
22
23
24
25
26
27
28
29
30
31
32

* [`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`.