Re: [boost] About template metaprogramming and functional programming

From: John Max Skaller (skaller_at_[hidden])
Date: 2001-07-25 16:39:56

Vesa Karvonen wrote:

> > The question is, if you knew some FP, why would you bother
> > with C++ in the first place?

> Although FP seems very interesting, I'm not yet convinced that it is The
> paradigm. 

        The key problem may perhaps be summarised
by the requirement for 'seamless integration of functional and
stateful programming'. Although no one knows how to do that,
recent research is beginning to hint at a solution 
(The idea is that if you take the categorical basis of FP
and apply duality, you get stateful programming. For example,
the dual of a list is a stream)

        There are two common 'mainstream' solutions,
ISWIM-like languages (like SML, which use reference handles),
and Algol-like languages (which use lvalues). Both solutions
are seriously flawed. (Ocaml is ISWIM, C++ is Algol-like).

        The difference between, say, Ocaml and C++ is emphasis:
C++ is primarily procedural, but it does have expressions
which can be functional, and it does have a sort of functional
template system, whereas Ocaml is primarily functional,
but it does have mutable data structures and sequencing
constructions (and objects). 

        The biggest problem in both ordinary C++ and C++
templates is immediately evident by comparison with 
SML like languages, and that is the lack of a proper 
discriminated union: you can sort of fudge it with
function templates by using overloading with classes as tags,
to switch between overloads, or class templates by using 
classes as tags, to switch between (partial) specialisations.
But it is _extremely_ ugly. Similarly, C++ lacks first class
functions: again, you can hack it using function objects,
but it's very ugly.

        My solution is Felix: it generates the ugly C++ code
for you: instead of writing a function object, you just
write a nested function:

        fun f(x:int, y:int): int {
                fun g():int {
                        return x + y;
                }
                return g();
        }
        f(1,2);

which generates something like:

        struct f {
                int x;
                int y;
                int apply(int _x, int _y) { 
                        x = _x; 
                        y = _y; 
                        return new g(this)
                }
        }
        struct g {
                f *pf;
                g(f *_pf) : pf(_pf) {}
                int apply() { return pf->x + pf->y; }
        }
        (new f())->apply(1,2);

Similarly, you can declare

        union list = Empty | Cons of int * list;
        match u { case Empty: .. case Cons (h,t): .. }

and you get

        struct _union {
                int tag; // = 1 for Cons
                void *data; // cast to tuple<int,list> for Cons
        };
        if(u.tag == 0) { .. // empty case
        if(u.tag == 1) { 
                h = ((tuple<int,list> *)u.data)->first;
                t = ((tuple<int,list> *)u.data->second;
                ...
        }

You can of course code all this by hand, but it seems better
to me to use a code generator. The biggest problem appears to
be debugging, but it isn't clear that the problem is any worse
than debugging templates, whereas the stronger type system
and high level semantics should reduce errors considerably.

Note that Felix doesn't replace C++, any more 
than C++ replaces C. Instead, it leverages it. It's designed
to be embedded in a C++ architecture (application framework),
and to use C++ types as primitives, that is, its
a kind of middleware product with a strong emphasis
on seamless integration. It does, however, tend to replace
a lot of template meta-programming.

-- 
John (Max) Skaller, mailto:skaller_at_[hidden] 
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
New generation programming language Felix  http://felix.sourceforge.net
Literate Programming tool Interscript     
http://Interscript.sourceforge.net