[Caml-list] Single-case union types as strong typedefs

[Caml-list] Single-case union types as strong typedefs

[Nathaniel Gray]

Hi,

Since we're talking about degenerate cases (unit vs. void) I might as
well ask a question that's been on my mind for a while.  There are
many times when you have types that are structurally identical but
conceptually different.  One example is lengths measured in different
units, another is values measured in identical units that shouldn't be
mixed unintentionally (e.g. widths and heights).  It would be really
nice to be able to use a coding style like this (contrived) example
that you could imagine coming from a graphics library:

(* Library code: *)
type relative_pos = Rpos of int * int
type absolute_pos = Apos of int * int

let displacement (Apos (x1, y1)) (Apos (x2, y2)) = 
   Rpos(x2 - x1, y2 - y1)
let scaled_move (Apos (x1, y1)) (Rpos (x2, y2)) mult = 
   Apos(x1 + x2*mult, y1 + y2*mult)

(* Client code: *)
let p1 = Apos (5,5) in
let p2 = Apos (7,9) in
(* Uh-oh, I didn't read the API docs! *)
scaled_move p1 p2 5

The idea is that the programmer isn't allowed to mix relative and
absolute positions without being explicit about it.  Essentially this
is a strong typedef.

This is all legal right now, but the problem is performance since the
tuples get boxed unnecessarily.  But non-polymorphic single-case union
types can always be optimized away.  Or rather, once type checking is
complete it's safe to (globally and atomically) perform the group of
transformations:
  type x = Foo y  
     --> type x = y  (* Only necessary if types are retained after
type checking *)
  Foo x
     --> x
  match x with Foo y -> expr
     --> let y = x in expr

Once this was done, inlining would probably catch any small conversion
functions, eliminating any overhead associated with this coding style.
 So you get the type checker helping you eliminate conceptual bugs
with little-to-no run time penalty.

So my question is, does the OCaml compiler optimize monomorphic
single-case union types this way?  If not, is there a conceptual
problem with my argument or is it just a lack of time and/or interest?

Thanks,
-n8

-- 
>>>-- Nathaniel Gray -- Caltech Computer Science ------>
>>>-- Mojave Project -- http://mojave.cs.caltech.edu -->

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

Re: [Caml-list] Single-case union types as strong typedefs

[Jacques Garrigue]

From: Nathaniel Gray <n8gray@gmail.com>

> Since we're talking about degenerate cases (unit vs. void) I might as
> well ask a question that's been on my mind for a while.  There are
> many times when you have types that are structurally identical but
> conceptually different.  One example is lengths measured in different
> units, another is values measured in identical units that shouldn't be
> mixed unintentionally (e.g. widths and heights).  It would be really
> nice to be able to use a coding style like this (contrived) example
> that you could imagine coming from a graphics library:
> 
> (* Library code: *)
> type relative_pos = Rpos of int * int
> type absolute_pos = Apos of int * int

[...]

> This is all legal right now, but the problem is performance since the
> tuples get boxed unnecessarily.  But non-polymorphic single-case union
> types can always be optimized away.

Unlucky!
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.
Indeed, this would be nice to have the overhead compiled away.
I don't remember whether there was a concrete reason not to.
At least one reason could be that if you add a new constructor later, you
will not be able to read dumped values of the previous type anymore,
but this doesn't seem a very strong reason.
Note that Haskell has a special notation for this case, using "newtype"
rather than "type" or "data", which marks explicit this as a special
case.

Jacques Garrigue

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

Re: [Caml-list] Single-case union types as strong typedefs

[David Brown]

On Sat, Oct 23, 2004 at 12:31:39PM +0900, Jacques Garrigue wrote:

> The problem you describe only occurs when your single constructor has
> only one argument.
> Indeed, this would be nice to have the overhead compiled away.
> I don't remember whether there was a concrete reason not to.

Another reason is that is breaks compatibility with existing C bindings, or
at least potentially does.

Dave

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

Re: [Caml-list] Single-case union types as strong typedefs

[skaller]

On Sat, 2004-10-23 at 13:39, David Brown wrote:
> On Sat, Oct 23, 2004 at 12:31:39PM +0900, Jacques Garrigue wrote:
> 
> > The problem you describe only occurs when your single constructor has
> > only one argument.
> > Indeed, this would be nice to have the overhead compiled away.
> > I don't remember whether there was a concrete reason not to.
> 
> Another reason is that is breaks compatibility with existing C bindings, or
> at least potentially does.

That problem would go away with the 'newtype' Jaques mentioned.

I'm curious about newtype, since it could do more,
and would have to I think, to be worthwhile ..

This:
	newtype metres = float
meaning
	type metres = Metres float

means you have to define all the operations on 'metres' all 
over again:

	let (++) (Metres x) (Metres y) = Metres (x .+ y)

I'd guess in Haskell newtype can benefit from typeclasses?

How about using functors in Ocaml somehow .. make 'metres' just
an abstract type via a functor Make.length representing the 
typeclass of lengths?

Actually for quantities, you'd use some phantom types
so you could represent products of the dimensions,
such as square metres too .. so the simplistic 
constructor representation isn't very good.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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

Re: [Caml-list] Single-case union types as strong typedefs

[Nathaniel Gray]

On Sat, 23 Oct 2004 12:31:39 +0900 (JST), Jacques Garrigue
<garrigue@kurims.kyoto-u.ac.jp> wrote:

> Unlucky!
> 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?

> Indeed, this would be nice to have the overhead compiled away.
> I don't remember whether there was a concrete reason not to.
> At least one reason could be that if you add a new constructor later, you
> will not be able to read dumped values of the previous type anymore,
> but this doesn't seem a very strong reason.

I would say not -- the whole point of using such a type would be that
it only has one constructor so adding another would not be likely.

> Note that Haskell has a special notation for this case, using "newtype"
> rather than "type" or "data", which marks explicit this as a special
> case.

That's a perfectly fine approach, but I prefer the single-constructor
union approach because there are no new concepts, just optimizations.

Cheers,
-n8

-- 
>>>-- Nathaniel Gray -- Caltech Computer Science ------>
>>>-- Mojave Project -- http://mojave.cs.caltech.edu -->

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

Re: [Caml-list] Single-case union types as strong typedefs

[Nathaniel Gray]

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:
> 
> > Unlucky!
> > 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?

Never mind.  After thinking about it for a minute I understand -- it's
not an optimization, it's just the normal physical representation. 
That's what I get for changing my example at the last minute --
originally it was inches vs. centimeters.  :-)

