www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Recursive discriminated unions [Phobos2]

reply Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Okay, we all [hopefully] know what a discriminated union is, and those 
of us who are trying out D2 can probably generally agree that 
std.variant.Algebraic makes life a good deal easier in this arena.  The 
actual usage is different, but it is definitely a gift from heaven. 
Except there's one thing it can't do: recursive types.


// D1
struct MyVar {
	// ...
	union {
		int i;
		double f;
		char[] s;
		MyVar[] l;	// lists good to go
		MyVar[MyVar] h;	// hashtables good to go
	}
	// ...
}


// D2
alias Algebraic!(int, double, string, MyVar[], MyVar[MyVar]) MyVar;

Bzzzzzt!  Big ole error!


Fooey.  Because I want this, badly (its absolutely necessary for a 
program I'm working on).  I asked Andrei if he had any suggestion, 
especially since it is a known limitation mentioned explicitly in the 
specs.  No luck.  He did have an idea on syntax:

Algebraic!(int, double, string, This[])

Where the 'This' token is recognized specially as recursive.  It reads 
well, although my first thought was '_' similar to the way std.bind 
works.  The million dollar question is: how to make this work?

-- Chris Nicholson-Sauls

PS: Apologies, as I just got home from a very long day, so the brain is 
a bit tired and I probably came off silly.
Feb 10 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Chris Nicholson-Sauls wrote:

 Okay, we all [hopefully] know what a discriminated union is, and those 
 of us who are trying out D2 can probably generally agree that 
 std.variant.Algebraic makes life a good deal easier in this arena.  The 
 actual usage is different, but it is definitely a gift from heaven. 
 Except there's one thing it can't do: recursive types.


[snip]

Ok, I have a solution now. I'm not checking it in yet because I have a 
brazillion other changes in my tree and I don't want to break something. 
But I attach it to this message and it contains the following unittest:

unittest
{
     alias Algebraic!(real, This[], This[int], This[This]) A;
     A v1, v2, v3;
     v2 = 5.0L;
     v3 = 42.0L;
     v1 = [ v2 ][];
     auto v = v1.peek!(A[]);
     writeln(v[0]);
     v1 = [ 9 : v3 ];
     writeln(v1);
     v1 = [ v3 : v3 ];
     writeln(v1);
}

The patterns This[], This*, This[U], U[This], and This[This] are 
detected, but alas, no general solution yet (I don't know how to). 
Anyhow, std.variant is starting to get interesting with this feature in tow.


Andrei
Feb 10 2009
parent reply Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Andrei Alexandrescu wrote:

 Ok, I have a solution now. I'm not checking it in yet because I have a 
 brazillion other changes in my tree and I don't want to break something. 
 But I attach it to this message and it contains the following unittest:
 
 unittest
 {
     alias Algebraic!(real, This[], This[int], This[This]) A;
     A v1, v2, v3;
     v2 = 5.0L;
     v3 = 42.0L;
     v1 = [ v2 ][];
     auto v = v1.peek!(A[]);
     writeln(v[0]);
     v1 = [ 9 : v3 ];
     writeln(v1);
     v1 = [ v3 : v3 ];
     writeln(v1);
 }
 
 The patterns This[], This*, This[U], U[This], and This[This] are 
 detected, but alas, no general solution yet (I don't know how to). 
 Anyhow, std.variant is starting to get interesting with this feature in 
 tow.
 
 
 Andrei
 


I've noticed a shortcoming that I somehow hadn't come across before. 
The same issue exists in the current Phobos2, so it isn't anything new. 
  Apparently (and this may be known to all but me already) in order to 
use an array type, you must also use its element type.  Doing otherwise 
results in tripping a static assert.

Example:

	module test2;

	import std.variant;

	alias Algebraic!(void, string) var_t;

	void main () {
	    var_t foo = "quux";
	}

Shows: ../bin/../src/phobos/std/variant.d(418): static assert  "Cannot 
store a immutable(char) in a VariantN!(maxSize,void,immutable(char)[])"

Add invariant(char) to the list and all works fine, though.  The 
offending code is seemingly in VariantN.handler!(A):

         case OpID.index:
             auto me = cast(A*) pStore;
             static if (isArray!(A))
             {
                 // array type; input and output are the same VariantN
                 auto result = cast(VariantN*) parm;
                 size_t index = result.convertsTo!(int)
                     ? result.get!(int) : result.get!(size_t);
                 *result = (*me)[index];

	break;
             }

Specifically the statement (*result = (*me)[index];) triggers it, by 
spawning an opAssign!(elem_type).  I'm not sure how to cleanly alter it 
right off the top of my head.

----------

On the other hand, the new form This[] works fine, so far.  The only 
missing feature is an opApply().

The form This[This]... Using 'foo.get!(table_t)[k] = v;' results in a 
range violation.  For the moment, they are essentially immutable hashes. 
  Could actually be fine for a number of purposes.

----------

If I get some extra free time this weekend (assuming V-day isn't the 
death of me) I'll hack away at it some and see if I can't figure some 
things out, on all counts above.

Oh, and THANKS.  :)

-- Chris Nicholson-Sauls
Feb 11 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Chris Nicholson-Sauls wrote:

 I've noticed a shortcoming that I somehow hadn't come across before. The 
 same issue exists in the current Phobos2, so it isn't anything new. 
  Apparently (and this may be known to all but me already) in order to 
 use an array type, you must also use its element type.  Doing otherwise 
 results in tripping a static assert.
 
 Example:
 
     module test2;
 
     import std.variant;
 
     alias Algebraic!(void, string) var_t;
 
     void main () {
         var_t foo = "quux";
     }


This was an oversight caused by implementing opIndex, which I now fixed 
with credit. Thanks!

Now if you haven an Algebraic containing an array, you won't be able to 
call its opIndex directly; it will throw an exception. This is because 
opIndex wants to return the same type as this, and that type is unable 
to hold the element type of the array!

[snip]

 Specifically the statement (*result = (*me)[index];) triggers it, by 
 spawning an opAssign!(elem_type).  I'm not sure how to cleanly alter it 
 right off the top of my head.
 
 ----------
 
 On the other hand, the new form This[] works fine, so far.  The only 
 missing feature is an opApply().


Ok, I filed a bug report on your behalf.


 The form This[This]... Using 'foo.get!(table_t)[k] = v;' results in a 
 range violation.  For the moment, they are essentially immutable hashes. 
  Could actually be fine for a number of purposes.


That's because foo.get returns by value. Try using peek, which returns a 
pointer. Could you please post some code if that doesn't work for your case?


 ----------
 
 If I get some extra free time this weekend (assuming V-day isn't the 
 death of me) I'll hack away at it some and see if I can't figure some 
 things out, on all counts above.
 
 Oh, and THANKS.  :)



is an artificial event created for commercial interests only because 
they want to sell blood diamonds. Watching "Blood Diamond" together a 
week before V-day recommended.


Andrei
Feb 15 2009
next sibling parent reply Brad Roberts <braddr puremagic.com> writes:
Andrei Alexandrescu wrote:


 is an artificial event created for commercial interests only because
 they want to sell blood diamonds. Watching "Blood Diamond" together a
 week before V-day recommended.
 
 Andrei


Psst.. not to burst your bubble, but you're just as much a foreigner as
she is.  So cut that out and go do something nice for your wife. :)

