Path to Y – Function Pointers

Most of the stuff you read on the internet about the Y combinator works in functional languages. This only makes sense: the Y combinator comes from the Lambda Calculus, and functional languages allow you to implement Lambda Calculus concepts more or less directly in that functions are first-class values in those languages. What that means is that you can (a) pass functions to other functions as arguments and (b) return functions from functions as values.

And indeed, I depended on both of those things in my own Coffeescript implementation of Y:

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

f is a function that needs to be made recursive, and though it’s not immediately obvious without expansion, the body of the function indeed returns a function that can be applied to an argument.

But you don’t really understand a thing if you’re just repeating it. So, can we implement the Y Combinator in an imperative language? And indeed, why not in functional programmers’ least favorite language of all time – C++?

In fact, it’s been done in C++, but not necessarily in the spirit of implementing Y in an imperative language. Yongwei Wu has a good example with explanation over at his blog – but it makes use of C++11 lambda constructs, i.e. uses new language support for functional programming constructs. That’s not to say it isn’t clever or useful – people who program primarily in C++ don’t generally think in these terms, after all – but it’s sort of outside the question being asked here – which isn’t really "can you do this in C++?" so much as "can you do this in an imperative style?"

As you can probably guess, the answer to the second question is "almost/sort of, but it’s reeeealllyy awkward."

Therefore, let’s take this in small bits.

First things first – can you pass a function as an argument to a C++ function and use it in the body? Perhaps surprisingly, the answer is YES! Using function pointers. Sing it, Wikipedia:

Instead of referring to data values, a function pointer points to executable code within memory. When dereferenced, a function pointer can be used to invoke the function it points to and pass it arguments just like a normal function call.

If you’re thinking that sounds a lot like a named GOTO, well, you’ve got it exactly. It makes sense, right? If you define a function, it has to exist somewhere on the stack, right? So, why can’t I just jump there when I need to, run the code that’s there with whatever arguments it takes, and then jump back? And the answer is that you can! Though, you gotta be careful, because this still isn’t a functional invocation the way you’re used to it in Scheme or Haskell or even Javascript because nothing about this guarantees that the function you’re jumping to captures its scope. So, let’s not try this with functions that have a lot of non-argument dependencies, kay?

That’s certainly OK for the factorial example, since our factorial function doesn’t have any outside dependencies. It just depends on its argument.

OK, so remember the first step? The first step is to define a function that implements factorial up to the recursive call, and that takes, as an argument, the function that will implement that recursive call. So, really, the first step is to implement factorial – so here ya go, in good ol’ C++98:

#include <iostream>
using namespace std;

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

int main() 
{
  cout << factorial(5) << endl;
}

If you save that in a file called factorial.cpp and compile it and run it:

g++ -o factorial factorial.cpp && ./factorial

you’ll get 120.

Now that that’s out of the way, we have to see if we can pass that to another function that’s identical to factorial, save that it takes, as an argument, the function that recursive call to factorial depends on in our original function. So, something like this:

int shallowfactorial (function_ptr f, int i)  {
  if( i == 0 ){
    return 1;
  } else {
    return i * f(i - 1);
  }
}

Of course, function_ptr isn’t a real C++ type, so we’ll have to define it. We already know it’s going to need to be a function pointer, since C++ doesn’t let you pass functions by value as such. And as you might expect, the syntax for that, in this statically typed language, requires you to specify a full type signature. In this case, we’re pointing to a function that has type

int → int

That is, it takes a single integer argument and returns an integer. Which you do in C++ for function pointers like so:

int (*f)(int)

That says that f is a pointer to a function that takes an int and returns an int.

Of course, it’s awkward and confusing – this is C++ after all – so we’ll want to use a typedef to avoid having to type that all the time:

typedef int (*function_ptr_i_i)(int);

Alright, so maybe my name is on the long side, but it carries with it its type signature, so I stand by it.

Now let’s use it. Remember, all we need to do is manage to pass the factorial function we defined earlier to shallowfactorial as an argument, just to prove that the first barrier to implementing Y in C++ – passing a function to a function – isn’t really there:

#include <iostream>

using namespace std;

typedef int (*function_ptr_i_i)(int);

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

int shallowfactorial (function_ptr_i_i f, int i)  {
  if( i == 0 ){
    return 1;
  } else {
    return i * f(i - 1);
  }
}

int main() 
{
  cout << factorial(5) << endl;
  cout << shallowfactorial(factorial, 5) << endl;
}

And there you go. Compile it and run it, and it prints out 120 twice, proving that shallowfactorial really accepted our pointer to factorial as an argument and called it. Notice as well that C++ really doesn’t make this that hard. That is, you don’t have to do any dereferencing in the body of the function. The compiler knows that a function pointer is really just an alias to a function call. You can, if you really want to, put the asterisk in front of it to make it clear that f is a pointer to a function, rather than just the name – but you know what? A pointer to a function is just a name for it anyway. The compiler doesn’t generate separate code for each time a function is called, after all. Under the hood, it does for normal function calls exactly what we’re asking it to do here: pushes the arguments to the stack, jumps to the implementation code, runs it, and then jumps back to whereever we were in the stack when we called it. Function calls are GOTOs! Get used to it!

So, that’s one step closer to Y in imperative C++. Still miles to go, though. Next step – can we also return a function(pointer) from a function 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>