Jeroen van Bemmel wrote:
> As with many things in life, it's a matter of choice: what do you want/need
> to be flexible, and what can be fixed
> 
> A programming language is in itself a very generic mechanism, because it can
> be used to implement any (well, almost) program. So the language itself is
> the most generic template. However, because it is so generic parameterizing
> this mechanism ("programming") takes a lot of effort (effort measured in
> amount of typing and thinking).
> 
> Fixing all parameters reduces the effort needed to reuse a piece of code to
> almost zero, but at the same time limits the applicability of that code to
> one specific situation. Hence we have a spectrum from ( everything fixed (no
> parameters) => low effort to reuse but limited applicability) to (
> everything flexible => high effort to reuse but wide applicability ). The
> low end of the spectrum is e.g. a completed program for which you have no
> sources, the high end is the language itself
> 
> So basically everything _is_ a template in a programming language, just the
> granularity of templatization ("templatizability?") differs

I agree.  Since my original post, I've become convinced that templates are great, and needed in the language, and that putting in the template parameters isn't such a bad thing.

The thing that was originally bugging me was my inability to reuse so much code easily.  This doesn't seem to be limitation in templates. Patric Down posted a solution he called "template frameworks", and "class frameworks" that solve the problem.  It looked like the difference was minor, in that both solved the problem, which lead me to wonder if everything could be thought of as a template, and thus the original post.

I now believe that templates fine as they are, and that my original problem, the difficulty reusing code with multiple recursive classes, is solved in various was with "template frameworks", "class frameworks", "virtual classes", Sather's "include" construct, and other mechanisms described in this news group.  Inheriting functionality is different than declaring new types with templates.

Bill

Hi,

Comments embedded.

In article <3E6B33FF.8060301@viasic.com>, Bill Cox says...
>
>Daniel Yokomiso wrote:
>> T k(T x, U, y) {
>>     return x;
>> }
>
>
>Hi, Dan.
>
>This is pretty cool.  I hadn't realized templates in D were quite that generic.
>
>Is "U, y" suppose to be "U y"?  Why do we want to ignore y in the body?
>  I'm confused as to why making a function that takes an ignored
>parameter is useful, but I'll take your word for it.  BTW, if you have a good link that describes this, I'd like to read it.


I'm doing lots of typos recently. I should compile every snippet before posting,
not just the most complex.
If you google for combinators s k, you'll get some good links, like:

http://undergraduate.cs.uwa.edu.au/courses/230.301/lectureNotes/13/15.pdf and http://undergraduate.cs.uwa.edu.au/courses/230.301/lectureNotes/13/16.pdf

They seem to be pretty good.
You can think of the K combinator as something similar to an if. An if has three
parameters, a boolean value, a then part and an else part. Just one of the
clauses of the if must be evaluated, the other can be ignored. It can be
formulated as:


if true  then-part else-part = then-part
if false then-part else-part = else-part


Using lambda calculus a function "f x y" is  curried, giving "(f x) y", and if "g = f x" we can use the equivalent "g y", so "if true" should give us something equivalent to the K combinator because it just returns the first parameter. There's a nice article about lambda calculus and perl (the perl part isn't important) at:

http://perl.plover.com/lambda/


>There's a subtle reason that D's templates don't give us power I was fishing for in my original post.  You've convinced me that D's templates are fully generic, and that they're extremely cool.  However, D currently limits how I get to use tempate generated classes.
>
>The problem is that I can't inherit functionality simultaneously from a framwork of classes.  A simple example data structure that has this problem is a directed graph, because it has mutually recursive classes (Nodes and Edges).  We can write great template parameterised graph packages.  I can instantiate them.  I just can't inherit their functionallity into my own classes in any clean way.
>
>This problem seems to have been identified by lots of people, and there are a variety of solutions.  "Virtual classes", "template frameworks", and Sather's "include" all solve this problem.
>
>I think this is why we've had a lot of discussion lately about "virtual classes", which seem to overcome this limitation.  I'm an advocate of Sather's "include" construct over "virtual classes", since using it takes less work for end-users, it offers slightly more power, and it leads to much simpler compilers.  It's also easier to understand.

