August 01, 2014 Re: Algebraic Data Types in D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | On 7/31/14, 5:35 PM, Timon Gehr wrote: > On 07/31/2014 06:23 PM, Andrei Alexandrescu wrote: >> On 7/31/14, 6:03 AM, w0rp wrote: >>> On Thursday, 31 July 2014 at 11:42:21 UTC, Remo wrote: >>>> http://tech.esper.com/2014/07/30/algebraic-data-types/ >>>> >>>> D already has product type it is struct. >>>> But D lacks sum type also called tagged-union. >>>> >>>> Do you think it would be possible to add something like this to D2 ? >>> >>> There is a library solution for this in the standard library. >>> >>> http://dlang.org/phobos/std_variant.html#.Algebraic >>> >>> It doesn't handle recursive types at the moment, like alias Foo = >>> Algebraic!(Foo[]). Apart from that, it should be what you are looking >>> for. >> >> alias Foo = Algebraic!(This[]); >> >> Andrei > > alias Foo = Algebraic!(int,Algebraic!(Foo[],double)[]); Good point! That's why I'd submitted this at some point: https://issues.dlang.org/show_bug.cgi?id=9608 It should be possible to achieve alpha replacement of This with the needed type at any level inside a composite type. > There is also this kind of approach: > > mixin ADT!q{ > List(T): > | Nil > | Cons T List!T > }; Interesting! Is there code available for that? > Of course, product types ("tuples") and sum types ("tagged unions") and > recursive types are elementary enough to be proper language features in > one way or another with all the syntactic convenience that yields for > pattern matching. Well one other way to look at it is that striving to do things in a library pushes introspection forward. I do agree tagged unions should be pushed into the language; they'd help the GC. Andrei |
August 01, 2014 Re: Algebraic Data Types in D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | Andrei Alexandrescu:
> I do agree tagged unions should be pushed into the language; they'd help the GC.
A more general solution is to add a onGC() optional method that gets called by the GC on collections, and tells it what's inside the union.
Bye,
bearophile
|
August 01, 2014 Re: Algebraic Data Types in D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On 08/01/2014 03:26 AM, Andrei Alexandrescu wrote: > On 7/31/14, 5:35 PM, Timon Gehr wrote: >> On 07/31/2014 06:23 PM, Andrei Alexandrescu wrote: >>> On 7/31/14, 6:03 AM, w0rp wrote: >>>> On Thursday, 31 July 2014 at 11:42:21 UTC, Remo wrote: >>>>> http://tech.esper.com/2014/07/30/algebraic-data-types/ >>>>> >>>>> D already has product type it is struct. >>>>> But D lacks sum type also called tagged-union. >>>>> >>>>> Do you think it would be possible to add something like this to D2 ? >>>> >>>> There is a library solution for this in the standard library. >>>> >>>> http://dlang.org/phobos/std_variant.html#.Algebraic >>>> >>>> It doesn't handle recursive types at the moment, like alias Foo = >>>> Algebraic!(Foo[]). Apart from that, it should be what you are looking >>>> for. >>> >>> alias Foo = Algebraic!(This[]); >>> >>> Andrei >> >> alias Foo = Algebraic!(int,Algebraic!(Foo[],double)[]); > > Good point! That's why I'd submitted this at some point: > https://issues.dlang.org/show_bug.cgi?id=9608 > > It should be possible to achieve alpha replacement of This with the > needed type at any level inside a composite type. > ... It might also be possible that this is what is actually wanted: alias Foo = Algebraic!(int,Algebraic!(This[],double)[]); (I.e. This refers to the inner type.) There is always this issue as well: alias ListInt=Algebraic!(Tuple!(),Tuple!(int,ListInt*)); How would you use the proposed enhancement to fix this? (BTW: Algebraic implements a plain sum type, so I again think the name is a little strange :o).) >> There is also this kind of approach: >> >> mixin ADT!q{ >> List(T): >> | Nil >> | Cons T List!T >> }; > > Interesting! Is there code available for that? > ... You can find an incomplete proof-of-concept implementation here: http://dpaste.dzfl.pl/77abae58a087 (The 'match' is not particularly great, opEquals is missing, etc.) It was quite hard to get past the compiler. >> Of course, product types ("tuples") and sum types ("tagged unions") and >> recursive types are elementary enough to be proper language features in >> one way or another with all the syntactic convenience that yields for >> pattern matching. > > Well one other way to look at it is that striving to do things in a > library pushes introspection forward. > ... Based on past experiences, I think we'd see some opposition if the language was to be extended in a way to allow those kinds of features to be implemented completely in the library such that they behave and look optimally. In any case, having a template Fix operator would sometimes be convenient: struct Foo1(T){ T* self; } alias Foo=Fix!Foo1; /+ instantiates to something like: struct Foo{ Foo* self; } +/ :o) the most natural implementation of Fix does not work for obvious reasons: alias Fix(alias F)=F!(Fix!F); Making this work is not completely out of reach though, I think. The best I can currently do to "save" 'Algebraic' is the following: http://dpaste.dzfl.pl/65afd3a7ce52 > I do agree tagged unions should be pushed into the language; they'd help > the GC. > ... The GC as well as the language semantics. E.g. how to lazily initialize a struct field of a type that has no .init value, such as a nested struct outside of its context, or something with @disable this()? (Many structs are nested because of local template instantiation.) Furthermore, they are really convenient if done right. > > Andrei > |
August 01, 2014 Re: Algebraic Data Types in D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | On 8/1/14, 7:18 AM, Timon Gehr wrote: > It might also be possible that this is what is actually wanted: > > alias Foo = Algebraic!(int,Algebraic!(This[],double)[]); > > (I.e. This refers to the inner type.) > > There is always this issue as well: > alias ListInt=Algebraic!(Tuple!(),Tuple!(int,ListInt*)); > > > How would you use the proposed enhancement to fix this? I don't think there's an easy way. > (BTW: Algebraic implements a plain sum type, so I again think the name > is a little strange :o).) Yah, there'd probably be a more precise name for it. >>> There is also this kind of approach: >>> >>> mixin ADT!q{ >>> List(T): >>> | Nil >>> | Cons T List!T >>> }; >> >> Interesting! Is there code available for that? >> ... > > You can find an incomplete proof-of-concept implementation here: > http://dpaste.dzfl.pl/77abae58a087 > (The 'match' is not particularly great, opEquals is missing, etc.) > It was quite hard to get past the compiler. On a cursory inspection, looks good! The question there is whether you or anyone would be interested in taking that to a proposal. >> Well one other way to look at it is that striving to do things in a >> library pushes introspection forward. >> ... > > Based on past experiences, I think we'd see some opposition if the > language was to be extended in a way to allow those kinds of features to > be implemented completely in the library such that they behave and look > optimally. > > In any case, having a template Fix operator would sometimes be convenient: > > struct Foo1(T){ > T* self; > } > > alias Foo=Fix!Foo1; > > /+ > instantiates to something like: > > struct Foo{ > Foo* self; > } > +/ > > :o) > > the most natural implementation of Fix does not work for obvious reasons: > > alias Fix(alias F)=F!(Fix!F); > > Making this work is not completely out of reach though, I think. > > The best I can currently do to "save" 'Algebraic' is the following: > http://dpaste.dzfl.pl/65afd3a7ce52 That's interesting. Fix is worth making to work either as a built-in on a library artifact. Andrei |
August 01, 2014 Re: Algebraic Data Types in D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On 08/01/2014 05:28 PM, Andrei Alexandrescu wrote: > On 8/1/14, 7:18 AM, Timon Gehr wrote: >> It might also be possible that this is what is actually wanted: >> >> alias Foo = Algebraic!(int,Algebraic!(This[],double)[]); >> >> (I.e. This refers to the inner type.) >> >> There is always this issue as well: >> alias ListInt=Algebraic!(Tuple!(),Tuple!(int,ListInt*)); >> >> >> How would you use the proposed enhancement to fix this? > > I don't think there's an easy way. > ... It's hard to fix without Fix! :o) > >>>> There is also this kind of approach: >>>> >>>> mixin ADT!q{ >>>> List(T): >>>> | Nil >>>> | Cons T List!T >>>> }; >>> >>> Interesting! Is there code available for that? >>> ... >> >> You can find an incomplete proof-of-concept implementation here: >> http://dpaste.dzfl.pl/77abae58a087 >> (The 'match' is not particularly great, opEquals is missing, etc.) >> It was quite hard to get past the compiler. > > On a cursory inspection, looks good! The question there is whether you Actually yes, but I currently have a backlog of work to do, partly due to having been involved in a strange debate about the meaning of words. > or anyone would be interested in taking that to a proposal. > ... I wouldn't be opposed to that option. Any volunteers willing to take up the effort? >>> Well one other way to look at it is that striving to do things in a >>> library pushes introspection forward. >>> ... >> ... >> >> In any case, having a template Fix operator would sometimes be >> convenient: >> ... >> >> the most natural implementation of Fix does not work for obvious reasons: >> >> alias Fix(alias F)=F!(Fix!F); >> >> Making this work is not completely out of reach though, I think. >> >> The best I can currently do to "save" 'Algebraic' is the following: >> http://dpaste.dzfl.pl/65afd3a7ce52 > > That's interesting. Fix is worth making to work either as a built-in on > a library artifact. > ... Agreed. The fact that the above 'iso-recursive' approach works now may serve as an implication that most relevant assumptions that templates may make about their parameters that are broken by a fix operator weren't valid before either. I have a very strong suspicion that Fix cannot be implemented without modifying the language a little bit, but I'd be happy to be proven wrong. > > Andrei |
Copyright © 1999-2021 by the D Language Foundation