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 QAA23015; Wed, 1 Aug 2001 16:09:53 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id QAA23011 for ; Wed, 1 Aug 2001 16:09:52 +0200 (MET DST) Received: from fichte.ai.univie.ac.at (fichte.ai.univie.ac.at [131.130.174.156]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f71E9mX24458 for ; Wed, 1 Aug 2001 16:09:49 +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 QAA24747; Wed, 1 Aug 2001 16:09:48 +0200 Received: (from markus@localhost) by kastanie.ai.univie.ac.at (8.9.3/8.9.3/Debian 8.9.3-21) id QAA14172; Wed, 1 Aug 2001 16:09:48 +0200 Date: Wed, 1 Aug 2001 16:09:47 +0200 From: Markus Mottl To: Thorsten Ohl Cc: caml-list@inria.fr Subject: Re: [Caml-list] "super-compaction" of values Message-ID: <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> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: <15208.1819.257638.641407@heplix4.ikp.physik.tu-darmstadt.de>; from ohl@hep.tu-darmstadt.de on Wed, Aug 01, 2001 at 15:41:47 +0200 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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