Lambda-Over-Lambda in C++14

Question

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}

Nice one for this list: http://www.gnu.org/fun/jokes/helloworld.html — stefaanv, Sep 02 '14 at 08:39
Actually, I'm interested in how this (is/can be) called, so I posted a follow-up question: http://stackoverflow.com/questions/25619769/how-is-this-c14-construct-called — stefaanv, Sep 02 '14 at 09:10
Duplicate of [this question](http://stackoverflow.com/q/25338795/596781)? — Kerrek SB, Sep 02 '14 at 09:13
Perhaps you intended `return terminal(func)(term);` instead of `return terminal(func(term));`? Note that `terminal` needs to be called with arguments *twice* before it does anything. — Aaron McDaid, Sep 02 '14 at 10:34
Oh my god, this: "auto main() -> int" is awful. It's not fun to try to use new tools when the old one are already perfect for the job. Or is "int main()" so 2010 ? — xryl669, Sep 02 '14 at 17:35
Note that the definition of `terminal` didn't capture the variable `terminal` which is used by the anonymous lambda returned by `terminal`. But it works ... it is because `terminal` is defined at the namespace level, which can be accessed by anyone, including the anonymous lambda. However, if it was defined in a function scope, this code wouldn't even compile; and the fix would be, as it is obvious now, capturing the variable `terminal` .....and the capturing of `terminal` by definition of `terminal` would require tricks involving `std::function` or so). — Nawaz, Jan 23 '17 at 13:38

score 45 · Accepted Answer · answered Sep 02 '14 at 08:37

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

terminal(stdout) - this simply returns a lambda which has captured stdout
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.
The result of 2. is called with the lambda world, which does the same as 2, this time the return value is discarded...

score 26 · Answer 2 · answered Sep 02 '14 at 08:33

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".

Thanks I was going through an article, where the author used with two different lambda, however, I unknowingly tried wrapping it over the original.And found it kinda confusing. Thanks for clarification. — P0W, Sep 02 '14 at 10:13

score 13 · Answer 3 · answered Sep 02 '14 at 08:58

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

Piotr Skotnicki · Answer 4 · 2014-09-08T13:32:33.523

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).

True (and technically impressive) but irrelevant to the question asked by OP. — Quuxplusone, Sep 03 '14 at 06:18

DarioP · Answer 5 · 2014-09-02T14:58:20.027

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:

terminal(stdout) returns an unnamed lambda which has captured stdout.
(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.
(world) same as 2.

score 3 · Answer 6 · answered Sep 03 '14 at 04:29

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

terminal(stdout) ==> x(func) { return terminal(func(stdout)) };
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.
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.

Lambda-Over-Lambda in C++14

6 Answers6

Linked