I'm starting a new thread but the topic was inspired
by Bill Cox's post earlier about implementing a Graph library.

Sometimes, like in the Graph example, we have an interrelated
set of classes that is a base implementation of some data structure
or pattern.  When inheritance is used to create a specific concrete
implementation the member functions inherited from the base still
deal with types in terms the base classes.

// Lets use the graph example. I'm going
// to oversimplify for brevity.

class Node
{
  Edge[] GetInEdges();
  Edge[] GetOutEdges();
}

class Edge
{
  Node GetFromNode();
  Node GetToNode();
}

// Now create My implementation.

class MyNode : Node
{
}

class MyEdge : Edge
{
}

MyEdge.GetFromNode() returns the Node type but
we would really like it the return the MyNode
type.

This problem reminds me of an article I read
about frameworks.  The article suggested that
frameworks of classes could be defined and
expanded as a group.


framework GraphLib
{
  class Node
  {
    Edge[] GetInEdges();
    Edge[] GetOutEdges();
  }

  class Edge
  {
    Node GetFromNode();
    Node GetToNode();
  }
}


framework MyGraphLib : GraphLib
{
  class Edge // Adds to the GraphLib definition
  {
  }
}


Perhaps D templates could be expanded to cover this?

template GraphLib
{
  class Node
  {
    Edge[] GetInEdges();
    Edge[] GetOutEdges();
  }

  class Edge
  {
    Node GetFromNode();
    Node GetToNode();
  }
}

instance GraphLib MyGraph
{
  // Append this definition to GraphLib's
  // Edge definition
  class Edge
  {
  }
}


This could be useful for other things too.
For example consider a templated sort
algorithm.


template SortAlgo(TYPE)
{

  bit LessThan(TYPE a, TYPE b);

  void Sort(TYPE[] arr)
  {
    // use LessThan
  }
}

instance SortAlgo(Foo) MySortAlgo
{
  bit LessThan(FOO a, FOO b)
  {
    return a.bar() < b.bar();
  }
}

Now you're talking!  I like it.  I'll live with inheriting from template parameters if I have to, but this syntax looks much nicer.

Bill

Patrick Down wrote:
> I'm starting a new thread but the topic was inspired
> by Bill Cox's post earlier about implementing a Graph library.
> 
> Sometimes, like in the Graph example, we have an interrelated
> set of classes that is a base implementation of some data structure
> or pattern.  When inheritance is used to create a specific concrete
> implementation the member functions inherited from the base still
> deal with types in terms the base classes.  
> 
> // Lets use the graph example. I'm going
> // to oversimplify for brevity.
> 
> class Node {
>   Edge[] GetInEdges();
>   Edge[] GetOutEdges();
> }
>  class Edge {
>   Node GetFromNode();
>   Node GetToNode();  }
> 
> // Now create My implementation.
> 
> class MyNode : Node {
> }
> 
> class MyEdge : Edge {
> }
> 
> MyEdge.GetFromNode() returns the Node type but
> we would really like it the return the MyNode
> type.  
> 
> This problem reminds me of an article I read
> about frameworks.  The article suggested that frameworks of classes could be defined and expanded as a group.
> 
> 
> framework GraphLib
> {
>   class Node   {
>     Edge[] GetInEdges();
>     Edge[] GetOutEdges();
>   }
>    class Edge   {
>     Node GetFromNode();
>     Node GetToNode();    }  }
> 
> 
> framework MyGraphLib : GraphLib
> {
>   class Edge // Adds to the GraphLib definition
>   {
>   }
> }
> 
> 
> Perhaps D templates could be expanded to cover this?
> 
> template GraphLib
> {
>   class Node   {
>     Edge[] GetInEdges();
>     Edge[] GetOutEdges();
>   }
>    class Edge   {
>     Node GetFromNode();
>     Node GetToNode();    }  }
> 
> instance GraphLib MyGraph
> {
>   // Append this definition to GraphLib's
>   // Edge definition
>   class Edge   {
>   }
> }
> 
> 
> This could be useful for other things too.
> For example consider a templated sort
> algorithm.
> 
> 
> template SortAlgo(TYPE)
> {
> 
>   bit LessThan(TYPE a, TYPE b);
>     void Sort(TYPE[] arr)
>   {
>     // use LessThan
>   }
> }
> 
> instance SortAlgo(Foo) MySortAlgo
> {
>   bit LessThan(FOO a, FOO b)
>   {
>     return a.bar() < b.bar();
>   }
> }
> 

