View mode: basic / threaded / horizontal-split · Log in · Help
February 11, 2009
Recursive discriminated unions [Phobos2]
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.
February 11, 2009
Re: Recursive discriminated unions [Phobos2]
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
February 12, 2009
Re: Recursive discriminated unions [Phobos2]
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
February 15, 2009
Re: Recursive discriminated unions [Phobos2]
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.  :)

Advantage #1 of marrying a foreigner: you get to convince her that V-day 
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
February 15, 2009
Re: Recursive discriminated unions [Phobos2]
Andrei Alexandrescu wrote:
> Advantage #1 of marrying a foreigner: you get to convince her that V-day
> 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
February 15, 2009
Re: Recursive discriminated unions [Phobos2]
Brad Roberts wrote:
> Andrei Alexandrescu wrote:
>> Advantage #1 of marrying a foreigner: you get to convince her that V-day
>> 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
February 16, 2009
Re: Recursive discriminated unions [Phobos2]
Andrei Alexandrescu wrote:
> Brad Roberts wrote:
>> Andrei Alexandrescu wrote:
>>> Advantage #1 of marrying a foreigner: you get to convince her that V-day
>>> 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
February 16, 2009
Re: Recursive discriminated unions [Phobos2]
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.  :)
> 
> Advantage #1 of marrying a foreigner: you get to convince her that V-day 
> 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
Top | Discussion index | About this forum | D home