www.digitalmars.com         C & C++   DMDScript  

D - Frameworks and templates

reply Patrick Down <pat codemoon.com> writes:
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();
  }
}
Feb 02 2003
next sibling parent Bill Cox <bill viasic.com> writes:
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();
   }
 }
Feb 02 2003
prev sibling next sibling parent reply "Jeroen van Bemmel" <anonymous somewhere.com> writes:
 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
Feb 02 2003
parent "Daniel Yokomiso" <daniel_yokomiso yahoo.com.br> writes:
"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

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
Feb 02 2003
prev sibling parent reply "Daniel Yokomiso" <daniel_yokomiso yahoo.com.br> writes:
"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
Feb 02 2003
next sibling parent reply Bill Cox <bill viasic.com> writes:
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
Feb 02 2003
parent "Daniel Yokomiso" <daniel_yokomiso yahoo.com.br> writes:
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
Feb 02 2003
prev sibling parent reply Patrick Down <pat codemoon.com> writes:
"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.
Feb 02 2003
parent reply "Daniel Yokomiso" <daniel_yokomiso yahoo.com.br> writes:
"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
Feb 02 2003
parent Bill Cox <bill viasic.com> writes:
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
Feb 03 2003