> MyEdge.GetFromNode() returns the Node type but
> we would really like it the return the MyNode
> type.

This has a name ('narrowing'?) and represents a relaxation for derivation rules. Normally, when you redefine/implement a super class' method in a derived class (redefine/implement defined as matching method name + parameters) then the specified returntype must match exactly too. With relaxed rules, the derived method would be allowed to declare a returntype that is itself a subtype of the super class' method returntype. gcc probably has more info

A similar scheme exists for parameter types, but then the parameter types can only be superclasses of parameters declared in the super class

"Jeroen van Bemmel" <anonymous@somewhere.com> escreveu na mensagem news:b1k75d$1fq8$1@digitaldaemon.com...
> > MyEdge.GetFromNode() returns the Node type but
> > we would really like it the return the MyNode
> > type.
>
> This has a name ('narrowing'?) and represents a relaxation for derivation rules. Normally, when you redefine/implement a super class' method in a derived class (redefine/implement defined as matching method name + parameters) then the specified returntype must match exactly too. With relaxed rules, the derived method would be allowed to declare a returntype that is itself a subtype of the super class' method returntype. gcc
probably
> has more info
>
> A similar scheme exists for parameter types, but then the parameter types can only be superclasses of parameters declared in the super class
>

This is called covariance (and the opposite is contravariance). There's a nice summary about it in http://sern.ucalgary.ca/courses/SENG/609.03/W98/Abadi/AbadiCh2.html#2.6 , from Abadi and Cardelli excelent "A Theory of Objects".


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.449 / Virus Database: 251 - Release Date: 27/1/2003

"Patrick Down" <pat@codemoon.com> escreveu na mensagem news:Xns9316831A8FD52patcodemooncom@63.105.9.61...
>
>
> I'm starting a new thread but the topic was inspired
> by Bill Cox's post earlier about implementing a Graph library.
>
> Sometimes, like in the Graph example, we have an interrelated
> set of classes that is a base implementation of some data structure
> or pattern.  When inheritance is used to create a specific concrete
> implementation the member functions inherited from the base still
> deal with types in terms the base classes.
>
> // Lets use the graph example. I'm going
> // to oversimplify for brevity.
>
> class Node
> {
>   Edge[] GetInEdges();
>   Edge[] GetOutEdges();
> }
>
> class Edge
> {
>   Node GetFromNode();
>   Node GetToNode();
> }
>
> // Now create My implementation.
>
> class MyNode : Node
> {
> }
>
> class MyEdge : Edge
> {
> }
>
> MyEdge.GetFromNode() returns the Node type but
> we would really like it the return the MyNode
> type.
>
> This problem reminds me of an article I read
> about frameworks.  The article suggested that
> frameworks of classes could be defined and
> expanded as a group.
>
>
> framework GraphLib
> {
>   class Node
>   {
>     Edge[] GetInEdges();
>     Edge[] GetOutEdges();
>   }
>
>   class Edge
>   {
>     Node GetFromNode();
>     Node GetToNode();
>   }
> }
>
>
> framework MyGraphLib : GraphLib
> {
>   class Edge // Adds to the GraphLib definition
>   {
>   }
> }
>
>
> Perhaps D templates could be expanded to cover this?
>
> template GraphLib
> {
>   class Node
>   {
>     Edge[] GetInEdges();
>     Edge[] GetOutEdges();
>   }
>
>   class Edge
>   {
>     Node GetFromNode();
>     Node GetToNode();
>   }
> }
>
> instance GraphLib MyGraph
> {
>   // Append this definition to GraphLib's
>   // Edge definition
>   class Edge
>   {
>   }
> }
>
>
> This could be useful for other things too.
> For example consider a templated sort
> algorithm.
>
>
> template SortAlgo(TYPE)
> {
>
>   bit LessThan(TYPE a, TYPE b);
>
>   void Sort(TYPE[] arr)
>   {
>     // use LessThan
>   }
> }
>
> instance SortAlgo(Foo) MySortAlgo
> {
>   bit LessThan(FOO a, FOO b)
>   {
>     return a.bar() < b.bar();
>   }
> }
>

