How do I manage declarations that require template parameters derived from recursive functors/lambdas?

Question

I am attempting to build a clean and neat implementation of recursive-capable lambda self-scoping (which is basically a Y-combinator although I think technically not quite). It's a journey that's taken me to, among many others, this thread and this thread and this thread.

I've boiled down one of my issues as cleanly as I can: how do I pass around templated functors which take lambdas as their template parameters?

#include <string>
#include <iostream>
#define uint unsigned int

template <class F>
class Functor {
public:
    F m_f;

    template <class... Args>
    decltype(auto) operator()(Args&&... args) {
        return m_f(*this, std::forward<Args>(args)...);
    }
};
template <class F> Functor(F)->Functor<F>;

class B {
private:
    uint m_val;
public:
    B(uint val) : m_val(val) {}
    uint evaluate(Functor<decltype([](auto & self, uint val)->uint {})> func) const {
        return func(m_val);
    }
};

int main() {
    B b = B(5u);
    Functor f = Functor{[](auto& self, uint val) -> uint {
        return ((2u * val) + 1u);
    }};

    std::cout << "f applied to b is " << b.evaluate(f) << "." << std::endl;
}

The code above does not work, with Visual Studio claiming that f (in the b.evaluate(f) call) does not match the parameter type.

My assumption is that auto & self is not clever enough to make this work. How do I get around this? How do I store and pass these things around when they are essentially undefinable? Is this why many of the Y-combinator implementations I've seen have the strange double-wrapped thing?

Any help or explanation would be enormously appreciated.

Answer 1

The easiest solution is:

uint evaluate(std::function<uint(uint)> func) const {
    return func(m_val);
}

a step up would be to write a function_view.

uint evaluate(function_view<uint(uint)> func) const {
    return func(m_val);
}

(there are dozens of implementations on the net, should be easy to find).

The easiest and most runtime efficient is:

template<class F>
uint evaluate(F&& func) const {
    return func(m_val);
}

because we don't care what func is, we just want it to quack like a duck. If you want to check it early...

template<class F> requires (std::is_convertible_v< std::invoke_result_t< F&, uint >, uint >)
uint evaluate(F&& func) const {
    return func(m_val);
}

using c++20, or using c++14

template<class F,
  std::enable_if_t<(std::is_convertible_v< std::invoke_result_t< F&, uint >, uint >), bool> = true
>
uint evaluate(F&& func) const {
    return func(m_val);
}

which is similar just more obscure.

You can write a fixes-signature type-erased Functor, but I think it is a bad idea. It looks like:

template<class R, class...Args>
using FixedSignatureFunctor = Functor< std::function<R( std::function<R(Args...)>, Args...) > >;

or slightly more efficient

template<class R, class...Args>
using FixedSignatureFunctor = Functor< function_view<R( std::function<R(Args...)>, Args...) > >;

but this is pretty insane; you'd want to forget what the F is, but not that you can replace the F!

To make this fully "useful", you'd have to add smart copy/move/assign operations to Functor, where it can be copied if the Fs inside each of them can be copied.

template <class F>
class Functor {
public:
  // ...
  Functor(Functor&&)=default;
  Functor& operator=(Functor&&)=default;
  Functor(Functor const&)=default;
  Functor& operator=(Functor const&)=default;

  template<class O> requires (std::is_constructible_v<F, O&&>)
  Functor(Functor<O>&& o):m_f(std::move(o.m_f)){}
  template<class O> requires (std::is_constructible_v<F, O const&>)
  Functor(Functor<O> const& o):m_f(o.m_f){}
  template<class O> requires (std::is_assignable_v<F, O&&>)
  Functor& operator=(Functor<O>&& o){
    m_f = std::move(o.mf);
    return *this;
  }
  template<class O> requires (std::is_assignable_v<F, O const&>)
  Functor& operator=(Functor<O> const& o){
    m_f = o.mf;
    return *this;
  }
  // ...
};

(c++20 version, replace requires clauses with std::enable_if_t SFINAE hack in c++17 and before).

How to decide

The core thing to remember here is that C++ has more than one kind of polymorphism, and using the wrong kind will make you waste a lot of time.

There is both compile time polymorphism and runtime polymorphism. Using runtime polymorphism when you only need compile time polymorphism is a waste.

Then in each category, there are even more subtypes.

std::function is a runtime polymorphic type erasure regular object. Inheritance based virtual functions is another runtime polymorphic technique.

Your Y-combinator is doing compile time polymorphism. It changes what it stores and exposed a more uniform interface.

Things talking to that interface don't care about the internal implementation details of your Y-combinator, and including them in their implementation is an abstraction failure.

evaluate takes a callable thing and pass it in uint and expects a uint in return. That is what it care about. It doesn't care if it is passed a Functor<Chicken> or a function pointer.

Making it care about it is a mistake.

If it takes a std::function, it does runtime polymorphism; if it takes a template<class F> with an argument of type F&&, it is compile time polymorphic. This is a choice, and they are different.

Taking a Functor<F> of any kind is putting contract requirements in its API it fundamentally shouldn't care about.

Answer 2

The only way I see is make evaluate() a template method; if you want to be sure to receive a Functor (but you can simply accept a callable: see Yakk's answer):

template <typename F>
uint evaluate(Functor<F> func) const {
    return func(m_val);
}

Take in count that every lambda is a different type, as you can verify with the following trivial code

auto l1 = []{};
auto l2 = []{};

static_assert( not std::is_same_v<decltype(l1), decltype(l2)> );

so impose a particular lambda type to evaluate() can't work because if you call the method with (apparently) the same lambda function, the call doesn't match, as you can see in the following example

auto l1 = []{};
auto l2 = []{};

void foo (decltype(l1))
 { }

int main ()
 {
   foo(l2); // compilation error: no matching function for call to 'foo'
 }