Type polymorphism and type variance

[Ali Çehreli]

On 12/05/2012 04:40 PM, js.mdnq wrote:
 > On Wednesday, 5 December 2012 at 22:53:11 UTC, Ali Çehreli wrote:
 >> On 12/05/2012 09:51 AM, js.mdnq wrote:
 >>
 >> > (if your having trouble understanding the problem then just
 >> think of how
 >> > you would efficiently store the nodes and edges of a directed
 >> acyclic
 >> > graph. Each node is of a somewhat arbitrary type and edges
 >> are functions
 >> > over the nodes that do computations, possibly changing the
 >> nodes
 >> > "value". These all need to be stored someway so that a full
 >> computation
 >> > chain can be carried out(the graph structure is arbitrary).)
 >>
 >> I do not fully understand the issue yet but I smell "double dispatch"
 >> in there. There is no elegant solution of double dispatch at least in
 >> C++ but there are a number of solutions with certain compromises. I
 >> will read your post more carefully later.
 >>
 >> Ali
 >
 > Thanks, I'll look at yours too when my head is more clear. I did have a
 > better post but it didn't get through.
 >
 > Here is possibly a better overview:
 >
 > http://faculty.ucr.edu/~hanneman/nettext/Figure7_11.jpg
 >
 > is a good representation of what I'm trying to do.
 >
 > The way I'm thinking about it is that for each node there is a function
 > that takes the data from all the other nodes that are coming to it.
 >
 > So, A's function is nill, B's function takes 2 values A.Data and D.Data,
 > C's function takes B.Data and C.Data, D's function takes B.Data and
 > E.Data, and E's function takes B.Data.
 >
 > Each function is different as it will not necessarily be the same
 > computation and the data in each node can be of a different type.
 >
 > This is easy to do by just passing around an array of objects and their
 > types then using a switch to typecast. Each "function" know exactly what
 > data it's trying to use though unless the "user" made a mistake as they
 > will supply the function they want to use.
 >
 > The edge direction also specifies the flow the computations as I will
 > iterate through the graph computing values on nodes. In my case I will
 > expect that a "cycle" of computations will be nilpotent. This keeps any
 > sequence of computations from creating unstable data that does stuff
 > like "toggles" back and forth or jumping around after each computation.
 >
 > For example,
 >
 > If A.Data is an int, B.Data is a bool, and D.Data is a double then the
 > user will supply a function that takes an int and a double that returns
 > a bool.
 >
 >
 > There just has to be a better way that avoids casting everything to an
 > object and using the very slow variant type. ;/ The issue is mainly
 > about storing the objects because this is very easy to do statically.
 >
 > Thanks again.
 >

Here is a solution that stores the types of the points in delegates. 
That is the "static information" that we know at compile time:

import std.stdio;

/* Although this can be a polymorphic type, I am assuming that all of 
the edge
  * handlers will produce the same type of result. */
struct HandlingResult
{}

/* This is the edge handler for (int, double) as well as (double, int). (See
  * below.) */
HandlingResult edgeHandler(int i, double d)
{
     writefln("Handling %s and %s", i, d);
     return HandlingResult();
}

struct S
{
     int i;
}

/* This is the edge handler for (int, S) and (S, int). */
HandlingResult edgeHandler(int i, S s)
{
     writefln("Handling %s and %s", i, s);
     return HandlingResult();
}

/* This defines what gets done with edges. */
interface IEdge
{
     HandlingResult handle();
}

class Edge(T0, T1) : IEdge
{
     alias HandlingResult function(T0, T1) Handler;

     /* Each edge consists of two values and a handling function. */
     T0 value0;
     T1 value1;
     Handler func;

     this(T0 value0, T1 value1, Handler func)
     {
         this.value0 = value0;
         this.value1 = value1;
         this.func = func;
     }

     /* Simply dispatches to the corresponding function. */
     HandlingResult handle()
     {
         return func(value0, value1);
     }
}

/* I've imagined that the function that handles int,double would handle
  * double,int as well. This template tries the arguments both ways.
  *
  * Note 1: This is just a draft. It should probably also detect 
ambiguities.
  *
  * Note 2: I had to use delegates as I think there is no way of taking the
  * address of a specific overload of a function.
  */
template HandlerFuncSelector(T0, T1)
{
     static if (__traits(compiles, edgeHandler(T0.init, T1.init))) {
         enum result = (T0 a, T1 b) => edgeHandler(a, b);

     } else static if (__traits(compiles, edgeHandler(T1.init, T0.init))) {
         enum result = (T0 a, T1 b) => edgeHandler(b, a);

     } else {
         static assert(false, "No edgeHandler("
                       ~ T0.stringof ~ ", " ~ T1.stringof ~ ") defined");
     }
}

/* The convenience function to make an Edge after choosing its handler. */
Edge!(T0, T1) edge(T0, T1)(T0 value0, T1 value1)
{
     return new Edge!(T0, T1)(value0, value1,
                              HandlerFuncSelector!(T0, T1).result);
}

void main()
{
     IEdge[] edges;

     /* These will be handled by edgeHandler(int,double). */
     edges ~= edge(1, 1.5);
     edges ~= edge(2.5, 2);

     /* These will be handled by edgeHandler(int,S). */
     edges ~= edge(3, S(100));
     edges ~= edge(S(200), 4);

     foreach (edge; edges) {
         edge.handle();
     }
}

Ali