Cheers,
-n8

-- 
>>>-- Nathaniel Gray -- Caltech Computer Science ------>
>>>-- Mojave Project -- http://mojave.cs.caltech.edu -->

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

Re: [Caml-list] Single-case union types as strong typedefs

[Nathaniel Gray]

On 23 Oct 2004 15:00:02 +1000, skaller <skaller@users.sourceforge.net> wrote:
> This:
>        newtype metres = float
> meaning
>        type metres = Metres float
> 
> means you have to define all the operations on 'metres' all
> over again:
> 
>        let (++) (Metres x) (Metres y) = Metres (x .+ y)
> 
> I'd guess in Haskell newtype can benefit from typeclasses?

I would have to try writing some code to be sure it makes sense, but I
envisioned this as more of a contract mechanism.  It would be a way of
making "semi-opaque" values without encapsulation guarantees but also
without performance penalties.  A function that needed to do any
serious work with the underlying values would destruct the wrappers:
  let hypoteneuse (Metres x) (Metres y): metres = sqrt(x*x + y*y)

> Actually for quantities, you'd use some phantom types
> so you could represent products of the dimensions,
> such as square metres too .. so the simplistic
> constructor representation isn't very good.

I'll have to read a bit about phantom types.  Maybe they fit the bill.

Cheers,
-n8

