From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id RAA25467; Wed, 1 Aug 2001 17:25:57 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA25460 for ; Wed, 1 Aug 2001 17:25:56 +0200 (MET DST) Received: from fichte.ai.univie.ac.at (fichte.ai.univie.ac.at [131.130.174.156]) by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id f71FPtn05135 for ; Wed, 1 Aug 2001 17:25:55 +0200 (MET DST) Received: from kastanie.ai.univie.ac.at (root@kastanie.ai.univie.ac.at [131.130.174.141]) by fichte.ai.univie.ac.at (8.9.3/8.9.3/Debian 8.9.3-21) with ESMTP id RAA32624; Wed, 1 Aug 2001 17:25:52 +0200 Received: (from markus@localhost) by kastanie.ai.univie.ac.at (8.9.3/8.9.3/Debian 8.9.3-21) id RAA14911; Wed, 1 Aug 2001 17:25:51 +0200 Date: Wed, 1 Aug 2001 17:25:51 +0200 From: Markus Mottl To: Thorsten Ohl Cc: caml-list@inria.fr Subject: Re: [Caml-list] "super-compaction" of values Message-ID: <20010801172551.A14242@kastanie.ai.univie.ac.at> References: <20010801122051.A12317@kastanie.ai.univie.ac.at> <15208.1819.257638.641407@heplix4.ikp.physik.tu-darmstadt.de> <20010801160947.A13832@kastanie.ai.univie.ac.at> <15208.4700.18141.346738@heplix4.ikp.physik.tu-darmstadt.de> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: <15208.4700.18141.346738@heplix4.ikp.physik.tu-darmstadt.de>; from ohl@hep.tu-darmstadt.de on Wed, Aug 01, 2001 at 16:29:48 +0200 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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