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 QAA23835; Wed, 1 Aug 2001 16:31:00 +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 QAA23828 for ; Wed, 1 Aug 2001 16:30:59 +0200 (MET DST) Received: from heplix4.ikp.physik.tu-darmstadt.de (heplix4.ikp.physik.tu-darmstadt.de [130.83.210.158]) by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id f71EUwn04206 for ; Wed, 1 Aug 2001 16:30:59 +0200 (MET DST) Received: (from ohl@localhost) by heplix4.ikp.physik.tu-darmstadt.de (8.11.2/8.11.2/SuSE Linux 8.11.1-0.5) id f71ETma30519; Wed, 1 Aug 2001 16:29:48 +0200 From: Thorsten Ohl MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15208.4700.18141.346738@heplix4.ikp.physik.tu-darmstadt.de> Date: Wed, 1 Aug 2001 16:29:48 +0200 To: caml-list@inria.fr Subject: Re: [Caml-list] "super-compaction" of values In-Reply-To: <20010801160947.A13832@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> X-Mailer: VM 6.84 under Emacs 20.7.1 Reply-To: ohl@hep.tu-darmstadt.de Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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