Path to Y – Functors

In yesterday’s post we showed that the first part of Y – passing a function to another function – is not only possible but fairly easy in C++. What about returning one?

As you might expect, that’s just as easy, though the signature can get a little awkward if you don’t use typedefs.

Let’s start by cheating completely and making a function called makeFactorial that just returns a (previously-defined) factorial function:

int factorial (int i)  {
  if( i == 0 ){
    return 1;
  } else {
    return i * factorial(i - 1);
  }
}

int (*makeFactorial(void))(int)
{
  return &factorial;
}

cout << (*makeFactorial())(5) << endl;

The void isn’t stricly necessary, but you can see how awkward this is. This defines a function called makeFactorial that takes no arguments, but returns a pointer to a function that takes an int and returns an int. To call the result, you have to dereference the result of the call before applying it to the argument. And notice that makeFactorial returns a reference to the factorial function. In fact, this isn’t necessary – we could have also written it like this:

int (*makeFactorial(void))(int)
{
  return factorial;
}

The reference operator is just there to make it clearer what’s going on – but to reiterate the point from last time, all function names are references to places in the stack anyway, so pointers to functions really aren’t any different, under the hood, than function names.

OK, so returning a function from a C++ function is "easy" – in shock quotes because it’s only easy modulo some truly awkward syntax – I mean, the kind of awkward that put the awk and ward in awkward. Fortunately, we can typedef that away:

typedef int (*function_ptr_i_i)(int);

int factorial (int i)  {
  if( i == 0 ){
    return 1;
  } else {
    return i * factorial(i - 1);
  }
}

function_ptr_i_i makeFactorial()
{
  return &factorial;
}

cout << (*makeFactorial())(5) << endl;

This says the same thing, but much more clearly.

Unfortunately, none of this really helps, because the reason we want to return a function from a function isn’t just to do it – we’d like our function to actually build the return function for us. Because the goal is to abstract out the recursive call inside factorial. Here’s the Coffeescript again:

shallowfactorial = (f) ->
  (n) ->
    if n is 0
      1
    else
      n * f(n-1)

The idea is to pass in a function that represents the recursive call in a normal factorial function, returning a function that is, therefore, a proper implementation of factorial. In C++.

OUCH.

Well, C++ can’t really do that. It can accept function pointers as arguments, and it can return function pointers as results, but C++ functions can’t directly compose functions for you. That’s because they don’t have any state of their own – they don’t close over their scope.

Fortunately, the language does give us a construct that does – or can at least fake it: classes.

You can define a class that takes a function pointer as an argument, and while it doesn’t straightfowardly return a function that has access to that argument necessarily, it can at least give you access to one. Here’s what I mean:

#include <iostream>

typedef int (*function_ptr_i_i)(int);

using namespace std;

int factorial (int i)  {
  if( i == 0 ){
    return 1;
  } else {
    return i * factorial(i - 1);
  }
}

class FactorialWrapper {
  private:
    function_ptr_i_i f;
  public:
    FactorialWrapper( function_ptr_i_i );
    int fwfactorial(int);
};

FactorialWrapper::FactorialWrapper(function_ptr_i_i p )
{
  f = p;
}

int FactorialWrapper::fwfactorial(int i)
{
  if( i == 0 ){
    return 1;
  } else {
    return i * f(i - 1);
  }
}


int main()
{
  FactorialWrapper * fw;
  fw = new FactorialWrapper( factorial );

  cout << fw->fwfactorial(5) << endl;
}

This you can copy, compile and run. We define a function factorial, same as before. Then there’s a class FactorialWrapper that exists, basically, just to take that function as an argument to its constructor and let us call a member function – also called factorial – that depends on it. Notice that FunctionWrapper‘s factorial function doesn’t call itself on its recursive call, it calls the private member variable f, which just so happens to be a pointer to a function that takes an int and returns an int. And we assign the (independent, outer) factorial to this in the constructor. So, at the time we call f, it points to an implementation of factorial. It’s the more or less same thing as what we did in Coffeescript, just done through a lot of awkward boilerplate, and without (technically) returning a function from a function. But the idea is the same – FuncionWrapper takes a reference to a function and makes it available in the body of a function that we then use to compute the result.

Of course, it’s a little awkward to have to call a named member function. What we’d really like to do is just call the thing directly, right?

Well, we can – with operator overloading. Instead of defining a method factorial, let’s overload the operator () instead. Here are the relevant sections of the previous example code updated to overload the operator rather than delegate to a member function:

class FactorialWrapper {
  private:
    function_ptr_i_i f;
  public:
    FactorialWrapper( function_ptr_i_i );
    int operator()(int);
};

int FactorialWrapper::operator()(int i)
{
  if( i == 0 ){
    return 1;
  } else {
    return i * f(i - 1);
  }
}

int main()
{

  FactorialWrapper * fw;
  fw = new FactorialWrapper( factorial );

  cout << (*fw)(5) << endl;

}

(Notice that you have to dereference fw before "calling" it.)

So, we’re definitely getting closer to an imperative (or at least object oriented) implementation of Y. This is really almost like currying.

By the way, what we’ve done here is called a functor – which is a function that maintains state. We’re fudging it a bit here, because we’re maintaining state through a wrapper object that C++ operator overloading lets us treat like a function, but let’s not split hairs. This is as close as C++ gets to a real functor, and it’s close enough.

But we’re still a ways from where we want to go – because to make Y work, we need to be able to pass the functor to itself to get the recursive component. To do that, we’d need some way of passing the result as an argument back to the constructor for the next iteration, and that we really can’t do. Yet.

Path to Y

  1. Pointer to Function Pointers
  2. Functors
  3. Shallow Composition
  4. Overloading
  5. Y

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>