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

"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.

"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

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

"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

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

"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

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

"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.

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