Re: [Caml-list] Subtyping structurally-equivalent records, or something like it?

Re: [Caml-list] Subtyping structurally-equivalent records, or something like it?

[Dario Teixeira]

Hi,

>  type kinematic = { lin: Vec.t; ang: Vec.t }
>
> Which I've been using to represent a medley of physical attributes (force, > momentum, velocity, etc.).

I second Stéphane's suggestion of using phantom types; moreover,
I recommend you read an article that discusses them to some detail
and covers their use for precisely this sort of problem:
http://camltastic.blogspot.com/2008/05/phantom-types.html

Cheers,
Dario Teixeira

Re: Subtyping structurally-equivalent records, or something like it?

[Sylvain Le Gall]

On 01-05-2010, Dario Teixeira <darioteixeira@yahoo.com> wrote:
> Hi,
>
>>  type kinematic = { lin: Vec.t; ang: Vec.t }
>>
>> Which I've been using to represent a medley of physical attributes (force, > momentum, velocity, etc.).
>
> I second Stéphane's suggestion of using phantom types; moreover,
> I recommend you read an article that discusses them to some detail
> and covers their use for precisely this sort of problem:
> http://camltastic.blogspot.com/2008/05/phantom-types.html
>

I really like the use of private type abbreviation for phantom type:
http://ocaml.janestreet.com/?q=node/77

Regards,
Sylvain Le Gall

Re: [Caml-list] Re: Subtyping structurally-equivalent records, or something like it?

[AUGER Cédric]

I am not expert in Ocaml, is the following the same in terms
of performances as the phantom types?

type kinematic = ...

type force = Force of kinematic
type momentum = Moment of kinematic
...

That is does the constructor introduce an overhead or not?
As there is only one constructor, no overhead should be done in an
optimized compiler.

So general functions should use a kinematic -> [Type]
and a specialized function, force -> [Type] and so on...

I understand this version is not as handy as the phantom types, as we
need to use "match ... with Force f -> ..." or at least "let Force f
= ... in ...", but my question is only in terms of efficiency;
obviously phantom types are more or equally efficient than what I
exposed, but does the reciproque also holds?

Re: Subtyping structurally-equivalent records, or something like it?

[Sylvain Le Gall]

On 04-05-2010, AUGER Cédric <Cedric.Auger@lri.fr> wrote:
> I am not expert in Ocaml, is the following the same in terms
> of performances as the phantom types?
>
> type kinematic = ...
>
> type force = Force of kinematic
> type momentum = Moment of kinematic
> ...
>
> That is does the constructor introduce an overhead or not?
> As there is only one constructor, no overhead should be done in an
> optimized compiler.
>

The variants are represented using a block. If you introduce a single
variant, it will create a block that points to kinematic. E.g. "Force of
kinematic" will create a pointer to the kinematic structure. 

Your construction of force and momentum will add a level of indirection
for every use of the kinematic structure.

Phantom type doesn't add a level of indirection and left no trace in the
generated assembler. 

This is not about optimized compiler in this case but about data
representation. Even if you use an optimized compiler (which is not
really the case with ocamlopt), you won't change datastructure
representation to optimize.

Regards,
Sylvain Le Gall

Re: [Caml-list] Re: Subtyping structurally-equivalent records, or something like it?

[rossberg]

"Sylvain Le Gall" <sylvain@le-gall.net>:
>
> This is not about optimized compiler in this case but about data
> representation. Even if you use an optimized compiler (which is not
> really the case with ocamlopt), you won't change datastructure
> representation to optimize.

What do you mean? There is no reason in general why a compiler cannot
optimize data representations, and some do in cases like this.

/Andreas

Re: Subtyping structurally-equivalent records, or something like it?

[Sylvain Le Gall]

