Re: [Caml-list] "super-compaction" of values

[Thorsten Ohl <ohl@hep.tu-darmstadt.de>]

Markus Mottl writes:

> I generate programs (abstract syntax trees) almost randomly. It can
> happen very often that generated programs have already been tried or
> share large subtrees with already known solutions. The programs are
> usually not terribly large, but evaluating them is extremely
> expensive.  Therefore, I would like to prevent it at all if the
> meaning is already known or at least speed it up significantly by
> reusing the meaning of subtrees (the programs are referentially
> transparent, of course).

This implies that you either have a good comparison function for your
(sub-)trees or a unique representation or that you can live with a
small fraction of program trees that are not recognized as equivalent.
In this case you can represent trees as maps from parent nodes to sets
of child nodes and you get a DAG representation with automatically
shared common subexpressions for free.

A different solution could probably be build on a variation of Chris
Okasaki's Tries of Trees. [I have only a bare bones O'Caml version,
but the usual tricks for working around the lack of polymorphic
recursion work.]
-- 
Thorsten Ohl, Physics Department, TU Darmstadt -- ohl@hep.tu-darmstadt.de
http://heplix.ikp.physik.tu-darmstadt.de/~ohl/ [<=== PGP public key here]
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr