Fixed point combinator and explicit result type

Question

To perform some recursive tasks locally I use the following approach to create fixed point combinator in place:

#include <utility>
#include <list>
#include <memory>
#include <iostream>

int main()
{
    struct tree
    {
        int payload;
        std::list< tree > children = {}; // std::list of incomplete type is allowed
    };
    std::size_t indent = 0;
    // indication of result type here is essential
    const auto print = [&] (const auto & self, const tree & node) -> void
    {
        std::cout << std::string(indent, ' ') << node.payload << '\n';
        ++indent;
        for (const tree & t : node.children) {
            self(self, t);
        }
        --indent;
    };
    print(print, {1, {{2, {{8}}}, {3, {{5, {{7}}}, {6}}}, {4}}});
}

It works fine and prints:

1
 2
  8
 3
  5
   7
  6
 4

But if I remove explicitly specified result type -> void, then I get compile error (GCC 8):

prog.cc: In instantiation of 'main():: [with auto:1 = main()::]':

prog.cc:24:64: required from here

prog.cc:20:17: error: use of 'main():: [with auto:1 = main()::]' before deduction of 'auto'

         self(self, t);

(clang 7):

prog.cc:20:13: error: function 'operator()<(lambda at prog.cc:15:24)>' with deduced return type cannot be used before it is defined

        self(self, t);

        ^

prog.cc:24:10: note: in instantiation of function template specialization 'main()::(anonymous class)::operator()<(lambda at prog.cc:15:24)>' requested here

print(print, {1, {{2, {{8}}}, {3, {{5, {{7}}}, {6}}}, {4}}});

     ^

prog.cc:15:24: note: 'operator()<(lambda at prog.cc:15:24)>' declared here

const auto print = [&] (const auto & self, const tree & node)

                   ^

1 error generated.

What is the cause of the error? I think compiler can deduce result type looking at function body. The result type is not dependent on "template" self parameter type.

Answer 1

In order to deduce the return type, the lambda (better, its call operator) is instantiated and it requires to be fully defined, mainly because return type is deduced from any non discarded return statement. When you use it from within the body, it isn't fully defined yet for obvious reasons and thus the return type is still unknown. Therefore it's impossible to say what's the type of the expression and the program is ill-formed.

Answer 2

The rule in [dcl.spec.auto] is:

If the type of an entity with an undeduced placeholder type is needed to determine the type of an expression, the program is ill-formed. Once a non-discarded return statement has been seen in a function, however, the return type deduced from that statement can be used in the rest of the function, including in other return statements.

If you explicitly specify void as the return type, there's no undeduced placeholder type, so we're fine.

But if we don't, then when we invoke

print(print, {1, {{2, {{8}}}, {3, {{5, {{7}}}, {6}}}, {4}}});

In the expression self(self, t), the type of print's operator() (an "entity with an undeduced placeholder type") is needed to determine the type of the expression, so we run afoul of that first sentence.