On 04-05-2010, rossberg@mpi-sws.org <rossberg@mpi-sws.org> wrote:
> "Sylvain Le Gall" <sylvain@le-gall.net>:
>>
>> This is not about optimized compiler in this case but about data
>> representation. Even if you use an optimized compiler (which is not
>> really the case with ocamlopt), you won't change datastructure
>> representation to optimize.
>
> What do you mean? There is no reason in general why a compiler cannot
> optimize data representations, and some do in cases like this.
>

Anyway, if it comes to data alignement and things like that, the
compiler should optimize data representations. But in this case, I
really don't think we are talking about data alignement.

Regards,
Sylvain Le Gall

Re: [Caml-list] Re: Subtyping structurally-equivalent records, or something like it?

[Fabrice Le Fessant]

"ocamlopt" does optimize data representation: for example, it can unbox
floats into registers, or into arrays of floats. However, there is a
tradeoff between such optimizations and efficiency: when you do too much
representation optimisation, you might end up performing a lot of tests
because a given type can be represented in multiple formats, and
performing a lot of transformations between the representations,
especially as the FFI (Ocaml interface to C) specifies the
representation of data.

Of course, I am not saying it is not possible to do better: it requires
a lot of energy, the compiler code becomes more complex, and the
improvement on speed is not clear.

--Fabrice


Sylvain Le Gall wrote, On 05/04/2010 03:42 PM:
> On 04-05-2010, rossberg@mpi-sws.org <rossberg@mpi-sws.org> wrote:
>> "Sylvain Le Gall" <sylvain@le-gall.net>:
>>> This is not about optimized compiler in this case but about data
>>> representation. Even if you use an optimized compiler (which is not
>>> really the case with ocamlopt), you won't change datastructure
>>> representation to optimize.
>> What do you mean? There is no reason in general why a compiler cannot
>> optimize data representations, and some do in cases like this.
>>
> 
> Anyway, if it comes to data alignement and things like that, the
> compiler should optimize data representations. But in this case, I
> really don't think we are talking about data alignement.
> 
> Regards,
> Sylvain Le Gall
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 

-- 
Fabrice LE FESSANT
Chercheur, Equipe ASAP
(As Scalable As Possible)
http://www.lefessant.net/

INRIA-Futurs, Bat P - 112
Parc Orsay Université
2-4, rue Jacques Monod
F-91893 Orsay Cedex, FRANCE

Re: [Caml-list] Re: Subtyping structurally-equivalent records, or something like it?

[Goswin von Brederlow]

rossberg@mpi-sws.org writes:

> "Sylvain Le Gall" <sylvain@le-gall.net>:
>>
>> This is not about optimized compiler in this case but about data
>> representation. Even if you use an optimized compiler (which is not
>> really the case with ocamlopt), you won't change datastructure
>> representation to optimize.
>
> What do you mean? There is no reason in general why a compiler cannot
> optimize data representations, and some do in cases like this.

How could it? At least for any type that is public in a module.

The data representation is part of the ABI. As such it is fixed and can
in no way be optimized by the compiler. Only thing you can do is change
the ABI and define a more optimized representation in the first place.

As example

type foo = { x : int; y : int; }
type bar = Bar of foo

Currently a bar is represented as

foo {
  tag = 0
  size = 2
  field[0] = int(x)
  field[1] = int(y)
}
bar {
  tag = 0 (for Bar)
  size = 1
  field[0] = &foo
}

2 Blocks taking up 5 words.


A better representation would be to combine the two:

bar {
  tag = 0 (for Bar)
  size = 2
  field[0] = int(x) 
  field[1] = int(y) 
}    

A single block of 3 words.

This also works for

type bar = Foo of foo | Blub of foo | Blubber of foo

but not for

type baz = Baz of bar


There are lots of cases where the representation could be improved for
special cases. But ocaml I think only does that for float arrays or
records that only contain floats. But that is a design decision and not
something the compiler can just optimize.

MfG
        Goswin

Re: [Caml-list] Re: Subtyping structurally-equivalent records, or something like it?

[rossberg]

