Re: [boost] A few questions about Phoenix, Boost.Bind, and FC++

From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2008-06-06 13:29:05

On Fri, Jun 6, 2008 at 6:16 PM, Daniel Walker <daniel.j.walker_at_[hidden]> wrote:
> Hello,
>

[...]

>
> However, one thing I noticed right away while reading about Phoenix
> was that it borrows the term rank-2 polymorphic function from FC++.
> I'm just learning this terminology, so I'm trying to gain confidence
> that I understand it. From briefly skimming (McNamara, 2000) in JFP,
> I'm under the impression that a rank-2 polymorphic function can only
> have two parametric types, i.e. two template parameters. So, for
> example, std::make_pair is rank-2 polymorphic, and FC++ has functions
> that will produce pairs when called with two different types. A rank-n
> polymorphic function can have arbitrarily many different template
> parameters; an example would be std::make_tuple. Doesn't Phoenix
> actually support rank-n polymorphism? For example, isn't the following
> a rank-3 polymorphic function in Phoenix and couldn't you write
> similar function objects for higher ranks?
>
> struct tupler_ {
>    template<class> struct result;
>
>    template<class F, class T0, class T1, class T2>
>    struct result<F(T0,T1,T2)> {
>        typedef tuple<T0,T1,T2> type;
>    };
>    template<class T0, class T1, class T2>
>    tuple<T0,T1,T2> operator()(T0 t0, T1 t1, T2 t2) const
>    {
>        return make_tuple(t0,t1,t2);
>    }
> };
> phoenix::function<tupler_> tupler;
>

For what I understand, rank-n polymorphism has nothing to do with the
number of type parameters but It has to do on the level of "higher
order nesting" that still allows polymorphic functions to be used
polymorphically.  If the previous sentence didn't make sense to you (I
would be surprised if it did :) ), I'll try with an example (I'll use
C++0x notations)

  struct times_two {
  template<class A>
    auto operator()(A a) -> decltype(a+a) { return a + a; }
  };

This is  polymorphic function which will apply operator+ to a value of
any type (for which + is defined, but this is another story).

  template<class F>
  int apply_int(F f) {
     return f(int(2));
 }

  int i = apply_int(times_two());

This is an higher order function which will exploit rank-1
polymorphism. i.e. it takes a polymorphic function but it will treat
it monomorphically inside it (as only a value of type int is passed to
it. Thus you can change its definition to:

  int apply_int(std::function<int(int)> f) { return f(int(2)) ; }

This is still a rank_1 polymorphic function as you can pass any
function to it. Passing a polymorphic function to it will monomorphize
it:

  int i = apply_int(times_two());

AFAIK plain ML only allows monomorphic functions. The reason is that
plain Hindely Milner type inference can only do type dedu
I think that this is still rank-1 polymorphism:

  template<typename V>
  V apply_any(std::function<V(V)> f, V x) { return f(x); }

Now the parameter to f is also type parametric, but inside apply_any,
f is still treated monomorphically.
Rank 2 polymorphism allows a function passed as a parameter to be
treated polymorphically:

  template<typename F>
  auto apply_poly(F f) -> decltype(std::make_pair(f(2),
std::string("hello world"))) {
      return std::make_pair(f(2), f(std::string("hello world")));
  }

  auto x = apply_poly(times_two());

Note that you cannot write the above function using std::function, as
it will cause its bound function to be monomorphized (modulo parameter
conversion).  A multisignature_function would help though.

Rank-3 polymorphism allows passing polymorphic functions as parameters
and still threat them as higher order rank-2 polymorphic functions
(i.e. they can in turn take a polymorphic function as parameter). You
can guess what Rank-4 and more means.

Modern functional languages (Haskel, ML dialects) allow rank-2
polymorphism (but, I think, not more) at the cost of requiring some
limited amount of type annotations.

C++ allows Rank-n polymorphism (i.e. there is no limit on the amount
of nesting). The price you pay is no separate compilation (modulo
export? but it will probably require some amount of link time
compilation),  type checking delayed at instantiation time, and of
course the amount of type inference that can be done by templates is
limited. And yes, both boost.MPL, FC++ and Phoenix actually support
rank-n polymorphism.

Now, my understanding of all this stuff is spotty at best, so there is
some FP expert is around here, it will very likely correct my
explanation

HTH,

-- 
gpd.