Path to Y – Y

Last time we got two important steps closer to implementing the Y Combinator in C++:

  1. How to enforce "composition" on every call – by overloading the call operator, delegating its functionality to our call member function, but only after calling compose

  2. How to pull responsibility for making our FactorialWrapper class recursive out of the class itself – by defining a generic class (ambitiously) named Y that takes a classname as a templatic argument, instantiates a member of that class, and exposes an overloaded call operator of its own that calls compose on the member – passing it to itself – before then calling call on it.

For review, here’s the code:

#include <iostream>

using namespace std;

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

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

FactorialWrapper* FactorialWrapper::compose(FactorialWrapper* p )
{
  cout << "COMPOSING..." << endl;
  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 FactorialWrapper::operator()(int n){
  return this->compose(this)->call(n);
}

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

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

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

Compile it, run it, and you’ll get:

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

Note, actually, the duplicated COMPOSING.... That’s because we called it in Y::operator() too. So, all Y is good for so far is just getting the ball rolling. We’re still cheating in the relevant ways.

Before going further, it’s worth taking a second look at the lazy eval version of Y – i.e. Haskell Curry’s Original Y – to remind ourselves what we’re aiming for.

Y = λf.(λx.f(x x))(λx.f(x x))

It’s in lambda calculus notation, but that’s pretty easy for any Coffeescripter. So, let’s watch what happens:

First – Y takes a function, which we’ll call recursive for fun:

Y(recursive) 
λf.(λx.f(x x))(λx.f(x x))(recursive)
(λx.recursive(x x))(λx.recursive(x x))
recursive((λx.recursive(x x))(λx.recursive(x x)))

OK, so stop it right there and take stock.

We pass our model function recursive to Y. Y substitutes that function in for its first argument (f). That sets up two anonymous functions that each take one argument and apply their argument to itself before passing it to recursive. Then, it passes the one to the other. Which is, you know, how the process works.

And then, what are you left with? Well, the process will repeat itself. We have recursive called with two functions, one applied to the other, each of which takes a single argument and called recursive on the result of applying its argument to itself. Voila! That’s how you get recursion without doing it explicitly, kids!

It’s easy to see that this will repeat forever without some kind of terminal condition in recursive somewhere.

Cool.

So how much of this have we already done?

Well, we did the first part, where Y is a thing that takes a function that it wants to make recurisve. Of course, we’re working in a language that’s not particularly friendly to this, so we had to model these parts. We modeled "function" with a class that wraps a function call, because C++ won’t otherwise let us pass function arguments a function to be substituted into the body of its definition. And we modelled composition by passing this class to itself (that is, the class has a member variable that’s a pointer to an instance of the class, and we can pass a pointer to an instance variable of the class to it – including its own this pointer (i.e. we can pass it to itself).

So, that’s actually pretty far.

We also figured out a way to make sure that composition only happens right before you call the function – by overloading the function call operator on the class (()) to make sure that it first calls compose – the member function we designated for handling "composition," and then calls call – the member function we designated for actually falling the wrapped function.

So, that’s actually really pretty far.

The missing pieces are: (1) composition needs to be pulled out of the function wrapper class, because the whole point of Y is that it abstracts recursion – i.e. we need to pull the composition "up" into our Y class and (2) composition has to be necessary for the recursive call to succeed, otherwise all our Y class is doing is instantiating recursion in another class (the function wrapper class itself – arguably the worst possible place, since the whole point here is to make something recursive without doing it explicitly).

Let’s do (1) first – because it’s easy, but also because it will end up pointing the way to (2).

All we need to do for (1) is make sure that FactorialWrapper isn’t doing its own composing on call, right? So, let’s try that. That’s a simple matter of changing the overloaded operator to:

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

OK, so compile it and run it and…

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

Which tells us that we successfully lifted composition up to the Y instantiator class, but we still have the problem that recursive calls aren’t being generated eatch time.

Well, OK, we can model that by creating a new instance of the FactorialWrapper class for each call. So, instead of creating a central one to use on every call, just recreate it. That is, after all, what Y is supposed to do: generate the recursive call on each iteration. So, modify the code fo Y to reflect this:

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

Now instead of creating a single instance in the constructor, we create a new instance of FactorialWrapper each time the Y::() method is called.

And … you’ve probably already spotted the mistake, but it’s an instructive error:

COMPOSING...
WRAPPER: 5
WRAPPER: 4
WRAPPER: 3
Segmentation fault: 11

In addition to (obviously) not solving our problem of enforcing composition each time, we eventually end up with a segfault. This is caused by trying to dereference an uninitialized pointer. Think about it – on the first pass, we call inner. This prints out the 5, and returns 5 multiplied by whatever the result of calling the continuation with 5 - 1 = 4 is. Well, we composed inner with otherinner, so there actually is a continuation pointer. So, we get another call, which prints out the 4 … and then I admit I’m a bit stumped why the next one happens. Apparently since we have an instantiated object, even though *f itself doesn’t point to anything, the compiler knows what to call, and so it does. But in any case, the call is just to the class method – it doesn’t get a this pointer … because no one ever composed otherinner with anything, and so we’re eventually pointing to unallocated memory, and there’s a segfault. Which anyone could have seen coming – I just mention it here because it gives us a way to stay honest about whether we’re really generating the recursive call each time through. If we always compose with a new instantiation of FactorialWrapper, we know we’ll (eventually) get a segfault if we’re failing to regenerate the recursive call each time. Great!

Now the tricky part. If you remember from above, what Y does is generate the recursive call each time. So, we actually need the f in the recursive line to be an instance of Y – since the whole point is to pull recursion out of the function and abstract it to Y. Put differently, Y is responsible for recursion, not FactorialWrapper. Which actually fits in with how the lambda calculus version works too. Look at it again:

Y(recursive) 
λf.(λx.f(x x))(λx.f(x x))(recursive)
(λx.recursive(x x))(λx.recursive(x x))
recursive((λx.recursive(x x))(λx.recursive(x x)))

We stopped here because in a lazy language what actually gets passed to recursive is:

((λx.recursive(x x))(λx.recursive(x x)))

Yes, that thing as such. In a strict language, the argument to a function will get evaluated before being passed – which is why in Coffeescript we had to define it like this:

y = (f) ->
  ((g) -> f (x) -> g(g)(x))((g) -> f (x) -> g(g)(x))

Rather than this:

y = (f) ->
  ((x) -> f(x x))((x) -> f(x x))

Coffeescript can’t handle the second, more straightforward, definition because the application of (x x) will just keep expanding forever. So, we suspend evaluation by wrapping that in a function to pass in. That way the composition bit doesn’t get evaluated until the function gets called. But in either case, the application part – the (x x) part – shouldn’t happen until we recurr. So, it needs to wait to happen until here in the C++ version:

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

Dereferencing f and then calling it is what should cause the composition to happen. So, that – f – whatever it is – needs to be a thing that:

  1. Creates a new instance of FactorialWrapper,
  2. Composes it with whatever is responsible for the recursive call (i.e. for doing this again next time),
  3. calls this new instance (it’s crucial that it be the newly-created instance, or else we’re cheating the way we were before!) with the integer argument passed to it.

SOLUTION: It – f – really needs to be an instance of Y, NOT FactorialWrapper!

IMPLICATION: The thing we’re composing the new instance of FactorialWrapper with should be an instance of Y.

PROBLEM: We don’t really want to make the f member of FactorialWrapper be of type Y because that makes the dependence explicit – something we’re trying to avoid. The whole point is to be able to pass any candidate FunctionWrapper class to Y as a template argument and have the resulting class function like a recursive function. The Y part does the recursion. Otherwise, we should be able to pass another function in – i.e. not one "composed" by Y – to the compose argument and get a quite different result.

QUESTION: This would be easy if there were a way to treat Y and FactorialWrapper as the same type, even though they’re not. Is there?

ANSWER: YES! Inheritance! We can make them both inherit from the same base class, and that base class can provide a virtual overload on operator(), so that both base classes have the same callable interface, but the callable interface can still behave differently depending on which underlying type the class is!

I’m just going to paste the final code in now, and you can see how it works from that:

#include <iostream>

using namespace std;

class CallableFunction {
  public:
    virtual int operator()(int n) = 0;
};

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

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

FactorialWrapper* FactorialWrapper::compose(CallableFunction* p )
{
  cout << "COMPOSING..." << endl;
  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 FactorialWrapper::operator()(int n){
  return this->call(n);
}

int main()
{
  Y<FactorialWrapper>* y = new Y<FactorialWrapper>();
  cout << (*y)(5) << endl;
}

Ok, now let’s go over the highlights.

First, both Y and FactorialWrapper inherit from the CallableFunction base class now. This class really just exists so that we can treat them as the same thing from time to time, even though they’re not. But in any case – here’s the inheritance in the flesh:

class FactorialWrapper : public CallableFunction {

And a similar line for Y of course. Now, any instance of FactorialWrapper is an instance of CallableFunction as well. This is also true of any instance of Y.

The CallableFunction class has a super simple interface: it only requires that its child classes define an overloaded operator (that takes an int and returns an int – yes, ideally we should make this more generic, but to keep the illustration simple for now our CallableFunction only applies to functions that are of type intint). Notice that this interface is declared virtual. This is critical – if we actually declared a full member function here (much less defined it!) then the instances of CallableFunction we refernce throughout the code would try to call this overloaded operator – but we don’t want that. We want instances of Y to call the Y class member, and instances of FactorialWrapper to call the FactorialWrapper class member – even if they’re being passed off as instances of CallableFunction for convenience. Look up the virtual keyword for background if you don’t quite get it, but the short version is that it enforces "late binding" – i.e. the function to call isn’t looked up till runtime, at which point we can resolve whether something that looks like a CallableFunction is actually a Y or a FactorialWrapper.

But in any case, note that the interface to FactorialWrapper has changed – now instead of expecting to be passed a pointer to FactorialWrapper in its compose function, it will accept any kind of CallableFunction – be that Y or FactorialWrapper. This lets us "sneak in" an instance of Y, so it will be an instance of Y that gets called in the recursive call.

The final thing to point out is that the overloaded operator on Y creates a new instance of FactorialWrapper each time it’s called, and it composes this with its own this pointer. That is, Y passes itself in to each new instance. Y is, after all, responsible for doing the recursion.

And now it all works. Compile, run, and it’ll output what it’s supposed to:

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

HOORAY! WE GOT THERE! Y COMBINATOR IN C++!!!

Now, there’s plenty of room for nitpicking. At any stage of this, it’s possible to quibble with my representations. Is it really cool to wrap a function in a class and pass that off as a composable function? Meh, I don’t know, and I don’t really care. The point of this isn’t to argue that the Y Combinator is a natural or easy fit for C++ – it’s clearly not. The point is just to understand the Y Combinator a little better by implementing it in a language that’s hostile to its direct implementation. And hey, if we get a little better at C++ in the process, what’s the harm, right?

Personally, I think the biggest, most legitimate nit to pick with this is that I should probably come up with a way to do this such that it’s not FactorialWrapper that gets a new instance created at each recursive call, but rather Y. It’s true that Y is the class responsible for handling recursion (and so arguably it should act as a kind of crucible for the operation of the whole thing – the engine if you will). But if we replay that expansion of Curry’s Original yet again another time already:

Y(recursive) 
λf.(λx.f(x x))(λx.f(x x))(recursive)
(λx.recursive(x x))(λx.recursive(x x))
recursive((λx.recursive(x x))(λx.recursive(x x)))

You’ll notice that f – which is our FactorialWrapper analogue – gets pased in once – as a symbol – and that’s it. The name just gets passed down with each new rewrite. It’s the recursive component that really gets created anew on each call. So, ideally it should probably be Y that gets reinstantiated each time ’round the block and not FactorialWrapper.

But let’s split that hair another time. The illustration is still successful – you really can (mostly) implement Y in C++, but it’s very, very cumbersome.

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>