I suspect that templates are the answer, but I haven't really thought through applying it to the problem you pose.

"Bill Cox" <bill@viasic.com> wrote in message news:3E57E58F.4080108@viasic.com...
> Hi, Walter.
>
> Walter wrote:
> > "Bill Cox" <bill@viasic.com> wrote in message news:3E57BCC7.6050301@viasic.com...
> >
> >>If it could just support directed graphs well, I'd be happy.
> >
> >
> > Could you elaborate, please? (I apologize if you have before.)
>
> Sure.  It's somewhat complicated.  I wish I could sumarize the problems in one or two lines, but I can't.
>
> Just to jump ahead, I think a good solution can be found in Sather. Their "reuse" construct looks easy to implement (of course, templates looked easy too...).  Ken Carpenter's suggested "framwork" idea seems to also work well.
>
> If you look at the non-reusable pseudo-code I posted for the Pizza Contest, I think you'll find it both readable, and likely to lead to an efficient implementation (Ok, I haven't compiled it yet... you'll probably find that I've got glaring errors).  I think when you see the reusable versions people hopefully will write for the contest, you'll see that they are either very complex, or not very efficient.  With a "reuse" construct, I think you could directly reuse the simple and otherwise non-reusable version.
>
> First, let's look at why the pseudo code I suggested is not reusable in D.  This is simple.  Inheriting from Node, Edge, and Graph is the only way to reuse this code, since it wasn't defined as an interface or template.  If Netlist were to inherit from Graph, it would inherit a linked list of nodes, but what I asked for was two doubly linked lists, one of Instances, and one of Nets.  Similar problems occur with the other classes.  We also run into the problem of having to do lots casts to derived classes if we ever want to traverse the derived objects.
>
> Let's try that again, but this time with templates.  Graph, Node, and Edge could all be rewritten to be template classes, and the container classes could be provided by the user.  But all that does is let us define various kinds of directed graphs.  It doesn't allow me to directly embed graph functionality in my netlist.  The two doubly linked lists in Netlist are not easily going to get defined by using the Graph template class.  You'd have to do something goofy like inherit from two versons of the Graph template at the same time.  It's all down-hill from there.
>
> Ken Carpenter suggested making Graph, Node, and Edge template classes
> that inherit from template parameters.  This may actually lead to the
> winning implementation, but I think it's going to be pretty convoluted.
>   Frankly, if a programmer didn't shoot himself in the foot with such
> code, I'd buy a gun and shoot it for him.
>
> How about using interfaces?  This actually works, but has some issues.
> Now we have to define a large interface that mimics every method and
> attribute used in the pseudo code.  It could be dozens of methods.
> Every one of them has to be defined by the user.  Worse, every time I
> add a graph related atribute or method to the Graph interface, every
> user has to upgrade his code, even if he doesn't need the new graph
> functionallity.  There are all kinds of attributes that would eventually
> be needed.  For example, we have a level attribute in our simple code
> for the contest.  There are other problems.  The foreach(Graph, node)
> functionality would have to be done with some sort of virtual iterator.
>   When writing the foreach loop in the Graph code, you can't just
> instantiate the iterator on the stack as you would in C++, because you
> don't know it's size.  That's determined by the user's choice of
> contaner class, which is hidden behind the interface.  You have to use
> something like Java Enumeration interfaces, which leads to pretty slow
> code.  The darned iterators are going to wind up on the heap!  Finally,
> there's the potential overhead of lots of virtual function calls since
> everything is done through an interface.  However, if the D compiler
> were to do global optimizations across modules, it might succeed in
> binding most of them statically.
>
> It seems to me that writing a good reusable graph module in D is hard. I think it should make for an interesting contest, if I can get any competitors interested.  If someone could show me how to do a really good one that D specifically enables, I think I'd ask my company to start using D, since we currently have to rewrite basic code like this every day in C.
>
> I haven't used the Sather "reuse" constructs before, so I don't know what hidden pitfalls are there.  However, it seems to mimic what I do today in C: copy the functions and class attributes from one module and paste them into my new module, and then rename things to make it all work.  It's very similar to the "framwork" stuff Ken Carpenter was talking about, which also seems like it would do the trick.
>
> I sure hope I'm wrong about all this, and someone just shows me how to reuse code...  It would definately be worth the 30 bucks for pizza.
>
> Bill
>

