7 ms·

Curious C++ Lambda Examples: Recursion, constexpr, Containers C++23 included

67 points by joebaf 4y ago

nh23423fefe 4y ago
People say things like, "haskell is hard to reason about because of lazy evaluation" but then this. Also many sets of people are disjoint.
dleslie 4y ago
Oof, just a whole lot of oof. So much developer thought and mental energy expended to do something as simple as recursion.
- klyrs 4y ago
  To be fair, most of the examples (and all of the ugly ones, IMO) are warts in today's C++ standard that are being greatly improved in C++23. That said, unless I use it frequently (spoiler: I won't), "this auto&& self" is gonna look weird and I really hope that searching the web for "this auto self" will produce useful hits by the time C++23 is in common use.
  - amluto 4y ago
    I find it quite bizarre that ‘this’ ends up with two names in this construct.
    - lionkor 4y ago
      It really is bizarre, and this is the first time i've seen "deducing this" used. However, I get the naming so far: `this` can be captured, like [this](int x) { return x + this->x; } which we can use, in thise case, to discern between the local x, and this's x. Super contrived, but it illustrates that "this" may be there, too. Then, if you want to capture the lambda, and `this`. Then you need a new name, you can name it `self`, you can name it `this_lambda`, you can name it `ben` - but not `this` since it's reserved and can actually be used in that scope.
- stinos 4y ago
  Recursion is just one of the things being used as a means to explain/show lambdas here, i.e. the energy spent is for the explanation, not for recursion.
- einpoklum 4y ago
  Recursion in C++ is quite simple: int factorial (int n) { return (n > 1) ? n * factorial(n - 1) : 1; } it gets more complicated for more esoteric use cases: * Recursion in an anonymous function. Are you sure this is so simple in other languages? * Compile-time recursion with anonymous functions. Which other languages even have this to begin with? Both of these cases are rarely used in practice. The C++23 addition which facilitates them is actually due to another issue entirely, which is avoiding code duplication when you want to specialize methods according to features of the object they're running for (const/non-const, lvalue/rvalue). See: https://devblogs.microsoft.com/cppblog/cpp23-deducing-this/ https://devblogs.microsoft.com/cppblog/cpp23-deducing-this/
  - SnowHill9902 4y ago
    Can the compiler statically prove that it’ll not cause stack overflow? Otherwise recursion seems quite unsafe.
    - jeffbee 4y ago
      A theoretical compiler could statically prove that this program would have undefined behavior for any argument larger than 12, because signed overflow is UB, and it could arrive at the worst-case stack size from that.
    - einpoklum 4y ago
      Naturally (if we remember our Turing machine computational capability analysis), the compiler cannot generally prove things about recursive functions, including how deep the recursion will go. What it can do in practice is use (configurable) hard limits on the depth and on the amount of time for evaluating constexpr expressions. That way it doesn't overflow its own stack/buffers, nor will it hang on such evaluations. This is good enough, since the purpose of this feature is not perform heavy computations using the compiler, but rather preventing not-so-heavy computations from being performed repeatedly at run-time (and to be able to use their results in template instantiation etc.)
  - dleslie 4y ago
    It's a named lambda, using self capture, and that's been in other languages for decades. Scheme is a good example, with letrec. Compile time recursive functions are likewise available in common lisp via recursive macros. Some schemes have them, too. And the syntax is much more elegant.
cjfd 4y ago
I think they should stop adding new major feature to C++. It is big enough. One can do enough with it. O, you cannot call a lambda recursively? Then just tell people to write a normal named function instead of polluting the language further with unneeded stuff.
- einpoklum 4y ago
  Many features are added to C++ not in order to "cover more", but to be able to do things better, or often - to allow making things _easier_ for the lay programmer (which is not the same thing as making things easier for library authors).
josephcsible 4y ago
The examples with `fact_impl` are basically how you'd write recursion in terms of a fixed-point combinator (e.g., the very Y combinator that this site is named after).
- goldenkey 4y ago
  It took me a while to grok the y-combinator, but I eventually realized it's just a generic factory, as a trampoline, that ceases to return a function invocation, just the last value, when it reaches the fixed point -- so it can actually reach a stopping point and not cause infinite recursion, without needing a self-reference.
