You may (or may not...) have heard of the Y-combinator proposal for the C++ standard library. If you are like me, then you may have been asking yourself why should we need such a thing in C++? Is that because of the current functional programming fad? Keeping up with the (programming-) Joneses? At that point you probably shrugged and went on with your life (like me)...But then I met with a similar problem in some template metaprogramming contexts ans I think it is worth a separate blogpost. So I started writing this post... back in 2017 and finished it only now (2022) 😐.
Y-What???
It originates from lambda calculus - this, in its turn is a simple formalization of the notion of mathematical function. And lambda calculus does not have (BTW: did you notice that in modern days you have to know more and more of the CS-gibberish as working programmer?) recursion: a function can call another functions, as this is all that got formalized (see above). No looping there... You cannot loop when everything you have is function call with some parameters. Or can you?
The inventor of lambda calculus didn't think so, but his PhD student (some guy called, that's not a joke (!!!), Haskell Curry*) disabused him of that notion - he found the trick. We don't want to discuss it here (this post isn't about lambda calculus** in the end!) but you will maybe get a feeling of it after you have seen the C++ implementation.
Why in C++?
Ok, the Y-combinator stuff is clear now, but why do we need in in C++? AFAIK we have recursion in C++, by Jove, we even are blessed with iteration! Not so fast young Padawan, there is a context in the language where this is not true. Guess what... Of course, the lambdas.
The problem is, that we cannot refer to the current lambda in its body. When you try *this, this will give you the captured context class - does it ring a bell? Yes, thats the situation we have in Javascript's callbacks! So what can we do about it? in Javascript you just save the value of this in the self variable and forward it to the function. Can we do that in C++ too?
Well, not really: we'd need the type of lambda to declare a pointer to it, to be given in it's constructor... You see, it's a vicious circle :-/. Loosely typed languages escape this predicament by just not typing anything, but what can we do with our oldskool C++ type system?
First, we could request a new language feature - why not? It's so obvious, that somebody even tried to do this (guess who?***):
auto foo = [] self (int x) -> int
{
if(x == 0)
return 0;
else
return self(x - 1);
}
Here there is additional "parameter" in lambda's definition (i.e. self) that can be used inside of the lambda. But as Bjarne is known to dislike solutions which require a new language features if the problem can be solved in library (written 2017) , the question is: can we have a workaround for this?How?
The easy way is to use std::function to wrap the lambda. As it uses type erasure, there's no need for the exact type and thus we can duplicate the solution of loosely typed languages! Here is the xample code from the proposal:
std::function<int(int, int)> gcd = [&](int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
};
// use:
int res = gcd(20, 110);
Bingo? Not really, this solution shares one weekness with dynamically typed languages - it sucks at performance! Why's that? I won't discuss it in detail here, let it be enough to say that std::function generally isn't by any means a paragon of performance.However, we can work around the problem by just defining a, let's call it, "almost"-lambda, and then invoking it form the outside passing its own reference as one of the parameters! But how would that look like? Show me the code! Voila, here is an example implementation for a left fold of a sequence using lambdas:
template <typename Acc, typename F, typename... T>
// wrapper
constexpr auto foldLeft(F func, Acc acc, T... xs)
{
// the "almost"-foldLeft-lambda
auto step = [=](auto self, auto acc_, auto x_, auto... xs_)
{
// calculation
auto sum = func(acc_, x_);
// recursion?
if constexpr(sizeof...(xs_) != 0)
return self(self, sum, xs_...);
else
// finish
return sum;
};
// result: the fully recursive lambda!
return step(step, acc, xs...);
}
If you pay attention to the comments and give it a little thought, this code should be clear enough. Now let us test it: #include <iostream>
int main()
{
std::cout << "sum 1,2,3,4,5 = "
<< foldLeft([](int a, int b) { return a + b; },
0,
1,2,3,4,5);
std::cout << "\nfact 1,2,3,4,5 = "
<< foldLeft([] (int a, int b) { return a * b; },
1,
1,2,3,4,5);
}
and indeed we get the following output:
sum 1,2,3,4,5 = 15 fact 1,2,3,4,5 = 120
Good, seems to be working!
Abstracting things away?
As programmers, we are are trying to separate the functionalities for sake of code clarity. Could we somehow abstract away this whole business of forwarding the reference to self? As it seems, this is possible with followintg trick:
#include <utility>
template<class F>
struct y_combinator_impl
{
F func; // recursive lambda (taking self as 1st parameter)
template<class...Args>
decltype(auto) operator()(Args&&...args) const
{
// forward the reference to self when called!
return func(*this, std::forward<Args>(args)...);
}
};
template<class F>
y_combinator_impl<std::decay_t<F>> make_y_combinator(F&& func)
{
return {std::forward<F>(func)};
};
The trick here is that we do not forward the reference of a lambda directly, but use a plain, old C++ class wrapping the lambda instead! Out of a sudden we have no problems whatsoever with getting a reference of the recursive function object! Problem solved using an additonal level of abstraction! 🙂 With the above code we can simplify our implementation of left fold as follows:
template <typename Acc, typename F, typename... T>
constexpr auto foldLeft(F func, Acc acc, T... xs)
{
// the "almost"-foldLeft-lambda
auto step = [=](auto self, auto acc_, auto x_, auto... xs_)
{
auto sum = func(acc_, x_);
if constexpr(sizeof...(xs_) != 0)
// simplify: no passing of self-reference needed!
return self(sum, xs_...);
else
return sum;
};
// "bless" the almost-lambda, invoke it with arguments
return make_y_combinator(step)(acc, xs...);
}
// use:
std::cout << "sum 1,2,3,4,5 = "
<< foldLeft([](int a, int b) { return a + b; },
0,
1,2,3,4,5);
In fact, we can simplify it even further:
auto almost_lfold = [=](auto self, auto func, auto acc_, auto x_, auto... xs_)
{
auto sum = func(acc_, x_);
if constexpr(sizeof...(xs_) != 0)
return self(func, sum, xs_...);
else
return sum;
};
auto fold_left = make_y_combinator(almost_lfold); // curried with "almost_lfold"!
// use:
std::cout << "sum 1,2,3,4,5 = "
<< fold_left([](int a, int b) { return a + b; },
0,
1,2,3,4,5);
Now the trick becoms even clearer - the make_y_combinator() function call only wraps the lambda in a plain, old C++ class and leaves the call operator unspecified at first. Only when the call operator is invoked, will it be generated from its template specification, thus leaving us with the impression of a preexisting curried function. Nice!The proposal
The proposal we mention (P0200R0) includes following example implementation of the Y combinator:
template<class Fun>
class y_combinator_result {
Fun fun_;
public:
template<class T>
explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args>
decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template<class FunT>
decltype(auto) y_combinator(Fun &&fun)
{
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
On a cursory look upon it, we can see that its std::y_combinator() function corresponds to our make_y_combinator() and the std::y_combinator_result class to our y_combinator_impl structure with the applied technique being exactly the same. After having understood our home-made implementation from above, we shouldn't have any problems reading the example implementation from the proposal!Let us finally show the recursive lambda example used in the proposal. The code follows below:
auto almost_gcd = [](auto gcd, int a, int b) -> int
{
return b == 0 ? a : gcd(b, a % b);
};
auto gcd = std::y_combinator(std::ref(almost_gcd));
std::cout << gcd(20, 30) << std::endl;
Here you can see the pattern present in all the explanations of the Y combinator - first we define an "almost" implementation, then we "bless" it with the Y combinator and voila, the recursion is automagically there!OK, next let us try and find out if the above example can be written with our home-made code for Y combinator:
// lambda from the proposal:
auto almost_gcd = [](auto gcd, int a, int b) -> int
{
return b == 0 ? a : gcd(b, a % b);
};
// use our own impl. to "bless" it
auto gcd = make_y_combinator(std::ref(almost_gcd));
// test:
std::cout << "\ngcd 20,30 = " << gcd(20, 30) << std::endl;
std::cout << "\ngcd 77,122 = " << gcd(77, 122) << std::endl;
and indeed we get the following output:
gcd 20,30 = 10 gcd 77,122 = 11
Seems to be working too, cool!
Needed?
Now, at last we can respond to the question we posed in the title - do we really need the Y combinator in C++? The short answer is: it depends. The longer answer is: maybe. The long answer follows below.
To begin with, passing the self parameter down in the recursion isn't that difficult. We can even get more into functional programming style and write the foldLeft example as follows****:
template <typename Acc, typename F, typename... T>
constexpr auto foldLeft(Acc acc, F func, T... xs)
{
auto step = [=](auto self)
{
return [=](auto acc_, auto x_, auto... xs_)
{
auto sum = func(acc_, x_);
if constexpr(sizeof...(xs_) != 0)
return self(self)(sum, xs_...);
else
return sum;
};
};
return step(step)(acc, xs...);
}
Depending on your background this style can be more or less eaysy on your eyes (admittedly the self(self)/step(step) syntax can look pretty confusing at first 😨). What we are doing here is to define a lambda returning a lambda and then first call the outer lambda to access the inner lambda and call it in its turn. Calling the outer lambda with a parameter is what we call currying in functional languages like Haskell (Haskell's curry anyone? 😉).
From this perspective the answer is a maybe, because the Y combinator takes care of passing the self parameter down in the recursion, provided, of course, you know what a Y combinator is. The problem is, not many imperative programmers seem to know that. Maybe recurse() would be a better name for it?
// this proposal
auto fib = [](this auto self, int n) {
if (n < 2) return n;
return self(n-1) + self(n-2);
};
So you have it - in C++23 we don't need it al all! So the second answer is then it depends, namely, it depends on what C++ version you are using... Admittedly, the syntax of the of the above recursive lamba maybe isn't that self-explaining, but as this one is already getting too long, I will defer discussion of P0847 to a separate post. See you there!
PS: Get the code to play with from this Github gist: https://gist.github.com/mrkkrj/712ad5c1e6cfb6d91262b3582bd691a6
--
* he's name should rather be Curry Haskell or Currying Haskell or Haskell "Is-By-Default" Curried! 😊
** you can read about lambda calculs and C++ here: https://yongweiwu.wordpress.com/2014/12/14/y-combinator-and-cplusplus/
*** yes, you guessed it: proposal P0200R0 (Add Y Combinator to the Standard Library), but only as a side note. Also a separate proposal allowing just that existed: P0839R0 (Recursive lambdas)
**** https://stackoverflow.com/questions/35608977/understanding-y-combinator-through-generic-lambdas
No comments:
Post a Comment