"Patrick Down" <pat@codemoon.com> wrote in message news:Xns932AB5EFBBD40patcodemooncom@63.105.9.61...
> Actually it was me but to give credit where credit is due I got the the framework idea from an article by Tim Sweeney.
>
> http://www.gamespy.com/legacy/articles/devweek_b.shtm

A great read. The article lists as a new requirement:

"The language needs to support "function references bound to specific objects;" such entities (unsupported in C++ and Java) are the essential glue for binding parametric components together; without them, you often have to write an enormous amount of "duct tape" code to hold a framework together."

D does this with delegates.

I didn't really understand what they were talking about with inner classes, and why the same effect could not be achieved by simply adding a pointer to a class as a member of the framework class.

Patrick Down wrote:
> Bill Cox <bill@viasic.com> wrote in news:3E57E58F.4080108@viasic.com:
> 
> 
>>Hi, Walter.
>>
>>Walter wrote:
>>
>>>"Bill Cox" <bill@viasic.com> wrote in message
>>>news:3E57BCC7.6050301@viasic.com...
>>>
>>>
>>>>If it could just support directed graphs well, I'd be happy.
>>>
>>>
>>>Could you elaborate, please? (I apologize if you have before.)
>>
>>Sure.  It's somewhat complicated.  I wish I could sumarize the
>>problems in one or two lines, but I can't.
>>
>>Just to jump ahead, I think a good solution can be found in Sather. Their "reuse" construct looks easy to implement (of course, templates looked easy too...).  Ken Carpenter's suggested "framwork" idea seems
>>to also work well.
> 
> 
> Actually it was me but to give credit where credit is due I got the
> the framework idea from an article by Tim Sweeney.

Oops... Sorry Patrick.  Ken suggested the pizza link.


> http://www.gamespy.com/legacy/articles/devweek_b.shtm
> 
> A notable quote is...
> <quote>
> While object-oriented languages handled pure objects well, they modeled
> complex relationships between objects poorly. Frameworks and collections
> turn out not to be truly modular or extensible because the languages
> can't represent families of objects. </quote>

This is the short version of what goes wrong representing graphs.  With only one class, like with a binary tree, you're in good shape.  As soon as the data structures involve multiple inter-related classes, reuse gets hard.

Bill

Walter wrote:
> "Patrick Down" <pat@codemoon.com> wrote in message
> news:Xns932AB5EFBBD40patcodemooncom@63.105.9.61...
> 
>>Actually it was me but to give credit where credit is due I got the
>>the framework idea from an article by Tim Sweeney.
>>
>>http://www.gamespy.com/legacy/articles/devweek_b.shtm
> 
> 
> A great read. The article lists as a new requirement:
> 
> "The language needs to support "function references bound to specific
> objects;" such entities (unsupported in C++ and Java) are the essential glue
> for binding parametric components together; without them, you often have to
> write an enormous amount of "duct tape" code to hold a framework together."
> 
> D does this with delegates.
> 
> I didn't really understand what they were talking about with inner classes,
> and why the same effect could not be achieved by simply adding a pointer to
> a class as a member of the framework class.

Hi.

I agree, it's a really good artical.  I tend to focus more on what he calls "virtual classes", more than delegates.  I haven't ever seemed to need delegates, so I'm unfamiliar with the problem he's solving.

If I read it right, "virtual classes" are simply classes that can be replaced (just like virtual functions).  You define a higher level containing class, inherit the whole thing, and replace classes that need custom definitions for your app.