- deleted 4y ago
  [deleted]
krater23 4y ago
This examples are reading all like 'How to use the newest C++ features to write unreadable code'.
- imron 4y ago
  Right. This is the sort of thing that’s interesting to know from an intellectual perspective to see how far can you bend and twist a language to do certain things, but you’re setting yourself up for a world of maintenance pain if you use this sort of stuff in your code base.
- seeekr 4y ago
  I was expecting a horrible mess when I clicked through to TFA, after having read comments like yours, but then... I actually enjoyed what I found there. Maybe it's because I'm quite interested in C++'s ongoing modernization story, even though it's unlikely to ever catch up to Rust (and others) in terms of safety?
jeffbee 4y ago
Recursion is one of those things that for some reason they continue to teach kids in college, which has no utility in practice. Things like recursion and linked lists should be erased from the curricula. There probably is a language and an application where recursion makes sense but C++ isn't one of those languages. Certainly a factorial is a horrible example because iterative is strictly better.
- deleted 4y ago
  [deleted]
- CoastalCoder 4y ago
  I'm guessing that recursion isn't used much in whatever work you do, but it's very helpful for things like parsers, compiler passes, etc. Basically anything that has to walk to tree or directed graph, and where you need to build up context based on the traversal path from the starting point to the node you're currently handling. Obviously in a non-functional language, you can do these things without recursion by using your own stack rather than the runtime function-call stack. But sometimes it's nice to have the stack provided for you. That also plays well with C++ runtime exception propagation.
  - mxz3000 4y ago
    In production code, you'd generally avoid recursion to avoid stack overflows. Given in most languages you can't enforce tail call optimisation, it's risky to use unbounded recursion.
    - CoastalCoder 4y ago
      I suspect this guideline varies a lot by industry or by target hardware. The last time I worked on a project with that rule was about 23 years ago, and that was on a 32-bit system.
- nextaccountic 4y ago
  I actually +1 on linked lists since it's very cache unfriendly and is actually very niche, but recursion is very solid, specially if your language has tail call elimination
mgaunard 4y ago
I find it interesting that other commenters are finding those trivialities convoluted and unreadable while at the same time constantly championing languages which are genuinely complicated.
- viktorcode 4y ago
  There are complex languages and there are readable languages. One language can be both at the same time, like Swift. The syntax examples here is what makes C++ hard to read: scores of special symbols hiding rather simple underlying mechanism.
- spoiler 4y ago
  I think the main issue is the quantity and density of complexity in the language (which is just a side effects of its long existence). A lot of it is hidden, or implicit; probably why people call them footguns, too. I used to write C++ for a few years, and the mental burden is real, you just stop noticing it. Having come back to C++ for an old project a few months ago, and writing it felt like a chore. Maybe I just never liked it without realising, and it's only just surfaced, though!
  - mgaunard 4y ago
    C++ lambdas behave exactly like functions in any other functional language. In OCaml, for example, you can't do recursion for the same reason without the special "let rec" construct.
  - hot_gril 4y ago
    I think the flaw with C++ is that it's too low-level for high-level applications, and it's too complex for performance-sensitive applications. I don't know what it's really good for. It feels far easier to use either extreme of C or Python/JS depending on the job. C++ seemingly grew to fill the high-level space that others have already filled better by now.
    - sakras 4y ago
      For what it’s worth, I treat C++ as C with a basket of goodies that you can use if it makes your code better (at least in the context of performance-sensitive stuff). Things like templates and classes can help if you don’t overuse them. STL is nice for rapid prototyping and writing tests. But I agree with you it’s often the case where people go overboard with the abstraction and cause an incoherent, slow, buggy mess
