January 17, 2003
Daniel Yokomiso wrote:
> Hi,
> 
> Expression templates aren't the only way of achieving performance in "correct" OO systems. In a good type system we can do more agressive inlining of operations, reduce the need for dynamic dispatch, do strictness analysis to ignore partial unnecessary results, do loop unrolling, etc.. All of these are good in every piece of code, not just in some particular mechanism. The problem with expression templates is that they require someone (the library writer) to know how to write code with optimization hints. In C++ template syntax is almost a language of its own. In Common Lisp macro expansion (which can do anything expression templates do and more) gives you similar performance, but the syntax is much more similar to Common Lisp. Scheme also provides a expressive and simple to use macro system.

Very true. Al these parts have to play together. As far as I can see it, the main advantage of expression templates is, just as you say, that C++ templates are a language on their own, allowing a library author to do all kinds of optimizations and complex decisions at compile time. The only use for them is in heavily optimized libraries - otherwise the effort for writing them will never be justified.

Anyhow, in the quest for performance one always has to consider all the bottlenecks, and in the main field of usage for expression templates of C++ - i.e. array calculations - one of the main bottlenecks is the need for temporary copies. And this can only be solved by either implementing far more advanced array manipulations in D directly or give the library authors the tools necessary to do their best.

Ciao,
Nobbi
January 18, 2003
"Norbert Nemec" <nobbi_at_theorie3.physik.uni-erlangen.de@NOSPAM.COM> escreveu na mensagem news:b08u26$2orh$1@digitaldaemon.com...
> Daniel Yokomiso wrote:
>
> > In article <b03d7n$2m9r$1@digitaldaemon.com>, Norbert Nemec says...
> >>-------------------------
> >>The one thing that I dislike most about C++ templates, and which has
been
> >>carried over to D as well, is, that template parameters are not typed. I.e. if I have:
> >>        template <typename T>
> >>        class Test {
> >>                static T add(T a,T b) { return a + b; } /* X */
> >>        };
> >>
> >>        bool foo() {
> >>                return Test<bool>::add(true,false); /* Y */
> >>        };
> >>the compiler actually complains about line /*X*/ which is absolutely correct, instead of telling the user that Test simply should not be instatiated with bool. Now if Test is somewhere deep within a library,
the
> >>application programmer may get a huge bunch of error messages looking
like
> >>a bug somewhere in the library, even though, the actual error was simply the wrong instatiation of a template.
> >>
> >>Solution to this would be something like interfaces in D, specifying a
set
> >>of capabilities of a type (be it a class or a predefined type), and the possibility to restrict parameters in a template definition to such an interface.
> >
> > If you restrict yourself to classes, you can restrict the type
parameters:
> >
> > template TSort(T : Comparable) {
> > }
> >
> > where Comparable is a type or class. AFAIK it's valid D code, if not is should ;-) .
>
> I'm not sure whether that should really be the correct way to say it.
> Otherwise
>         template X(T:T[]) {}
> would mean that T has to be a subtype of T[], which is complete nonsense.
It
> is hard to name the actual meaning of the ":", but it definitely is not
> "subtype of". Actually, I don't have the slightest idea what would be
> better. Perhaps:
>         template X(T:T < Comparable) {}
> as in Sather?


    Maybe if we use the subtype operator <: from theoretical OO work.


template X(T <: Comparable; U; V <: Somethingable, Otherthingable) {}


with multiple constraints possible. Are multiple constraints possible in Sather? I don't remember reading about this in the docs, but I'm sure in Eiffel they aren't.

>
> > I don't think there's any reason for the compiler to always
> > complain about line /*X*/, instead of saying: Template instantiation at
> > line /*Y*/ is invalid because of /*X*/ requirement in template body.
> > Systems with type inference algorithms usually provide some intelligent
> > error messages. There's also some papers about giving intelligent error
> > messages in type inference algorithms.
>
> Problem is, that in C++ code (and in D code as well), one cannot even say where the error lies. Did the library author do something illegal with the argument, or did the application programmer do a wrong instatiation? As long as there is no way to specify what capabilities the parameter types are supposed to have, even the most intelligent compiler cannot say more than: /*Y*/ seems to be wrong because of /*X*/, or even more nested error messages. In a case of 10 nested instantiations, the actual error might be located at any level.
>
> And what it worse: there is no way to completely test the compilability of
a
> template without doing all possible instantiations.


    The way I see it, a template is always correct. The complete set of
