www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - std.variant.Algebraic, self referential types and delegate members

reply Panke <tobias pankrath.net> writes:
import std.variant, std.stdio;

---
struct NodeTypeA(T) { T[] children; }
struct NodeTypeB(T) { Tree children; }
struct Leaf(T) { T delegate() dg; }

alias Tree = Algebraic!(Leaf, NodeTypeA!This, NodeTypeB!This);

void main()
{
   Tree t;
}
---

yields

tmp.d(6): Error: functions cannot return opaque type This by value
tmp.d(8): Error: template instance tmp.Leaf!(This) error 
instantiating

This limitation seems arbitrary to me. What's the reason here?
Nov 08 2015
next sibling parent reply Jonathan M Davis via Digitalmars-d-learn writes:
On Sunday, November 08, 2015 10:31:11 Panke via Digitalmars-d-learn wrote:

 import std.variant, std.stdio;

 ---
 struct NodeTypeA(T) { T[] children; }
 struct NodeTypeB(T) { Tree children; }
 struct Leaf(T) { T delegate() dg; }

 alias Tree = Algebraic!(Leaf, NodeTypeA!This, NodeTypeB!This);

 void main()
 {
    Tree t;
 }
 ---

 yields

 tmp.d(6): Error: functions cannot return opaque type This by value
 tmp.d(8): Error: template instance tmp.Leaf!(This) error
 instantiating

 This limitation seems arbitrary to me. What's the reason here?


Okay. Several things here. For starters, NodeTypeA, NodeTypeB, and Leaf are
not actually types. They're templates for types. If you want a type, you
have to instantiate them. So, something like Algebraic!Leaf doesn't make any
sense. You need an instantiation of Leaf - e.g. Algebraic!(Leaf!int) -
rather than just Leaf.

Next, you have a recursive template instantiation going on here. Tree
depends on knowing what a NodeTypeB looks like, because it's using it in its
instantiation of Algebraic. Algebraic!(Foo, Bar) is told to hold either a
Foo or a Bar, which means that it needs to know their definitions - not just
their names. You need to be using pointers if you want to be able to avoid
having to know the actual definition of the type. So, when you tell
NodeTypeB to hold a Tree when a Tree holds a NodeTypeB, it's impossible to
figure out what the actual layout of those types. You have a recursive
expansion.

If you want to have a recursive type definition, you _must_ use pointers so
that the actual definition of the type is not required.

Also, I have no idea what the deal with the This in your code is. IIRC,
there's a feature involving This with template definitions, but you're just
using it outside of a template definition, so I don't know if that's legal.
But I'm also not at all familiar with what This actually does even if it's
used in the right place. So, maybe what you're doing with it is valid. I
question it, but I don't know enough to know for sure one way or the other.

