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

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

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
>

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

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