throwaway72937 4y ago
Is there a book like “C++ for C++ programmers” for people that knew C++ 20 years ago but didn’t keep up with the latest features?
- laurowyn 4y ago
  Modern Effective C++ by Scott Meyers is my go to for people in this situation. I'm not sure if there's an even more recent edition that covers C++17 and C++20, but C++11/14 is definitely a great head start over C++03 and earlier.
  - 6equj5 4y ago
    I can second Effective Modern C++: https://www.oreilly.com/library/view/effective-modern-c/9781491908419/ https://www.oreilly.com/library/view/effective-modern-c/9781... The most amazing thing about it is how it manages to be so entertaining to read (the last thing I expected from a C++ textbook and a thing that made getting through it way easier)! >I'm not sure if there's an even more recent edition that covers C++17 and C++20 Sadly, there is not. Scott for-the-most-part retired in 2015: https://scottmeyers.blogspot.com/2015/12/good-to-go.html https://scottmeyers.blogspot.com/2015/12/good-to-go.html
- gardn_water 4y ago
  Please let us know too, I been searching one for myself
- einpoklum 4y ago
  There are lots of good CppCon sessions you could watch. Unfortunately, they're not in the form of a comprehensive book. Maybe you should try Bjarne Stroupstrup's "Tour of C++": https://www.stroustrup.com/tour2.html https://www.stroustrup.com/tour2.html which might fit the bill. It doesn't go very far in depth, though. 240 pages.
- Willox 4y ago
  My go-to for this is "A Tour of C++". It's pretty short and only really covers up to C++17 with a few mentions of C++20.
dig1 4y ago
Instead of using "this auto&&" trick to get recursive lambdas, I wonder why they didn't go with named lambdas (Clojure made it really nice). E.g. auto factorial23 = [] fact_recur (int n) { if (n <= 1) return 1; return n * fact_recur(n - 1); }; Maybe this has to do with the usual C++ complicated parsing rules... But, on the other hand, named lambdas, besides recursion, in the language mentioned above helps with stacktraces, so you get the idea where the issue could be, instead of getting an anonymous mangled name mess.
- gpderetta 4y ago
  Honestly approximately nobody cares about recursive lambdas in c++, it is mostly a party trick. The this auto syntax is just a side effect of the new 'explicit this' syntax that affects all member functions.
- einpoklum 4y ago
  Because `this auto&&` was not introduced to allow for recursive lambads. That's just a happy (though not very interesting) side effect. It was introduced so that you don't have to write duplicated code such as: class Awesome { // ... foo& my_method() { /* ... */ } const foo& my_method() const { /* ... */ } }; and the extra duplication for lvalues and rvalues.

67 points by joebaf 4y ago

People say things like, "haskell is hard to reason about because of lazy evaluation" but then this. Also many sets of people are disjoint.

dleslie 4y ago

Oof, just a whole lot of oof. So much developer thought and mental energy expended to do something as simple as recursion.

klyrs 4y ago
To be fair, most of the examples (and all of the ugly ones, IMO) are warts in today's C++ standard that are being greatly improved in C++23. That said, unless I use it frequently (spoiler: I won't), "this auto&& self" is gonna look weird and I really hope that searching the web for "this auto self" will produce useful hits by the time C++23 is in common use.
- amluto 4y ago
  I find it quite bizarre that ‘this’ ends up with two names in this construct.
  - lionkor 4y ago
    It really is bizarre, and this is the first time i've seen "deducing this" used. However, I get the naming so far: `this` can be captured, like [this](int x) { return x + this->x; } which we can use, in thise case, to discern between the local x, and this's x. Super contrived, but it illustrates that "this" may be there, too. Then, if you want to capture the lambda, and `this`. Then you need a new name, you can name it `self`, you can name it `this_lambda`, you can name it `ben` - but not `this` since it's reserved and can actually be used in that scope.
