2

I've been reading about combinators for three days now and I finally started writing them in code (more like copying stuff from places and making sense of things).

Here's some code that I'm trying to run:

#include <iostream>
#include <utility>

template <typename Lambda>
class y_combinator {
  private:
    Lambda lambda;
  public:
    template <typename T>
    constexpr explicit y_combinator (T&& lambda)
        : lambda (std::forward <T> (lambda))
    { }

    template <typename...Args>
    decltype(auto) operator () (Args&&... args) {
        return lambda((decltype(*this)&)(*this), std::forward <Args> (args)...);
    }
};

template <typename Lambda>
decltype(auto) y_combine (Lambda&& lambda) {
    return y_combinator <std::decay_t <Lambda>> (std::forward <Lambda> (lambda));
}

int main () {
    auto factorial = y_combine([&] (auto self, int64_t n) {
        return n == 1 ? (int64_t)1 : n * self(n - 1);
    });
    
    int n;
    std::cin >> n;

    std::cout << factorial(n) << '\n';
}

If I explicitly state the return type of the lambda as -> int64_t, everything works well. However, when I remove it, the compiler complains. The error:

main.cpp|16|error: use of 'main()::<lambda(auto:11, int64_t)> [with auto:11 = y_combinator<main()::<lambda(auto:11, int64_t)> >; int64_t = long long int]' before deduction of 'auto'

Why can't the compiler figure out the return type and deduce auto? I first thought that maybe I needed to change ... ? 1 : n * self(n - 1) to ... ? int64_t(1) : n * self(n - 1) so that the type of both return values ends up as int64_t and no possible ambiguities remain. This doesn't seem to be the case though. What am I missing?

Also, in the y_combinator class, declaring lambda as an object of type Lambda&& seems to cause problems. Why is this the case? This only happens when I write the cast in the operator () overload as (decltype(*this)&) instead of std::ref(*this). Are they doing different things?

Improve this question

1 Answer 1

Reset to default
4

Type deduction

The type of n == 1 ? (int64_t)1 : n * self(n - 1) depends on the the return type of self, therefore it can't be deduced. You would think that int64_t is an obvious candidate, but float and double are also just as good. You can't expect the compiler to consider every possible return type and choose the best candidate.

To fix this instead of using a ternary expression, use an if-else block:

int main () {
    auto factorial = y_combine([&] (auto self, int64_t n) {
        if (n == 1) {
            return (int64_t)1;
        } else {
            return n * self(n - 1);
        }
    });
    // ...
}

With this one of the return statements doesn't depend on the return type of self, so type deduction can happen.

When deducting the return type of a function, the compiler looks at all of the return statements in the body of the function in sequence and tries to deduce their type. If it fails you get a compilation error.

Using the ternary operator the type of the return statement return n == 1 ? (int64_t)1 : n * self(n - 1); depends on the return type of self, which is not yet known. Therefore you get a compilation error.

When using an if statement and multiple return statements, the compiler can deduce the return type from the first one it encounters, since

If there are multiple return statements, they must all deduce to the same type.

and

Once a return statement has been seen in a function, the return type deduced from that statement can be used in the rest of the function, including in other return statements.

as seen on cppreference. This is why

        if (n == 1) {
            return (int64_t)1;
        } else {
            return n * self(n - 1);
        }

can be deduced to return an int64_t.

As a side note

        if (n == 1) {
            return 1; // no explicit cast to int64_t
        } else {
            return n * self(n - 1);
        }

would fail to compile because from the first return statement the return type of the function will be deduced as int, and from the second return statement as int64_t.

        if (n != 1) {
            return n * self(n - 1);
        } else {
            return (int64_t)1;
        }

would also fail, because the first return statement it incounters depends on the return type of the function, so it can't be deduced.

Second question

The error happens because when calling lambda you're trying to make a copy of *this because of the lambda's auto self parameter. This is due to having an rvalue reference member. (see clang's great error message on godbolt)

To fix this either use std::ref as mention in the original question or make the lambda have an auto &&self parameter (and use std::forward<decltype(self)>(self)).

Also note that the member Lambda &&lambda is an rvalue reference, so you can only construct an instance of y_combinator with a temporary or moved lambda. In general copying functors in not a big deal, the standard library also takes functor parameters by copy.

Improve this answer
Sign up to request clarification or add additional context in comments.

10 Comments

Could also just use an explicit return type, [](auto self, int64_t n) -> int64_t { ... }
@N.Shead True, but that was already mentioned in the question.
I'm not sure I understand what difference there is between if and ?: for type deduction.
Same as Kostas, I'm not sure I completely understand the "why". I would mark the answer as accepted because maybe there are differences in the working of type deduction for if and ?: branches. However, if someone provides a complete answer to my second question too along with a good explanation to the first, I'd consider that instead. In any case, thanks!
@LostArrow Functors are structs/classes that usually have only a few members that need to be copied. In lambdas they're usually the captured references (basically pointers), which are cheap to copy. I suggest looking into how lambdas work under the hood, this CppCon talk is a good starting point.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.