template functions 
Author Message
 template functions

I've just told some little white lies over on
comp.os.linux.development.apps, in a thread entitled "Why not C++".

I've implied that Dylan compilers automatically template expand methods
(or will be able to soon). In actual fact I know that d2c doesn't do that
now, and I don't know of any plans to make it do it.

Does Harlequin Dylan template expand functions?

My comp.os.linux.development.apps post follows.  Comments?  I sure don't
see any reason that this *couldn't* be done.

-- Bruce

---------------------------------


Quote:

> Could you describe what you don't like about C++ templates, and how a
> statically-checked language that intends to minimize runtime cost could
> do better?

Well, here's what *I* don't like about C++'s templates...

Actually, C++ templates are just fine -- they're probably one of the best
parts of the language.

The *problem* is that C++ templates are an ad-hoc solution to just one
problem, and C++ has too *many* ad-hoc solutions.  When you write a
function in C++ you've got to choose between template functions, inline
functions, overloaded functions, virtual functions ... it's a mess.  (Yes,
I know those choices aren't orthogonal, and can be combined -- that just
makes it worse.)

Bjarne Stroustrup started with the simple "one name = one function"
principle in C and added on on virtual functions with runtime dispatch on
the first argument so that he could emulate Simula.

Then he thought "wouldn't it be nice if you could write new versions of
'+' and '<' and use the same name for several similar functions of your
own?".  So he created overloaded functions, which are a completly
different and incompatable thing from virtual functions.

To try to close the gap between overloaded functions and virtual functions
a bit, he eventually added template functions, which basically let you
write a number of overloaded functions more economically.

It's a big untidy mess.  And sometimes you actually can't do what you want
to do.

Don't get me wrong -- I greatly admire Bjarne Stroustrup and think he did
a great job, and C++ was a big improvement on the state-of-the-art in 1980
when he started to implement it (or 1990, when it started to spread
widely).  But I think it's time to move on now.

Quote:
> how a statically-checked language that intends to minimize runtime cost
> could do better?

Ok, let's look at what happens in Dylan.

Dylan has only *one* kind of function -- the generic method -- but
depending on the circumstances, the compiler will do any of:

- compile time selection of the right function
  - inlining of the right function
  - outlining of the right function (using it as a template)
- run time selection of the right function

Let's look at an example:

define inline method myAdd(a, b)
  a + b;
end myAdd;

define method f(x, y)
  myAdd(x, y);
end f;

define method g(x :: <integer>, y :: <integer>) => (z :: <integer>)
  myAdd(x, y);
end g;

define method h(x :: <single-float>, y :: <single-float>)
=> (z :: <single-float>)
  myAdd(x, y);
end h;

Look at "myAdd".  Unlike g and h, it doesn't declare the paramter types,
or the return value type(s).  What sort of function is it?  You could
think of it either as a C++ template function with a and b declared to be
of some unspecified type...

template<class T> T myAdd(T a, T b){
   return a + b;

Quote:
}

... but it's bit more than that.  C++ templates require that the actual
types of a and b be known at compile time.  This C++ template requires
that a and b be of the *same* type, which is also the type of the result.
But with the Dylan function the arguments could be of different types,
more like this:

template<class T1, class T2> ???? myAdd(T1 a, T2 b){
   return a + b;

Quote:
}

But this is not easy in C++.  What is the function return type?  T1?  Not
necessarily.  T2?  Not necessarily.  Something else?  But *what* else?
It's impossible to say.  Dylan doesn't care.

You could also think of myAdd as being like a C++ virtual function that is
not actually part of a class, and that does runtime type dispatch based on
the types of *both* arguments, not just the first one.

