www.digitalmars.com         C & C++   DMDScript  

D - Why isn't everything a template?

reply Bill Cox <bill viasic.com> writes:
Hi.

The problem I have with templates is that you have to ask your 
programmers to parameterise their code, and turn it into a template, or 
you don't get the awesome reusability.  My question is this:

Why isn't everything a template by default?

Instead of parameterising code up front, you could reuse code that never 
got that upgrade.  Basically, if a programmer has done his job and 
written a useful algorithm, why can't we just reuse it as if he'd made 
all the identifiers in his code template parameters.

When trying to reuse code, you'd specify what identifiers to make 
parameters, and then instantiate it.

Reguardless of the mechanism, I feel strongly that when a piece of code 
is finished and works, we shouldn't have to muck with it to make it 
reusable.  A program is a mathematically precise definition of an 
algorithm.  Why go through the process of parameterising it?

Bill
Feb 02 2003
parent reply "Walter" <walter digitalmars.com> writes:
"Bill Cox" <bill viasic.com> wrote in message
news:3E3D337D.6030501 viasic.com...
 Reguardless of the mechanism, I feel strongly that when a piece of code
 is finished and works, we shouldn't have to muck with it to make it
 reusable.  A program is a mathematically precise definition of an
 algorithm.  Why go through the process of parameterising it?

What you're describing is in essence a typeless programming language, such as javascript.
Mar 08 2003
next sibling parent reply "Daniel Yokomiso" <daniel_yokomiso yahoo.com.br> writes:
"Walter" <walter digitalmars.com> escreveu na mensagem
news:b4dof2$pej$1 digitaldaemon.com...
 "Bill Cox" <bill viasic.com> wrote in message
 news:3E3D337D.6030501 viasic.com...
 Reguardless of the mechanism, I feel strongly that when a piece of code
 is finished and works, we shouldn't have to muck with it to make it
 reusable.  A program is a mathematically precise definition of an
 algorithm.  Why go through the process of parameterising it?

What you're describing is in essence a typeless programming language, such as javascript.