Hi,

    Perhaps it should be

template MyGraph : GraphLib {
}

    IMHO it's more like the D's syntax for extension of existing code. But I
prefer ther earlier example using composition of templates instead of
inheritance. With template inheritance we must have a way to defined
abstract functions in templates, and so on. Using template parameters we
have more freedom in the way we extend our code, and composition is at least
as powerful as inheritance.
    Most languages that allow generic module creation, like ML or Ada, use
type, function and value parameters to do this, so your example would be:

template SortAlgo(TYPE, bit (*LessThan)(TYPE, TYPE)) {
    void Sort(TYPE[] arr) {
        // use LessThan
    }
}

    Best regards,
    Daniel Yokomiso.

"To be without some of the things you want is an indispensable part of
happiness."
- Bertrand Russell


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.449 / Virus Database: 251 - Release Date: 27/1/2003

Hi.

I'm leaving Patricks suggested code here.  I think it looks very nice:

>>template GraphLib
>>{
>>  class Node
>>  {
>>    Edge[] GetInEdges();
>>    Edge[] GetOutEdges();
>>  }
>>
>>  class Edge
>>  {
>>    Node GetFromNode();
>>    Node GetToNode();
>>  }
>>}
>>
>>instance GraphLib MyGraph
>>{
>>  // Append this definition to GraphLib's
>>  // Edge definition
>>  class Edge
>>  {
>>  }
>>}

Here's suggested code from Daniel:

> Hi,
> 
>     Perhaps it should be
> 
> template MyGraph : GraphLib {
> }

Why would I make MyGraph a template?  I'm not planning on making it reusable.  I'm just a bit confused on this point.

>     IMHO it's more like the D's syntax for extension of existing code.  But I
> prefer ther earlier example using composition of templates instead of
> inheritance. With template inheritance we must have a way to defined
> abstract functions in templates, and so on. Using template parameters we
> have more freedom in the way we extend our code, and composition is at least
> as powerful as inheritance.

What's composition?  Frankly, I'd been very concerned about giving a group of programmers a graph package that was built out of templates that inherit from template parameters.  If it get's any more complicated, I'll probably just stick to non-reusable graph code.  At least it would make for a fair comparison between C and D.

Bill

"Daniel Yokomiso" <daniel_yokomiso@yahoo.com.br> wrote in news:b1kh01$1lca$1@digitaldaemon.com:

> 
> Hi,
> 
>     Perhaps it should be
> 
> template MyGraph : GraphLib {
> }
> 
>     IMHO it's more like the D's syntax for extension of existing code.
>     But I
> prefer ther earlier example using composition of templates instead of
> inheritance. With template inheritance we must have a way to defined
> abstract functions in templates, and so on. Using template parameters
> we have more freedom in the way we extend our code, and composition is
> at least as powerful as inheritance.

It's true that it may be at least as powerful.  Multiple ways to achieve the same result is not always bad.  I would say that what I have specified above is more readable and understandable for the task it accomplishes.

>     Most languages that allow generic module creation, like ML or Ada,
>     use
> type, function and value parameters to do this, so your example would
> be:
> 
> template SortAlgo(TYPE, bit (*LessThan)(TYPE, TYPE)) {
>     void Sort(TYPE[] arr) {
>         // use LessThan
>     }
> }

Yes I would like to use functions as template parameters.

Hi,

    Comments embedded,