requirements that a type parameter must meet is in all the possible usages
inside the template (all execution paths). So if the template requires your
type to provide + & [] .connectToSQL() operations, it's your problem meeting
this. At least until we can add operation interfaces. In current mechanisms
the template determine a structural typing constraint a la OCaml methods on
their parameters.


>
> > C++ template mechanism is very powerful, but almost impossible to get right. Walter writes C++ compiler writes since the beginning of C++, so
he
> > knows about the pitfalls of template mechanism. All these issues about template are causes of several threads in this newsgroup (check the archives where lots of people, including me, argue for a better template mechanism). Blitz++ does a very good usageof templates, I like particularly the tensor notation. But it carries a 750 page language standard behind it, defining the mechanism it uses. Walter wants
something
> > better, we just have to keep throwing him good ideas and critics.
>
> Nothing to say against that! Probably, the whole power of the C++ template mechanism was never actually planned. Actually, the fact that it hides a complete language on its own was even found by accident. And up to now, I guess nobody has really pinned down what the details are that make it so powerful. Guess it will take a good portion of genious to extract that
part
> without carrying over all the drawbacks...
>
> Ciao,
> Nobbi


    Maybe if we ordinary folks think hard enough for sufficient time we can
mimic geniality? ;-)

    Best regards,
    Daniel Yokomiso.

"It is a bit embarrassing to have been concerned with the human problem all
one's life and find at the end that one has no more to offer by way of
advice than 'Try to be a little kinder'."
- Aldous Huxley


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.443 / Virus Database: 248 - Release Date: 11/1/2003


January 18, 2003
"Norbert Nemec" <nobbi_at_theorie3.physik.uni-erlangen.de@NOSPAM.COM> escreveu na mensagem news:b08ums$2p3a$1@digitaldaemon.com...
> Daniel Yokomiso wrote:
> > Hi,
> >
> > Expression templates aren't the only way of achieving performance in "correct" OO systems. In a good type system we can do more agressive inlining of operations, reduce the need for dynamic dispatch, do strictness analysis to ignore partial unnecessary results, do loop unrolling, etc.. All of these are good in every piece of code, not just
in
> > some particular mechanism. The problem with expression templates is that they require someone (the library writer) to know how to write code with optimization hints. In C++ template syntax is almost a language of its own. In Common Lisp macro expansion (which can do anything expression templates do and more) gives you similar performance, but the syntax is much more similar to Common Lisp. Scheme also provides a expressive and simple to use macro system.
>
> Very true. Al these parts have to play together. As far as I can see it,
the
> main advantage of expression templates is, just as you say, that C++ templates are a language on their own, allowing a library author to do all kinds of optimizations and complex decisions at compile time. The only use for them is in heavily optimized libraries - otherwise the effort for writing them will never be justified.
>
> Anyhow, in the quest for performance one always has to consider all the bottlenecks, and in the main field of usage for expression templates of
C++
> - i.e. array calculations - one of the main bottlenecks is the need for temporary copies. And this can only be solved by either implementing far more advanced array manipulations in D directly or give the library
authors
> the tools necessary to do their best.
>
> Ciao,
> Nobbi


    We can add more powerful array operations if they became safer:
http://www.sys.uea.ac.uk/~jrwg/Sisal/ This may solve the problems Expression
Templates try to solve...




---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.443 / Virus Database: 248 - Release Date: 11/1/2003


January 18, 2003
"Daniel Yokomiso" <Daniel_member@pathlink.com> wrote in message news:b06sg3$1m3l$1@digitaldaemon.com...
> I'm glad you're considering adding this to the language. Which kind of
value
> parameters will be possible: just integers or any kind of value?

Probably just integer constants. I like to be conservative on adding these kinds of things until a real need is clear.

> Also there's another problem with current template syntax. We can't define templates which define templatized methods. E.g. a List(T) class with a
method
> List(U) map(U (*operation)(T)). This is a very good thing to have.

I don't understand.