Hi, There are several layers of parametrization possible when a language allows you to use higher-order functions. A simple recursive binary search looks like this: int binarySearch(int[] array, int item) { in { assert(isSorted(array)); } out(result) { assert(result >= -1); if (result >= 0) { assert(array[result] == item); } if (array.length == 0) { assert(result == -1); } } body { if (array.length == 0) { return -1; } int middle = array.length / 2; if (array[middle] == item) { return middle; } else if (array[middle] < item) { return binarySearch(array[middle + 1 .. array.length], item); } else { return binarySearch(array[0 .. middle], item); } } Hmmm, the obvious parametrization is at type, so we could use a template. This simple parametrization work for every type that provides a comparison operation, but some don't. If we parametrize over this we get: // type parametrization included // contracts removed for brevity public int binarySearch(T[] array, int function(T, T) order, T item) { if (array.length == 0) { return -1; } else { int middle = array.length / 2; if (order(item, array[middle]) == 0) { return middle; } else if (order(item, array[middle]) == -1) { return binarySearch(array[0 .. middle], order, item); } else if (order(item, array[middle]) == +1) { return binarySearch(array[middle + 1.. array.length], order, item); } else { assert(0); // here we protect ourselves against bad order functions return -1; // just pleasing the compiler } } } The original version looks like: public int binarySearch(T[] array, T item) { // using DTL ascending comparison function. return binarySearch(array, cmp.ascending, item); } Much better isn't it? Wait again, we assume that our user wants to compare againt a passed item. We can simulate this behaviour using a order function that encloses (closure-like) the search item. We also can parametrize the return of the function to be a generic function that'll be applied to the (index, value) pair that satisfies the ordering function: public int binaryApply(T[] array, int function(T) order, S function(int, T) apply) { if (array.length == 0) { return apply(-1, null); } else { int middle = array.length / 2; if (order(array[middle]) == 0) { return apply(middle, array[middle]); } else if (order(array[middle]) == -1) { return binaryApply(array[0 .. middle], order, apply); } else if (order(array[middle]) == +1) { return binaryApply(array[middle + 1.. array.length], order, apply); } else { assert(0); // here we protect ourselves against bad order functions return apply(-1, null); // just pleasing the compiler } } } The original version looks like: public int binarySearch(T[] array, int function(T, T) order, T item) { // using DTL ascending comparison function. return binaryApply(array, int function(T each) {return order(each, item);}, int function(int index, T each) {return index;}); } We could parametrize the slicing of the array and let the binaryApply operation work on any type that provides a threeWaySplit function, that given a ordering function returns the before and after slices and the middle element. We could also parametrize the algorithm we use to obtain the middle index, and get a more generic divideAndConquer function (it's not binary if we don't divide by two anymore ;-) ). Any algorithm can be parametrized over all operations it uses. Studying lambda calculus we see that all functions can be defined using two combinator s and k: k = \x.\y.x s =\x.\y.\z.(x z) (y z) \ means lambda. In D (without currying k and s parameters) they would look like: T k(T x, U, y) { return x; } T s((T function(S)) function(R) x, S function(R) y, R z) { return x(z)(y(z)); } That's as abstract as abstract can get. Well you curry k and s parameters in D too, but I leave this as an exercise to the reader. The point is that everything can be parametrized, loops, operations, ifs, gotos, etc. not just types and values. But if you parametrize everything you get something like unlambda. Templates are a nice way to parametrize algorithms, either types or functions. TANSTAFL as the tribe's elders used to say. Best regards, Daniel Yokomiso. P.S.: Every time someone equates "templates = generic parameter types for languages without function types" I feel a terrible urge to tell them to read something like STL sourcecode or the Haskell prelude. This usually enlightens them. "It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration." - Edsger W. Dijkstra --- Outgoing mail is certified Virus Free. Checked by AVG anti-virus system (http://www.grisoft.com). Version: 6.0.459 / Virus Database: 258 - Release Date: 25/2/2003
Mar 08 2003
next sibling parent reply "Mike Wynn" <mike.wynn l8night.co.uk> writes:
may seem a little picky but ....
"Antti Sykari" <jsykari gamma.hut.fi> wrote in message
news:87bs0lpe6a.fsf hoastest1-8c.hoasnet.inet.fi...
 As a side note:

 "Daniel Yokomiso" <daniel_yokomiso yahoo.com.br> writes:

 int binarySearch(int[] array, int item) {
 in {
     assert(isSorted(array));
 } out(result) {
     assert(result >= -1);
     if (result >= 0) {
         assert(array[result] == item);
     }
     if (array.length == 0) {
         assert(result == -1);
     }


int binarySearch(int[] array, int item) { in { assert( array !== null ); // get the assert here rather than from isSorted. assert(isSorted(array)); } out(result) { assert(result >= -1); if (array.length == 0) { // check the length before getting array index exception assert(result == -1); } if (result >= 0) { assert( result < array.length ) // get an assert rather than an other possible array index exception from the assert. assert(array[result] == item); } if( result < 0 ) { for( int i =0; i < array.length; i++ ) { if (array[i] == item) { assert( false ) } } } } which reduces to } out(result) { assert( result < array.length ) // get an assert rather than an array index exception from the assert. if (result >= 0) { assert(array[result] == item); }else { assert(result == -1); for( int i =0; i < array.length; i++ ) { if (array[i] == item) { assert( false ) } } } }
Mar 08 2003
parent reply "Daniel Yokomiso" <daniel_yokomiso yahoo.com.br> writes:
"Mike Wynn" <mike.wynn l8night.co.uk> escreveu na mensagem
news:b4e74v$vut$1 digitaldaemon.com...
 may seem a little picky but ....
 "Antti Sykari" <jsykari gamma.hut.fi> wrote in message
 news:87bs0lpe6a.fsf hoastest1-8c.hoasnet.inet.fi...
 As a side note:

 "Daniel Yokomiso" <daniel_yokomiso yahoo.com.br> writes:

 int binarySearch(int[] array, int item) {
 in {
     assert(isSorted(array));
 } out(result) {
     assert(result >= -1);
     if (result >= 0) {
         assert(array[result] == item);
     }
     if (array.length == 0) {
         assert(result == -1);
     }


int binarySearch(int[] array, int item) { in { assert( array !== null ); // get the assert here rather than from isSorted. assert(isSorted(array)); } out(result) { assert(result >= -1); if (array.length == 0) { // check the length before getting array index exception assert(result == -1); } if (result >= 0) { assert( result < array.length ) // get an assert rather than an other possible array index exception from the assert. assert(array[result] == item); } if( result < 0 ) { for( int i =0; i < array.length; i++ ) { if (array[i] == item) { assert( false ) } } } } which reduces to } out(result) { assert( result < array.length ) // get an assert rather than an array index exception from the assert. if (result >= 0) { assert(array[result] == item); }else { assert(result == -1); for( int i =0; i < array.length; i++ ) { if (array[i] == item) { assert( false ) } } } }

Yes, you're correct. I just wrote down the contract without trying to make it less verbose. Your version is nicer than mine, as it makes explicit the relation between the valid results and the array length. Can I put your version in the contracts of binarySearch in DTL? --- Outgoing mail is certified Virus Free. Checked by AVG anti-virus system (http://www.grisoft.com). Version: 6.0.459 / Virus Database: 258 - Release Date: 25/2/2003
Mar 08 2003
parent "Mike Wynn" <mike.wynn l8night.co.uk> writes:
"Daniel Yokomiso" <daniel_yokomiso yahoo.com.br> wrote in message
news:b4f83b$1gcc$1 digitaldaemon.com...
 "Mike Wynn" <mike.wynn l8night.co.uk> escreveu na mensagem
 news:b4e74v$vut$1 digitaldaemon.com...
 may seem a little picky but ....
 "Antti Sykari" <jsykari gamma.hut.fi> wrote in message
 news:87bs0lpe6a.fsf hoastest1-8c.hoasnet.inet.fi...
 As a side note:

 "Daniel Yokomiso" <daniel_yokomiso yahoo.com.br> writes:

 int binarySearch(int[] array, int item) {
 in {
     assert(isSorted(array));
 } out(result) {
     assert(result >= -1);
     if (result >= 0) {
         assert(array[result] == item);
     }
     if (array.length == 0) {
         assert(result == -1);
     }


int binarySearch(int[] array, int item) { in { assert( array !== null ); // get the assert here rather than from isSorted. assert(isSorted(array)); } out(result) { assert(result >= -1); if (array.length == 0) { // check the length before getting array index exception assert(result == -1); } if (result >= 0) { assert( result < array.length ) // get an assert rather than an other possible array index exception from the assert. assert(array[result] == item); } if( result < 0 ) { for( int i =0; i < array.length; i++ ) { if (array[i] == item) { assert( false ) } } } } which reduces to } out(result) { assert( result < array.length ) // get an assert rather than an


 index exception from the assert.
      if (result >= 0) {
          assert(array[result] == item);
     }else {
        assert(result == -1);
        for( int i =0; i < array.length; i++ ) { if (array[i] == item) {
 assert( false ) } }
     }
  }

Yes, you're correct. I just wrote down the contract without trying to make it less verbose. Your version is nicer than mine, as it makes explicit the relation between the valid results and the array length. Can I put your version in the contracts of binarySearch in DTL?

Yes, no problem, the point I was trying to make was your where missing failures and the contract had potential to cause exceptions, two things in my mind that should be avoided, having added those, all I did was reorder to remove the redundant checks. as an aside the reduced form does make explicit the relationship between valid results and array length which had I been thinking clearly I possible would have started with anyway as it is the most important check, I also think that checking failure is correct is also important it may be slow, it could be changed to }else { assert(result == -1); for( int i =0; i < array.length; i++ ) { assert( array[i] != item ); } } I was thinking that the isSorted check could be delayed until the end too } out(result) { bit found = false; assert( result < array.length ); if ( array.length > 0 ) { found = (array[0] == item); for( int i = 1; i < array.length; i++ ) { found |= (array[i] == item); assert( array[i-1] <= array[i] ); } } if (result >= 0) { assert( array[result] == item ); }else { assert((result == -1) && (!found)); } } although that's just a performance idea, as I don't know a way to perform the found check in the in contract and pass it to the out (the only Idea I had was a nested function ) int find( int[] ar, int i ) { bit found = false; int real_find( int[] ar, int i ) in { found = isFoundAssertOrdered(); } out { .... } body { ....... } return real_find( ar, i ); } as I feel that ordered is an input contract and item existing is an output contract I would not delay the checks (are two itterations through the array actually that expensive). anyway I'm jibbering must get some sleep today.
Mar 09 2003
prev sibling next sibling parent reply Bill Cox <bill viasic.com> writes:
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. 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. Bill
Mar 09 2003
parent reply Daniel Yokomiso <Daniel_member pathlink.com> writes:
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.
Mar 10 2003
parent reply Bill Cox <bill viasic.com> writes:
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
Mar 10 2003
parent reply Daniel Yokomiso <Daniel_member pathlink.com> writes:
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).
Mar 11 2003
parent reply Bill Cox <bill viasic.com> writes:
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
Mar 12 2003
parent reply Daniel Yokomiso <Daniel_member pathlink.com> writes:
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
Mar 12 2003
parent Bill Cox <bill viasic.com> writes:
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
Mar 12 2003
prev sibling parent reply "Jeroen van Bemmel" <anonymous somewhere.com> writes:
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
Mar 09 2003
parent Bill Cox <bill viasic.com> writes:
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
Mar 09 2003
prev sibling parent reply Antti Sykari <jsykari gamma.hut.fi> writes:
As a side note:

"Daniel Yokomiso" <daniel_yokomiso yahoo.com.br> writes:

 int binarySearch(int[] array, int item) {
 in {
     assert(isSorted(array));
 } out(result) {
     assert(result >= -1);
     if (result >= 0) {
         assert(array[result] == item);
     }
     if (array.length == 0) {
         assert(result == -1);
     }

These two make assertions made me want the operator "implies"... equivalent to: bit implies(bit lhs, bit rhs) { return !lhs || rhs; } but infix... assert(result >= 0 implies array[result] == item); assert(array.length == 0 implies result == -1); or even assert(result >= 0 => array[result] == item); assert(array.length == 0 => result == -1); Well, might not be that much readable anyway. But a nice convention perhaps. -Antti
Mar 08 2003
parent "Daniel Yokomiso" <daniel_yokomiso yahoo.com.br> writes:
"Antti Sykari" <jsykari gamma.hut.fi> escreveu na mensagem
news:87bs0lpe6a.fsf hoastest1-8c.hoasnet.inet.fi...
 As a side note:

 "Daniel Yokomiso" <daniel_yokomiso yahoo.com.br> writes:

 int binarySearch(int[] array, int item) {
 in {
     assert(isSorted(array));
 } out(result) {
     assert(result >= -1);
     if (result >= 0) {
         assert(array[result] == item);
     }
     if (array.length == 0) {
         assert(result == -1);
     }

These two make assertions made me want the operator "implies"... equivalent to: bit implies(bit lhs, bit rhs) { return !lhs || rhs; } but infix... assert(result >= 0 implies array[result] == item); assert(array.length == 0 implies result == -1); or even assert(result >= 0 => array[result] == item); assert(array.length == 0 => result == -1); Well, might not be that much readable anyway. But a nice convention perhaps. -Antti

It'll give us a problem, because implies is lazy. It must have the same semantics as a short-circuit "and" or "or". Perhaps using anonymous functions we can make it without compiler magic: assert(result >= 0 => bit function() {return array[result] == item;}); Ugh! In Smalltalk it works: assert: (result >= 0) => [(array at result) == item]. Some kind of block syntax would be necessary to make things non-intrusive. --- Outgoing mail is certified Virus Free. Checked by AVG anti-virus system (http://www.grisoft.com). Version: 6.0.459 / Virus Database: 258 - Release Date: 25/2/2003
Mar 08 2003