Maybe we should have something like template inheritance. if we allow abstract templates, we could use them for defining both frameworks and parametrically polimorphic structures. Something like:

abstract template TGraph(T) { // T is the node content type
abstract class Edge {
// stuff here
}
abstract class Node {
// stuff here
}
}

template MyGraphFramework(T) : TGraph(T) {
class Edge : TGraph.Edge {
// overrides TGraph definitions
}
class Node : TGraph.Node {
// overrides TGraph definitions
}
}

alias instance MyGraphFramework(int) graph;
graph.Node node = new graph.Node();


This looks like solves the problem using a syntax familiar to D programmers ;-) Also template inheritance is useful when you use templates as a module-like unit of abstraction. I wouldn't mind if modules and templates get merged, some time ago I voted for this.

>Bill
>


Best regards,
Daniel Yokomiso.

Daniel Yokomiso wrote:
> Hi,
> 
> Comments embedded.
> 
> In article <3E6B33FF.8060301@viasic.com>, Bill Cox says...
> 
>>Daniel Yokomiso wrote:
>>
>>>T k(T x, U, y) {
>>>    return x;
>>>}
>>
>>
>>Hi, Dan.
>>
>>This is pretty cool.  I hadn't realized templates in D were quite that generic.
>>
>>Is "U, y" suppose to be "U y"?  Why do we want to ignore y in the body? 
>> I'm confused as to why making a function that takes an ignored 
>>parameter is useful, but I'll take your word for it.  BTW, if you have a good link that describes this, I'd like to read it.
> 
> 
> 
> I'm doing lots of typos recently. I should compile every snippet before posting,
> not just the most complex.
> If you google for combinators s k, you'll get some good links, like:
> 
> http://undergraduate.cs.uwa.edu.au/courses/230.301/lectureNotes/13/15.pdf
> and
> http://undergraduate.cs.uwa.edu.au/courses/230.301/lectureNotes/13/16.pdf
> 
> They seem to be pretty good.
> You can think of the K combinator as something similar to an if. An if has three
> parameters, a boolean value, a then part and an else part. Just one of the
> clauses of the if must be evaluated, the other can be ignored. It can be
> formulated as:
> 
> 
> if true  then-part else-part = then-part
> if false then-part else-part = else-part
> 
> 
> Using lambda calculus a function "f x y" is  curried, giving "(f x) y", and if
> "g = f x" we can use the equivalent "g y", so "if true" should give us something
> equivalent to the K combinator because it just returns the first parameter.
> There's a nice article about lambda calculus and perl (the perl part isn't
> important) at:
> 
> http://perl.plover.com/lambda/
> 
> 
> 
>>There's a subtle reason that D's templates don't give us power I was fishing for in my original post.  You've convinced me that D's templates are fully generic, and that they're extremely cool.  However, D currently limits how I get to use tempate generated classes.
>>
>>The problem is that I can't inherit functionality simultaneously from a framwork of classes.  A simple example data structure that has this problem is a directed graph, because it has mutually recursive classes (Nodes and Edges).  We can write great template parameterised graph packages.  I can instantiate them.  I just can't inherit their functionallity into my own classes in any clean way.
>>
>>This problem seems to have been identified by lots of people, and there are a variety of solutions.  "Virtual classes", "template frameworks", and Sather's "include" all solve this problem.
>>
>>I think this is why we've had a lot of discussion lately about "virtual classes", which seem to overcome this limitation.  I'm an advocate of Sather's "include" construct over "virtual classes", since using it takes less work for end-users, it offers slightly more power, and it leads to much simpler compilers.  It's also easier to understand.
> 
> 
> Maybe we should have something like template inheritance. if we allow abstract
> templates, we could use them for defining both frameworks and parametrically
> polimorphic structures. Something like:
> 
> abstract template TGraph(T) { // T is the node content type
> abstract class Edge {
> // stuff here
> }
> abstract class Node {
> // stuff here
> }
> }
> 
> template MyGraphFramework(T) : TGraph(T) {
> class Edge : TGraph.Edge {
> // overrides TGraph definitions
> }
> class Node : TGraph.Node {
> // overrides TGraph definitions
> }
> }
> 
> alias instance MyGraphFramework(int) graph;
> graph.Node node = new graph.Node();
> 
> 
> This looks like solves the problem using a syntax familiar to D programmers ;-)
> Also template inheritance is useful when you use templates as a module-like unit
> of abstraction. I wouldn't mind if modules and templates get merged, some time
> ago I voted for this.
> 
> 
>>Bill
>>
> 
> 
> 
> Best regards,
> Daniel Yokomiso.
> 
> 