"Bill Cox" <bill@viasic.com> escreveu na mensagem news:3E3DE4F8.1050009@viasic.com...
> Hi.
>
> I'm leaving Patricks suggested code here.  I think it looks very nice:
>
> >>template GraphLib
> >>{
> >>  class Node
> >>  {
> >>    Edge[] GetInEdges();
> >>    Edge[] GetOutEdges();
> >>  }
> >>
> >>  class Edge
> >>  {
> >>    Node GetFromNode();
> >>    Node GetToNode();
> >>  }
> >>}
> >>
> >>instance GraphLib MyGraph
> >>{
> >>  // Append this definition to GraphLib's
> >>  // Edge definition
> >>  class Edge
> >>  {
> >>  }
> >>}
>
> Here's suggested code from Daniel:
>
> > Hi,
> >
> >     Perhaps it should be
> >
> > template MyGraph : GraphLib {
> > }
>
> Why would I make MyGraph a template?  I'm not planning on making it reusable.  I'm just a bit confused on this point.


    Let me try to explain this. When you want an object with a specialized
behaviour, different from it's class default, even if you'll only create one
instance, you need to create a derived class:


class Edge {
    int something() {
        return 10;
    }
}

// invalid Java-like anonymous class.
Edge e = new Edge() { int something() {return 1;}};

class MyEdge {
    int something() {
        return 1;
    }
}
// correct
Edge e = new MyEdge();


    What I'm trying to say is that in D the granularity for method
specialization is a class. With a template is similar. If a template is used
to define common behaviour, the expected granularity for specialization of
this template should be a template too, even if you want only one instance
of it. If it's still strange I may be able to clarify it.


> >     IMHO it's more like the D's syntax for extension of existing code.
But I
> > prefer ther earlier example using composition of templates instead of inheritance. With template inheritance we must have a way to defined abstract functions in templates, and so on. Using template parameters we have more freedom in the way we extend our code, and composition is at
least
> > as powerful as inheritance.
>
> What's composition?  Frankly, I'd been very concerned about giving a group of programmers a graph package that was built out of templates that inherit from template parameters.  If it get's any more complicated, I'll probably just stick to non-reusable graph code.  At least it would make for a fair comparison between C and D.
>
> Bill
>

    There are two forms of code reuse in OO languages: inheritance
(extension) and composition. An example shall suffice:


// Inheritance code reuse:

abstract class Integrator {
    abstract double functionToIntegrate(double x);
    double integrate(double from, double to) {
        // integration goes here. Uses functionToIntegrate method
    }
}

class MyIntegrator {
    double functionToIntegrate(double x) {
        return x * x;
    }
}

Integrator integrator = new MyIntegrator();
double result = integrator.integrate(0.0, 100.0);



// Composition code reuse:

class Integrator {
    double (*_functionToIntegrate)(double);
    this(double (*functionToIntegrate)(double)) {
        this._functionToIntegrate = functionToIntegrate;
    }
    double integrate(double from, double to) {
        // integration goes here. Uses _functionToIntegrate attribute
    }
}

double functionToIntegrate(double x) {
    return x * x;
}

Integrator integrator = new Integrator(&functionToIntegrate);
double result = integrator.integrate(0.0, 100.0);


    With inheritance you must inherit from the base class to reuse the
integrate method. With composition you pass a parameter to your instance so
it knows what to integrate. The same goes with templates.

    Best regards,
    Daniel Yokomiso.

"First they ignore you, then they laugh at you, then they fight you, then
you win."
- Mohandas Gandi


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.449 / Virus Database: 251 - Release Date: 27/1/2003

"Patrick Down" <pat@codemoon.com> escreveu na mensagem news:Xns9316E76A51E94patcodemooncom@63.105.9.61...
> "Daniel Yokomiso" <daniel_yokomiso@yahoo.com.br> wrote in news:b1kh01$1lca$1@digitaldaemon.com:
>
> >
> > Hi,
> >
> >     Perhaps it should be
> >
> > template MyGraph : GraphLib {
> > }
> >
> >     IMHO it's more like the D's syntax for extension of existing code.
> >     But I
> > prefer ther earlier example using composition of templates instead of
> > inheritance. With template inheritance we must have a way to defined
> > abstract functions in templates, and so on. Using template parameters
> > we have more freedom in the way we extend our code, and composition is
> > at least as powerful as inheritance.
>
> It's true that it may be at least as powerful.  Multiple ways to achieve the same result is not always bad.  I would say that what I have specified above is more readable and understandable for the task it accomplishes.

    I like your syntax too, but it's not coherent with the rest of D's