Now, mucking around with your code, trying to see if I could get it to
compile, I suspect that Algebraic has something in its implementation that
doesn't play nicely with what you're trying to do (which may or may not
be a bug), but I don't know exactly what's going on. The error message I'm
getting (which does not match the one that you're getting) involves a
complaint about recursive template expansion, which implies that Algebraic
may need to know the definition of Foo even if you instantiate it with Foo*
- e.g. Algebraic!(Foo*), though I don't know why that would be the case.

The error that you're seeing implies that the code is trying to return a
type by value when it does not know the definition of the type, and that's
not going to work. To return a type by value, the compiler needs to know
what its layout is. So, that probably relates to trying to the recursive
expansion problem where the code ends up trying to use a NodeTypeB!This when
it doesn't know the layout of NodeTypeB!This yet, because it's trying to
define Tree, which requires that it know the definition of NodeTypeB!This...
So, it's likely that with whatever version of the compiler you're using,
you're just triggering a slightly different error than the version I'm using
hits, though the root cause is the same.

So, you need to change your types so that they're not actually recursively
defined (which almost certainly means using pointers), and Algebraic may or
may not actually be able to do what you want due to some aspect of its
current implementation.

- Jonathan M Davis
Nov 08 2015
parent Panke <tobias pankrath.net> writes:
On Sunday, 8 November 2015 at 11:28:05 UTC, Jonathan M Davis 
wrote:

 On Sunday, November 08, 2015 10:31:11 Panke via 
 Digitalmars-d-learn wrote:

 import std.variant, std.stdio;

 ---
 struct NodeTypeA(T) { T[] children; }
 struct NodeTypeB(T) { Tree children; }
 struct Leaf(T) { T delegate() dg; }

 alias Tree = Algebraic!(Leaf, NodeTypeA!This, NodeTypeB!This);

 void main()
 {
    Tree t;
 }
 ---

 yields

 tmp.d(6): Error: functions cannot return opaque type This by 
 value
 tmp.d(8): Error: template instance tmp.Leaf!(This) error
 instantiating

 This limitation seems arbitrary to me. What's the reason here?


 Okay. Several things here. For starters, NodeTypeA, NodeTypeB, 
 and Leaf are not actually types. They're templates for types. 
 If you want a type, you have to instantiate them. So, something 
 like Algebraic!Leaf doesn't make any sense. You need an 
 instantiation of Leaf - e.g. Algebraic!(Leaf!int) - rather than 
 just Leaf.


My failure, I've played with the code while crafting the post. 
I've used
---
alias Tree = Algebraic!(Leaf!This, NoteTypeA!This, NoteTypeB!This)
---

So no templates, just types.


 Next, you have a recursive template instantiation going on 
 here. Tree depends on knowing what a NodeTypeB looks like, 
 because it's using it in its instantiation of Algebraic. 
 Algebraic!(Foo, Bar) is told to hold either a Foo or a Bar, 
 which means that it needs to know their definitions - not just 
 their names. You need to be using pointers if you want to be 
 able to avoid having to know the actual definition of the type. 
 So, when you tell NodeTypeB to hold a Tree when a Tree holds a 
 NodeTypeB, it's impossible to figure out what the actual layout 
 of those types. You have a recursive expansion.

 If you want to have a recursive type definition, you _must_ use 
 pointers so that the actual definition of the type is not 
 required.


Thing is that delegate is nothing more than a glorified pair of 
pointers.


 Also, I have no idea what the deal with the This in your code 
 is. IIRC, there's a feature involving This with template 
 definitions, but you're just using it outside of a template 
 definition, so I don't know if that's legal.


It's a recent feature of Algebraic to allow recursive 
definitions. I'd assume that it uses pointers under the hood.

Older compiler but same error message: http://goo.gl/P0wmqe
Nov 08 2015
prev sibling parent Meta <jared771 gmail.com> writes:
On Sunday, 8 November 2015 at 10:31:13 UTC, Panke wrote:

 import std.variant, std.stdio;

 ---
 struct NodeTypeA(T) { T[] children; }
 struct NodeTypeB(T) { Tree children; }
 struct Leaf(T) { T delegate() dg; }

 alias Tree = Algebraic!(Leaf, NodeTypeA!This, NodeTypeB!This);

 void main()
 {
   Tree t;
 }
 ---

 yields

 tmp.d(6): Error: functions cannot return opaque type This by 
 value
 tmp.d(8): Error: template instance tmp.Leaf!(This) error 
 instantiating

 This limitation seems arbitrary to me. What's the reason here?


The issue is because your delegate inside Leaf returns a T by 
value, and T in this case is
the type std.variant.This; it's an opaque struct type to allow 
for recursive structures. If it sees This* or This[] in the 
template argument list to Algebraic, it'll do some magic to 
replace this with another Variant. That magic is 
std.typecons.ReplaceType[1]. However, note the warning on 
ReplaceType:

"However, member types in `struct`s or `class`es are not replaced 
because there
are no ways to express the types resulting after replacement."

And thus it can't replace the T return type of your delegate with 
the proper type. The compiler sees that you're trying to return 
the opaque struct This by value and violently disagrees with that 
notion, refusing to compile. To make that particular compiler 
error go away you can change the return type of the delegate to 
T* or T[], but that's not particularly useful as you're still 
just returning a pointer to This, not the recursive type. I'm not 
completely sure what you're trying to do is possible in D, and 
definitely not without enhancements to ReplaceType.


1. 
https://github.com/D-Programming-Language/phobos/blob/245c7ab0b591cb48b3dbb239640dd54e0717110a/std/typecons.d#L6643
Nov 08 2015