This style of template framework looks good to me.  I've not implemented templates in a language before, so I'm not very familiar with the hairy problems that arise.  If this structure didn't foobar the compiler, I'd be for it.  As you've said, the syntax is familiar to D developers, and that is important.

I think there is still one significant limitation to this aproach, which this example demonstrates.  We're using template inheritance to add graph functionality to classes in MyGraphFramework.  Since D is a single-inheritance based language, like Java, that can lead to problems.
If graph functionality is just something I want to add to my classes, rather than what defines my classes, I'd be left wanting multiple inheritance.

Bill

In article <3E6CA73E.7000103@viasic.com>, Bill Cox says...

[snip]

>This style of template framework looks good to me.  I've not implemented templates in a language before, so I'm not very familiar with the hairy problems that arise.  If this structure didn't foobar the compiler, I'd be for it.  As you've said, the syntax is familiar to D developers, and that is important.

Probably it'll be as efficient as regular objects (they may be more optimizable, since templates are supposed to be resolved at compile-time).

>I think there is still one significant limitation to this aproach, which this example demonstrates.  We're using template inheritance to add graph functionality to classes in MyGraphFramework.  Since D is a single-inheritance based language, like Java, that can lead to problems. If graph functionality is just something I want to add to my classes, rather than what defines my classes, I'd be left wanting multiple inheritance.
>
>Bill

Walter decided against multiple inheritance due to the mess C++ does. Eiffel has a different model, but has its problems too. AFAIK there are no statically-typed imperative languages with a simple, safe, MI model. Sather is safe, but not simple, with all the abstract, partial, generic classes. But I don't know if there are significant problems in the real world, using extensible templates like these. Can you propose a problem that this solution can't solve, or leads to a awkward solution (e.g. duplicated code, additional levels of indirection)? I'm just trying to "test" this model, not try to say that MI is bad (I like MI, but I admit that it's a hard problem to solve).

Daniel Yokomiso wrote:
> Walter decided against multiple inheritance due to the mess C++ does. Eiffel has
> a different model, but has its problems too. AFAIK there are no statically-typed
> imperative languages with a simple, safe, MI model. Sather is safe, but not
> simple, with all the abstract, partial, generic classes. But I don't know if
> there are significant problems in the real world, using extensible templates
> like these. Can you propose a problem that this solution can't solve, or leads
> to a awkward solution (e.g. duplicated code, additional levels of indirection)?
> I'm just trying to "test" this model, not try to say that MI is bad (I like MI,
> but I admit that it's a hard problem to solve).
> 
> 

Hi, Daniel.

A simple example would be inheriting linked list functionality into my classes.  A traditional linked list adds fields and methods to both parent and child classes, so inheriting these as a template framework of some sort makes sense.  Clearly, I wouldn't want to waste my one real inheritance on a simple linked list capability.

To make the example more solid, let's imagine I'm trying to implement a simple model of a company organization.  I might want a Department class to have linked lists of Employees and Computers:

module linkedList;

class Parent {
    Child first;
    add(Child child) {
        child.next = first;
        first = child;
    }
}

class Child {
    Child next;
}

module sillyCompanyModel;

class Department {
    string name;
    ...
}

class Employee {
    string name;
    int employeeNumber;
    ...
}

class Computer {
    string osType;
    ...
}

