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

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

Thorsten Ohl schrieb am Mittwoch, den 01. August 2001:
> In my experience, one can beat the combinatorial complexity only if one
> understands the genesis of such values with high sharing potential.
> Then one can construct algorithms that start from building all
> possible combinations in a highly condensed representation and select
> the interesting ones later.  This will be much more efficient than
> building only the interesting ones and searching for shared nodes later.

My requirements are a bit different: 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).

Merging the programs into a shared datastructure would allow me to quickly
find out about (syntactic) equivalences of whole programs or their parts.

The three options I currently have:

  * Write a specialized implemention for program trees. Would probably be
    most efficient, because I can exploit some of their properties.

  * Write a generic implementation, which lets the user provide decompose-
    and comparison functions for his types. The latter puts some work
    on the user, but is otherwise generic and elegant.

  * Write a fully generic implementation that works on any type by
    traversing the low-level representation of OCaml-values. Somewhat
    messy to implement and may break when representations change...

A difficult question how to proceed best. Considering changes to
datastructures, a generic solution would be fine. This would also allow me
(and you :) to reuse it...

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