Path to Y – Shallow Composition

Last time we saw how to pass "build" functions (i.e. return a function from a function that depends on the arguments passed to the outer function) in C++, even though C++ functions don’t really "do that." The trick is to wrap the return function in a class that can set private member variables which are referenced in the body of the function. A lot people like to call this a "functor," because it’s a function that maintains state. Of course, we’re just faking functors here by using a class, but since we can’t have proper composable functions in this language, we’ll take what we can get.

The outstanding problem now is how we compose these. To illustrate why the code from yesterday isn’t all the way there yet, let’s log out which functions are being called:

#include <iostream>

typedef int (*function_ptr_i_i)(int);

using namespace std;

int factorial (int i)  {
  cout << "FACTORIAL: " << i << endl;
  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 operator()(int);
};

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

int FactorialWrapper::operator()(int i)
{
  cout << "WRAPPER: " << i << endl;
  if( i == 0 ){
    return 1;
  } else {
    return i * f(i - 1);
  }
}

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

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

Compile it and run it and you get this:

WRAPPER: 5
FACTORIAL: 4
FACTORIAL: 3
FACTORIAL: 2
FACTORIAL: 1
FACTORIAL: 0
120

So, all this really does is calls the FactorialWrapper function once, and then delegates all further operation to factorial. To get to Y, we really need it to be FactorialWrapper that’s calling itself (but without using an explicit reference to itself). And of course we want it to do this by taking itself as an argument.

To illustrate, let’s back off a bit from using the constructor and operator() and just label each step directly. For reference, here’s the Coffeescript function we’re aiming at again:

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

shallowfactorial takes a function (that it will recur on) and returns a function (that takes integer input). If you pass shallowfactorial to itself:

(shallowfactorial shallowfactorial)(5)

…you get a complete factorial implementation. We’d like to do that in C++.

Now, notice that there are two steps here, which I’ll call compose and call. First you compose shallowfactorial with its continuation (itself in this case), then you call the result of that with an argument. So, let’s do that explicitly in C++:

#include <iostream>

typedef int (*function_ptr_i_i)(int);

using namespace std;

int factorial (int i)  {
  cout << "FACTORIAL: " << i << endl;
  if( i == 0 ){
    return 1;
  } else {
    return i * factorial(i - 1);
  }
}

class FactorialWrapper {
  private:
    function_ptr_i_i f;
  public:
    FactorialWrapper(){};
    FactorialWrapper* compose(  function_ptr_i_i );
    int call(int);
};

FactorialWrapper* FactorialWrapper::compose(function_ptr_i_i p )
{
  f = p;
  return this;
}

int FactorialWrapper::call(int i)
{
  cout << "WRAPPER: " << i << endl;
  if( i == 0 ){
    return 1;
  } else {
    return i * f(i - 1);
  }
}

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

  cout << fw->compose( factorial )->call(5) << endl;
}

Note the changes. We’re no longer passing the function pointer in via the constructor, but rather via a method compose. This sets the functionpointer we’re going to use for the continuation call and returns a reference to the wrapper object so that we can chain calls. Then we pass in the integer argument as usual, but we’ve changed the name of this to a more explicit call. Now it looks a lot closer to how the Coffeescript worked: take an argument (a function(pointer)), then another argument (an integer) and return a result (an integer).

If you run it, you get the same output before, so it’s equivalent. But we’re still one step away. The thing we’re passing to compose is not the right type. We’re passing in a function, but in the Coffeescript original f is really supposed to be a thing of the same type as shallowfactorial. After all, we’re aiming to pass shallowfactorial to itself. So, we really need to change compose to take a FunctionWrapper instance. Let’s do that:

#include <iostream>

typedef int (*function_ptr_i_i)(int);

using namespace std;

int factorial (int i)  {
  cout << "FACTORIAL: " << i << endl;
  if( i == 0 ){
    return 1;
  } else {
    return i * factorial(i - 1);
  }
}

class FactorialWrapper {
  private:
    FactorialWrapper* f;
  public:
    FactorialWrapper(){};
    FactorialWrapper* compose(  FactorialWrapper* );
    int call(int);
};

FactorialWrapper* FactorialWrapper::compose(FactorialWrapper* p )
{
  f = p;
  return this;
}

int FactorialWrapper::call(int i)
{
  cout << "WRAPPER: " << i << endl;
  if( i == 0 ){
    return 1;
  } else {
    return i * f(i - 1);
  }
}

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

  cout << fw->compose( fw )->call(5) << endl;
}

Ok, so we’ve changed the type of the inner argument to a pointer to FactorialWrapper, and we’re now passing fw to itself in the compose component. Compile, run and … it fails. But not, thankfully, because there’s anything incorrect about passing fw a reference to itself. It’s because the type of the continuation variable inside the call method is now wrong. In:

return i * f(i - 1);

f is now a pointer to FactorialWrapper. So, if we’re doing this strictly by the book, it should really be this:

return i * f->compose(f)->call(i - 1);

Now if you run it, you get the right result! Not only do we get 120 as the answer, but we log out:

WRAPPER: 5
WRAPPER: 4
WRAPPER: 3
WRAPPER: 2
WRAPPER: 1
WRAPPER: 0
120

proviing that it called the "right" function each time! We took a non-recursive function, passed it to itself, and managed to make it recursive!

Or did we?

Actually, we’re still cheating, and a little bit of thought will make it obvious how. Try taking out the composition bit of that revision and see what happens:

return i * f->call(i - 1);

Same result.

Oops.

So, the composition part of it isn’t actually necessary. And we knew it wouldn’t be – the f pointer just points back to itself, really, and it already has its f argument satisfied. So, this is equivalent to some Coffeescript code we saw in one of the background posts:

y = (generator) ->
  fakeFn = (x) -> realFn(x)
  realFn = generator(fakeFn)
  realFn

This looks like a plausible implementation of Y, and it does what Y is supposed to do – take a non-recursive function and make it recursive – but it does it by directly setting a reference to the name of the produced recursive function in its body. That’s not exactly what we’re aiming for. Really, we need one more level of indirection. To fully "pull recursion out," we need the (recursive) f->call() call to compute-and-return the function call before taking the integer argument. So, this is most of the way there, but not 100%. To really get Y, we need to pull out the recursive component and make it "its own thing." And that’s the part we’re nto really going to be able to do in C++.

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>