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
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 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
next sibling 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
prev 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);
     }




shouldn't this be

 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);
     }




 shouldn't this be

  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);
     }




 shouldn't this be

  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?


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