Curious C++ Lambda Examples: Recursion, constexpr, Containers C++23 included(cppstories.com)
cppstories.com
Curious C++ Lambda Examples: Recursion, constexpr, Containers C++23 included
https://www.cppstories.com/2020/07/lambdas5ex.html/
58 comments
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).
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]
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?
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.
I can second Effective Modern C++: 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
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
[deleted]
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
which might fit the bill. It doesn't go very far in depth, though. 240 pages.
https://www.stroustrup.com/tour2.html
which might fit the bill. It doesn't go very far in depth, though. 240 pages.
Isn't that what the linked website is for? https://www.cppstories.com/p/start-here/
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.
For C++0x I found the Wikipedia article on C++0x back in the day to be a good summary. That might still hold.
Wouldn't call recursive lambdas a feature, more like 4chan for C++ devs
Please let us know too, I been searching one for myself
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);
};
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.
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 { /* ... */ }
};
People say things like, "haskell is hard to reason about because of lazy evaluation" but then this.
Also many sets of people are disjoint.
Also many sets of people are disjoint.
Oof, just a whole lot of oof.
So much developer thought and mental energy expended to do something as simple as recursion.
So much developer thought and mental energy expended to do something as simple as recursion.
Recursion in C++ is quite simple:
* 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/
int factorial (int n) { return (n > 1) ? n * factorial(n - 1) : 1; }
* 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/
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.
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.
Can the compiler statically prove that it’ll not cause stack overflow? Otherwise recursion seems quite unsafe.
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.)
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.)
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.
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.
I find it quite bizarre that ‘this’ ends up with two names in this construct.
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` can be captured, like
[this](int x) { return x + this->x; }
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.
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.
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!
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!
C++ is a swiss army knife that can do everything, it's designed so that you don't need any specialized language at all.
If you do, you can just make an embedded domain specific language, since it supports that too.
If you do, you can just make an embedded domain specific language, since it supports that too.
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.
In OCaml, for example, you can't do recursion for the same reason without the special "let rec" construct.
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.
I worked on a C++ codebase that was essentially C with a few obvious domain classes and the addition of std::string and std::vector for convenience. I suspect that this is quite a common space, and it's immune to the march of the whizzy new features that are being added. Probably the only remotely modern bit of C++ that we could have benefited from is a salting of std::moves to remove some redundant copying, but this wasn't really worth the candle tbh.
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
Yeah, that discipline works when you're solo, but in a team each person will have their own ideas. Mine would be to avoid using classes, and someone else would OOP it up.
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.
The syntax examples here is what makes C++ hard to read: scores of special symbols hiding rather simple underlying mechanism.
This examples are reading all like 'How to use the newest C++ features to write unreadable code'.
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?
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.
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.
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.
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).
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.
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.
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.
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.
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.
Given in most languages you can't enforce tail call optimisation, it's risky to use unbounded recursion.
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.
The last time I worked on a project with that rule was about 23 years ago, and that was on a 32-bit system.
Very hard to relate to this perspective. Recursion is extremely useful. It definitely has practical utility, and even in many cases where one shouldn't use recursion in actual code (perhaps because it would risk blowing the stack), it's often much easier to first develop a recursive algorithm and then afterwards create an iterative implementation.
As for linked lists, obviously it's true that the cases where they should be used are much more limited than they used to be. But still, they're a very simple data structure that's easy to reason about and which software engineers are very likely to occasionally encounter in practice. I don't think there's much to be gained by eliminating them from students' education.
As for linked lists, obviously it's true that the cases where they should be used are much more limited than they used to be. But still, they're a very simple data structure that's easy to reason about and which software engineers are very likely to occasionally encounter in practice. I don't think there's much to be gained by eliminating them from students' education.
Recursion shines when you recurse into many different functions. Function A, B, C, etc. all being called multiple times from each other based on conditions in the data, never returning from the calls. VMs can be like that, also some regex implementations.
Recursion as a concept is useful. In practice, you can sometimes achieve better performance (or avoid exceeding some call stack limit) by doing it "iteratively" in a way that's still conceptually equivalent to recursion, i.e. with a stack you manually manage. I've never had a function call itself in C++, but I've done conceptually recursive things a lot in it.
Manually managing a stack is significantly more expensive compared to utilizing the call stack for recursion. Modern hardware and calling conventions are designed to make call stacks fast.
You should measure this!
You should measure this!
For my job involving C++, it doesn't matter which is faster. Just doing whatever is more readable, and since I'm usually doing a DFS/BFS func, it's nice being able to easily toggle that by popping from front vs back. When I'm not, I'd rather have a readable stack trace if something goes wrong and not have to deal with the oddities of recursive lambdas.
In Python, the issue is the easily reachable max recursion depth. Tail recursion isn't optimized.
In Erlang, you use recursion even just to iterate through a list. It's fine, the language is made for that.
In Python, the issue is the easily reachable max recursion depth. Tail recursion isn't optimized.
In Erlang, you use recursion even just to iterate through a list. It's fine, the language is made for that.
My comment was in response to your 'better performance' point.
I agree with your other points of course.
[deleted]
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
It does depend though, on how the linked list is implemented. If it is backed by an array for example ...
Not sure what sort of code for you write but recursion and linked lists are incredibly helpful.
Why a linked list?
The linked list is a peculiar data structure which makes a lot of sense in the 1970s because all memory reads cost the same and addresses are small, but is terrible in most cases in 2022 because we have huge addresses and very fast local cache. There still are good uses for the linked list, but they're now pretty esoteric.
Using the list concept with recursion is great, but fast implementations of languages in 2022 do not lean on the linked list. Java's ArrayList, and the terribly named C++ std::vector, are more appropriate structures for a lot of cases where a 1970s algorithms book says "list".
The linked list is a peculiar data structure which makes a lot of sense in the 1970s because all memory reads cost the same and addresses are small, but is terrible in most cases in 2022 because we have huge addresses and very fast local cache. There still are good uses for the linked list, but they're now pretty esoteric.
Using the list concept with recursion is great, but fast implementations of languages in 2022 do not lean on the linked list. Java's ArrayList, and the terribly named C++ std::vector, are more appropriate structures for a lot of cases where a 1970s algorithms book says "list".
Linked lists are probably most common in memory managers, and in embedded programming where memory is very tight, timing is critical, and the cache might be limited. Memory managers use intrusive linked lists to manage the free list; they need a data structure that doesn’t require malloc or new, can grow & shrink dynamically without relocating, and has constant time inserts & deletes from the middle of the list.
Linked lists aren’t very common in desktop application programming, if they ever were, and non-intrusive linked lists as container classes do seem particularly prone to having better alternatives, especially naïve implementations that allocate the list nodes and node content separately. One of the best reasons to reach for a linked list is to avoid all calls to new or malloc or free, so doubling up on them is especially silly.
I don’t think this is really a 70s thing though. Linked lists might have been used slightly more often in the past, but I think they’ve always been used far less than arrays, and my old algorithms books that predate std::vector just use arrays. Maybe the main utility of linked lists is to teach about pointers and algorithm complexity. They do make good examples of pointer management and of algorithms with different big-O than arrays, hashes, trees, etc. I maybe used linked lists a couple of times in games programming, but have rarely ever used them, while they were covered thoroughly in school.
Linked lists aren’t very common in desktop application programming, if they ever were, and non-intrusive linked lists as container classes do seem particularly prone to having better alternatives, especially naïve implementations that allocate the list nodes and node content separately. One of the best reasons to reach for a linked list is to avoid all calls to new or malloc or free, so doubling up on them is especially silly.
I don’t think this is really a 70s thing though. Linked lists might have been used slightly more often in the past, but I think they’ve always been used far less than arrays, and my old algorithms books that predate std::vector just use arrays. Maybe the main utility of linked lists is to teach about pointers and algorithm complexity. They do make good examples of pointer management and of algorithms with different big-O than arrays, hashes, trees, etc. I maybe used linked lists a couple of times in games programming, but have rarely ever used them, while they were covered thoroughly in school.
For a conventional malloc-type memory manager I can see this, you don't want to actually walk this list in most cases, you may be concurrent (in which case cache defeating is a feature) and so on.
In embedded my guess would be that you see linked lists because lots of embedded programmers are C programmers and that's what they learned to do, not because it's actually a good choice. I reckon if you look at C programs I wrote in the 1990s there are a lot of linked lists, and I can't defend any of those as the right solution.
In embedded my guess would be that you see linked lists because lots of embedded programmers are C programmers and that's what they learned to do, not because it's actually a good choice. I reckon if you look at C programs I wrote in the 1990s there are a lot of linked lists, and I can't defend any of those as the right solution.