stinos 4y ago
Recursion is just one of the things being used as a means to explain/show lambdas here, i.e. the energy spent is for the explanation, not for recursion.
einpoklum 4y ago
Recursion in C++ is quite simple: int factorial (int n) { return (n > 1) ? n * factorial(n - 1) : 1; } it gets more complicated for more esoteric use cases: * Recursion in an anonymous function. Are you sure this is so simple in other languages? * Compile-time recursion with anonymous functions. Which other languages even have this to begin with? Both of these cases are rarely used in practice. The C++23 addition which facilitates them is actually due to another issue entirely, which is avoiding code duplication when you want to specialize methods according to features of the object they're running for (const/non-const, lvalue/rvalue). See: https://devblogs.microsoft.com/cppblog/cpp23-deducing-this/ https://devblogs.microsoft.com/cppblog/cpp23-deducing-this/
- SnowHill9902 4y ago
  Can the compiler statically prove that it’ll not cause stack overflow? Otherwise recursion seems quite unsafe.
  - jeffbee 4y ago
    A theoretical compiler could statically prove that this program would have undefined behavior for any argument larger than 12, because signed overflow is UB, and it could arrive at the worst-case stack size from that.
  - einpoklum 4y ago
    Naturally (if we remember our Turing machine computational capability analysis), the compiler cannot generally prove things about recursive functions, including how deep the recursion will go. What it can do in practice is use (configurable) hard limits on the depth and on the amount of time for evaluating constexpr expressions. That way it doesn't overflow its own stack/buffers, nor will it hang on such evaluations. This is good enough, since the purpose of this feature is not perform heavy computations using the compiler, but rather preventing not-so-heavy computations from being performed repeatedly at run-time (and to be able to use their results in template instantiation etc.)
- dleslie 4y ago
  It's a named lambda, using self capture, and that's been in other languages for decades. Scheme is a good example, with letrec. Compile time recursive functions are likewise available in common lisp via recursive macros. Some schemes have them, too. And the syntax is much more elegant.

cjfd 4y ago

I think they should stop adding new major feature to C++. It is big enough. One can do enough with it. O, you cannot call a lambda recursively? Then just tell people to write a normal named function instead of polluting the language further with unneeded stuff.

einpoklum 4y ago
Many features are added to C++ not in order to "cover more", but to be able to do things better, or often - to allow making things _easier_ for the lay programmer (which is not the same thing as making things easier for library authors).

josephcsible 4y ago

The examples with `fact_impl` are basically how you'd write recursion in terms of a fixed-point combinator (e.g., the very Y combinator that this site is named after).

goldenkey 4y ago
It took me a while to grok the y-combinator, but I eventually realized it's just a generic factory, as a trampoline, that ceases to return a function invocation, just the last value, when it reaches the fixed point -- so it can actually reach a stopping point and not cause infinite recursion, without needing a self-reference.
deleted 4y ago
[deleted]

krater23 4y ago

This examples are reading all like 'How to use the newest C++ features to write unreadable code'.

imron 4y ago
Right. This is the sort of thing that’s interesting to know from an intellectual perspective to see how far can you bend and twist a language to do certain things, but you’re setting yourself up for a world of maintenance pain if you use this sort of stuff in your code base.
seeekr 4y ago
I was expecting a horrible mess when I clicked through to TFA, after having read comments like yours, but then... I actually enjoyed what I found there. Maybe it's because I'm quite interested in C++'s ongoing modernization story, even though it's unlikely to ever catch up to Rust (and others) in terms of safety?

jeffbee 4y ago

Recursion is one of those things that for some reason they continue to teach kids in college, which has no utility in practice. Things like recursion and linked lists should be erased from the curricula. There probably is a language and an application where recursion makes sense but C++ isn't one of those languages. Certainly a factorial is a horrible example because iterative is strictly better.

deleted 4y ago
[deleted]
CoastalCoder 4y ago
I'm guessing that recursion isn't used much in whatever work you do, but it's very helpful for things like parsers, compiler passes, etc. Basically anything that has to walk to tree or directed graph, and where you need to build up context based on the traversal path from the starting point to the node you're currently handling. Obviously in a non-functional language, you can do these things without recursion by using your own stack rather than the runtime function-call stack. But sometimes it's nice to have the stack provided for you. That also plays well with C++ runtime exception propagation.
- mxz3000 4y ago
  In production code, you'd generally avoid recursion to avoid stack overflows. Given in most languages you can't enforce tail call optimisation, it's risky to use unbounded recursion.
  - CoastalCoder 4y ago
    I suspect this guideline varies a lot by industry or by target hardware. The last time I worked on a project with that rule was about 23 years ago, and that was on a 32-bit system.
nextaccountic 4y ago
I actually +1 on linked lists since it's very cache unfriendly and is actually very niche, but recursion is very solid, specially if your language has tail call elimination

mgaunard 4y ago