-- 
>>>-- Nathaniel Gray -- Caltech Computer Science ------>
>>>-- Mojave Project -- http://mojave.cs.caltech.edu -->

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

Re: [Caml-list] Single-case union types as strong typedefs

[John Prevost]

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

Re: [Caml-list] Single-case union types as strong typedefs

[skaller]

On Sun, 2004-10-24 at 07:24, Nathaniel Gray wrote:
> On Sat, 23 Oct 2004 12:31:39 +0900 (JST), Jacques Garrigue
> <garrigue@kurims.kyoto-u.ac.jp> wrote:
> 
> > Unlucky!
> > 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?

For two arguments, it's a pointer to a pair on the heap.
For one, its a pointer to a one element tuple on the heap.
This case might be optimised by replacing the pointer
with the value stored in that single field, but it isn't.

That's what Jacques meant -- there's no issue of optimising
the composite case, so there is 'no problem' then,
the problem 'only occurs when .. has only one argument'
because that's the only time you might get rid of the
extra level of indirection. 

Note this would only be possible for the single constructor 
with one argument, because the tag field (for the variant case) 
stored on the  heap is lost too, but it isn't needed 
for the single constructor case. It isn't needed for
the composite argument case either .. but a heap
block is needed for the tuple, so the tag field is there anyhow.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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

Re: [Caml-list] Single-case union types as strong typedefs

[Nathaniel Gray]

On 24 Oct 2004 15:18:47 +1000, skaller <skaller@users.sourceforge.net> wrote:
> On Sun, 2004-10-24 at 07:24, Nathaniel Gray wrote:
> > On Sat, 23 Oct 2004 12:31:39 +0900 (JST), Jacques Garrigue
> > <garrigue@kurims.kyoto-u.ac.jp> wrote:
> >
> > > Unlucky!
> > > 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?
> 
> For two arguments, it's a pointer to a pair on the heap.
> For one, its a pointer to a one element tuple on the heap.
> This case might be optimised by replacing the pointer
> with the value stored in that single field, but it isn't.

Right.  As I said in my reply to myself, after thinking for a minute I
figured it out.

-- 
>>>-- Nathaniel Gray -- Caltech Computer Science ------>
>>>-- Mojave Project -- http://mojave.cs.caltech.edu -->

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

Re: [Caml-list] Single-case union types as strong typedefs

[Damien Doligez]

On Oct 23, 2004, at 03:49, Nathaniel Gray wrote:

>   type x = Foo y
>      --> type x = y  (* Only necessary if types are retained after
> type checking *)
>   Foo x
>      --> x
>   match x with Foo y -> expr
>      --> let y = x in expr

Once again, consider this:

   type foo = Constr of foo;;
   let rec x = Constr x;;

If you eliminate the constructor, there's nothing left!

-- Damien

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

RE: [Caml-list] Single-case union types as strong typedefs

[Jacques Carette]

> Once again, consider this:
> 
>    type foo = Constr of foo;;
>    let rec x = Constr x;;
> 
> If you eliminate the constructor, there's nothing left!
> 
> -- Damien

Isn't that correct though?  The value x is completely known statically, and
all computation on x can be done statically, so it is not necessary to have
any traces of x left at run-time.

Yes, I am assuming that a fair bit of partial evaluation is a good thing for
the compiler to do.

Jacques

Re: [Caml-list] Single-case union types as strong typedefs

[Damien Doligez]

On Oct 25, 2004, at 16:25, Jacques Carette wrote:

> Isn't that correct though?  The value x is completely known 
> statically, and
> all computation on x can be done statically, so it is not necessary to 
> have
> any traces of x left at run-time.

Then how do you pass it to a polymorphic function?

> Yes, I am assuming that a fair bit of partial evaluation is a good 
> thing for
> the compiler to do.

