Re: Templates in FPL?
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
On 22-May-2001, Carl R. Witty <cwitty@newtonlabs.com> wrote:
I agree with Marcin about the bad points of templates.
Me too. Marcin summed it up very well. Of the five disadvantages that he mentioned, I think at least three (lack of explicit interfaces, incredibly complicated rules about name lookup, and very poor error messages) are very serious problems. For an example of the problems caused by the lack of explicit interfaces, the C++ standards committee has still not agreed on what the interface to vector is. The standard is contradictory, because the vector<bool> specialization doesn't obey the rules specified for vector<T>, and as yet there's no concensus about which should be changed. For an example of the problems caused by the complicated rules about name lookup, just today someone posted a bug report for gcc 2.95.* to gcc@gcc.gnu.org, reporting a problem where one of the standard library templates didn't work when they had a typedef named `destroy' in their code. My guess is that it was probably because the standard library code was using the function std::destroy(), but the standard library implementor didn't realize that it had to be explicitly namespace qualified; in other words, the rules were too complex and/or too cumbersome for the standard library developer to understand and/or apply. Marcin already posted a good example of a poor error message ;-)
(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.)
Yes... hence overlapping type classes are EVIL! ;-) ;-) ;-) ;-)
There are some very cool things about C++ templates; they are more powerful than you might suspect.
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; 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).
Right. It wasn't designed for that purpose, it just turned out that it could be used for it. It's a bit like that simulation of Conway's game of life in vi macros! Makes for a very impressive demo, but there are serious drawbacks to using such techniques in day-to-day work. I agree that it would be very nice if Haskell and other FPLs had some equivalent feature, with a nicer syntax. I think you might be able to do a lot of it using ordinary Haskell syntax with just some additional annotation that directs the compiler to evaluate part of the program at compile time. -- Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit | of excellence is a lethal habit" WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
Fergus Henderson :
I agree that it would be very nice if Haskell and other FPLs had some equivalent feature, with a nicer syntax. I think you might be able to do a lot of it using ordinary Haskell syntax with just some additional annotation that directs the compiler to evaluate part of the program at compile time.
Actually, whole my posting was driven by that. (And by Clean macros which are not macros, but not yet templates, and by the fact that you can parameterize templates with constants, and Haskell classes not). Yours anwers, very thorough, concentrated sometimes on the realization of templates in C++, and I am the last to defend them, or to want to see them implemented in Haskell. But, as a - not too run-time-expensive way to deal with some facets of polymorphism by compiling specialized functions, it is a possible option. The syntactic issues, and the relation of these "macros" to class system is another story. Thanks. Jerzy Karczmarczuk Caen, France
At 02:35 AM 5/24/2001 +1000, Fergus Henderson wrote:
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; 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).
Right. It wasn't designed for that purpose, it just turned out that it could be used for it. It's a bit like that simulation of Conway's game of life in vi macros! Makes for a very impressive demo, but there are serious drawbacks to using such techniques in day-to-day work.
:) So true. In some ways, it sounds great: here we have a useful general-purpose feature that you can use for all kinds of things (a programming Swiss army knife, so to speak), and then build all kinds of _concrete_ useful things with it. Problem is that it doesn't allow you to redefine the syntax in any way. Thus, you can do compile-time assertions, computations, things like that, but the meaning of what you want to do often gets quite obfuscated by this syntax and by the contrived compiler error messages. I must say, though, that the beta compiler of MSVC 7 does a MUCH improved work on it.
I agree that it would be very nice if Haskell and other FPLs had some equivalent feature, with a nicer syntax. I think you might be able to do a lot of it using ordinary Haskell syntax with just some additional annotation that directs the compiler to evaluate part of the program at compile time.
This is close to my personal vision. That is, a language that handles both run-time and compile-time computations seamlessly. Thus, the compiler would evaluate as much as it can, and then what's left is put in the executable. I assume that's something optimizing compilers for Haskell already do, at least in part. Problem is that, ideally, the language should allow the programmer to be explicit about things that should be done at compile-time and things that should be done at run-time, which Haskell doesn't quite have. Let's see how this could work: - IO actions must be executed at run-time, evidently. - We might be able to define another action monad (let's call it "CT", for compile-time) which defines just the opposite: an action that must be executed by the compiler. - We'd need a new primitive function: executeCompilerAction :: CT a -> a - And we'd need another: compilerEval :: a -> CT a So, let's say we want to force this program: main = print (fact 1000) to evaluate the factorial expression at compile-time. Then, we'd write something like: main = print (executeCompilerAction (compilerEval (fact 1000))) Of course, we'd eventually define any useful recurring patterns as new functions, as in here: eval a = executeCompilerAction (compilerEval a) Anyway, I don't know if I'm making much sense here. Just letting my brains fly on their own. Then, there's the explicit handling of types which templates allow and Haskell doesn't. I think that, the hardest part of Haskell that I'm having trouble with here is the way overloading is defined, using classes. I still have problems with that. Some times it is really obvious that it's best. Some other times, it really doesn't seem to fit (finding about the multi-parameter class extension was a very gratifying moment there). I can think of something that I don't know how to do in Haskell. Suppose that I have two classes, which I'll call Class1 and Class2: class Class1 a where func1 :: a -> Bool class Class2 a where ... (doesn't matter what goes here) And say that I want to express the fact that ALL types that are instances of Class2 will ALWAYS be instances of Class1, and will always return "False" from "func1". So, is there any way to express this kind of class-relationship in Haskell? It's not definitely inheritance, I think. Salutaciones, JCAB --------------------------------------------------------------------- Juan Carlos "JCAB" Arevalo Baeza | http://www.roningames.com Senior Technology programmer | mailto:jcab@roningames.com Ronin Entertainment | ICQ: 10913692 (my opinions are only mine) JCAB's Rumblings: http://www.metro.net/jcab/Rumblings/html/index.html
participants (4)
-
cwitty＠newtonlabs.com -
Fergus Henderson -
Jerzy Karczmarczuk -
Juan Carlos Arevalo Baeza