I find it interesting that other commenters are finding those trivialities convoluted and unreadable while at the same time constantly championing languages which are genuinely complicated.

viktorcode 4y ago
There are complex languages and there are readable languages. One language can be both at the same time, like Swift. The syntax examples here is what makes C++ hard to read: scores of special symbols hiding rather simple underlying mechanism.
spoiler 4y ago
I think the main issue is the quantity and density of complexity in the language (which is just a side effects of its long existence). A lot of it is hidden, or implicit; probably why people call them footguns, too. I used to write C++ for a few years, and the mental burden is real, you just stop noticing it. Having come back to C++ for an old project a few months ago, and writing it felt like a chore. Maybe I just never liked it without realising, and it's only just surfaced, though!
- mgaunard 4y ago
  C++ lambdas behave exactly like functions in any other functional language. In OCaml, for example, you can't do recursion for the same reason without the special "let rec" construct.
- hot_gril 4y ago
  I think the flaw with C++ is that it's too low-level for high-level applications, and it's too complex for performance-sensitive applications. I don't know what it's really good for. It feels far easier to use either extreme of C or Python/JS depending on the job. C++ seemingly grew to fill the high-level space that others have already filled better by now.
  - sakras 4y ago
    For what it’s worth, I treat C++ as C with a basket of goodies that you can use if it makes your code better (at least in the context of performance-sensitive stuff). Things like templates and classes can help if you don’t overuse them. STL is nice for rapid prototyping and writing tests. But I agree with you it’s often the case where people go overboard with the abstraction and cause an incoherent, slow, buggy mess

throwaway72937 4y ago

Is there a book like “C++ for C++ programmers” for people that knew C++ 20 years ago but didn’t keep up with the latest features?

laurowyn 4y ago
Modern Effective C++ by Scott Meyers is my go to for people in this situation. I'm not sure if there's an even more recent edition that covers C++17 and C++20, but C++11/14 is definitely a great head start over C++03 and earlier.
- 6equj5 4y ago
  I can second Effective Modern C++: https://www.oreilly.com/library/view/effective-modern-c/9781491908419/ https://www.oreilly.com/library/view/effective-modern-c/9781... The most amazing thing about it is how it manages to be so entertaining to read (the last thing I expected from a C++ textbook and a thing that made getting through it way easier)! >I'm not sure if there's an even more recent edition that covers C++17 and C++20 Sadly, there is not. Scott for-the-most-part retired in 2015: https://scottmeyers.blogspot.com/2015/12/good-to-go.html https://scottmeyers.blogspot.com/2015/12/good-to-go.html
gardn_water 4y ago
Please let us know too, I been searching one for myself
einpoklum 4y ago
There are lots of good CppCon sessions you could watch. Unfortunately, they're not in the form of a comprehensive book. Maybe you should try Bjarne Stroupstrup's "Tour of C++": https://www.stroustrup.com/tour2.html https://www.stroustrup.com/tour2.html which might fit the bill. It doesn't go very far in depth, though. 240 pages.
Willox 4y ago
My go-to for this is "A Tour of C++". It's pretty short and only really covers up to C++17 with a few mentions of C++20.

dig1 4y ago

Instead of using "this auto&&" trick to get recursive lambdas, I wonder why they didn't go with named lambdas (Clojure made it really nice). E.g. auto factorial23 = [] fact_recur (int n) { if (n <= 1) return 1; return n * fact_recur(n - 1); }; Maybe this has to do with the usual C++ complicated parsing rules... But, on the other hand, named lambdas, besides recursion, in the language mentioned above helps with stacktraces, so you get the idea where the issue could be, instead of getting an anonymous mangled name mess.

gpderetta 4y ago
Honestly approximately nobody cares about recursive lambdas in c++, it is mostly a party trick. The this auto syntax is just a side effect of the new 'explicit this' syntax that affects all member functions.
einpoklum 4y ago
Because `this auto&&` was not introduced to allow for recursive lambads. That's just a happy (though not very interesting) side effect. It was introduced so that you don't have to write duplicated code such as: class Awesome { // ... foo& my_method() { /* ... */ } const foo& my_method() const { /* ... */ } }; and the extra duplication for lvalues and rvalues.