A lot of programmers and languages use the concept of a class to replace the concept of a module.  Personally, I prefer a module to be named a "module", and the classes within "classes".

If you rename entities a bit, I think you'll see that Patrick Down's "frameworks" and "virtual classes" are essentially the same thing.  As far as I can tell, they are also very similar to Sather's "reuse" construct.  All of these have one thing in common:  They let me inherit all the code in a module into my module, while letting me replace the things that don't work for me.  This is very much like class inheritance, where I get to fix the methods by overriding them. However, it applies at a module level.

I think this is what it takes to reuse code with multiple inter-relating classes cleanly.  Of these concepts, Sather's reuse concept seems to me to be the most straight-forward to implement.  It also seems easier to explain to people.  I wouldn't like to have to teach "virtual classes" to new programmers.  However the "reuse" stuff looks like what they already do: copy, paste, and edit.  I can explain it in terms of actions rather than higher-level polymorphism.

On the other hand, a lot of C++ programmers might give D a serious look if they though they could achieve higher level polymorphism through virtual classes.  Marketing is everything.  Mabe D should incorporate Strategic Programming, too :-)

Bill

"Bill Cox" <bill@viasic.com> wrote in message news:3E584E7A.2060908@viasic.com...
> If I read it right, "virtual classes" are simply classes that can be replaced (just like virtual functions).  You define a higher level containing class, inherit the whole thing, and replace classes that need custom definitions for your app.

That's the way I read it, too, but how is it different from (in C++):

    class Foo
    {
        class Bar *p;
    };

where you can inherit from Foo, derive from Bar, and replace p?

> A lot of programmers and languages use the concept of a class to replace the concept of a module.  Personally, I prefer a module to be named a "module", and the classes within "classes".

So do I. I discovered quite by accident that the module concept makes the C++ concept of "friends" irrelevant. That was a nice surprise. Modules are so much more natural.


> If you rename entities a bit, I think you'll see that Patrick Down's "frameworks" and "virtual classes" are essentially the same thing.  As far as I can tell, they are also very similar to Sather's "reuse" construct.  All of these have one thing in common:  They let me inherit all the code in a module into my module, while letting me replace the things that don't work for me.  This is very much like class inheritance, where I get to fix the methods by overriding them. However, it applies at a module level.
>
> I think this is what it takes to reuse code with multiple inter-relating classes cleanly.

Yup, the 'friend' issue.

> Of these concepts, Sather's reuse concept seems to me
> to be the most straight-forward to implement.  It also seems easier to
> explain to people.  I wouldn't like to have to teach "virtual classes"
> to new programmers.  However the "reuse" stuff looks like what they
> already do: copy, paste, and edit.  I can explain it in terms of actions
> rather than higher-level polymorphism.
>
> On the other hand, a lot of C++ programmers might give D a serious look if they though they could achieve higher level polymorphism through virtual classes.  Marketing is everything.  Mabe D should incorporate Strategic Programming, too :-)

I think I'll just find a way to bury all those buzzwords into the D spec so that D pops up when people google on them <g>.

"Bill Cox" <bill@viasic.com> schrieb im Newsbeitrag news:3E57BCC7.6050301@viasic.com...

> If it could just support directed graphs well, I'd be happy.

Hi, I'm very interested in this graph stuff as well. But sorry, I can't code it for some pizza ;-)) even it would be a lot of fun. Anyway, graphs are on my todo list for some other project I need them for.

I highly suggest to take a look at these links: http://www.mpi-sb.mpg.de/LEDA/leda.html http://www.algorithmic-solutions.de/leda.htm

I have used the LEDA graph stuff some years ago. Very advanced and well done. Easy to use as plug-in etc. That's the concept I want to use to do it in D.

What I'm mostly interested in is doing persistens graphs and traversal of persistens graphs. Perhaps using Berkely DB as base... Just thinking loud.