Let's see what "d2c" (see < http://www.*-*-*.com/ >) does with this --
here is the C code output by d2c (with my comments after //):

// This is a reference to the "generic function" (i.e. runtime virtual
// function dispatch) for "+"

extern descriptor_t dylanZdylan_visceraZPLUS;   /* + */

// This is the "virtual function" method for myAdd, used when the compiler
// doesn't know the types of the operands at compile time, and doesn't
// inline it either for some reason -- which doesn't happen in this example.

/* myAdd{<object>, <object>} */
descriptor_t * templateZtemplateZmyadd_METH(
   descriptor_t *orig_sp, descriptor_t A0 /* a */, descriptor_t A1 /* b */
){
    descriptor_t *cluster_0_top;
    orig_sp[0] = A0;
    orig_sp[1] = A1;
    /* + */
    cluster_0_top = GENERAL_ENTRY(dylanZdylan_visceraZPLUS.heapptr)(
       orig_sp + 2, dylanZdylan_visceraZPLUS.heapptr, 2
    );
    return cluster_0_top;

Quote:
}

// This is "f".  The compiler has inlined the code for myAdd, so this looks
// just the same as the code for myAdd (above).

/* f{<object>, <object>} */
descriptor_t * templateZtemplateZf_METH(
   descriptor_t *orig_sp, descriptor_t A0 /* x */, descriptor_t A1 /* y */
){
    descriptor_t *cluster_0_top;
    orig_sp[0] = A0;
    orig_sp[1] = A1;
    /* + */
    cluster_0_top = GENERAL_ENTRY(dylanZdylan_visceraZPLUS.heapptr)(
       orig_sp + 2, dylanZdylan_visceraZPLUS.heapptr, 2
    );
    return cluster_0_top;

Quote:
}

// now we get to the interesting part!  Not only was the code for myAdd
// inlined, the compiler also knew the types of the parameters, so it
// was able to replace the virtual dispatch of "+" in myAdd with direct
// use of an integer add instruction, just as you would get in C++
// inline template functions

/* g{<integer>, <integer>} */
long templateZtemplateZg_METH(
   descriptor_t *orig_sp, long A0 /* x */, long A1 /* y */
){
    return (A0 + A1);

Quote:
}

// just the same as the above function, but this time it's inlined to a
// direct use of a floating-point add instruction.  Which just happens to
// look the same in C, but that's not essential -- it could have been '+'
// for a user-defined class, in which case d2c would have use the appropriate
// C function call for that class.

/* h{<single-float>, <single-float>} */
float templateZtemplateZh_METH(
   descriptor_t *orig_sp, float A0 /* x */, float A1 /* y */
){
    return (A0 + A1);

Quote:
}

Now, in this case, d2c has decided to inline all uses of myAdd().  But
this isn't essential.  If myAdd() had been something a bit more
complicated then it might have choosen not to inline it, but to instead
use it as a template to create specialised versions of myAdd().

We can force the issue (and demonstrate the point) by adding the following
functions:

define method myAdd(a :: <integer>, b :: <integer>, #next super)
=> (c :: <integer>)
  super();
end myAdd;

define method myAdd(a :: <single-float>, b :: <single-float>, #next super)
=> (c :: <single-float>)
  super();
end myAdd;

This is essentially identical in purpose and effect to C++ explicit
instantiation of template functions.

"super()" is essentially the same idea as "super" in Java or Smalltalk or
"inherited" in Object Pascal (or the unsucessful C++ "inherited::"
proposal -- see section 13.6 in "The Design and Evolution of C++") --
except that in Dylan it applies to any overloaded function, not just
virtual functions.  (btw, the name "super" is arbitrary, and in fact the
conventional name in Dylan code is "next-method").  The meaning, as usual,
is "call the function that would have been called in the first place, had
the current function not existed"

This change results in the C code output from d2c including the following
functions:

/* myAdd{<integer>, <integer>} */
long templateZtemplateZmyadd_METH_2(
   descriptor_t *orig_sp, long A0 /* a */, long A1 /* b */, heapptr_t A2
){
    return (A0 + A1);

Quote:
}

/* myAdd{<single-float>, <single-float>} */
float templateZtemplateZmyadd_METH(
   descriptor_t *orig_sp, float A0 /* a */, float A1 /* b */, heapptr_t A2
){
    return (A0 + A1);

Quote:
}

In this case we've forced the compiler to produce this.  If the contents
of "myAdd" were a bit more complex then a smart compiler (d2c isn't smart
enough right now, but I'm hoping we'll make it smart enough soon) would
generate these functions automatically, for use when the types of a and b
were known but it wasn't worth inlining the whole function.

Unlike C++ template functions, these specialised functions are also useful
when the types of a and b are NOT known in advance, but fortuitously turn
out to be <integer> or <single-float> at run time.  The specialised method
will automatically be called, rather than the general one, which will
result in not having to do virtual (generic) calls of arithmetic,
comparisons etc inside the function, and it may result in more efficient
calling (or even inlining) of any other functions called from within
myAdd().

I hope that I have demonstrated that a single simple mechanism in Dylan
can sucessfully replace *all* the different kinds of functions in C++,
with no loss of efficiency over C++.

I'll just point out at the end that the Dylan compiler I've used as the
example, d2c, is a free open source compiler that is still under active
development.  Hopefully it will soon automatically inline and outline
(template expansion) functions automatically rather than needing the hints
I've used here.

d2c happens to generate C code, which is then compiled using gcc (or
other).  This is convenient for the purposes of this note, because it
means we don't have to delve through Pentium or PowerPC or other machine
code to see what's going on  under the covers.  I have not altered the
genuine output of d2c except to clean up the formating and remove
extraneous comments and ...

read more »



Thu, 13 Dec 2001 03:00:00 GMT  
 template functions

Quote:

> I've implied that Dylan compilers automatically template expand methods
> (or will be able to soon).

It seems as though you can do this relatively easy with macros regardless
of inline capabilities of a particular implementation.  

something along the following lines.

define  template-fragment foo ( a  , b )
     .... a ... b ...
end

[ some "sugar" for defining the approriate marco. ]

then used

         foo (  c , d )

would give a more function like flavor to the macro.

Inlining everywhere isn't quite the same as a template function.  
Nor the substitution by a macro.  The macro would have to
obey the hygiene rules.  Inlining a function should do the same.

Both of these will lead to far greater bloat than the instantiation of
a function template.  The latter should be instantiation once per requested
type(s), not per call site.

I think your approach here is that the inlining process will automagically
associate the local, more specific var-name/type with the arguments.   A
macro seems more direct way of doing that.

What you have a bit of a problem doing in Dylan in the name-mangling and
just-in-time instantiate of a function template during compliation.  

---

Lyman



Thu, 13 Dec 2001 03:00:00 GMT  
 template functions


Quote:
>I believe Cecil calls this optimization "copy-down methods", because it is as
>if you textually copied methods on an abstract class down to a specific
>implementation class (whereby you can eliminate dispatching within the method
>because you know the specific type of each parameter).

This is also what Apple Dylan called them.

--

                                            http://www.folly.org/~alms
This is our garden, although we have no grass.
-Bahrije Baftiu, Kosavar refugee in Macedonia



Fri, 14 Dec 2001 03:00:00 GMT  
 template functions

A template is a way to trick the user into writing an optimization that a good compiler should be able to do for itself.  But no compiler can make the needed inferences in C++ because there are too many back-doors in the type system, hence the user is required to inform the compiler that he does not plan to use any of those backdoors by writing a template.

I believe Cecil calls this optimization "copy-down methods", because it is as if you textually copied methods on an abstract class down to a specific implementation class (whereby you can eliminate dispatching within the method because you know the specific type of each parameter).



Sat, 15 Dec 2001 03:00:00 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. Template Function

2. Standard functions ABC-templates

3. Copy File Function - 3rd Party Template

4. Function, using CW4 with Clarion templates.

5. ALIAS Function with Super Invoice Template

6. Date @ Get Function String/Template

7. New Product - PictureDialog() function w/Templates

8. Math Template -ATAN2 Function

9. Function Declaration by Template generation...

10. Need function template for generell tuple construction out of lists

11. Function Template for NASM and IBMCPP on OS/2

12. function templates for fast callbacks

 

 
Powered by phpBB® Forum Software