"Goswin von Brederlow" <goswin-v-b@web.de>:
>
>>> This is not about optimized compiler in this case but about data
>>> representation. Even if you use an optimized compiler (which is not
>>> really the case with ocamlopt), you won't change datastructure
>>> representation to optimize.
>>
>> What do you mean? There is no reason in general why a compiler cannot
>> optimize data representations, and some do in cases like this.
>
> How could it? At least for any type that is public in a module.
>
> The data representation is part of the ABI. As such it is fixed and can
> in no way be optimized by the compiler. Only thing you can do is change
> the ABI and define a more optimized representation in the first place.

Yes, and I didn't say that OCaml easily could, given external constraints
like the one you mention. I only was objecting to the statement that this is
not an optimization.

> A better representation would be to combine the two:
>
> bar {
>   tag = 0 (for Bar)
>   size = 2
>   field[0] = int(x)
>   field[1] = int(y)
> }

That is called flattening or unboxing, and in degenerate use cases it can
actually be costly because you have to copy the record if you extract it
first-class. However, for the original case there would be a much simpler
optimization: if a data type has only one constructor (more precisely, one
except for nullary ones), you don't need to represent its tag at all, so the
whole indirection is unnecessary.

/Andreas

Re: [Caml-list] Re: Subtyping structurally-equivalent records, or something like it?

[Goswin von Brederlow]

rossberg@mpi-sws.org writes:

> "Goswin von Brederlow" <goswin-v-b@web.de>:
>>
>>>> This is not about optimized compiler in this case but about data
>>>> representation. Even if you use an optimized compiler (which is not
>>>> really the case with ocamlopt), you won't change datastructure
>>>> representation to optimize.
>>>
>>> What do you mean? There is no reason in general why a compiler cannot
>>> optimize data representations, and some do in cases like this.
>>
>> How could it? At least for any type that is public in a module.
>>
>> The data representation is part of the ABI. As such it is fixed and can
>> in no way be optimized by the compiler. Only thing you can do is change
>> the ABI and define a more optimized representation in the first place.
>
> Yes, and I didn't say that OCaml easily could, given external constraints
> like the one you mention. I only was objecting to the statement that this is
> not an optimization.
>
>> A better representation would be to combine the two:
>>
>> bar {
>>   tag = 0 (for Bar)
>>   size = 2
>>   field[0] = int(x)
>>   field[1] = int(y)
>> }
>
> That is called flattening or unboxing, and in degenerate use cases it can
> actually be costly because you have to copy the record if you extract it
> first-class. However, for the original case there would be a much simpler
> optimization: if a data type has only one constructor (more precisely, one
> except for nullary ones), you don't need to represent its tag at all, so the
> whole indirection is unnecessary.
>
> /Andreas

Actualy in this case you don't. In foo the "tag" part of the block is
unused and in bar it is the constructor id. (foo) and (Bar foo) just
happen to have the same representation. Extracting a foo from a bar
means you just ignore the tag part, which is already ignored anyway.

The case of only having one constructor can be seen as special case for
this in the case of records. But type gnarf = Gnarf of int could be
represented as plain int as you say. The idea is the same.


The reason ocaml does not do this is that defining lots of exception for
the representation of data makes the compiler much more complicated and
ocamls compiler aims at being simple. At least that's what has been said
in the past.

MfG
        Goswin

Re: [Caml-list] Re: Subtyping structurally-equivalent records, or something like it?

[Edgar Friendly]

On 05/04/2010 07:53 AM, Sylvain Le Gall wrote:
> On 04-05-2010, AUGER Cédric<Cedric.Auger@lri.fr>  wrote:
>> type momentum = Moment of kinematic
>>
>> That is does the constructor introduce an overhead or not?
>> As there is only one constructor, no overhead should be done in an
>> optimized compiler.
>>
> This is not about optimized compiler in this case but about data
> representation. Even if you use an optimized compiler (which is not
> really the case with ocamlopt), you won't change datastructure
> representation to optimize.
>
The OCaml compiler *could* special-case this kind of constructor, but as 
there's the syntax:

type momentum = kinematic

