## digitalmars.D - Self-referential tuples?

- Andrei Alexandrescu (15/15) Jun 09 2015 Following the use of This in Algebraic
- Brian Rogoff (12/28) Jun 09 2015 Yes, I'm interested. As a practical example, how would you
- Andrei Alexandrescu (16/47) Jun 09 2015 Excellent example! Here's a shot:
- Timon Gehr (3/19) Jun 09 2015 Well, the issue is with this kind of use case:
- Andrei Alexandrescu (3/29) Jun 09 2015 So a list is either nothing, or a head and a tail. What is the problem
- Idan Arye (10/44) Jun 09 2015 The `This*` here is not mapped to
- Timon Gehr (3/40) Jun 09 2015 Exactly. Probably it was confusing that I used a raw pointer and not
- Andrei Alexandrescu (3/10) Jun 09 2015 Way ahead of you :o). Algebraic would use std.variant.This, whereas
- Timon Gehr (4/16) Jun 09 2015 I generally assume that the same identifier in the same scope of the
- Timon Gehr (9/40) Jun 09 2015 It's about which type 'This' refers to. Is it the Algebraic or the
- Timon Gehr (5/46) Jun 09 2015 If I'm not mistaken Algebraic already suffers from this kind of "This
- Brian Rogoff (66/68) Jun 10 2015 Could you explain this a bit more, maybe using some pseudo-D for
- Timon Gehr (12/18) Jun 10 2015 import std.typecons, std.variant;
- deadalnix (3/20) Jun 09 2015 Useful, not ground breaking. I would not add right now.