Unfortunately, the compiler doesn't have all the information about the
program.  A lot of things are not known until link-time.

-- Damien

Re: [Caml-list] Single-case union types as strong typedefs

[Jacques Carette]

Good points, which I will comment on in opposite order:

Damien Doligez <damien.doligez@inria.fr> wrote:
> On Oct 25, 2004, at 16:25, Jacques Carette wrote:
> > Yes, I am assuming that a fair bit of partial evaluation is a good 
> > thing for
> > the compiler to do.
> 
> Unfortunately, the compiler doesn't have all the information about the
> program.  A lot of things are not known until link-time.

I consider a linker to be an integral part of a compiler 'suite'.  I could not care less when a particular code 
optimization is done.  If it *has* to be done by the linker, then so be it.  I do not understand why link-time 
optimizations seem to have been somehow less research-worthy than other parts of the compiler.

> > Isn't that correct though?  The value x is completely known 
> > statically, and
> > all computation on x can be done statically, so it is not necessary to 
> > have any traces of x left at run-time.
> 
> Then how do you pass it to a polymorphic function?

And then what?  What could that polymorphic function do with that value (without using Obj)?

In a system which insists on separate compilation, there is indeed a problem, and this ideal cannot be achieved.  I 
should have been clearer about the fact that I knew this.

Personally, I do not use separate compilation at "production" time anymore, only at development/debugging time.  When 
it comes time to produce a final executable, I use a colleague's script to make one (large) .ml file containing the 
complete program.  I'd love to have a compiler switch to tell the compiler I am producing an executable in one pass 
versus creating a reusable library.  The intentional differences between those two activities are huge, and apparently 
still under-recognized (and thus under-used).  This is surprising.

Side note: Ocaml (and Haskell) are the two languages I actively choose to code in, and get my students to code in, 
after having coded in a whole bunch of languages (professionally and otherwise).  When I need efficiency or 
non-trivial I/O, I chose Ocaml, if I only need elegance and brevity, I choose Haskell.  I still hack in Maple because 
I can prototype things there faster than in most other languages (for my own work).  But I am keeping up with Focal 
(ex-FOC) and Epigram, as they both seem to be going where I'd like my programming languages to be.  Of course, I would 
rather use fewer languages!  So I see it as worth my while to see Ocaml evolve.

Jacques

Re: [Caml-list] Single-case union types as strong typedefs

[skaller]

On Wed, 2004-10-27 at 01:05, Jacques Carette wrote:

> I consider a linker to be an integral part of a compiler 'suite'. 
>  I could not care less when a particular code 
> optimization is done.  If it *has* to be done by the linker, then so be it.  
> I do not understand why link-time 
> optimizations seem to have been somehow less research-worthy 
> than other parts of the compiler.

Why do we need separate compilation 
and linkage in the style of C on modern systems?

Surely, we would like to have fast compilations, but 
why can't the compiler treat that as an automatic
optimisation, rather than a user managed one?

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Caml-list] Combined compilation and linking

[Jon Harrop]

On Tuesday 26 October 2004 18:34, skaller wrote:
> Why do we need separate compilation
> and linkage in the style of C on modern systems?

In other languages you might want to do separate compilation in order to 
distribute object files instead of source. Seeing as this doesn't really work 
in OCaml, I can't see that another approach couldn't be equally productive.

> Surely, we would like to have fast compilations, but
> why can't the compiler treat that as an automatic
> optimisation, rather than a user managed one?

As a start, this could be performed by a combined compiler-linker which could, 
for example, cache compilations by file name (module name) and the hash and 
contents of the file for the "n" most recently compiled files. Then you just 
feed this program all your source files.

More advanced versions could split source files up and compile each part 
separately, combining the result.

A preliminary test of the potential productivity of this would be to measure 
the time taken to load vs the time taken to compile some example source 
files.

Cheers,
Jon.