inherit linkedList {
    Parent -> Department;
    Parent.first -> Department.firstEmployee;
    Parent.add -> Departement.addEmployee;
    Child -> Employee;
    Child.next -> Employee.nextEmployee;
}

inherit linkedList {
    Parent -> Department;
    Parent.first -> Department.firstComputer;
    Parent.add -> Departement.addComputer;
    Child -> Computer;
    Child.next -> Employee.nextComputer;
}

I used Ocaml's "inherit" keyword, rather than Sather's "include" in this example.  You only need multiple inheritance in the sense that Ocaml does it: simple parse tree copying.  Also, while Sather has complex inheritance mechanisms like partial classes, it's "include" feature is more like Ocaml's "inherit" in that it is based on simple copying of parse trees.

A nice property of this style of module level inheritance is that it puts the mapping in one place.  Spreading out the inheritance mapping over a bunch of classes could make it hard to see what's going on if I make extensive use of renameing.

In general, I think it makes a lot of sense to specify a mapping when inheriting a module's functionality.  It's also important to be able to rename stuff.  If we build the mechanism on simple syntax tree copying, we can do multiple inheritance easily.

Bill

In article <3E6EFA11.2080903@viasic.com>, Bill Cox says...
>
>Daniel Yokomiso wrote:
>> Walter decided against multiple inheritance due to the mess C++ does. Eiffel has a different model, but has its problems too. AFAIK there are no statically-typed imperative languages with a simple, safe, MI model. Sather is safe, but not simple, with all the abstract, partial, generic classes. But I don't know if there are significant problems in the real world, using extensible templates like these. Can you propose a problem that this solution can't solve, or leads to a awkward solution (e.g. duplicated code, additional levels of indirection)? I'm just trying to "test" this model, not try to say that MI is bad (I like MI, but I admit that it's a hard problem to solve).
>> 
>> 
>
>Hi, Daniel.
>
>A simple example would be inheriting linked list functionality into my classes.  A traditional linked list adds fields and methods to both parent and child classes, so inheriting these as a template framework of some sort makes sense.  Clearly, I wouldn't want to waste my one real inheritance on a simple linked list capability.
>
>To make the example more solid, let's imagine I'm trying to implement a simple model of a company organization.  I might want a Department class to have linked lists of Employees and Computers:
>
>module linkedList;
>
>class Parent {
>     Child first;
>     add(Child child) {
>         child.next = first;
>         first = child;
>     }
>}
>
>class Child {
>     Child next;
>}
>
>module sillyCompanyModel;
>
>class Department {
>     string name;
>     ...
>}
>
>class Employee {
>     string name;
>     int employeeNumber;
>     ...
>}
>
>class Computer {
>     string osType;
>     ...
>}
>
>inherit linkedList {
>     Parent -> Department;
>     Parent.first -> Department.firstEmployee;
>     Parent.add -> Departement.addEmployee;
>     Child -> Employee;
>     Child.next -> Employee.nextEmployee;
>}
>
>inherit linkedList {
>     Parent -> Department;
>     Parent.first -> Department.firstComputer;
>     Parent.add -> Departement.addComputer;
>     Child -> Computer;
>     Child.next -> Employee.nextComputer;
>}
>
>I used Ocaml's "inherit" keyword, rather than Sather's "include" in this example.  You only need multiple inheritance in the sense that Ocaml does it: simple parse tree copying.  Also, while Sather has complex inheritance mechanisms like partial classes, it's "include" feature is more like Ocaml's "inherit" in that it is based on simple copying of parse trees.
>
>A nice property of this style of module level inheritance is that it puts the mapping in one place.  Spreading out the inheritance mapping over a bunch of classes could make it hard to see what's going on if I make extensive use of renameing.
>
>In general, I think it makes a lot of sense to specify a mapping when inheriting a module's functionality.  It's also important to be able to rename stuff.  If we build the mechanism on simple syntax tree copying, we can do multiple inheritance easily.
>
>Bill

Hi,

You can achieve what you want in Eiffel using non-conforming inheritance (a feature of ETL3). You can inherit from some class without forming a subtype relationship (the syntax may be incorrect but the idea is here):