--
Robert M. Münch
IT & Management Freelancer
Mobile: +49 (0)177 2452 802
Fax   : +49 (0)721 8408 9112
Web   : http://www.robertmuench.de

In article <b38jlm$1nb9$1@digitaldaemon.com>, Walter says...
>
>
>"Mark Evans" <Mark_member@pathlink.com> wrote in message news:b37347$cdr$1@digitaldaemon.com...
>> http://www.paulgraham.com/fix.html
>
>D: C++ is too complicated
; Java, C# use VMs and don't have generics

Walter wrote:
> "Bill Cox" <bill@viasic.com> wrote in message
> news:3E584E7A.2060908@viasic.com...
> 
>>If I read it right, "virtual classes" are simply classes that can be
>>replaced (just like virtual functions).  You define a higher level
>>containing class, inherit the whole thing, and replace classes that need
>>custom definitions for your app.
> 
> 
> That's the way I read it, too, but how is it different from (in C++):
> 
>     class Foo
>     {
>         class Bar *p;
>     };
> 
> where you can inherit from Foo, derive from Bar, and replace p?
> 

I think the idea is that Foo could just use Bar instances without regard for polymorphism, and it would all just work if you subclassed Foo and Bar.  Existing Foo methods would use the derived class.

class Baz : Foo
{
   class Bleagh : Bar { ... }
   // Foo methods will use Bleagh instead of Bar
}

In languages like D, this is a simple matter of using a method of Foo as a factory; subclass and override that to return new instances of your derived class, and you're gold.  Override the factory, and everything uses the new inner class.

> 
>>A lot of programmers and languages use the concept of a class to replace
>>the concept of a module.  Personally, I prefer a module to be named a
>>"module", and the classes within "classes".
> 
> 
> So do I. I discovered quite by accident that the module concept makes the
> C++ concept of "friends" irrelevant. That was a nice surprise. Modules are
> so much more natural.
> 
> 
> 
>>If you rename entities a bit, I think you'll see that Patrick Down's
>>"frameworks" and "virtual classes" are essentially the same thing.  As
>>far as I can tell, they are also very similar to Sather's "reuse"
>>construct.  All of these have one thing in common:  They let me inherit
>>all the code in a module into my module, while letting me replace the
>>things that don't work for me.  This is very much like class
>>inheritance, where I get to fix the methods by overriding them.
>>However, it applies at a module level.
>>
>>I think this is what it takes to reuse code with multiple inter-relating
>>classes cleanly.
> 
> 
> Yup, the 'friend' issue.
> 
> 
>>Of these concepts, Sather's reuse concept seems to me
>>to be the most straight-forward to implement.  It also seems easier to
>>explain to people.  I wouldn't like to have to teach "virtual classes"
>>to new programmers.  However the "reuse" stuff looks like what they
>>already do: copy, paste, and edit.  I can explain it in terms of actions
>>rather than higher-level polymorphism.
>>
>>On the other hand, a lot of C++ programmers might give D a serious look
>>if they though they could achieve higher level polymorphism through
>>virtual classes.  Marketing is everything.  Mabe D should incorporate
>>Strategic Programming, too :-)
> 
> 
> I think I'll just find a way to bury all those buzzwords into the D spec so
> that D pops up when people google on them <g>.
> 
> 

Hi, Robert, and Thanks for the links.

Robert M. Münch wrote:
> "Bill Cox" <bill@viasic.com> schrieb im Newsbeitrag
> news:3E57BCC7.6050301@viasic.com...
> 
> 
>>If it could just support directed graphs well, I'd be happy.
> 
> 
> Hi, I'm very interested in this graph stuff as well. But sorry, I can't code
> it for some pizza ;-)) even it would be a lot of fun. Anyway, graphs are on
> my todo list for some other project I need them for.
> 
> I highly suggest to take a look at these links:
> http://www.mpi-sb.mpg.de/LEDA/leda.html
> http://www.algorithmic-solutions.de/leda.htm
> 
> I have used the LEDA graph stuff some years ago. Very advanced and well
> done. Easy to use as plug-in etc. That's the concept I want to use to do it
> in D.
> 
> What I'm mostly interested in is doing persistens graphs and traversal of
> persistens graphs. Perhaps using Berkely DB as base... Just thinking loud.

