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

[Markus Mottl <markus@mail4.ai.univie.ac.at>]

Thorsten Ohl schrieb am Mittwoch, den 01. August 2001:
> 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.

Comparing program trees for equivalence is straightforward. Their concrete
representation is:

  type tree = Tree of int * tree array | Leaf of int

"Tree (1, [| Leaf 2 |])" would read "from the current nonterminal (e.g.
start symbol), choose production 1, which contains a terminal in state 2".

Of course, semantic equivalence doesn't imply syntactic equivalence.
Exploitation of semantic equivalences is handled by preprocessing programs
with user specified rewrite rules to get normal forms. The latter can
then be exploited with syntactic equivalences again.

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

This is the non-generic solution I currently have in mind. I'd only
have to convert between my representation and this one so it shouldn't
be terribly difficult.

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

Yes, I remember this chapter (though I currently don't have the book
at hand). I'll probably take another look at it, maybe it inspires me
to implement a solution I like. I had hoped that somebody might have
already implemented a generic solution, but so I'll have to continue
experimenting...

Thanks a lot for the help!

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
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