Re: [boost] About template metaprogramming and functional programming

From: Vesa Karvonen (vesa.karvonen_at_[hidden])
Date: 2001-07-21 19:52:13

From: "David Abrahams" <david.abrahams_at_[hidden]>
> From: "Vesa Karvonen" <vesa.karvonen_at_[hidden]>
>
> > I'm thinking of polishing and submitting (just after I get the first
> version
> > of the PREPROCESSOR library ready for inclusion to Boost (and before I
> submit
> > libraries using the functionality)) a C++ template implementation of a
                                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^

> > considerable subset of functionality from the built-in features and
> (standard)
> > libraries of some functional programming languages such as Haskell and
> CAML. I
> > will also intend to develop techniques for converting functional
> programming
> > designs into C++ template metacode.
>
> Vesa,
>
> That would be fabulous. It seems to me that the only serious pitfall would
> be if your library didn't interoperate well with other libraries in the same
> general domain. I'm thinking in particular of Lambda and the MPL stuff that
> Aleksey has been working on.

[The underlined portion of my message above was a bit ambiguous. I'm referring
only to template metaprogramming.]

It should be possible to interface two distinct metaprogramming libraries
using adapters - at least to some extent. A significant technical obstacle
between interfacing two metaprogramming libraries might be the use of partial
specialization for pattern matching (e.g. Loki uses it for typelists), because
it constraints template parameters to use a specific class template rather
than just requiring a specific interface. Fortunately MPL does not use much
partial specialization.

It might be worthwhile to eventually restructure the MPL library into possibly
multiple libraries (otherwise it would probably get too large and somewhat
incoherent) and then integrate the primitives inspired by functional
programming to the libraries.

Functional programming literature is packed full of useful
generalizations/variations and theory (there are lots of proofs of properties
of higher-order functions, for example) of primitives you can find in template
metaprogramming literature and libraries.

For example, the foldr[/foldl] higher-order functions in Haskell are different
from the for_each metafunction in MPL. Basically, for_each takes two
parameters:
- a sequence and
- a unary metafunction *with state*,
where foldr[/foldl] take three parameters:
- a sequence,
- a binary function, and
- an initial value (or more accurately the result for an empty sequence).
Foldr[/foldl] then "folds" the given binary function into the sequence,
bracketing to the right[/left]. [This may be difficult to understand unless
you are basically familiar with foldr. Just use some search engine and look it
up.]

IMO, foldr[/foldl] seems quite attractive compared to for_each. The MPL
example that computes the sum of a value list using for_each, could be written
basically like this using foldr:

  struct add
  { template
    < class x
    , class y
    >
    struct code
    { enum
      { value = x::value + y::value
      };
      typedef value_identity<value>
        type;
    };
  };

  foldr<add,value_identity<0>,sequence>::type

This seems much more intuitive to me than the MPL example code using for_each.
Apparently a couple of decades of research has provided us with some very
powerful primitives.