> C# generics
> proposal allows definition of generic classes with generic methods, and
you have
> to instantiate the generic method when you use it, not when you
instantiate the
> generic class. This, together with integer template parameters will allow
D to
> have type-safe unit classes for scientific programming:
>
> // Using CGS unit system
> public template class Unit(int C, int G, int S) {
> private double _value;
> public this(double value) {
> this._value = value;
> }
> public double value() {
> return this._value;
> }
> public Unit(C, G, S) mul(int other) {
> return new Unit(C, G, S)(value() * other);
> }
> public template Unit(C - X, G - Y, S - Z) div(Unit(X, Y, Z) other) {
> return new Unit(C - X, G - Y, S - Z)(value() / other.value());
> }
> }
>
> alias Unit(1, 0, 0) Length;
> alias Unit(0, 1, 0) Mass;
> alias Unit(0, 0, 1) Time;
> alias Unit(1, 0, -1) Speed;
> alias Unit(2, 1, 2) Energy;
>
> const Length metre = new Length(100);
> const Length second = new Time(1);
> const Length kilogram = new Mass(1000);
> const Speed c = 299792458 * metre / second;
>
> Mass m = 100 * kilogram;
> Energy e;
>
> e = m * c * c;
>
> Nice isn't it? Some issues about invalid instantiation can happen if the
code
> uses variables to define dimensions, but I think limiting dimensions to be constant isn't a big problem. I don't think the compiler complexity is a
burden
> when we compare it to the benefits it brings.
>
> Best regards,
> Daniel Yokomiso.
>
>


January 18, 2003
Daniel Yokomiso wrote:
>     Maybe if we use the subtype operator <: from theoretical OO work.
> 
> 
> template X(T <: Comparable; U; V <: Somethingable, Otherthingable) {}
> 
> 
> with multiple constraints possible.

> Are multiple constraints possible in Sather?

No, but you have multiple inheritance (with ingeniously simple mechanisms to avoid all the hassle of it) so you can just pull two interfaces together to a combined one.

>     The way I see it, a template is always correct. The complete set of
> requirements that a type parameter must meet is in all the possible usages
> inside the template (all execution paths). So if the template requires
> your type to provide + & [] .connectToSQL() operations, it's your problem
> meeting this. At least until we can add operation interfaces. In current
> mechanisms the template determine a structural typing constraint a la
> OCaml methods on their parameters.

True, but the core of the problem really is, that you cannot specify those requirements in the interface of the template. That way, a template cannot really be separated into interface and implementation, but you (and the compiler as well) have to read the whole implementation to know the interface.

> Maybe if we ordinary folks think hard enough for sufficient time we can mimic geniality? ;-)

Dream on! Ingenious ideas have always suddenly sprung up from somewhere, and the hardest part always was to recognize them as such. There are probably tons of ingenious ideas hidden in the discussions of this newsgroup, but in the end it will be the responsibility of Walter to pick out the good ones. And that will always need some geniality on its own... :-)


January 18, 2003
Walter wrote:

> "Daniel Yokomiso" <Daniel_member@pathlink.com> wrote:
>> I'm glad you're considering adding this to the language. Which kind of value parameters will be possible: just integers or any kind of value?
> 
> Probably just integer constants. I like to be conservative on adding these kinds of things until a real need is clear.

Hopefully bits and enums as well?


January 18, 2003
"Walter" <walter@digitalmars.com> escreveu na mensagem news:b0b9dm$165s$1@digitaldaemon.com...
>
> "Daniel Yokomiso" <Daniel_member@pathlink.com> wrote in message news:b06sg3$1m3l$1@digitaldaemon.com...
> > I'm glad you're considering adding this to the language. Which kind of
> value
> > parameters will be possible: just integers or any kind of value?
>
> Probably just integer constants. I like to be conservative on adding these kinds of things until a real need is clear.
>
> > Also there's another problem with current template syntax. We can't
define
> > templates which define templatized methods. E.g. a List(T) class with a
> method
> > List(U) map(U (*operation)(T)). This is a very good thing to have.
>
> I don't understand.


    We define a template for a generic list class:

template TList(T) {
    class List {
        T first();
        List rest();
        T get(int index);
        void set(int index, T value);
        int length();
        List slice(int start, int afterEnd);
        List filter(boolean (*predicate)(T));
    }
}

    With all needed operations. One idiom from functional programming is
using a map operation to transverse data-structures using higher-order
functions:


Address getAddress(Employee emp) {
    return emp.address;
}
instance TList(Employee).List employees = ...;
instance TList(Address).List addresses = employees.map(&getAddress);


and map has a body that looks like (types ommited):


map(*operation) {
    List result = new List(this.length());
    for (int i = 0; i < this.length(); i++) {
        result.set(i, operation(get(i)));
    }
    return result;
}


    If *operation is function that maps values of one type into another
