Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] Single-case union types as strong typedefs
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: John Prevost <j.prevost@g...>
Subject: Re: [Caml-list] Single-case union types as strong typedefs
On Sat, 23 Oct 2004 14:24:28 -0700, Nathaniel Gray <n8gray@gmail.com> wrote:
> On Sat, 23 Oct 2004 12:31:39 +0900 (JST), Jacques Garrigue
> <garrigue@kurims.kyoto-u.ac.jp> wrote:
> > With your example, there is no extra boxing involved.
> > I.e. (1,3) and Rpos(1,3) and Apos(1,3) all share the same physical
> > representation (a block with 2 fields).
> > The problem you describe only occurs when your single constructor has
> > only one argument.
> 
> Really??  You're kidding.  That's kind of cool but kind of strange --
> why does it only optimize for composite types?

It's not so much that it's only optimized for "composite types" as
that all of these constructors are *already* considered n-tuples. 
Think of it this way:

type foo = Foo | Bar of int * int | Baz of int

This is represented as something like:

Foo = 0
Bar (x, y) = (0, x, y)
Baz (x) = (1, x)
(a, b) = (a, b)

This isn't really what's going on, of course.  (More precisely, which
constructor was used is encoded in the block header.)  But, it does
provide enough of a model to see why what Jacques says is true. 
Essentially, you need to think of the tag as another integral piece of
information.  And then realize that everything bigger than an integer
is (at least sometimes) boxed.  So all of the above with (...) needs
to be boxed.

The true picture of the world is that there's a header at the start of
the values in memory, and that header includes information about the
length and which constructor was used.  So the above in reality go to
something more like:

Foo = 0
Bar (x, y) = <0; 2; x; y>
Baz x = <1; 1; x>
(a, b) = <0; 2; a; b>

(where <t; l; v_0 ... v_(l-1)> represents a tagged block allocated by
the Caml runtime, with tag t and length l, which is typically passed
around as a pointer to v_0.  See section 18.2.2 of the O'Caml manual
for more detail.)

So the first non-constant constructor for an algebraic type is
represented the exact same way as a normal tuple.  Any further
constructors are identical except for the tag.

John.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners