View mode: basic / threaded / horizontal-split · Log in · Help
February 22, 2003
Re: First-class Functions
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
>
February 23, 2003
Re: First-class Functions
"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.
February 23, 2003
Re: First-class Functions
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
February 23, 2003
Re: First-class Functions
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
February 23, 2003
Re: First-class Functions
"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>.
February 23, 2003
Re: First-class Functions
"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
February 23, 2003
Re: Succinctness is Power
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
February 23, 2003
Re: First-class Functions
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>.
> 
>
February 23, 2003
Re: First-class Functions
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
February 23, 2003
Re: First-class Functions
"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(); } 
}
1 2 3 4 5
Top | Discussion index | About this forum | D home