type. It's a higher-order function, that means a function that has other
functions as parameters. But map must be generic beyond the scope of initial
template instantiation, because we can instantiate a list template of ints
and use mapping functions that gives lists of doubles (e.g. applying sqrt to
all ints), lists of char[] (e.g. string forms of numbers) or even lists of
ints (e.g. negated values). This application of functions that are
templatized and introduce a second level of parametrization is useful in
lots of different areas, a map function in a list type is one of the
simplest form of using it. Today we have to write another template:


template TMap(T, U) {
    instance TList(U).List ListU;
    instance TList(T).List ListT;
    ListU map(ListT list, U (*operation)(T)) {
        ListU result = new ListU(this.length());
        for (int i = 0; i < list.length(); i++) {
            result.set(i, operation(list.get(i)));
        }
        return result;
    }
}


    And users must always explicitly instantiate the templates and use
tmap.map(list, op) instead of a simpler form list.map(op). There are
functions that may be parametrized with more than one extra type parameter,
so we end with lots of explicit templates. Also the additional templates
must have a way to efficiently access the data from the list type, either
using an external iterator, or something like that, where a generic method
can access the internals of the class without penalty.
    As I said, C# and Java's generics proposal allows this kind of
specialization. Any statically typed functional language has it too. In Java
generic methods look like this:

// snippet from last proposal
class Seq<A> {
    <B> Seq<Pair<A,B>> zip(Seq<B> that) {
        if (this.isEmpty() || that.isEmpty()) {
            return new Seq<Pair<A,B>>();
        } else {
            return new Seq<Pair<A,B>>(
                new Pair<A,B>(this.head, that.head),
                this.tail.<B>zip(that.tail));
        }
    }
}


where Seq is a sequence type, and zip takes two sequences and return a
sequence of pairs taken from each.
    I think we need this kind of functionality, or else we will be forced to
written additional templates for each possible combination of parametrized
methods. Also the trick I used in the last a email of making type-safe unit
types (combining integer parameters and generic methods) won't be available
:-(

    Best regards,
    Daniel Yokomiso.

"Sometimes I think the surest sign that intelligent life exists elsewhere in
the universe is that none of it has tried to contact us."
- Bill Watterson


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.443 / Virus Database: 248 - Release Date: 10/1/2003


January 18, 2003
"Norbert Nemec" <Nobbi_at_theorie3.physik.uni-erlangen.de@NOSPAM.COM> escreveu na mensagem news:b0bej0$18bu$1@digitaldaemon.com...
> Daniel Yokomiso wrote:
> >     Maybe if we use the subtype operator <: from theoretical OO work.
> >
> >
> > template X(T <: Comparable; U; V <: Somethingable, Otherthingable) {}
> >
> >
> > with multiple constraints possible.
>
> > Are multiple constraints possible in Sather?
>
> No, but you have multiple inheritance (with ingeniously simple mechanisms
to
> avoid all the hassle of it) so you can just pull two interfaces together
to
> a combined one.


    Sather provide sub and super typing operator IIRC, but it can be used to
redefine the inheritance hierarchy of two different set of classes? E.g. in
library A there's a method that requires something of type NumericComparable
that is both Numeric and Comparable. In library B exists class C that
inherits from Numeric and Comparable, but not from NumericComparable. The
user of these two libraries may say that C inherits from NumericComparable
too?


>
> >     The way I see it, a template is always correct. The complete set of
> > requirements that a type parameter must meet is in all the possible
usages
> > inside the template (all execution paths). So if the template requires
> > your type to provide + & [] .connectToSQL() operations, it's your
problem
> > meeting this. At least until we can add operation interfaces. In current mechanisms the template determine a structural typing constraint a la OCaml methods on their parameters.
>
> True, but the core of the problem really is, that you cannot specify those requirements in the interface of the template. That way, a template cannot really be separated into interface and implementation, but you (and the compiler as well) have to read the whole implementation to know the interface.
>


    Or rely on the intelligent and informative error messages from the
compiler ;-)


> > Maybe if we ordinary folks think hard enough for sufficient time we can mimic geniality? ;-)
>
> Dream on! Ingenious ideas have always suddenly sprung up from somewhere,
and
> the hardest part always was to recognize them as such. There are probably tons of ingenious ideas hidden in the discussions of this newsgroup, but
in
> the end it will be the responsibility of Walter to pick out the good ones. And that will always need some geniality on its own... :-)
>


    That's why I keep reading posts from several different sources (e.g.:
