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 MAA18062; Wed, 1 Aug 2001 12:20:53 +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 MAA18058 for <caml-list@pauillac.inria.fr>; Wed, 1 Aug 2001 12:20:52 +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 f71AKpn01109
	for <caml-list@inria.fr>; Wed, 1 Aug 2001 12:20:51 +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 MAA02203
	for <caml-list@inria.fr>; Wed, 1 Aug 2001 12:20:51 +0200
Received: (from markus@localhost)
	by kastanie.ai.univie.ac.at (8.9.3/8.9.3/Debian 8.9.3-21) id MAA12790
	for caml-list@inria.fr; Wed, 1 Aug 2001 12:20:51 +0200
Date: Wed, 1 Aug 2001 12:20:51 +0200
From: Markus Mottl <markus@mail4.ai.univie.ac.at>
To: OCAML <caml-list@inria.fr>
Subject: [Caml-list] "super-compaction" of values
Message-ID: <20010801122051.A12317@kastanie.ai.univie.ac.at>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
User-Agent: Mutt/1.2.5i
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

Hello,

has anybody already attempted to implement some kind of "super-compaction"
of arbitrary values, e.g.:

  let list_a = [1, 2, 3, 4]
  let list_b =       [3, 4]

Both are in completely distinct parts of the memory. What I'd find
interesting is a module like:

  type 'a t

  val empty : unit -> 'a t
  val add : 'a -> 'a t -> 'a

which, when applied like this:

  let t = empty () in
  let la = add list_a t in
  let lb = add list_b t in
  ...

would return "la" unchanged but "lb" would now share the common structure
with list_a (= la) (also when inserted in any other order).

If this worked for arbitrary datastructures, one could exploit this to
produce very compact representations of values by maximizing the amount
of sharing between them.

One could use the "Obj"-module for this purpose. Problems, however, are:

  * Probably not useful for cyclic datastructures (too inefficient), but
    support of acyclic structures only would be ok.

  * Support automatic GC? Or should the user make sure that possible
    administrative memory overhead is prevented by telling "'a t" that
    some value need not be remembered for sharing with further values
    anymore.  The "automatic" version is probably less efficient and
    much more complicated.

An extreme form of this implementation could even have functions +
types like:

  val add : 'a -> t -> 'a

This would even allow sharing between representations of different types.

A correct and efficient implementation is probably everything else but
trivial. If anybody has already tried this crazy idea, I'd be interested
to know!

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