Re: Algebraic Data Types in D?
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
Re: Algebraic Data Types in D?
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
Re: Algebraic Data Types in D?
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
Re: Algebraic Data Types in D?
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
Re: Algebraic Data Types in D?
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.
Re: Algebraic Data Types in D?
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 ? I think you're looking for std.variant? http://dlang.org/phobos/std_variant.html (My understanding is it's undergoing some heavy work, so do be aware of that.) -Wyatt
Re: Algebraic Data Types in D?
Am 31.07.2014 13:42, schrieb Remo: 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 ? I'm currently in the process of polishing one up to improve vibe.d's Json/Bson type implementations. It's definitely possible to do (I've been using one for years), but has its caveats when there are dependency cycles in the code. Just to make clear what the difference is: - Variant: open set of types, using TypeInfo for identification - Algebraic: closed set of types, using TypeInfo for identification - Tagged union: closed set of types with a numeric ID for each type The latter has a few advantages in some situations - Doesn't require type info - Can use switch instead of iterating over all possible types or storing a pointer to helper functions for dealing with the type - Allows to use final switch to guarantee handling all cases - Provides a handy type value that can be used and stored in user code (vs. passing and storing TypeInfo instances) - Could be made to store the same type with different IDs
Re: Algebraic Data Types in D?
On Thu, 31 Jul 2014 11:42:20 +, 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 ?
In addition to the suggestions of Algebraic or Variant elsewhere in this
thread, it's trivial to implement your own concrete tagged unions:
struct MyTaggedUnion
{
enum Type { Int, Float, String }
Type tag;
union {
int int_;
float float_;
string string_;
}
}
You can also hide the union members with private and only allow access
via property getters that check the tag.
Re: Algebraic Data Types in D?
Justin Whear:
In addition to the suggestions of Algebraic or Variant
elsewhere in this
thread, it's trivial to implement your own concrete tagged
unions:
struct MyTaggedUnion
{
enum Type { Int, Float, String }
Type tag;
union {
int int_;
float float_;
string string_;
}
}
You can also hide the union members with private and only allow
access
via property getters that check the tag.
See for a bare-bones built-in pattern matching, with an optional
opMatch struct method that gets called by the improved switch:
https://d.puremagic.com/issues/show_bug.cgi?id=596
Bye,
bearophile
Re: Algebraic Data Types in D?
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
Re: Algebraic Data Types in D?
On Thursday, 31 July 2014 at 15:03:09 UTC, Justin Whear wrote:
On Thu, 31 Jul 2014 11:42:20 +, 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 ?
In addition to the suggestions of Algebraic or Variant
elsewhere in this
thread, it's trivial to implement your own concrete tagged
unions:
struct MyTaggedUnion
{
enum Type { Int, Float, String }
Type tag;
union {
int int_;
float float_;
string string_;
}
}
You can also hide the union members with private and only allow
access
via property getters that check the tag.
Thanks for all the answers !
it's trivial to implement your own concrete tagged unions
Yes this is also possible to do in C++ too.
But I do not think that this is trivial at least not for 10 or 20
values.
Enum and Union need always to be in sync and compiler will not
output error if the programmer/user will make any mistake.
How to translate this useless Rust code to D, with as least D
code as possible ?
How be sure that everything will still work as expected if
programmer will add White color ?
enum Color {
Red,
Green,
Blue,
Rgb(int,int,int)
}
fn main() {
let r = Rgb(64,128,255);
match r {
Red = println!(Red),
Green = println!(Green),
Blue = println!(Blue),
Rgb(r,g,b) = println!(Rgb({},{},{}),r,g,b),
}
}
Re: Algebraic Data Types in D?
On Thursday, 31 July 2014 at 20:28:55 UTC, Remo wrote:
How to translate this useless Rust code to D, with as least D
code as possible ?
How be sure that everything will still work as expected if
programmer will add White color ?
enum Color {
Red,
Green,
Blue,
Rgb(int,int,int)
}
fn main() {
let r = Rgb(64,128,255);
match r {
Red = println!(Red),
Green = println!(Green),
Blue = println!(Blue),
Rgb(r,g,b) = println!(Rgb({},{},{}),r,g,b),
}
}
import std.stdio;
import std.variant;
struct Red {}
struct Green{}
struct Blue {}
struct RGB
{
int r;
int g;
int b;
}
alias Color = Algebraic!(Red, Green, Blue, RGB);
void main()
{
auto r = Color(RGB(64, 128, 255));
r.visit!(
(Red r) = writeln(Red),
(Green g) = writeln(Green),
(Blue b) = writeln(Blue),
(RGB rgb) = writefln(RGB(%s, %s, %s), rgb.r, rgb.g, rgb.b),
);
}
D's Algebraic needs some work, but it's okay for basic usage. The
most annoying thing is that you can't instantiate an RGB and
expect the compiler to magically know that it's a subtype of
Color. Maybe there's a way to work around that, but I can't think
of one right off.
Re: Algebraic Data Types in D?
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)[]);
There is also this kind of approach:
mixin ADT!q{
List(T):
| Nil
| Cons T List!T
};
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.
Re: Algebraic Data Types in D?
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
