www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Self-referential tuples?

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
next sibling parent reply "Brian Rogoff" <brogoff gmail.com> writes:
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
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/9/15 8:59 AM, Brian Rogoff wrote:
 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.
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, Andrei
Jun 09 2015
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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?


 Andrei
Well, the issue is with this kind of use case: alias List(T)=Algebraic!(Tuple!(),Tuple!(T,This*));
Jun 09 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/9/15 3:58 PM, Timon Gehr wrote:
 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?


 Andrei
Well, the issue is with this kind of use case: alias List(T)=Algebraic!(Tuple!(),Tuple!(T,This*));
So a list is either nothing, or a head and a tail. What is the problem here? -- Andrei
Jun 09 2015
next sibling parent reply "Idan Arye" <GenericNPC gmail.com> writes:
On Tuesday, 9 June 2015 at 23:04:41 UTC, Andrei Alexandrescu 
wrote:
 On 6/9/15 3:58 PM, Timon Gehr wrote:
 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?


 Andrei
Well, the issue is with this kind of use case: alias List(T)=Algebraic!(Tuple!(),Tuple!(T,This*));
So a list is either nothing, or a head and a tail. What is the problem here? -- Andrei
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...
Jun 09 2015
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 06/10/2015 01:43 AM, Idan Arye wrote:
 On Tuesday, 9 June 2015 at 23:04:41 UTC, Andrei Alexandrescu wrote:
 On 6/9/15 3:58 PM, Timon Gehr wrote:
 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?


 Andrei
Well, the issue is with this kind of use case: alias List(T)=Algebraic!(Tuple!(),Tuple!(T,This*));
So a list is either nothing, or a head and a tail. What is the problem here? -- Andrei
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.
Exactly. Probably it was confusing that I used a raw pointer and not some kind of NonNull!T hack. Non-null was the intention.
Jun 09 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 06/10/2015 01:52 AM, Andrei Alexandrescu wrote:
 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
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.
Jun 09 2015
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 06/10/2015 01:04 AM, Andrei Alexandrescu wrote:
 On 6/9/15 3:58 PM, Timon Gehr wrote:
 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?


 Andrei
Well, the issue is with this kind of use case: alias List(T)=Algebraic!(Tuple!(),Tuple!(T,This*));
So a list is either nothing, or a head and a tail. What is the problem here? -- Andrei
It's about which type 'This' refers to. Is it the Algebraic or the Tuple? I assume here it would be the algebraic, which is expected, but it can get non-obvious quickly especially when e.g. a template parameter is a recursive tuple and the template uses the type in an Algebraic. It's just a mess. E.g. what happens if you do List!(Tree!int)? ReplaceType would need to treat Tuples specially, and then you lose the other semantics even though it might sometimes be needed. 'This' is a cute hack, but it doesn't replace a proper template fixpoint operator.
Jun 09 2015
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 06/10/2015 01:48 AM, Timon Gehr wrote:
 On 06/10/2015 01:04 AM, Andrei Alexandrescu wrote:
 On 6/9/15 3:58 PM, Timon Gehr wrote:
 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?


 Andrei
Well, the issue is with this kind of use case: alias List(T)=Algebraic!(Tuple!(),Tuple!(T,This*));
So a list is either nothing, or a head and a tail. What is the problem here? -- Andrei
It's about which type 'This' refers to. Is it the Algebraic or the Tuple? I assume here it would be the algebraic, which is expected, but it can get non-obvious quickly especially when e.g. a template parameter is a recursive tuple and the template uses the type in an Algebraic. It's just a mess. E.g. what happens if you do List!(Tree!int)? ReplaceType would need to treat Tuples specially, and then you lose the other semantics even though it might sometimes be needed. 'This' is a cute hack, but it doesn't replace a proper template fixpoint operator.
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
prev sibling parent reply "Brian Rogoff" <brogoff gmail.com> writes:
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
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 06/10/2015 05:52 PM, Brian Rogoff wrote:
 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. ...
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.
Jun 10 2015
prev sibling parent "deadalnix" <deadalnix gmail.com> writes:
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?


 Andrei
Useful, not ground breaking. I would not add right now.
Jun 09 2015