www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Dispatching on a variant

reply Justin Johansson <procode adam-dott-com.au> writes:
I've had a good poke around the forums and couldn't find anything on this so ...

What's the recommended method for dispatching code off the runtime type of a
variant variable
(Phobos D2 std.variant)?

Does one use a bunch of

if ( var.peek!(type1)) { ... }
else if ( var.peek!(type2)  { ... }

for all N possible types, or is there a better & faster way with a switch or
jump table of sorts?

Thanks all.

-- Justin Johansson
Sep 26 2009
next sibling parent reply language_fan <foo bar.com.invalid> writes:
Sat, 26 Sep 2009 09:32:55 -0400, Justin Johansson thusly wrote:


 I've had a good poke around the forums and couldn't find anything on
 this so ...
 
 What's the recommended method for dispatching code off the runtime type
 of a variant variable (Phobos D2 std.variant)?
 
 Does one use a bunch of
 
 if ( var.peek!(type1)) { ... }
 else if ( var.peek!(type2)  { ... }
 
 for all N possible types, or is there a better & faster way with a
 switch or jump table of sorts?


If the type count gets large, how fast it is depends on the backend 
optimizations of the compiler. In the worst case it is a O(n) time linear 
search. A jump table or almost any other way of dispatching would be 
faster. If the variant had an integral tag field, it could be used in a 
switch; that way the compiler could easily optimize it further with the 
currently available constructs.

This problem is solved in higher level languages by providing pattern 
matching constructs. The compiler is free to optimize the code the way it 
likes:

  case var of
    type1 => ...
    type2 => ...
    ...

But since no C-like language has ever implemented pattern matching, it 
might be too radical to add it to D.
Sep 26 2009
parent reply Justin Johansson <procode adam-dott-com.au> writes:
language_fan Wrote:


 Sat, 26 Sep 2009 09:32:55 -0400, Justin Johansson thusly wrote:
 

 I've had a good poke around the forums and couldn't find anything on
 this so ...
 
 What's the recommended method for dispatching code off the runtime type
 of a variant variable (Phobos D2 std.variant)?
 
 Does one use a bunch of
 
 if ( var.peek!(type1)) { ... }
 else if ( var.peek!(type2)  { ... }
 
 for all N possible types, or is there a better & faster way with a
 switch or jump table of sorts?


 
 If the type count gets large, how fast it is depends on the backend 
 optimizations of the compiler. In the worst case it is a O(n) time linear 
 search. A jump table or almost any other way of dispatching would be 
 faster. If the variant had an integral tag field, it could be used in a 
 switch; that way the compiler could easily optimize it further with the 
 currently available constructs.
 
 This problem is solved in higher level languages by providing pattern 
 matching constructs. The compiler is free to optimize the code the way it 
 likes:
 
   case var of
     type1 => ...
     type2 => ...
     ...
 
 But since no C-like language has ever implemented pattern matching, it 
 might be too radical to add it to D.


Thanks both for replies.

I've got about 2 dozen types in the variant so the O(n) really hurts.
The variant thing seemed like a really cool idea at the time but now ...
Without something like suggested above or a computed goto on typeid or Andrei's
visitator,
it almost pushes me to backout from using variants and having to redesign
around some common base class or interface and using virtual function dispatch.
:-(
Sep 26 2009
next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Sat, 26 Sep 2009 10:36:06 -0400, Justin Johansson  
<procode adam-dott-com.au> wrote:

 language_fan Wrote:


 Sat, 26 Sep 2009 09:32:55 -0400, Justin Johansson thusly wrote:


 I've had a good poke around the forums and couldn't find anything on
 this so ...

 What's the recommended method for dispatching code off the runtime  


 type

 of a variant variable (Phobos D2 std.variant)?

 Does one use a bunch of

 if ( var.peek!(type1)) { ... }
 else if ( var.peek!(type2)  { ... }

 for all N possible types, or is there a better & faster way with a
 switch or jump table of sorts?


 If the type count gets large, how fast it is depends on the backend
 optimizations of the compiler. In the worst case it is a O(n) time  
 linear
 search. A jump table or almost any other way of dispatching would be
 faster. If the variant had an integral tag field, it could be used in a
 switch; that way the compiler could easily optimize it further with the
 currently available constructs.

 This problem is solved in higher level languages by providing pattern
 matching constructs. The compiler is free to optimize the code the way  
 it
 likes:

   case var of
     type1 => ...
     type2 => ...
     ...

 But since no C-like language has ever implemented pattern matching, it
 might be too radical to add it to D.


 Thanks both for replies.

 I've got about 2 dozen types in the variant so the O(n) really hurts.
 The variant thing seemed like a really cool idea at the time but now ...
 Without something like suggested above or a computed goto on typeid or  
 Andrei's visitator,
 it almost pushes me to backout from using variants and having to  
 redesign around some common base class or interface and using virtual  
 function dispatch. :-(


Here's an idea. Since you know each type at compile time, you can generate  
the list of methods they implement + a private set of delegates for their  
implementation. Then on assignment of a type, variant would simply assign  
the correct delegate for each supported method and an exception throwing  
delegate for un-supported methods.
Sep 26 2009
prev sibling next sibling parent reply Jeremie Pelletier <jeremiep gmail.com> writes:
Justin Johansson wrote:

 language_fan Wrote:
 

 Sat, 26 Sep 2009 09:32:55 -0400, Justin Johansson thusly wrote:


 I've had a good poke around the forums and couldn't find anything on
 this so ...

 What's the recommended method for dispatching code off the runtime type
 of a variant variable (Phobos D2 std.variant)?

 Does one use a bunch of

 if ( var.peek!(type1)) { ... }
 else if ( var.peek!(type2)  { ... }

 for all N possible types, or is there a better & faster way with a
 switch or jump table of sorts?


 If the type count gets large, how fast it is depends on the backend 
 optimizations of the compiler. In the worst case it is a O(n) time linear 
 search. A jump table or almost any other way of dispatching would be 
 faster. If the variant had an integral tag field, it could be used in a 
 switch; that way the compiler could easily optimize it further with the 
 currently available constructs.

 This problem is solved in higher level languages by providing pattern 
 matching constructs. The compiler is free to optimize the code the way it 
 likes:

   case var of
     type1 => ...
     type2 => ...
     ...

 But since no C-like language has ever implemented pattern matching, it 
 might be too radical to add it to D.


 
 Thanks both for replies.
 
 I've got about 2 dozen types in the variant so the O(n) really hurts.
 The variant thing seemed like a really cool idea at the time but now ...
 Without something like suggested above or a computed goto on typeid or
Andrei's visitator,
 it almost pushes me to backout from using variants and having to redesign
around some common base class or interface and using virtual function dispatch.
:-(
 


I see this sort of design in C all the time with event handling, 
although its with unions rather than discriminated unions, the same 
logic applies.

enum EventType {
	Mouse,
	Key,
	Move,
	...
}
struct Event {
	EventType type;
	union {
		MouseEvent mouse;
		KeyEvent key;
		MoveEvent move;
		...
	}
}

void dispatchEvent(const(Event)* event) {
	...
	with(EventType) final switch(event.type) {
	case Mouse: ...
	case Key: ...
	case Move: ...
	...
	}
	...
}

That's the logic with standard unions, you should be able to get 
something similar with variants. It's more code to setup, but you end up 
with a simple jump table from the switch, and final in D makes it easy 
to change EventType without forgetting to update dispatchEvent.
Sep 26 2009
parent reply language_fan <foo bar.com.invalid> writes:
Sat, 26 Sep 2009 12:25:23 -0400, Jeremie Pelletier thusly wrote:


 Justin Johansson wrote:

 language_fan Wrote:
 

 Sat, 26 Sep 2009 09:32:55 -0400, Justin Johansson thusly wrote:


 I've had a good poke around the forums and couldn't find anything on
 this so ...

 What's the recommended method for dispatching code off the runtime
 type of a variant variable (Phobos D2 std.variant)?

 Does one use a bunch of

 if ( var.peek!(type1)) { ... }
 else if ( var.peek!(type2)  { ... }

 for all N possible types, or is there a better & faster way with a
 switch or jump table of sorts?


 If the type count gets large, how fast it is depends on the backend
 optimizations of the compiler. In the worst case it is a O(n) time
 linear search. A jump table or almost any other way of dispatching
 would be faster. If the variant had an integral tag field, it could be
 used in a switch; that way the compiler could easily optimize it
 further with the currently available constructs.

 This problem is solved in higher level languages by providing pattern
 matching constructs. The compiler is free to optimize the code the way
 it likes:

   case var of
     type1 => ...
     type2 => ...
     ...

 But since no C-like language has ever implemented pattern matching, it
 might be too radical to add it to D.


 
 Thanks both for replies.
 
 I've got about 2 dozen types in the variant so the O(n) really hurts.
 The variant thing seemed like a really cool idea at the time but now
 ... Without something like suggested above or a computed goto on typeid
 or Andrei's visitator, it almost pushes me to backout from using
 variants and having to redesign around some common base class or
 interface and using virtual function dispatch. :-(
 
 


 I see this sort of design in C all the time with event handling,
 although its with unions rather than discriminated unions, the same
 logic applies.
 
 enum EventType {
 	Mouse,
 	Key,
 	Move,
 	...
 }
 struct Event {
 	EventType type;
 	union {
 		MouseEvent mouse;
 		KeyEvent key;
 		MoveEvent move;
 		...
 	}
 }
 
 void dispatchEvent(const(Event)* event) {
 	...
 	with(EventType) final switch(event.type) { case Mouse: ...
 	case Key: ...
 	case Move: ...
 	...
 	}
 	...
 }
 
 That's the logic with standard unions, you should be able to get
 something similar with variants. It's more code to setup, but you end up
 with a simple jump table from the switch, and final in D makes it easy
 to change EventType without forgetting to update dispatchEvent.


Exactly, this is what I mentioned previously. Isn't it ugly compared to

  type Event = Mouse | Key | Move;

  void dispatchEvent(Event event) {
    match(event) {
      Mouse m => m.squeek();
      Key k => ...
      ...
    }
  }

What's with all the language proposals here? Why hasn't anyone proposed 
this before? This is in fact very helpful - that's why several modern 
languages have adopted it.
Sep 26 2009
parent reply Jeremie Pelletier <jeremiep gmail.com> writes:
language_fan wrote:

 Sat, 26 Sep 2009 12:25:23 -0400, Jeremie Pelletier thusly wrote:
 

 Justin Johansson wrote:

 language_fan Wrote:


 Sat, 26 Sep 2009 09:32:55 -0400, Justin Johansson thusly wrote:


 I've had a good poke around the forums and couldn't find anything on
 this so ...

 What's the recommended method for dispatching code off the runtime
 type of a variant variable (Phobos D2 std.variant)?

 Does one use a bunch of

 if ( var.peek!(type1)) { ... }
 else if ( var.peek!(type2)  { ... }

 for all N possible types, or is there a better & faster way with a
 switch or jump table of sorts?


 If the type count gets large, how fast it is depends on the backend
 optimizations of the compiler. In the worst case it is a O(n) time
 linear search. A jump table or almost any other way of dispatching
 would be faster. If the variant had an integral tag field, it could be
 used in a switch; that way the compiler could easily optimize it
 further with the currently available constructs.

 This problem is solved in higher level languages by providing pattern
 matching constructs. The compiler is free to optimize the code the way
 it likes:

   case var of
     type1 => ...
     type2 => ...
     ...

 But since no C-like language has ever implemented pattern matching, it
 might be too radical to add it to D.


 Thanks both for replies.

 I've got about 2 dozen types in the variant so the O(n) really hurts.
 The variant thing seemed like a really cool idea at the time but now
 ... Without something like suggested above or a computed goto on typeid
 or Andrei's visitator, it almost pushes me to backout from using
 variants and having to redesign around some common base class or
 interface and using virtual function dispatch. :-(


 I see this sort of design in C all the time with event handling,
 although its with unions rather than discriminated unions, the same
 logic applies.

 enum EventType {
 	Mouse,
 	Key,
 	Move,
 	...
 }
 struct Event {
 	EventType type;
 	union {
 		MouseEvent mouse;
 		KeyEvent key;
 		MoveEvent move;
 		...
 	}
 }

 void dispatchEvent(const(Event)* event) {
 	...
 	with(EventType) final switch(event.type) { case Mouse: ...
 	case Key: ...
 	case Move: ...
 	...
 	}
 	...
 }

 That's the logic with standard unions, you should be able to get
 something similar with variants. It's more code to setup, but you end up
 with a simple jump table from the switch, and final in D makes it easy
 to change EventType without forgetting to update dispatchEvent.


 
 Exactly, this is what I mentioned previously. Isn't it ugly compared to
 
   type Event = Mouse | Key | Move;


This can be confusing, for example the first thing that comes to mind 
for me is that Event is the bitwise OR result of 3 constants, not an 
enumerated type.

Besides, how is it any different than:

enum { Mouse, Key, Move };


   void dispatchEvent(Event event) {
     match(event) {
       Mouse m => m.squeek();
       Key k => ...
       ...
     }
   }


match(event) is no different than switch(event), except that pattern 
matching often implies runtime semantics and is often slower than a 
straight jump table generated from a switch.


 What's with all the language proposals here? Why hasn't anyone proposed 
 this before? This is in fact very helpful - that's why several modern 
 languages have adopted it.
Sep 26 2009
parent reply Jarrett Billingsley <jarrett.billingsley gmail.com> writes:
On Sat, Sep 26, 2009 at 4:18 PM, Jeremie Pelletier <jeremiep gmail.com> wro=
te:


 =A0type Event =3D Mouse | Key | Move;


 This can be confusing, for example the first thing that comes to mind for=


 me

 is that Event is the bitwise OR result of 3 constants, not an enumerated
 type.

 Besides, how is it any different than:

 enum { Mouse, Key, Move };


It's not an enumerated constant. Mouse, Key, and Move are all types,
and Event is a discriminated union of the three. See more below.


 match(event) is no different than switch(event), except that pattern
 matching often implies runtime semantics and is often slower than a strai=


ght

 jump table generated from a switch.


Not in this case. See, when you would do "type Event =3D Mouse | Key |
Move", it's actually more like doing:

struct Event
{
    enum Type { Mouse, Key, Move }
    Type type;
    union
    {
        Mouse m;
        Key k;
        Move v;
    }
}

Then, when you do "match(e) { Mouse m =3D> ... }" it's actually being turne=
d into:

switch(e.type)
{
    case Event.Type.Mouse: alias e.m m; ...
    case Event.Type.Key: alias e.k k; ...
}

Basically discriminated unions get rid of this annoying boilerplate
that you have to use every time you want a tagged union.
Sep 26 2009
parent reply Jeremie Pelletier <jeremiep gmail.com> writes:
Jarrett Billingsley wrote:

 On Sat, Sep 26, 2009 at 4:18 PM, Jeremie Pelletier <jeremiep gmail.com> wrote:
 

  type Event = Mouse | Key | Move;


 This can be confusing, for example the first thing that comes to mind for me
 is that Event is the bitwise OR result of 3 constants, not an enumerated
 type.

 Besides, how is it any different than:

 enum { Mouse, Key, Move };


 
 It's not an enumerated constant. Mouse, Key, and Move are all types,
 and Event is a discriminated union of the three. See more below.
 

 match(event) is no different than switch(event), except that pattern
 matching often implies runtime semantics and is often slower than a straight
 jump table generated from a switch.


 
 Not in this case. See, when you would do "type Event = Mouse | Key |
 Move", it's actually more like doing:
 
 struct Event
 {
     enum Type { Mouse, Key, Move }
     Type type;
     union
     {
         Mouse m;
         Key k;
         Move v;
     }
 }
 
 Then, when you do "match(e) { Mouse m => ... }" it's actually being turned
into:
 
 switch(e.type)
 {
     case Event.Type.Mouse: alias e.m m; ...
     case Event.Type.Key: alias e.k k; ...
 }
 
 Basically discriminated unions get rid of this annoying boilerplate
 that you have to use every time you want a tagged union.


Oh, that makes sense, but I don't see why you need language support for 
that, a variant type should be able to get most of it using type tuples, 
maybe just add support to switch on type tuples along with an opSwitch() 
method:

alias Algebraic!(Mouse, Key, Move) Event;

final switch(Event) {
case Mouse:
case Key:
case Move:
}

Jeremie
Sep 26 2009
next sibling parent Jarrett Billingsley <jarrett.billingsley gmail.com> writes:
On Sat, Sep 26, 2009 at 4:50 PM, Jeremie Pelletier <jeremiep gmail.com> wrote:


 Oh, that makes sense, but I don't see why you need language support for
 that, a variant type should be able to get most of it using type tuples,
 maybe just add support to switch on type tuples along with an opSwitch()
 method:


I'm pretty sure D2's std.typecons has something that almost does just
that. I don't know how it handles dispatching though.
Sep 26 2009
prev sibling parent language_fan <foo bar.com.invalid> writes:
Sat, 26 Sep 2009 16:50:36 -0400, Jeremie Pelletier thusly wrote:


 Jarrett Billingsley wrote:

 On Sat, Sep 26, 2009 at 4:18 PM, Jeremie Pelletier <jeremiep gmail.com>
 wrote:
 

  type Event = Mouse | Key | Move;


 This can be confusing, for example the first thing that comes to mind
 for me is that Event is the bitwise OR result of 3 constants, not an
 enumerated type.

 Besides, how is it any different than:

 enum { Mouse, Key, Move };


 
 It's not an enumerated constant. Mouse, Key, and Move are all types,
 and Event is a discriminated union of the three. See more below.
 

 match(event) is no different than switch(event), except that pattern
 matching often implies runtime semantics and is often slower than a
 straight jump table generated from a switch.


 
 Not in this case. See, when you would do "type Event = Mouse | Key |
 Move", it's actually more like doing:
 
 struct Event
 {
     enum Type { Mouse, Key, Move }
     Type type;
     union
     {
         Mouse m;
         Key k;
         Move v;
     }
 }
 
 Then, when you do "match(e) { Mouse m => ... }" it's actually being
 turned into:
 
 switch(e.type)
 {
     case Event.Type.Mouse: alias e.m m; ... case Event.Type.Key: alias
     e.k k; ...
 }
 
 Basically discriminated unions get rid of this annoying boilerplate
 that you have to use every time you want a tagged union.


 
 Oh, that makes sense, but I don't see why you need language support for
 that, a variant type should be able to get most of it using type tuples,
 maybe just add support to switch on type tuples along with an opSwitch()
 method:
 
 alias Algebraic!(Mouse, Key, Move) Event;
 
 final switch(Event) {
 case Mouse:
 case Key:
 case Move:
 }


It does not need language support, but is considered fundamental in some 
languages, thus offered as built-in construct. Yep, my code was a bit 
hastily written. Of course I meant the enumerated entities also support 
subtype relation in an OOP language. For an example, see case classes in 
Scala. Even in Java enums are more powerful than in D - the only 
advantage D has is the conversion rules with primitive types.
Sep 26 2009
prev sibling next sibling parent reply Lutger <lutger.blijdestijn gmail.com> writes:
Justin Johansson wrote:

...

 
 I've got about 2 dozen types in the variant so the O(n) really hurts.
 The variant thing seemed like a really cool idea at the time but now ...
 Without something like suggested above or a computed goto on typeid or
 Andrei's visitator, it almost pushes me to backout from using variants and
 having to redesign around some common base class or interface and using
 virtual function dispatch. :-(


You can use a hash literal as a jump table but it's an unsafe hack and 
probably not performant depending on what you need to do. Maybe it's easier 
still to write the visitation code yourself or generate code with ctfe than 
to redesign to common base classes.

a hash literal works like this, index with the typeid to get a function ptr 
you can call:

Algebraic!(int, Foo) a;
a = 3;
[ typeid(int) : function { writeln("a is int"); },
  typeid(Foo) : function { writeln("a is Foo"); }
] [a.type] ();
Sep 26 2009
parent language_fan <foo bar.com.invalid> writes:
Sat, 26 Sep 2009 18:28:52 +0200, Lutger thusly wrote:


 a hash literal works like this, index with the typeid to get a function
 ptr you can call:
 
 Algebraic!(int, Foo) a;
 a = 3;
 [ typeid(int) : function { writeln("a is int"); },
   typeid(Foo) : function { writeln("a is Foo"); }
 ] [a.type] ();


A visitor approach might have a bit slower coefficient than the hash, but 
the same time complexity.
Sep 26 2009
prev sibling parent reply Jarrett Billingsley <jarrett.billingsley gmail.com> writes:
On Sat, Sep 26, 2009 at 10:36 AM, Justin Johansson
<procode adam-dott-com.au> wrote:


 I've got about 2 dozen types in the variant so the O(n) really hurts.
 The variant thing seemed like a really cool idea at the time but now ...
 Without something like suggested above or a computed goto on typeid or
Andrei's visitator,
 it almost pushes me to backout from using variants and having to redesign
around some common base class or interface and using virtual function dispatch.
:-(


Ouch. 2 dozen types? No offense, but that sounds like "you're doing it
wrong." Revising your strategy is probably for the best.

What are you doing, anyway?
Sep 26 2009
parent reply Justin Johansson <procode adam-dott-com.au> writes:
Jarrett Billingsley Wrote:


 On Sat, Sep 26, 2009 at 10:36 AM, Justin Johansson
 <procode adam-dott-com.au> wrote:
 

 I've got about 2 dozen types in the variant so the O(n) really hurts.
 The variant thing seemed like a really cool idea at the time but now ...
 Without something like suggested above or a computed goto on typeid or
Andrei's visitator,
 it almost pushes me to backout from using variants and having to redesign
around some common base class or interface and using virtual function dispatch.
:-(


 
 Ouch. 2 dozen types? No offense, but that sounds like "you're doing it
 wrong." Revising your strategy is probably for the best.
 
 What are you doing, anyway?



Sorry I can't go too much into the confidential details of this
particular project.  However if you remember when I joined this
group, what is it, 3 weeks ago I gave a short bio of myself by
way of introduction.

So knowing my background in electrical engineering, maths & physics
and being a C++ hacker of 20 or so years, you might well guess
that my specialist domain is in industrial control and scientific
data analysis.  You might say its about real-time, high-speed
gaming (discrete and analog sensor inputs instead of joy sticks)
but without any GUI :-)

There is currently a desire to fit a scripting layer over a highly
tuned core application (written in C/C++) that works with
strongly-typed, mostly numeric value-based data.  Typing in this
sense largely means range-checked. So, picking a simple example,
an integer in the range [0..999] is a different data type to another
in the range say [-4000..4000].  Most of the datatypes (size-wise)
fit conveniently into a union of (short, int, float, double), but,
it's the value space of the data that determines its type.

The primitive numeric types are typedef'ed in C++ code. So you might
have, eg, typedef int16 sensor1_t; representing the range checked value
[0..999] from sensor type 1.  All in all there's about 18 different
primitive data types. (btw. this explains the reason for asking the
"is typedef an alien in D" question on this forum a few days ago).

More complex datatypes in this system are composed as tuples of the
"primitive" datatypes in the system-wide data dictionary.  Accordingly
there's a lot of variable-width data and this is demanding on heap
allocation.

So that's the background in vanilla terms.  The scripting layer is
essentially a DSL.  It's been decided to use a strongly-typed FP
paradigm for this exercise and with a leaning towards immutable data.

Hopefully this design decision will make for easier system T&A (test
and acceptance).

Now looking into different language options for constructing this
DSL, no question about it; the implementing language must support GC.

So far I've considered Java and Scala but there are performance-
crippling JNI issues.  Also given C language interoperability plus GC,
right now D is looking like a much better bet.

Besides, aside some compiler bug issues, D looks like a lot more fun :-)


Getting back to core business, both memory and speed criteria are
important for this project.  I'm hoping to use primitive data types,
rather than wrapping low-level data in an object, to get a performance
benefit.

Up until now, Andrei's discriminated union (aka variant) was looking
like a good idea, using probably about half the memory(***) compared with
the everything-is-an-object approach in Java.  For my application, I'd
be using the general Algebraic form rather than the standard Variant to
model my 18 primitive data types.

*** btw. Here's some miscellaneous links wrt Java object overhead:

http://www.javamex.com/tutorials/memory/object_memory_usage.shtml

http://devblog.streamy.com/2009/07/24/determine-size-of-java-object-class/

http://www.javaspecialists.eu/archive/Issue142.html


At the end of the day, if I can get this thing to fly using D, it will,
at least to me, prove that D is a killer language.


Thanks for listening.

-- Justin Johansson
Sep 26 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Justin Johansson wrote:

 At the end of the day, if I can get this thing to fly using D, it will,
 at least to me, prove that D is a killer language.


One way or another you will, and if you have difficulties let us hear of 
them. Practical experience with Algebraic and friends is very valuable.

Andrei
Sep 26 2009
parent Justin Johansson <procode adam-dott-com.au> writes:
Andrei Alexandrescu Wrote:


 Justin Johansson wrote:

 At the end of the day, if I can get this thing to fly using D, it will,
 at least to me, prove that D is a killer language.


 
 One way or another you will, and if you have difficulties let us hear of 
 them. Practical experience with Algebraic and friends is very valuable.
 
 Andrei


Thanks, Andrei, for your very encouraging and supportive comments.

My feeling is that I should stick with the new design using Algebraic even if
the current regime means I need to use a long series of if else if else's.

By the time I get towards finishing this project, matters may well have
improved in std.variant and then I can easily upgrade my code at no cost.

OTOH, to go backtracking at this time, to one of the old schools of
(1) non-discriminated unions or (2) everything-is-an-object
just to work around a current deficency in std.variant would almost certainly
be an extremely bad software engineering design decision, and having serious
impact upon both runtime performance and code maintainability.

It would also do absolutely nothing to improve the enjoyment and quality of my
life :-)

The beauty of my current design is that it appropriately addresses the 80/20
rule
of where time and money should be spent in a project of this nature.

Further, and worth mentioning given another raging thread on this forum at the
moment,
it turns out the ensuring type-safety of my design means that NPE's are a thing
of the
past (for me at least).  This is due to strong static type checking together
with runtime type
validation all for a pretty reasonable cost.

So it's pretty obvious which side of the fence I'm on in the null ref redux
debate.

Cheers
Justin
Sep 26 2009
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Justin Johansson wrote:

 I've had a good poke around the forums and couldn't find anything on this so
...
 
 What's the recommended method for dispatching code off the runtime type of a
variant variable
 (Phobos D2 std.variant)?
 
 Does one use a bunch of
 
 if ( var.peek!(type1)) { ... }
 else if ( var.peek!(type2)  { ... }
 
 for all N possible types, or is there a better & faster way with a switch or
jump table of sorts?
 
 Thanks all.
 
 -- Justin Johansson


I'd planned to implement visitation for Variant, but never got around to it.

Andrei
Sep 26 2009
prev sibling next sibling parent reply #ponce <aliloko gmail.com> writes:
 Exactly, this is what I mentioned previously. Isn't it ugly compared to
 
   type Event = Mouse | Key | Move;
 
   void dispatchEvent(Event event) {
     match(event) {
       Mouse m => m.squeek();
       Key k => ...
       ...
     }
   }
 
 What's with all the language proposals here? Why hasn't anyone proposed 
 this before? This is in fact very helpful - that's why several modern 
 languages have adopted it.


Algebraic data types are indeed a neat feature.
But the languages which implemented this (ML, Haskell, scala...) seems only to
be functionals one. 
I suppose it's because it replaces enums and unions for those. In procedural
languages one can emulate this with 1 enum + 1 union.

I would prefer having some computed goto (through final switch).
Sep 26 2009
parent language_fan <foo bar.com.invalid> writes:
Sat, 26 Sep 2009 18:51:19 -0400, #ponce thusly wrote:


 Exactly, this is what I mentioned previously. Isn't it ugly compared to
 
   type Event = Mouse | Key | Move;
 
   void dispatchEvent(Event event) {
     match(event) {
       Mouse m => m.squeek();
       Key k => ...
       ...
     }
   }
 
 What's with all the language proposals here? Why hasn't anyone proposed
 this before? This is in fact very helpful - that's why several modern
 languages have adopted it.


 
 Algebraic data types are indeed a neat feature. But the languages which
 implemented this (ML, Haskell, scala...) seems only to be functionals
 one. I suppose it's because it replaces enums and unions for those. In
 procedural languages one can emulate this with 1 enum + 1 union.
 
 I would prefer having some computed goto (through final switch).


Agreed.

On the other hand I cannot fully agree that Scala is more a functional 
language than something else. The core is both object oriented and 
functional. It is even more object oriented (purer) than most mainstream 
C-like languages. By this I mean that in my opinion it is not impossible 
to imagine that D also implemented something like case classes and 
extended switch to handle also simple patterns.
Sep 26 2009
prev sibling parent reply Christopher Wright <dhasenan gmail.com> writes:
Justin Johansson wrote:

 I've had a good poke around the forums and couldn't find anything on this so
...
 
 What's the recommended method for dispatching code off the runtime type of a
variant variable
 (Phobos D2 std.variant)?
 
 Does one use a bunch of
 
 if ( var.peek!(type1)) { ... }
 else if ( var.peek!(type2)  { ... }
 
 for all N possible types, or is there a better & faster way with a switch or
jump table of sorts?


Variant should have an accessible typeinfo property. (When I say should, 
I mean that it would be appropriate for it to have it. I am not saying 
that I believe it has it.) It should be faster to compare that (or 
switch on typeinfo.name) than to peek for each type.
Sep 26 2009
next sibling parent Justin Johansson <procode adam-dott-com.au> writes:
Christopher Wright Wrote:


 Justin Johansson wrote:

 I've had a good poke around the forums and couldn't find anything on this so
...
 
 What's the recommended method for dispatching code off the runtime type of a
variant variable
 (Phobos D2 std.variant)?
 
 Does one use a bunch of
 
 if ( var.peek!(type1)) { ... }
 else if ( var.peek!(type2)  { ... }
 
 for all N possible types, or is there a better & faster way with a switch or
jump table of sorts?


 
 Variant should have an accessible typeinfo property. (When I say should, 
 I mean that it would be appropriate for it to have it. I am not saying 
 that I believe it has it.) It should be faster to compare that (or 
 switch on typeinfo.name) than to peek for each type.


Thanks, there is and I was considering that.

    TypeInfo type()
    {
        TypeInfo result;
        fptr(OpID.getTypeInfo, null, &result);
        return result;
    }

Would you need a full char-by-char string compare or could you cook it on the
basis of a string memory address == comparison?
(Sorry, I'm a veteran C++'er not a fully-fledged D'er yet).
Sep 26 2009
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Christopher Wright wrote:

 Justin Johansson wrote:

 I've had a good poke around the forums and couldn't find anything on 
 this so ...

 What's the recommended method for dispatching code off the runtime 
 type of a variant variable
 (Phobos D2 std.variant)?

 Does one use a bunch of

 if ( var.peek!(type1)) { ... }
 else if ( var.peek!(type2)  { ... }

 for all N possible types, or is there a better & faster way with a 
 switch or jump table of sorts?


 
 Variant should have an accessible typeinfo property.


It does, see member function type().

Andrei
Sep 26 2009
prev sibling parent reply Jeremie Pelletier <jeremiep gmail.com> writes:
Christopher Wright wrote:

 Justin Johansson wrote:

 I've had a good poke around the forums and couldn't find anything on 
 this so ...

 What's the recommended method for dispatching code off the runtime 
 type of a variant variable
 (Phobos D2 std.variant)?

 Does one use a bunch of

 if ( var.peek!(type1)) { ... }
 else if ( var.peek!(type2)  { ... }

 for all N possible types, or is there a better & faster way with a 
 switch or jump table of sorts?


 
 Variant should have an accessible typeinfo property. (When I say should, 
 I mean that it would be appropriate for it to have it. I am not saying 
 that I believe it has it.) It should be faster to compare that (or 
 switch on typeinfo.name) than to peek for each type.


I wouldn't make that rely on string switch. While it's a very convenient 
feature to have in D that's usually only seen in scripting, its also a 
*slow* one when compared to integral switch.

string switch actually walks the case strings and compares with the 
source string until it finds a match, a binary search is much faster if 
you don't care about the order of the tests.

Also if someone strips his executable from all names in TypeInfo and 
ClassInfo to prevent people from peeking into his internals, it breaks 
the code. Some companies out there goes to great lengths to make their 
executables as hard to reverse engineer as possible.

A good alternative would be for the algebraic type to define an internal 
enum which is used for switch statements:

alias Algebraic!(int, void*, Object) MyType;

switch(myType.typeId) {
case MyType.INT:
case MyType.VOIDPTR:
case MyType.OBJECT:
}

While not perfect it definitely is fast.
Sep 26 2009
parent reply Jarrett Billingsley <jarrett.billingsley gmail.com> writes:
On Sat, Sep 26, 2009 at 11:16 PM, Jeremie Pelletier <jeremiep gmail.com> wrote:


 string switch actually walks the case strings and compares with the source
 string until it finds a match, a binary search is much faster if you don't
 care about the order of the tests.


FWIW the runtime does perform a binary search of the strings in a
switch. The compiler outputs the string table as a sorted list.
Sep 26 2009
parent Jeremie Pelletier <jeremiep gmail.com> writes:
Jarrett Billingsley wrote:

 On Sat, Sep 26, 2009 at 11:16 PM, Jeremie Pelletier <jeremiep gmail.com> wrote:
 

 string switch actually walks the case strings and compares with the source
 string until it finds a match, a binary search is much faster if you don't
 care about the order of the tests.


 
 FWIW the runtime does perform a binary search of the strings in a
 switch. The compiler outputs the string table as a sorted list.


Oh, you're right! I just checked in druntime.
Sep 26 2009