Which produces the non-boxed kinematic values, the authors probably 
decided to follow the maxim "Do what the programmer says" for singleton 
variant types.  The question becomes whether phantom types solve this 
problem sufficiently or do we need another type-level construct - 
explicit subtyping relationships.  Forever ago I suggested this to 
achieve a similar goal, and was given yet another solution:

module M : sig
	type momentum
	val of_kin : kinematic -> momentum
	val to_kin : momentum -> kinematic
end = struct
	type momentum = kinematic
	let of_kin x = x
	let to_kin x = x
end

Yes, it's a lot of boilerplate for each type, but you only have to write 
it once (per type), and cross-module inlining should give zero runtime 
cost.  If not, use "%identity", and expose it in the interface.  This 
method is along the lines of Anthony's proposal #4.

E.

Re: [Caml-list] Re: Subtyping structurally-equivalent records, or something like it?

[Goswin von Brederlow]

Edgar Friendly <thelema314@gmail.com> writes:

> On 05/04/2010 07:53 AM, Sylvain Le Gall wrote:
>> On 04-05-2010, AUGER Cédric<Cedric.Auger@lri.fr>  wrote:
>>> type momentum = Moment of kinematic
>>>
>>> That is does the constructor introduce an overhead or not?
>>> As there is only one constructor, no overhead should be done in an
>>> optimized compiler.
>>>
>> This is not about optimized compiler in this case but about data
>> representation. Even if you use an optimized compiler (which is not
>> really the case with ocamlopt), you won't change datastructure
>> representation to optimize.
>>
> The OCaml compiler *could* special-case this kind of constructor, but
> as there's the syntax:
>
> type momentum = kinematic
>
> Which produces the non-boxed kinematic values, the authors probably
> decided to follow the maxim "Do what the programmer says" for
> singleton variant types.  The question becomes whether phantom types
> solve this problem sufficiently or do we need another type-level
> construct -
> explicit subtyping relationships.  Forever ago I suggested this to
> achieve a similar goal, and was given yet another solution:
>
> module M : sig
> 	type momentum
> 	val of_kin : kinematic -> momentum
> 	val to_kin : momentum -> kinematic
> end = struct
> 	type momentum = kinematic
> 	let of_kin x = x
> 	let to_kin x = x
> end

I think that can be cut down to:

module M = struct
  type momentum = private kinematic
  let of_kin = %identity
  let to_kin = %identity
end

> Yes, it's a lot of boilerplate for each type, but you only have to
> write it once (per type), and cross-module inlining should give zero
> runtime cost.  If not, use "%identity", and expose it in the
> interface.  This method is along the lines of Anthony's proposal #4.
>
> E.

MfG
        Goswin

Re: [Caml-list] Re: Subtyping structurally-equivalent records, or something like it?

[Yaron Minsky]

[-- Attachment #1: Type: text/plain, Size: 1052 bytes --]

On Tue, May 4, 2010 at 9:37 AM, Edgar Friendly <thelema314@gmail.com> wrote:

> module M : sig
>        type momentum
>        val of_kin : kinematic -> momentum
>        val to_kin : momentum -> kinematic
> end = struct
>        type momentum = kinematic
>        let of_kin x = x
>        let to_kin x = x
> end
>
> Yes, it's a lot of boilerplate for each type, but you only have to write it
> once (per type), and cross-module inlining should give zero runtime cost.
>  If not, use "%identity", and expose it in the interface.  This method is
> along the lines of Anthony's proposal #4.


You can do the above solution with essentially no boilerplate:

module M = struct
   type t = kinematic
   val to_kin x = x
   val of_kin x = x
end

module type S = sig
  type t
  val to_kin : t -> kinematic
  val of_kin : kinematic -> t
end

module Momentum : S = M
module Position : S = M
module Force : S = M

and so on.  Just  one line per kinematic-like type you want to create.

That said, I still think the phantom type solution will end up cleaner.

y

[-- Attachment #2: Type: text/html, Size: 1479 bytes --]