Following the use of This in Algebraic (https://github.com/D-Programming-Language/phobos/pull/3394), we can apply the same idea to Tuple, thus allowing one to create self-referential types with ease. Consider: // A singly-linked list is payload + pointer to list alias List(T) = Tuple!(T, This*); // A binary tree is payload + two children alias Tree(T) = Tuple!(T, This*, This*); // or alias Tree(T) = Tuple!(T, "payload", This*, "left", This*, "right"); // A binary tree with payload only in leaves alias Tree2(T) = Algebraic!(T, Tuple!(This*, This*)); Is there interest in this? Other application ideas to motivate the addition? Andrei

Jun 09 2015

On Tuesday, 9 June 2015 at 15:28:16 UTC, Andrei Alexandrescu wrote:Following the use of This in Algebraic (https://github.com/D-Programming-Language/phobos/pull/3394), we can apply the same idea to Tuple, thus allowing one to create self-referential types with ease. Consider: // A singly-linked list is payload + pointer to list alias List(T) = Tuple!(T, This*); // A binary tree is payload + two children alias Tree(T) = Tuple!(T, This*, This*); // or alias Tree(T) = Tuple!(T, "payload", This*, "left", This*, "right"); // A binary tree with payload only in leaves alias Tree2(T) = Algebraic!(T, Tuple!(This*, This*)); Is there interest in this? Other application ideas to motivate the addition?Yes, I'm interested. As a practical example, how would you represent a JSON AST type, which might look something like this in OCaml (type json at the top) http://mjambon.com/yojson-doc/Yojson.Safe.html using Algebraic? And once you've encoded it using Algebraic, how do you operate on it, for example, how would you write a 'toString' on the AST? These are both straightforward in OCaml (the straightforward yet inefficient toString pracitically writes itself from the definition, the efficient version with buffers is only a little more involved) so a D version would be a good test.

Jun 09 2015

On 6/9/15 8:59 AM, Brian Rogoff wrote:On Tuesday, 9 June 2015 at 15:28:16 UTC, Andrei Alexandrescu wrote:Excellent example! Here's a shot: alias JsonPayload = Algebraic!( bool, double, long, string, This[], This[string] ); I notice that in Ocaml you get to give names to fields, so I added https://issues.dlang.org/show_bug.cgi?id=14670 to investigate the matter. Converting a complex JsonPayload to string can be done with relative ease by using visitation. Thansk, AndreiFollowing the use of This in Algebraic (https://github.com/D-Programming-Language/phobos/pull/3394), we can apply the same idea to Tuple, thus allowing one to create self-referential types with ease. Consider: // A singly-linked list is payload + pointer to list alias List(T) = Tuple!(T, This*); // A binary tree is payload + two children alias Tree(T) = Tuple!(T, This*, This*); // or alias Tree(T) = Tuple!(T, "payload", This*, "left", This*, "right"); // A binary tree with payload only in leaves alias Tree2(T) = Algebraic!(T, Tuple!(This*, This*)); Is there interest in this? Other application ideas to motivate the addition?Yes, I'm interested. As a practical example, how would you represent a JSON AST type, which might look something like this in OCaml (type json at the top) http://mjambon.com/yojson-doc/Yojson.Safe.html using Algebraic? And once you've encoded it using Algebraic, how do you operate on it, for example, how would you write a 'toString' on the AST? These are both straightforward in OCaml (the straightforward yet inefficient toString pracitically writes itself from the definition, the efficient version with buffers is only a little more involved) so a D version would be a good test.

Jun 09 2015

On 06/09/2015 05:28 PM, Andrei Alexandrescu wrote:Following the use of This in Algebraic (https://github.com/D-Programming-Language/phobos/pull/3394), we can apply the same idea to Tuple, thus allowing one to create self-referential types with ease. Consider: // A singly-linked list is payload + pointer to list alias List(T) = Tuple!(T, This*); // A binary tree is payload + two children alias Tree(T) = Tuple!(T, This*, This*); // or alias Tree(T) = Tuple!(T, "payload", This*, "left", This*, "right"); // A binary tree with payload only in leaves alias Tree2(T) = Algebraic!(T, Tuple!(This*, This*)); Is there interest in this? Other application ideas to motivate the addition? AndreiWell, the issue is with this kind of use case: alias List(T)=Algebraic!(Tuple!(),Tuple!(T,This*));

Jun 09 2015

On 6/9/15 3:58 PM, Timon Gehr wrote:On 06/09/2015 05:28 PM, Andrei Alexandrescu wrote:So a list is either nothing, or a head and a tail. What is the problem here? -- AndreiFollowing the use of This in Algebraic (https://github.com/D-Programming-Language/phobos/pull/3394), we can apply the same idea to Tuple, thus allowing one to create self-referential types with ease. Consider: // A singly-linked list is payload + pointer to list alias List(T) = Tuple!(T, This*); // A binary tree is payload + two children alias Tree(T) = Tuple!(T, This*, This*); // or alias Tree(T) = Tuple!(T, "payload", This*, "left", This*, "right"); // A binary tree with payload only in leaves alias Tree2(T) = Algebraic!(T, Tuple!(This*, This*)); Is there interest in this? Other application ideas to motivate the addition? AndreiWell, the issue is with this kind of use case: alias List(T)=Algebraic!(Tuple!(),Tuple!(T,This*));

Jun 09 2015

On Tuesday, 9 June 2015 at 23:04:41 UTC, Andrei Alexandrescu wrote:On 6/9/15 3:58 PM, Timon Gehr wrote:The `This*` here is not mapped to `Algebraic!(Tuple!(),Tuple!(T,This*))` - it's mapped to the closest containing tuple, `Tuple!(T,This*)`. This means that the tail is not a list - it's a head and a tail. The list is either empty or infinite. At any rate, I think this feature is useful enough even if it doesn't support such use cases. You can always declare a list as a regular struct...On 06/09/2015 05:28 PM, Andrei Alexandrescu wrote:So a list is either nothing, or a head and a tail. What is the problem here? -- Andrei

Jun 09 2015

On 06/10/2015 01:43 AM, Idan Arye wrote:On Tuesday, 9 June 2015 at 23:04:41 UTC, Andrei Alexandrescu wrote:Exactly. Probably it was confusing that I used a raw pointer and not some kind of NonNull!T hack. Non-null was the intention.On 6/9/15 3:58 PM, Timon Gehr wrote:The `This*` here is not mapped to `Algebraic!(Tuple!(),Tuple!(T,This*))` - it's mapped to the closest containing tuple, `Tuple!(T,This*)`. This means that the tail is not a list - it's a head and a tail. The list is either empty or infinite.

Jun 09 2015

On 6/9/15 4:43 PM, Idan Arye wrote:The `This*` here is not mapped to `Algebraic!(Tuple!(),Tuple!(T,This*))` - it's mapped to the closest containing tuple, `Tuple!(T,This*)`. This means that the tail is not a list - it's a head and a tail. The list is either empty or infinite. At any rate, I think this feature is useful enough even if it doesn't support such use cases. You can always declare a list as a regular struct...Way ahead of you :o). Algebraic would use std.variant.This, whereas Tuple would use std.typecons.This. So you get to choose. -- Andrei

Jun 09 2015

On 06/10/2015 01:52 AM, Andrei Alexandrescu wrote:On 6/9/15 4:43 PM, Idan Arye wrote:I generally assume that the same identifier in the same scope of the same code snippet refers to the same symbol, but sure, this avoids this specific problem, but not others.The `This*` here is not mapped to `Algebraic!(Tuple!(),Tuple!(T,This*))` - it's mapped to the closest containing tuple, `Tuple!(T,This*)`. This means that the tail is not a list - it's a head and a tail. The list is either empty or infinite. At any rate, I think this feature is useful enough even if it doesn't support such use cases. You can always declare a list as a regular struct...Way ahead of you :o). Algebraic would use std.variant.This, whereas Tuple would use std.typecons.This. So you get to choose. -- Andrei

Jun 09 2015

On 06/10/2015 01:04 AM, Andrei Alexandrescu wrote:

Jun 09 2015

On 06/10/2015 01:48 AM, Timon Gehr wrote:On 06/10/2015 01:04 AM, Andrei Alexandrescu wrote:If I'm not mistaken Algebraic already suffers from this kind of "This replacement hijacking". alias List(T)=Algebraic!(Tuple!(),Tuple!(T,std.variant.This*)); List!(List!(int)) // not a list of list of int, is it?

Jun 09 2015

On Tuesday, 9 June 2015 at 23:48:05 UTC, Timon Gehr wrote:'This' is a cute hack, but it doesn't replace a proper template fixpoint operator.Could you explain this a bit more, maybe using some pseudo-D for your proposed template fixpoint operator? Thanks. I don't think I'd need such a thing for the JSON AST example, since it isn't parameterized by type. There, the D mapping looks clumsy because, as Andrei noticed, the 'fields' are not named. If you map the OCaml straight to D you get something like what I write below, and you want both the Kind and the internal structure to be non-private so you can write functions which work on them. It's the same as tagged unions/variants in other languages but so much easier to use. enum Kind { Bool, Number, String, Null, Array, Object } alias JSON = JSONStruct *; struct JSONStruct { public: Kind kind; union { bool jsonBool; double jsonNumber; string jsonString; JSON[] jsonArray; JSON[string] jsonObject; } this(Kind kind, bool jsonBool) in { assert(kind == Kind.Bool); } body { kind = Kind.Bool; this.jsonBool = jsonBool; } this(Kind kind, double jsonNumber) in { assert(kind == Kind.Number); } body { kind = Kind.Number; this.jsonNumber = jsonNumber; } this(Kind kind, string jsonString) in { assert(kind == Kind.String); } body { kind = Kind.String; this.jsonString = jsonString; } this(Kind kind) in { assert(kind == Kind.Null); } body { kind = Kind.Null; } this(Kind kind, JSON[] jsonArray) in { assert(kind == Kind.Array); } body { kind = Kind.Array; this.jsonArray = jsonArray; } this(Kind kind, JSON[string] jsonObject) in { assert(kind == Kind.Object); } body { kind = Kind.Object; this.jsonObject = jsonObject; } }

Jun 10 2015

On 06/10/2015 05:52 PM, Brian Rogoff wrote:On Tuesday, 9 June 2015 at 23:48:05 UTC, Timon Gehr wrote:import std.typecons, std.variant; alias List(T)=Algebraic!(Tuple!(),Tuple!(T,List!T*)); void main(){ List!int l; } The following error message is the reason why the 'This' hack is necessary: tt.d(3): Error: template instance Algebraic!(Tuple!(), Tuple!(int, List!int*)) recursive template expansion tt.d(6): Error: template instance tt.List!int error instantiating The simple solution is to just not have this error. The code can easily be given an unambiguous meaning.'This' is a cute hack, but it doesn't replace a proper template fixpoint operator.Could you explain this a bit more, maybe using some pseudo-D for your proposed template fixpoint operator? Thanks. ...

Jun 10 2015

On Tuesday, 9 June 2015 at 15:28:16 UTC, Andrei Alexandrescu wrote:

Jun 09 2015