class Department is
inherit
expanded LinkedList(Employee)
rename
firstElement as firstEmployee
addElement as addEmployee
end
expanded LinkedList(Computer)
rename
firstElement as firstComputer
addElement as addComputer
end
end
class Computer is
inherit Link(Computer)
rename
next as nextComputer
end
end
class Employee is
inherit Link(Employee)
rename
next as nextEmployee
end
end

class LinkedList(T -> Link) is
feature
firstElement: T
addElement(link: T) is
do
link.next(firstElement);
firstElement := link;
end
end

class Link(T) is
feature
next: T
end


You can read more about it at http://www.inf.ethz.ch/~meyer/ongoing/. Just a
couple of questions. Why don't use a generic LinkedList template and make it an
attribute of Department, instead of merging linked list functionality with your
classes? IIRC you questioned this because memory locality and additional levels
of indirection hurt the performance. Isn't this model flawed? Also, I don't
think that everyone besides department should be able to see nextComputer and
nextEmployee, so we need some kind of access control feature, like Eiffel export
clauses or C++ friendship. There's a third concern about this kind of solution:
what will happen when two classes, let them be Department and TechSupport, need
to maintain distinct lists of Computer (e.g. department resources and broken
computers). With this model we'll force every Computer instance to have n member
variables, where n is the number of lists needed, even if they aren't in the
lists most of the time.
In this example I don't think that include-like functionality is necessary or a
good design decision. Otherwise if your problem requires that your classes have
next references (e.g. modelling chains) then this kind of solution is good. I'm
looking forward an example where include mechanism (i.e. code inheritance
without subtyping relationship) is necessary, not just an implementation
decision.

Best regards,
Daniel Yokomiso.

"I'm not a lawyer, but I'm pedantic and that's just as good."
 - D. Gary Grady

