Templates in FPL?

[Carl R. Witty]

Jerzy Karczmarczuk <karczma@info.unicaen.fr> writes:

> We know that a good part of "top-down" polymorphism (don't ask me what
> do I mean by that...) in C++ is emulated using templates.
> 
> Always when somebody mentions templates in presence of a True Functionalist
> Sectarian, the reaction is "What!? Abomination!!".
> 
> Now the question: WHY?
> 
> Why so many people say "the C++ templates are *wrong*" (and at the same time
> so many people use it every day...)

I agree with Marcin about the bad points of templates.  (I'd like to
point out, though, that the idea that "adding new code can't change
the meaning of a program" no longer holds in Haskell extended with
overlapping type classes.)

> Is it absolutely senseless to make a functional language with templates?
> Or it is just out of fashion, and difficult to implement?

There are some very cool things about C++ templates; they are more
powerful than you might suspect.  (Note: the following summarizes and
paraphrases several papers I've read on the topic; let me know if you
want more information and I'll look up references for you.)

Basically, templates let you extend the compiler.  You get a primitive
functional programming language, with which you can do basically
arbitrary computations on types and on integers; this language can be
used to generate special-purpose code.  One way to look at this is as
a form of partial evaluation (although there's nothing which
automatically decides which computation to do at compile time and
which at run time).

In the functional programming language, you have conditionals, the
usual arithmetic operations, pairing, recursion, etc.; basically, it's
a real programming language (although a very annoying one -- the
syntax is atrocious).

Here are a few examples of the kind of thing you can do with C++
templates:

* Compute log base 2 at compile time.  You can write a template such
that if n is a compile-time constant, Log2<n>::val is its log base 2.

* Generate FFT routines.  You can write a template such that if n is a
compile-time constant which is a power of 2, then FFT<n>::do_fft() is
a routine which computes an FFT on an array of size n, as a single
chunk of straight-line code (no loops).  (Not necessarily useful -- it
generates a lot of code for reasonable-sized arrays, and cache effects
probably mean that something with loops is more efficient -- but cool
nonetheless.)

* Implement lambda (over a subset of full C++).  You can make
lambda(X, a*(X+b)) do "the right thing" (basically by arranging for
the expression a*(X+b) to have a type like 
	Times<Num, Plus<PlaceholderX, Num> >
and then writing a function using recursion over this type).

These techniques are useful when you're going for speed and
generality; I would certainly imagine that such things could be useful
in a functional programming language as well.  In fact, over the past
few weeks, people on the Haskell mailing lists have been trying to do
vaguely similar kinds of compile-time computation at the type level,
using type classes and functional dependencies.

On the other hand, C++ templates have huge flaws for this kind of
thing.  As I mentioned, the syntax is atrocious; also, there are lots
of things you would like to do which are apparently just out of reach
(the template language is not quite powerful enough).

I'd like to see somebody make a serious effort to add this kind of
compile-time processing to Haskell.  It might not look anything like
templates; something like OpenC++ and OpenJava might be better.
(These are C++ and Java compilers which are extensible; you can write
compiler extension modules using a standard API, and the compiler
dynamically loads your extensions.)  

There is a big reason why C++ templates (or any other form of
compile-time arbitrary computation on types) would be hard to add to
Haskell: type inference and polymorphism.  For C++ templates, you need
to know the argument types before you can do the template processing,
and you cannot know the type of the result until the processing is
done.  Probably this facility would only be useful for monomorphic
parts of your program, which might mean it's not appropriate for
Haskell at all.

Carl Witty