Path to Y – Overloading

Last time, we’d found a way to (sort of) ape function composition in C++ by using Functors … modeled as classes that bundle the function to-be-made-recursive with a private member pointer to itself. The class exposess two public methods – compose and call – which are meant to correspond to the two stages that a function passed to the Y combinator goes through in "becoming" recursive. As a reminder, here’s a Y-able factorial function in Coffeescript:

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

It’s a curried function that first takes the continuation call (f), then takes the actual argument (n). In our model class, the compose member function accepts another member of the class type – to be used as the continuation call – and the call member function accepts an integer parameter, i.e. the actual argument to factorial.

OK, so far so good.

But we realized that it’s actually cheating, because the "continuation" member already refers to itself on the recursive call. That is, when you call call, it’s really supposed to reach the recursive call and then have to regenerate recursion. Otherwise, we’re really doing something like this:

y = (fnGenerator) ->
  fakeFn = (arg) -> realFn(arg)
  realFn = fnGenerator(fakeFn)
  realFn

(y notyetrecursivefactorial)(5)

If you expand that out, you’ll notice that the function returned from y is already fully recursive – it doesn’t have to regenerate it’s recursive call on each iteration.

y = (notyetrecursivefactorial) ->
  fakeFn = (arg) -> realFn(arg)
  realFn = notyetrecursivefactorial(fakeFn)
  realFn

y = 
  fakeFn = (arg) -> realFn(arg)
  realFn = 
    (fakeFn) ->
      (n) ->
        if n is 0
          1
        else
          n * fakeFn(n-1)

y = 
  realFn = 
    (n) ->
      if n is 0
        1
      else
        n * ((arg) -> realFn(arg))(n-1)

So, it’s most of the way there, but it isn’t really an application of Y. Our C++ implementation is like that too, because once you pass the Functor to itself via compose, its internal reference just points to itself. Done. It’s recursive already, without needing to regenerate recursion on each iteration through factorial. Here’s the code for reference:

#include <iostream>

using namespace std;

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->call(i - 1);
  }
}

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

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

Once you’ve composed, that f inside of call is always defined and callable. So, this does what Y is supposed to do, but maybe not really in the spirit of the way it’s supposed to do it.

To try to solve this problem, let’s first ignore it and just go through the motions of requiring f to compose on every recursive call. We can do this through a syntactic trick in C++ that allows us to redefine certain language operators. This is called operator overloading. We’ll use it to redefine the () operator so that it enforces compose before call. Which is to say, we’ll be overloading it twice, and the compiler will be smart enough to call the compose version when we pass it a composeable argument and call when the argument is callable.

This is dead simple for call – we just mimic the call signature for call:

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

And then define it:

int FactorialWrapper::operator()(int n){
  return this->call(n);
}

Now, if this actualy works, we can replace the explicit f->call(n-1) in the body of our call function:

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

(Note that f is still a pointer, so you have to dereference it.)

And it works!

Now, the purpose in doing this was to make sure that we composed every time we called, but that’s now easy – just do it inside the overloaded operator – or (perhaps more properly) inside call.

int FactorialWrapper::operator()(int n){
  return (this->compose(f))->call(n);
}

And, since compose is invisible, you can, if you like, log out that it’s been called just to convince yourself it’s happening:

FactorialWrapper* FactorialWrapper::compose(FactorialWrapper* p )
{
  cout << "COMPOSING..." << endl;
  f = p;
  return this;
}

Compile and run and you should get:

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

Neat!

But we’re still cheating in at least two ways. First, because the composition isn’t really necessary to get the recursive call – which is to say that we haven’t actually pulled recursion out of the function definition, not really. I mean, you do have to do it once, but not after that. Doing it on every step here is just pro forma. The second way it’s cheating is of course that we’re leaving the responsibility of making the function recursive up to the function itself – that is, up to its containing class. Again, to stick with the spirit of it, there would have to be some other thing called Y that took our containing class as an argument and returned something recursive.

The second part, at least, is easy, so let’s get it out of the way. Let’s define a class called Y that takes responsibility for (1) initializiing our wrapper class and (2) composing it initially.

To pretend that we’re being general about this (even though we’re really not), let’s make Y a generic class – one that expects a callable class that has a compose method and overloads its () operator. This technically means our Y takes any wrapped "function" (modeled here as a class) and "makes it recursive."

template<class C>
class Y {
  private:
    C* inner;
  public: 
    Y(){inner = new C(); inner = inner->compose(inner);};
    int operator()(int n){ return (*inner)(n); }
};

And then you instantiate it in the obvious way:

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

  Y<FactorialWrapper>* y = new Y<FactorialWrapper>();

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

So, again, you have to be a little liberal with your understanding of how Y is "taking" FactorialWrapper as an "argument" and "returning" a recursive version of it. Really, it’s the class template that does the "taking," so maybe we’re abusing the term "argument" a little. And we’re certainly abusing the term "return," since all Y does here is tell FactorialWrapper to make itself recursive (and then provides a convenient interface to calling it – which is kind of fun but also beside the point).

But I think these "abuses" of term are OK. C++ doesn’t give you composable functions, so we’re modelling them using what it does give you – and since we’re modelling them with classes, modelling Y as a class that composes with another class seems fair.

Of course, our Y still isn’t Y. To make it Y, we’ll need it to take responsibility for the recursion of factorial. And to do that, we’ll have to figure out how to stop cheating on composition – that is, how to make it required, and not merely pro forma, on each iteration. And if that turns out not to be possible in C++, at the very least we’ll ahve to pull the compose call up into Y. Stay tuned.

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>