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