syntax. Syntax incoherence is a big language smell. IMHO we should not have
to extend a template if we just need an instance. So your intent is clearer
than mine, but I think both forms aren't good enough.

>
> >     Most languages that allow generic module creation, like ML or Ada,
> >     use
> > type, function and value parameters to do this, so your example would
> > be:
> >
> > template SortAlgo(TYPE, bit (*LessThan)(TYPE, TYPE)) {
> >     void Sort(TYPE[] arr) {
> >         // use LessThan
> >     }
> > }
>
> Yes I would like to use functions as template parameters.


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.449 / Virus Database: 251 - Release Date: 27/1/2003

Hi.

The nice thing about Patrick's syntax is that it seems to elegantly solve a significant problem: How to build a very efficient reusable graph package.

Can you write the outline of a graph package in D in a natural way?  I am actually looking for this code, so it wouldn't be wasted.  Patrick started one where he instantiates templates that inherit from my classes that need graph functionality added to them.  I think this could probably be finished in a reasonable way, but it's pretty confusing. I'll use it if it's the best we can do in D.

Another aproach might be to use interfaces like this:

interface Graph {
    Node firstNode(); // To implement graph->node itteration
// Graph applications...
}

interface Node {
    Node nextGraphNode();
    Edge firstInEdge();
    Edge firstOutEdge();
    Graph owner();
}

interface Edge {
    Edge nextNodeInEdge();
    Edge nextNodeOutEdge();
    Node fromNode();
    Node toNode();
}

// Graph applications would be in a separate module:

color(Graph graph, int numColors) {...}
findMinCut(Graph graph) {...}
    ...

This way, I get to define the actual container classes in MyGraph, which is critical.  Is D able to eliminate all the virtual function calls in the interface?

Bill

Daniel Yokomiso wrote:
> "Patrick Down" <pat@codemoon.com> escreveu na mensagem
> news:Xns9316E76A51E94patcodemooncom@63.105.9.61...
> 
>>"Daniel Yokomiso" <daniel_yokomiso@yahoo.com.br> wrote in
>>news:b1kh01$1lca$1@digitaldaemon.com:
>>
>>
>>>Hi,
>>>
>>>    Perhaps it should be
>>>
>>>template MyGraph : GraphLib {
>>>}
>>>
>>>    IMHO it's more like the D's syntax for extension of existing code.
>>>    But I
>>>prefer ther earlier example using composition of templates instead of
>>>inheritance. With template inheritance we must have a way to defined
>>>abstract functions in templates, and so on. Using template parameters
>>>we have more freedom in the way we extend our code, and composition is
>>>at least as powerful as inheritance.
>>
>>It's true that it may be at least as powerful.  Multiple ways to
>>achieve the same result is not always bad.  I would say that what
>>I have specified above is more readable and understandable for the
>>task it accomplishes.
> 
> 
>     I like your syntax too, but it's not coherent with the rest of D's
> syntax. Syntax incoherence is a big language smell. IMHO we should not have
> to extend a template if we just need an instance. So your intent is clearer
> than mine, but I think both forms aren't good enough.
> 
> 
>>>    Most languages that allow generic module creation, like ML or Ada,
>>>    use
>>>type, function and value parameters to do this, so your example would
>>>be:
>>>
>>>template SortAlgo(TYPE, bit (*LessThan)(TYPE, TYPE)) {
>>>    void Sort(TYPE[] arr) {
>>>        // use LessThan
>>>    }
>>>}
>>
>>Yes I would like to use functions as template parameters.
> 
> 
> 
> ---
> Outgoing mail is certified Virus Free.
> Checked by AVG anti-virus system (http://www.grisoft.com).
> Version: 6.0.449 / Virus Database: 251 - Release Date: 27/1/2003
> 
>