## 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
• 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.
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
"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
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
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
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
"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
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
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
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
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
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
"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
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
"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