Lambda-Over-Lambda in C++14

How following recursive lambda call ends/terminates ?

#include <cstdio>

auto terminal = [](auto term)            // <---------+  
{                                        //           |
    return [=] (auto func)               //           |  ???
    {                                    //           |
        return terminal(func(term));     // >---------+
    };
};


auto main() -> int
{
    auto hello =[](auto s){ fprintf(s,"Hello\n"); return s; };
    auto world =[](auto s){ fprintf(s,"World\n"); return s; };

    
    terminal(stdout)
            (hello)
            (world) ;
    
    return 0;

}

What am I missing over here ?

^{Running code}

It's not a recursive function call, look at it step-by-step:

1. terminal(stdout) - this simply returns a lambda which has captured stdout
2. The result of 1. is called with the lambda hello, which executes the lambda (func(term)), the result of which is passed to terminal(), which simply returns a lambda as in 1.
3. The result of 2. is called with the lambda world, which does the same as 2, this time the return value is discarded...

The call itself is not recursive. It returns a function object which, if called, will call terminal again to generate yet another function object.

So terminal(stdout) returns a functor which captures stdout and can be called with another function object. Calling it again, (hello), calls the hello functor with the captured term stdout, outputting "Hello"; the calls terminal and returns another functor which this time captures the return value of hello - which is still stdout. Calling that functor, (world), just the same again, outputting "World".

The key here is to understand that this is valid:

world(hello(stdout));

and will print "Hello World". The recursive series of lambdas can be unrolled as

#include <cstdio>

auto terminal = [](auto term)            // <---------+  
{                                        //           |
    return [=] (auto func)               //           |  ???
    {                                    //           |
        return terminal(func(term));     // >---------+
    };
};

/*
terminal(stdout) -returns> anonymous_lambda which captures stdout (functor)
anonymous_lambda(hello) is called, func(term) is hello(stdout) and prints "Hello" and returns stdout, the anonymous_lambda -returns> terminal(stdout)
(the above 2 lines start again)
terminal(stdout) is called and -returns> anonymous_lambda which captures stdout (functor)
anonymous_lambda(world) is called, func(term) is world(stdout) and prints "World" and returns stdout, the anonymous_lambda -returns> terminal(stdout)
terminal(stdout) is called and -returns> anonymous_lambda which captures stdout (functor)
nobody uses that anonymous_lambda.. end.
*/

auto main() -> int
{
    auto hello =[](auto s){ fprintf(s,"Hello\n"); return s; };
    auto world =[](auto s){ fprintf(s,"World\n"); return s; };

    world(hello(stdout));
    
    
    terminal(stdout)
            (hello)
            (world) ;

    return 0;

}

Coliru example

It can be internally translated into something that looks as follows:

#include <cstdio>

template <typename T>
struct unnamed_lambda
{
    unnamed_lambda(T term) : captured_term(term) {}

    template <typename A>
    unnamed_lambda operator()(A func);
    
    T captured_term;
};

struct terminal_lambda
{
    template <typename A>
    unnamed_lambda<A> operator()(A term)
    {
        return unnamed_lambda<A>{term};
    }
};

terminal_lambda terminal;

template <typename T>
template <typename A>
unnamed_lambda<T> unnamed_lambda<T>::operator()(A func)
{
    return terminal(func(captured_term));
}

struct Hello
{
    FILE* operator()(FILE* s)
    {
        fprintf(s, "Hello\n");
        return s;
    }
};

struct World
{
    FILE* operator()(FILE* s)
    {
        fprintf(s, "World\n");
        return s;
    }
};
    
int main()
{    
	Hello hello;
	World world;
    unnamed_lambda<FILE*> l1 = terminal(stdout);
    unnamed_lambda<FILE*> l2 = l1(hello);
    unnamed_lambda<FILE*> l3 = l2(world);
    
    // same as:
    terminal(stdout)(hello)(world);
}

LIVE DEMO

Actually this is what the compiler does behind the scene with lambdas (with some approximation).

I think that the source of confusion comes from reading a lambda declaration as a lambda call. Indeed here:

auto terminal = [](auto term)            // <---------+  
{                                        //           |
    return [=] (auto func)               //           |  ???
    {                                    //           |
        return terminal(func(term));     // >---------+
    };
};

the author just declared a lambda terminal which takes one arbitrary argument term and returns an unnamed lambda, nothing more! Let's look at this unnamed lambda, it:

• accepts a callable object func as argument and calls it on the copy-captured parameter term and
• returns the result of terminal called with the result of the call func(term); so it returns another unnamed lambda that captures the result of func(term), it but this lambda is not called by now, there is no recursion.

Now the trick in the main should be more clear:

1. terminal(stdout) returns an unnamed lambda which has captured stdout.
2. (hello) calls this unnamed lambda passing as arg the hello callable. This gets called on the stdout previously captured. hello(stdout) returns again stdout which is used as argument of a call to terminal, returning another unnamed lambda which has captured stdout.
3. (world) same as 2.

1. terminal(stdout) returns a function, let's call it function x, with param func. So:

   terminal(stdout) ==> x(func) { return terminal(func(stdout)) };

2. Now terminal(stdout)(hello) calls function x(hello):

   terminal(stdout)(hello) ==> x(hello) { return terminal(hello(stdout)) };

   This results in hello function get called and returns function x again.

3. Now terminal(std)(hello)(world) calls function x(world):

   terminal(stdout)(hello) ==> x(world) { return terminal(world(stdout)) };

   This results in world function get called and returns function x again. Function x now is not called any more as there is no more param.