comp.lang.functional, comp.compilers) and download more papers than I can
read. To improve my geniality skills ;-)

"Norbert Nemec" <Nobbi_at_theorie3.physik.uni-erlangen.de@NOSPAM.COM> escreveu na mensagem news:b0bej0$18bu$1@digitaldaemon.com...
> Daniel Yokomiso wrote:
> >     Maybe if we use the subtype operator <: from theoretical OO work.
> >
> >
> > template X(T <: Comparable; U; V <: Somethingable, Otherthingable) {}
> >
> >
> > with multiple constraints possible.
>
> > Are multiple constraints possible in Sather?
>
> No, but you have multiple inheritance (with ingeniously simple mechanisms
to
> avoid all the hassle of it) so you can just pull two interfaces together
to
> a combined one.


    Sather provide sub and super typing operator IIRC, but it can be used to
redefine the inheritance hierarchy of two different set of classes? E.g. in
library A there's a method that requires something of type NumericComparable
that is both Numeric and Comparable. In library B exists class C that
inherits from Numeric and Comparable, but not from NumericComparable. The
user of these two libraries may say that C inherits from NumericComparable
too?


>
> >     The way I see it, a template is always correct. The complete set of
> > requirements that a type parameter must meet is in all the possible
usages
> > inside the template (all execution paths). So if the template requires
> > your type to provide + & [] .connectToSQL() operations, it's your
problem
> > meeting this. At least until we can add operation interfaces. In current mechanisms the template determine a structural typing constraint a la OCaml methods on their parameters.
>
> True, but the core of the problem really is, that you cannot specify those requirements in the interface of the template. That way, a template cannot really be separated into interface and implementation, but you (and the compiler as well) have to read the whole implementation to know the interface.
>


    Or rely on the intelligent and informative error messages from the
compiler ;-)


> > Maybe if we ordinary folks think hard enough for sufficient time we can mimic geniality? ;-)
>
> Dream on! Ingenious ideas have always suddenly sprung up from somewhere,
and
> the hardest part always was to recognize them as such. There are probably tons of ingenious ideas hidden in the discussions of this newsgroup, but
in
> the end it will be the responsibility of Walter to pick out the good ones. And that will always need some geniality on its own... :-)
>


    That's why I keep reading posts from several different sources (e.g.:
comp.lang.functional, comp.compilers) and download more papers than I can
read. To improve my geniality skills ;-)


January 18, 2003
Daniel Yokomiso wrote:
> "Norbert Nemec" <Nobbi_at_theorie3.physik.uni-erlangen.de@NOSPAM.COM>
>> Daniel Yokomiso wrote:
>> >     Maybe if we use the subtype operator <: from theoretical OO work.
>> >
>> >
>> > template X(T <: Comparable; U; V <: Somethingable, Otherthingable) {}
>> >
>> >
>> > with multiple constraints possible.
>>
>> > Are multiple constraints possible in Sather?
>>
>> No, but you have multiple inheritance (with ingeniously simple mechanisms to avoid all the hassle of it) so you can just pull two interfaces together to a combined one.
> 
> Sather provide sub and super typing operator IIRC, but it can be used to redefine the inheritance hierarchy of two different set of classes? E.g. in library A there's a method that requires something of type NumericComparable that is both Numeric and Comparable. In library B exists class C that inherits from Numeric and Comparable, but not from NumericComparable. The user of these two libraries may say that C inherits from NumericComparable too?

No, but through post-hoc supertyping, he can define MyNumericComparable as a subtype of Numeric and Comparable and a Supertype of C. Anyhow, at that point, the whole class system gets too different from D to be discussed on this list fruitfully.

Ciao,
Nobbi
January 20, 2003
Daniel Yokomiso wrote:
>     We can add more powerful array operations if they became safer:
> http://www.sys.uea.ac.uk/~jrwg/Sisal/ This may solve the problems
> Expression Templates try to solve...

You may also take a look at SAC (Single Assignment C) at http://www.informatik.uni-kiel.de/~sacbase/ which claims to the the official successor of Sisal. Anyway: Both languages are tailored towards high-performance numerical computing. No way to even consider taking D, which is explicitely designed to be a general purpose language in that direction. And just trying to pick bits from them will not buy us much.