Daniel Yokomiso wrote:
> In article <3E6EFA11.2080903@viasic.com>, Bill Cox says...
> 
>>Daniel Yokomiso wrote:
>>
>>>Walter decided against multiple inheritance due to the mess C++ does. Eiffel has
>>>a different model, but has its problems too. AFAIK there are no statically-typed
>>>imperative languages with a simple, safe, MI model. Sather is safe, but not
>>>simple, with all the abstract, partial, generic classes. But I don't know if
>>>there are significant problems in the real world, using extensible templates
>>>like these. Can you propose a problem that this solution can't solve, or leads
>>>to a awkward solution (e.g. duplicated code, additional levels of indirection)?
>>>I'm just trying to "test" this model, not try to say that MI is bad (I like MI,
>>>but I admit that it's a hard problem to solve).
>>>
>>>
>>
>>Hi, Daniel.
>>
>>A simple example would be inheriting linked list functionality into my classes.  A traditional linked list adds fields and methods to both parent and child classes, so inheriting these as a template framework of some sort makes sense.  Clearly, I wouldn't want to waste my one real inheritance on a simple linked list capability.
>>
>>To make the example more solid, let's imagine I'm trying to implement a simple model of a company organization.  I might want a Department class to have linked lists of Employees and Computers:
>>
>>module linkedList;
>>
>>class Parent {
>>    Child first;
>>    add(Child child) {
>>        child.next = first;
>>        first = child;
>>    }
>>}
>>
>>class Child {
>>    Child next;
>>}
>>
>>module sillyCompanyModel;
>>
>>class Department {
>>    string name;
>>    ...
>>}
>>
>>class Employee {
>>    string name;
>>    int employeeNumber;
>>    ...
>>}
>>
>>class Computer {
>>    string osType;
>>    ...
>>}
>>
>>inherit linkedList {
>>    Parent -> Department;
>>    Parent.first -> Department.firstEmployee;
>>    Parent.add -> Departement.addEmployee;
>>    Child -> Employee;
>>    Child.next -> Employee.nextEmployee;
>>}
>>
>>inherit linkedList {
>>    Parent -> Department;
>>    Parent.first -> Department.firstComputer;
>>    Parent.add -> Departement.addComputer;
>>    Child -> Computer;
>>    Child.next -> Employee.nextComputer;
>>}
>>
>>I used Ocaml's "inherit" keyword, rather than Sather's "include" in this example.  You only need multiple inheritance in the sense that Ocaml does it: simple parse tree copying.  Also, while Sather has complex inheritance mechanisms like partial classes, it's "include" feature is more like Ocaml's "inherit" in that it is based on simple copying of parse trees.
>>
>>A nice property of this style of module level inheritance is that it puts the mapping in one place.  Spreading out the inheritance mapping over a bunch of classes could make it hard to see what's going on if I make extensive use of renameing.
>>
>>In general, I think it makes a lot of sense to specify a mapping when inheriting a module's functionality.  It's also important to be able to rename stuff.  If we build the mechanism on simple syntax tree copying, we can do multiple inheritance easily.
>>
>>Bill
> 
> 
> Hi,
> 
> You can achieve what you want in Eiffel using non-conforming inheritance (a
> feature of ETL3). You can inherit from some class without forming a subtype
> relationship (the syntax may be incorrect but the idea is here):
> 
> 
> class Department is
> inherit
> expanded LinkedList(Employee)
> rename
> firstElement as firstEmployee
> addElement as addEmployee
> end
> expanded LinkedList(Computer)
> rename
> firstElement as firstComputer
> addElement as addComputer
> end
> end
> class Computer is
> inherit Link(Computer)
> rename
> next as nextComputer
> end
> end
> class Employee is
> inherit Link(Employee)
> rename
> next as nextEmployee
> end
> end
> 
> class LinkedList(T -> Link) is
> feature
> firstElement: T
> addElement(link: T) is
> do
> link.next(firstElement);
> firstElement := link;
> end
> end
> 
> class Link(T) is
> feature
> next: T
> end
> 
> 
> You can read more about it at http://www.inf.ethz.ch/~meyer/ongoing/. Just a
> couple of questions. Why don't use a generic LinkedList template and make it an
> attribute of Department, instead of merging linked list functionality with your
> classes? IIRC you questioned this because memory locality and additional levels
> of indirection hurt the performance. Isn't this model flawed? Also, I don't
> think that everyone besides department should be able to see nextComputer and
> nextEmployee, so we need some kind of access control feature, like Eiffel export
> clauses or C++ friendship. There's a third concern about this kind of solution:
> what will happen when two classes, let them be Department and TechSupport, need
> to maintain distinct lists of Computer (e.g. department resources and broken
> computers). With this model we'll force every Computer instance to have n member
> variables, where n is the number of lists needed, even if they aren't in the
> lists most of the time.
> In this example I don't think that include-like functionality is necessary or a
> good design decision. Otherwise if your problem requires that your classes have
> next references (e.g. modelling chains) then this kind of solution is good. I'm
> looking forward an example where include mechanism (i.e. code inheritance
> without subtyping relationship) is necessary, not just an implementation
> decision.

Hi, Daniel.

This would do the trick for this example.  Eiffel's 'expanded' construct seems to be like Ocaml's "inherit", with the addition of a renaming capability.

I'm not recommending that people implement linked lists in this way, although it is sometimes the right solution.  It's just a simple example that gives C++ fits.

In general, inheriting module funcitonality requires a detailed mapping of constructs.  Eiffel's 'expand' mechanism works, but spreads that mapping over multiple classes.  It also requires careful retyping of references to objects in the base module, which is error-prone and hard work.

Sather's "include" construct does virtually the same thing, just with the entire mapping in one place, and without the need for retyping references.

I really think Sather got module (or framework) level inheritance right with the "include" construct.  Add template frameworks, and you've really got something powerful.

As for a more compelling example that benifits from this capability, any data structures that have embedded directed graphs would be good.  I counted several of them in the application I'm currently working on. For example, wires on PC boards are connected with vias using a data structure isomorphic to directed graphs.  Template frameworks for the graphs are great, but I still need a powerful framework inheritance mechanism, and one with a renaming capability.

Bill