Re: Data structures in ocaml

[Michel Quercia <quercia@cal.enst.fr>]

Le sam, 09 oct 1999, vous avez écrit :

: For instance:
: 
: -- (any : int) was 0
: -- (any : string) was ""
: ...
: -- (any : t) where t was a sum type was the first constant constuctor if
: any ot the first functional constructor C of ty with (any : ty) as
: argument. (Hence (any : string list) was [].)
: -- (any : t) where t was a record type was the list of field with the
: value (any : ty) in each field (ty according to the label argument).-- (any : t1 -> t2) was (fun _ -> raise Bottom)
: 
: This is well-typed and semantically sound.

What about : "type t = T of int*t" (immutable circular int lists) ?
Well there is a solution : "let rec dummy = T(0,dummy)" but in more complicated
recursive type definitions the compiler will have to work hard to produce some
plausible value, it seems to me that this should always be possible, am I right
?

Concerning varying arrays,
--------------------------
I had an idea not far from Markus Mottl's own.
Define a new tag, let's call it Vtag flagging varying size (that is both growing
and shrinking) objects. A Vobject would say :

"Hello everybody, I'm a varying size object, I have TWO lengths, an allocation
length stored in my header and an actual length stored in my first field. And
you can pretty trust in me, the actual length never greater that the allocation
one will be.

Mr. GC, would be so kind as to not put your nose past my actual length ? There
is nothing interresting for you there.

Mr. compiler, please check index bounds against my actual length, and shift
actual index by one in order to retrieve the indexed value."

Now the need for uninitialized values disappears as well as the need to erase
pointers when shrinking a Varray ... Nice, but I have some doubts about O'caml
implementors accepting my proposal.


Concerning Lists implemented by varying arrays,
-----------------------------------------------
An awfull question pops up inside of me, how can one implement :

let l1 = a :: l and l2 = b :: l

if lists are actually arrays (with head at the end) without copying l ?


--
Michel Quercia
9/11 rue du grand rabbin Haguenauer, 54000 Nancy
http://pauillac.inria.fr/~quercia
mailto:quercia@cal.enst.fr