Re: [Caml-list] Can one implement greedy/inline data structures in ocaml?

[Gabriel Scherer <gabriel.scherer@gmail.com>]

> 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.

I believe the trick you need (either passing a dummy value of your
type, or Obj.magic) is less ugly that your Camlp4 solution for inline
access.
If I really needed absolute performance, I'd use the inline version
just like in C, with mutable fields, but without preprocessor sugar.
Preprocessing could avoid a bit of duplication (corresponding to
manual inlining) on the structure-definition side, but wouldn't
simplify the structure-using code much.

On Wed, Mar 7, 2012 at 5:32 PM, Goswin von Brederlow <goswin-v-b@web.de> wrote:
> Edgar Friendly <thelema314@gmail.com> 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
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>