Later,
Brad
Feb 15 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Brad Roberts wrote:

 Andrei Alexandrescu wrote:


 is an artificial event created for commercial interests only because
 they want to sell blood diamonds. Watching "Blood Diamond" together a
 week before V-day recommended.

 Andrei


 
 Psst.. not to burst your bubble, but you're just as much a foreigner as
 she is.  So cut that out and go do something nice for your wife. :)


Of course. That does not diminish the effectiveness of the technique in 
the least. The problems start of course when you share some V-Day 
equivalent in your native culture (e.g. March 8 for us). At that point I 
usually bring up the "When in Rome..." saying. :o)

Andrei
Feb 15 2009
parent Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Andrei Alexandrescu wrote:

 Brad Roberts wrote:

 Andrei Alexandrescu wrote:


 is an artificial event created for commercial interests only because
 they want to sell blood diamonds. Watching "Blood Diamond" together a
 week before V-day recommended.

 Andrei


 Psst.. not to burst your bubble, but you're just as much a foreigner as
 she is.  So cut that out and go do something nice for your wife. :)


 
 Of course. That does not diminish the effectiveness of the technique in 
 the least. The problems start of course when you share some V-Day 
 equivalent in your native culture (e.g. March 8 for us). At that point I 
 usually bring up the "When in Rome..." saying. :o)
 
 Andrei


A couple of years back I introduced her to the Japanese "white day," 
which is (warning: oversimplified explanation ahead) held a week later, 
with the roles reversed as it were.  Works out well for me.

-- Chris Nicholson-Sauls
Feb 15 2009
prev sibling parent Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Andrei Alexandrescu wrote:

 Chris Nicholson-Sauls wrote:

 On the other hand, the new form This[] works fine, so far.  The only 
 missing feature is an opApply().


 
 Ok, I filed a bug report on your behalf.


Thanks...  I somehow always forget we have that available.


 The form This[This]... Using 'foo.get!(table_t)[k] = v;' results in a 
 range violation.  For the moment, they are essentially immutable 
 hashes.  Could actually be fine for a number of purposes.


 
 That's because foo.get returns by value. Try using peek, which returns a 
 pointer. Could you please post some code if that doesn't work for your 
 case?


Will try that tomorrow after work.


 ----------

 If I get some extra free time this weekend (assuming V-day isn't the 
 death of me) I'll hack away at it some and see if I can't figure some 
 things out, on all counts above.

 Oh, and THANKS.  :)


 

 is an artificial event created for commercial interests only because 
 they want to sell blood diamonds. Watching "Blood Diamond" together a 
 week before V-day recommended.
 
 
 Andrei


Thanks for the advice, I'll try it next year.  ;)

-- Chris Nicholson-Sauls
Feb 15 2009