It sounds like they have some good software.  Their "Network" algorithm components sound like the kind of thing I do a lot.

I read some of their on-line documentation.  You have to create graphs in their database, run their algorthms, and then read out the results. It's not really reusable code.  For example, you couldn't use it to add graph functionality to hyper-graphs.

Bill

"Walter" <walter@digitalmars.com> wrote in news:b3a0o8$2sbt$1@digitaldaemon.com:

> 
> "Bill Cox" <bill@viasic.com> wrote in message news:3E584E7A.2060908@viasic.com...
>> If I read it right, "virtual classes" are simply classes that can be replaced (just like virtual functions).  You define a higher level containing class, inherit the whole thing, and replace classes that need custom definitions for your app.
> 
> That's the way I read it, too, but how is it different from (in C++):
> 
>     class Foo
>     {
>         class Bar *p;
>     };
> 
> where you can inherit from Foo, derive from Bar, and replace p?
> 

I think you missed the point. He was not talking about one class containing another.

The framework provides a context in which
all the classes in it may be overridden
by inheritance and all the classes will still
retain the same relationships with each other.

class A { B b }
class B { C c }
class C { }

Here A, B and C have a defined relationship
with one another.

class D : A {}
class E : B {}
class F : C {}

Now D doesn't own an E it owns a B.  D, E and F
don't have the same relationship to each other
the A, B and C do.  Sometimes this is what you want
but sometimes what you want is the relationship of
A, B and C to be a abstract pattern for a concrete
implementation ion of E, D and F.

Let's take Bill Cox's  Graph library as an more
concrete example.  Graph, Node and Edge are related
to one another.  There are graph algorithms in
the library that advantage of these relations
to do certain tasks.  Finding shortest path between
two nodes is an example.

class Graph
{
  void shortestPath(Node from, Node to,
    out Node[] pathNodes, out Edge[] pathEdges);
}

class Edge
{
  int getWeight();
  Node getFrom();
  Node getTo();
}

class Node
{
  Edge[] getEdges();
}

class Road : Edge { char[] getName(); }

class City : Node { char[] getName(); }

Graph usa = new Graph...

City[] stops;
Road[] route;

// ERROR shortestPath wants Node[] and Edge[]
// not City[] and Road[]
usa.shortestPath(boston,los_angles,stops,route);

You can get around this with some nasty casting.
Templates can supply a solution too.  There is
an example of this in the "Directed Graph Support"
thread. But it's clunky.

The framework way of doing this would be.

framework GraphLib
{
  class Graph
  {
    void shortestPath(Node from, Node to,
      out Node[] pathNodes, out Edge[] pathEdges);
  }

  class Edge
  {
    int getWeight();
    Node getFrom();
    Node getTo();
  }

  class Node
  {
    Edge[] getEdges();
  }
}


framework Map : GraphLib
{
  class Edge { char[] getName(); }

  class Node { char[] getName(); }
}

The Map framework brings forward the implementation
of all the classes in GraphLib and extends them.

I see framework as more of a template definition.
GraphLib provides a pattern that can be extended.
It might even be recast into the template syntax.
Like this...

template GraphLib
{
  class Graph
  {
    void shortestPath(Node from, Node to,
      out Node[] pathNodes, out Edge[] pathEdges);
  }

  class Edge
  {
    int getWeight();
    Node getFrom();
    Node getTo();
  }

  class Node
  {
    Edge[] getEdges();
  }
}

instance GraphLib MyGraph
{
  // Append this definition to GraphLib's
  // Edge and node definition
  class Edge { char[] getName(); }

  class Node { char[] getName(); }
}