Can Lambda Functions Be Recursive

Recursive lambda functions in C++11

Think about the difference between the auto version and the fully specified type version. The auto keyword infers its type from whatever it's initialized with, but what you're initializing it with needs to know what its type is (in this case, the lambda closure needs to know the types it's capturing). Something of a chicken-and-egg problem.

On the other hand, a fully specified function object's type doesn't need to "know" anything about what is being assigned to it, and so the lambda's closure can likewise be fully informed about the types its capturing.

Consider this slight modification of your code and it may make more sense:

std::function<int(int, int)> sum;

sum = [term, next, &sum](int a, int b) -> int {
if (a > b)
return 0;
else
return term(a) + sum(next(a), b);
};

Obviously, this wouldn't work with auto. Recursive lambda functions work perfectly well (at least they do in MSVC, where I have experience with them), it's just that they aren't really compatible with type inference.

Can lambda functions be recursive?

Yes, they can. Starting with C++23 you can use the explicit this parameter:

auto factorial = [](this auto self, int i) 
{
return (i == 1) ? 1 : i * self(i - 1);
};

With previous C++ standards, you can store the lambda in a variable and reference that variable (although you cannot declare the type of that variable as auto, you would have to use an std::function object instead). For instance:

std::function<int (int)> factorial = [&] (int i) 
{
return (i == 1) ? 1 : i * factorial(i - 1);
};

Can a lambda function call itself recursively in Python?

The only way I can think of to do this amounts to giving the function a name:

fact = lambda x: 1 if x == 0 else x * fact(x-1)

or alternately, for earlier versions of python:

fact = lambda x: x == 0 and 1 or x * fact(x-1)

Update: using the ideas from the other answers, I was able to wedge the factorial function into a single unnamed lambda:

>>> map(lambda n: (lambda f, *a: f(f, *a))(lambda rec, n: 1 if n == 0 else n*rec(rec, n-1), n), range(10))
[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

So it's possible, but not really recommended!

How to make recursion using only lambdas in Racket?

Given a sample factorial program -

(define fact
(lambda (n)
(if (= n 0)
1
(* n (fact (- n 1)))))) ;; goal: remove reference to `fact`

(print (fact 7)) ; 5040

Above fact is (lambda (n) ...) and when we call fact we are asking for this lambda so we can reapply it with new arguments. lambda are nameless and if we cannot use top-level define bindings, the only way to bind a variable is using a lambda's parameter. Imagine something like -

(lambda (r)
; ...lambda body...
; call (r ...) to recur this lambda
)

We just need something to make our (lambda (r) ...) behave this way -

(something (lambda (r)
(print 1)
(r)))

; 1
; 1
; 1
; ... forever

introducing U

This something is quite close to the U combinator -

(define u
(lambda (f) (f f)))

(define fact
(lambda (r) ;; wrap in (lambda (r) ...)
(lambda (n)
(if (= n 0)
1
(* n ((r r) (- n 1))))))) ;; replace fact with (r r)

(print ((u fact) 7))

; => 5040

And now that recursion is happening thru use of a parameter, we could effectively remove all define bindings and write it using only lambda -

; ((u fact) 7)
(print (((lambda (f) (f f)) ; u
(lambda (r) ; fact
(lambda (n)
(if (= n 0)
1
(* n ((r r) (- n 1)))))))
7))

; => 5040

Why U when you can Y?

The U-combinator is simple but having to call ((r r) ...) inside the function is cumbersome. It'd be nice if you could call (r ...) to recur directly. This is exactly what the Y-combinator does -

(define y
(lambda (f)
(f (lambda (x) ((y f) x))))) ;; pass (y f) to user lambda

(define fact
(lambda (recur)
(lambda (n)
(if (= n 0)
1
(* n (recur (- n 1))))))) ;; recur directly

(print ((y fact) 7))

; => 5040

But see how y has a by-name recursive definition? We can use u to remove the by-name reference and recur using a lambda parameter instead. The same as we did above -

(define u
(lambda (f) (f f)))

(define y
(lambda (r) ;; wrap in (lambda (r) ...)
(lambda (f)
(f (lambda (x) (((r r) f) x)))))) ;; replace y with (r r)

(define fact
(lambda (recur)
(lambda (n)
(if (= n 0)
1
(* n (recur (- n 1)))))))

(print (((u y) fact) 7)) ;; replace y with (u y)

; => 5040

We can write it now using only lambda -

; (((u y) fact) 7)
(print ((((lambda (f) (f f)) ; u
(lambda (r) ; y
(lambda (f)
(f (lambda (x) (((r r) f) x))))))
(lambda (recur) ; fact
(lambda (n)
(if (= n 0)
1
(* n (recur (- n 1)))))))
7))

; => 5040

need more parameters?

By using currying, we can expand our functions to support more parameters, if needed -

(define range
(lambda (r)
(lambda (start)
(lambda (end)
(if (> start end)
null
(cons start ((r (add1 start)) end)))))))

(define map
(lambda (r)
(lambda (f)
(lambda (l)
(if (null? l)
null
(cons (f (car l))
((r f) (cdr l))))))))

(define nums
((((u y) range) 3) 9))

(define squares
((((u y) map) (lambda (x) (* x x))) nums))

(print squares)
; '(9 16 25 36 49 64 81)

And as a single lambda expression -

; ((((u y) map) (lambda (x) (* x x))) ((((u y) range) 3) 9))
(print (((((lambda (f) (f f)) ; u
(lambda (r) ; y
(lambda (f)
(f (lambda (x) (((r r) f) x))))))
(lambda (r) ; map
(lambda (f)
(lambda (l)
(if (null? l)
null
(cons (f (car l))
((r f) (cdr l))))))))
(lambda (x) (* x x))) ; square
(((((lambda (f) (f f)) ; u
(lambda (r) ; y
(lambda (f)
(f (lambda (x) (((r r) f) x))))))
(lambda (r) ; range
(lambda (start)
(lambda (end)
(if (> start end)
null
(cons start ((r (add1 start)) end)))))))
3) ; start
9))) ; end

; => '(9 16 25 36 49 64 81)

lazY

Check out these cool implementations of y using lazy

#lang lazy

(define y
(lambda (f)
(f (y f))))
#lang lazy

(define y
((lambda (f) (f f)) ; u
(lambda (r)
(lambda (f)
(f ((r r) f))))))
#lang lazy

(define y
((lambda (r)
(lambda (f)
(f ((r r) f))))
(lambda (r)
(lambda (f)
(f ((r r) f))))))

Why is this recursive lambda function unsafe?

This is because in order to be recursive, it uses type erasure and captures the type erased container by reference.

This has the effect of allowing to use the lambda inside itself, by refering to it indirectly using the std::function.

However, for it to work, it must capture the std::function by reference, and that object has automatic storage duration.

Your lambda contains a reference to a local std::function. Even if you return the std::function by copy, the lambda will still refer to the old one, that died.

To make a secure to return recursive lambda, you can send the lambda to itself in an auto parameter and wrap that in another lambda:

auto factorial = [](auto self, int i) -> int { 
return (i == 1) ? 1 : i * self(self, i - 1);
};

return [factorial](int i) { return factorial(factorial, i); };

Recursive lambda functions in C++14

The crux of the issue is that in a C++ lambda expression the implicit this parameter will always refer to the object of the enclosing context of the expression, if present at all, and not the functor object resulting from the lambda expression.

Borrowing a leaf from anonymous recursion (sometimes also known as 'open recursion'), we can use the generic lambda expressions of C++14 to re-introduce an explicit parameter to refer to our would-be recursive functor:

auto f = [](auto&& self, int n) -> int
{ return n < 2 ? 1 : n * self(/* hold on */); };

The caller now has a new burden of making calls of the form e.g. f(f, 5). Since our lambda expression is self-referential, it is in fact a caller of itself and thus we should have return n < 2 ? 1 : n * self(self, n - 1);.

Since that pattern of explicitly passing the functor object itself in the first position is predictable, we can refactor this ugly wart away:

template<typename Functor>
struct fix_type {
Functor functor;

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

/* other cv- and ref-qualified overloads of operator() omitted for brevity */
};

template<typename Functor>
fix_type<typename std::decay<Functor>::type> fix(Functor&& functor)
{ return { std::forward<Functor>(functor) }; }

This allows one to write:

auto factorial = fix([](auto&& self, int n) -> int
{ return n < 2 ? 1 : n * self(self, n - 1); });

assert( factorial(5) == 120 );

Did we succeed? Since the fix_type<F> object contains its own functor which it passes to it for each call, there is never a risk of a dangling reference. So our factorial object can truly be endless copied, moved from, in and out of functions without hassle.

Except... while the 'external' callers can readily make calls of the form factorial(5), as it turns out inside our lambda expression the recursive call still looks like self(self, /* actual interesting args */). We can improve on this by changing fix_type to not pass functor to itself, but by passing *this instead. That is, we pass in the fix_type object which is in charge of passing the correct 'implicit-as-explicit' argument in the first position: return functor(*this, std::forward<Args>(args)...);. Then the recursion becomes n * self(n - 1), as it should be.

Finally, this is the generated code for a main that uses return factorial(5); instead of the assertion (for either flavour of fix_type):

00000000004005e0 <main>:
4005e0: b8 78 00 00 00 mov eax,0x78
4005e5: c3 ret
4005e6: 66 90 xchg ax,ax

The compiler was able to optimize everything away, as it would have done with a run-off-the-mill recursive function.


What are the costs?

The astute reader may have noticed one curious detail. In the move from a non-generic to a generic lambda, I added an explicit return type (i.e. -> int). How come?

This has to do with the fact that the return type to be deduced is the type of the conditional expression, which type depends on the call to self, which type is being deduced. A quick reading of Return type deduction for normal functions would suggest that rewriting the lambda expression as follows should work:

[](auto&& self, int n)
{
if(n < 2) return 1; // return type is deduced here
else return n * self(/* args */); // this has no impact
}

GCC will in fact accept this code with the first form of fix_type only (the one that passes functor). I'm not able to determine if it is right to complain about the other form (where *this is passed). I leave it to the reader to choose what trade-off to make: less type deduction, or less ugly recursive calls (it's also of course completely possible to have access to either flavour anyway).


GCC 4.9 examples

  • Complete code, first flavour
  • Complete code, second flavour
  • Complete code, first flavour, C++11
  • An example of a variadic fix for a group of mutually recursive lambda expressions

Recursive AWS Lambda function calls - Best Practice

UPDATE: AWS EventBridge now looks like the preferred solution.


It's "Coupling" that I was thinking of, see here: https://www.jeffersonfrank.com/insights/aws-lambda-design-considerations

Coupling

Coupling goes beyond Lambda design considerations—it’s more about the system as a whole. Lambdas within a microservice are sometimes tightly coupled, but this is nothing to worry about as long as the data passed between Lambdas within their little black box of a microservice is not over-pure HTTP and isn’t synchronous.

Lambdas shouldn’t be directly coupled to one another in a Request Response fashion, but asynchronously. Consider the scenario when an S3 Event invokes a Lambda function, then that Lambda also needs to call another Lambda within that same microservice and so on.

aws lambda coupling

Sample Image

You might be tempted to implement direct coupling, like allowing Lambda 1 to use the AWS SDK to call Lambda 2 and so on. This introduces some of the following problems:

  1. If Lambda 1 is invoking Lambda 2 synchronously, it needs to wait for the latter to be done first. Lambda 1 might not know that Lambda 2 also called Lambda 3 synchronously, and Lambda 1 may now need to wait for both Lambda 2 and 3 to finish successfully. Lambda 1 might timeout as it needs to wait for all the Lambdas to complete first, and you’re also paying for each Lambda while they wait.

  1. What if Lambda 3 has a concurrency limit set and is also called by another service? The call between Lambda 2 and 3 will fail until it has concurrency again. The error can be returned to all the way back to Lambda 1 but what does Lambda 1 then do with the error? It has to store that the S3 event was unsuccessful and that it needs to replay it.

This process can be redesigned to be event-driven: lambda coupling

Sample Image

Not only is this the solution to all the problems introduced by the direct coupling method, but it also provides a method of replaying the DLQ if an error occurred for each Lambda. No message will be lost or need to be stored externally, and the demand is decoupled from the processing.

Call C++ recursive lambda in the same line where it is declared

Let me offer a glimpse into the functional programming world, where people usually use combinators to deal with recursive lambdas. There was a proposal (P0200r0) last year to add a simple Y-combinator to the standard library.

Leaving aside the question whether it is a good idea to do this, this would allow you to write and invoke a recursive lambda like this:

y_combinator([](auto self, int i){
if (i>1) {
std::cout << "func(a, ";
self(i-1);
std::cout << ")";
} else {
std::cout << "a";
}
})(6);

The basic idea here is that the y-combinator is a higher order function that wraps a lambda which is passed 'itself' as a first argument. The combinator takes care of wrapping the self argument away for all invocations of the lambda.

You can try it in coliru.



Related Topics



Leave a reply



Submit