From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id q27GWbU7006688 for ; Wed, 7 Mar 2012 17:32:37 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AnkDAF+NV0/ZSMDyjmdsb2JhbABCtSQiAQEBAQkLCQkSBSSCCgEBBAE6PwULCw4KCSUPAQQNGyETiAMJt1eJOYc2BJsShVCHWg X-IronPort-AV: E=Sophos;i="4.73,545,1325458800"; d="scan'208";a="148078178" Received: from fmmailgate04.web.de ([217.72.192.242]) by mail1-smtp-roc.national.inria.fr with ESMTP; 07 Mar 2012 17:32:33 +0100 Received: from moweb001.kundenserver.de (moweb001.kundenserver.de [172.19.20.114]) by fmmailgate04.web.de (Postfix) with ESMTP id 6EA9873476F2 for ; Wed, 7 Mar 2012 17:32:33 +0100 (CET) Received: from frosties.localnet ([95.208.118.96]) by smtp.web.de (mrweb001) with ESMTPA (Nemesis) id 0LwZA7-1SRYw34Avf-018FNU; Wed, 07 Mar 2012 17:32:33 +0100 Received: from mrvn by frosties.localnet with local (Exim 4.77) (envelope-from ) id 1S5Jmy-0008Bu-Fx; Wed, 07 Mar 2012 17:32:32 +0100 From: Goswin von Brederlow To: Edgar Friendly Cc: caml-list@inria.fr References: <87sjhktqwi.fsf@frosties.localnet> <4F5777F2.2000806@gmail.com> Date: Wed, 07 Mar 2012 17:32:32 +0100 In-Reply-To: <4F5777F2.2000806@gmail.com> (Edgar Friendly's message of "Wed, 07 Mar 2012 10:00:02 -0500") Message-ID: <878vjctlr3.fsf@frosties.localnet> User-Agent: Gnus/5.110009 (No Gnus v0.9) XEmacs/21.4.22 (linux, no MULE) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Provags-ID: V02:K0:MoqfiKUJSKpNuX2J2Btj3Mkf2P0Ej9vOaTxjp2YXoES wd7IAXGh0ApKwwk0kYRtdUeIe7lCDjfOwswhDYvR/10A7Dxg/z 7C81vljiD+bi9+MhPQwlPYAuiYUAlK5wm4hi0PZiviR2YAvrVk TGr0jLI856B/Fd6TeS81Y9iv9H0a/LePJDwEN3qGPIpiC0rRSm OsNV6cr/Z+JfE0goFzX6A== Subject: Re: [Caml-list] Can one implement greedy/inline data structures in ocaml? Edgar Friendly writes: > On 03/07/2012 09:41 AM, Goswin von Brederlow wrote: >> The task then needs pointers to each of the lists data >> structures creating cycles. Not good for ocaml. It also would waste >> memory for 2 pointers (per list). > > Cycles are fine for ocaml, pointers are pretty cheap, and I think the > answer to your question is no - there's a regularity to values that's > required by the garbage collector, and what you seem to want is the > ability to inline nested structures without pointers, and OCaml's data > representation doesn't allow this, mainly because of the tag word > needed by the GC. > > Beware premature optimization. > > E. The problem with cycles is that you need to define all structures in a cyled atomically as the same time. That means using "let rec foo = ... and bar = ..." and sometimes needing to lift function calls out of the initialization. For example and from memory you couldn't write this: let rec task = { all_list = all_list; state_list = state_list; foo = bar; } and all_list = DList.create_item all_list_head task and state_list DList.create_item state_list_head task At the time the DList.create_item is called the task binding is still incomplete and you get an error that it can't be on the right-hand side. So then you need mutable option types or mutables that you initialize with dummy values and then overwrite with the real thing once all members of a cycle are created. Or some other trickery to make it work. Overall cycles are generally not good. Inlining the DList wihtout another indirection like in C would be nice but would certainly require some camlp4 code to pull off. But it would certainly be enough to pull in a pointer to the list structure as long as you don't also need a back pointer inside the list structure. The cycle is the problem there, just one direction is fine. MfG Goswin