22 ms·
John Carmack: Functional programming in C++ (2012)
- amelius 12y agoHere is a personal anecdote. I recently tried to make a lambda function in C++ call itself. My first approach didn't work, because the variables were captured by reference, causing my program to crash (the enclosing scope had disappeared when my recursive lambda function was called). I easily tracked down that problem. But this generated a second problem: without using "capturing by reference", I couldn't make the lambda function refer to itself! Of course, I looked around on the internet, and I found [1], which actually shows the insane amount of hacking required to make a lambda function call itself. And in the end, this solution didn't even work for me. So, concluding, I think we're a long way from "functional programming in C++". [1] http://cpptruths.blogspot.nl/2013/10/creating-recursive-lambdas-and.html http://cpptruths.blogspot.nl/2013/10/creating-recursive-lamb...
- readerrrr 12y agoThe article talks mostly about purity, and that is easily achieved.
- tromp 12y agoYou can in fact define a fixed point combinator in good old C99, one that compiles without warning, and doesn't take all that much code. From http://www.ioccc.org/2014/whowon.html http://www.ioccc.org/2014/whowon.html Most functional Freek Wiedijk - Y combinator We'll have to patiently await publication of the source though...
- readerrrr 12y agoDo you have any code examples?
- amelius 12y agoThe Y combinator causes problems with typing (it has an infinite recursive type), so I'm curious what solution they came up with. In any case, if calling a lambda function from within itself is going to take more than a single line of straightforward code, then I'm afraid the solution still doesn't cut it for practical purposes.
- anaphor 12y agoThey could've done something similar to what you do when you implement a functional language in C and used a union to represent every possible return type, and included functions (closures if you will) in that union, then you solve the problem of the infinite type.
- jjaredsimpson 12y agowhy does this matter, what is the overwhelming use case for self referential anonymous functions.
- userbinator 12y agoso I'm curious what solution they came up with. I'm guessing a cast. The infinitely long type is not at all a problem in languages with weak type systems like C.
- pmelendez 12y ago>"which actually shows the insane amount of hacking required to make a lambda function call itself" I doesn't require any hack at all, it doesn't even require to capture the variable. You just need to be sure to make it persist and be accessible in the scope of the lambda. For example: http://ideone.com/6hwVGy http://ideone.com/6hwVGy That said, please don't do it in production code. std::function is very inefficient when it is being used in a recursive way
- TillE 12y agoWhy is it inefficient with recursion? I know that at least non-recursive usage of std::function is generally well-optimized by most compilers.
- pmelendez 12y agoWhen you wrap a lambda into a std::function variable, it involves a call to a virtual function which add overheads (often unnoticed unless you repeat the call several times), so a regular recursive functor would be even faster. The subject was discussed in the following threads: http://stackoverflow.com/questions/2067988/recursive-lambda-functions-in-c0x/14591727#14591727 http://stackoverflow.com/questions/2067988/recursive-lambda-... http://stackoverflow.com/questions/17066667/overhead-of-recursive-lambdas/17067042#17067042 http://stackoverflow.com/questions/17066667/overhead-of-recu...
- amelius 12y agoThe lambda function was an event handler, that needed to add itself to the event loop under certain conditions (retry). Its parent scope is not persistent.
- psykotic 12y agoYou can easily write a fixed-point combinator for this: https://gist.github.com/pervognsen/eca3bc833a65195f053c https://gist.github.com/pervognsen/eca3bc833a65195f053c. The way you tie the knot in C++ type recursion is not that different from in other languages like Haskell. In Haskell you wrap it in a newtype (http://stackoverflow.com/a/5885270 http://stackoverflow.com/a/5885270). In C++ you wrap it in a struct.
- nly 12y agoWhy does a rather trivial construct like this require an arcane label like 'fixed-point combinator'? In any case, this is cheating. What you effectively have here is a pair of mutually recursive functions, Recursive<>::op() calls anonymous_lambda_type::op(), which calls Recursive<>::op() again, and so on. I checked Wikipedia without even knowing 'mutual recursion' was an official mathy thing, it just sounded right, and I'm pretty sure this label is sufficient to describe the idea. If only even more advanced functional concepts were demonstrated without all the unnecessary pomp and ceremony common to Haskell and other functional advocates then I'm sure we'd all benefit. I'm constantly reminded when I see examples like this of Bodil Stokkes presentation 'What Every Hipster Should Know About Functional Programming' http://vimeo.com/68331937 http://vimeo.com/68331937
- psykotic 12y ago> Why does a rather trivial construct like this require an arcane label like 'fixed-point combinator'? Because that's what it is. I'm trying to communicate to people who know basic ideas from computer science. This is the last place I would expect someone to call the Y combinator too highbrow. > In any case, this is cheating. You're not making any sense.
- yzzxy 12y ago> Why does a rather trivial construct like this require an arcane label like 'fixed-point combinator'? On a site named after fixed-point recursion, no less.
- nly 12y agoHaving a lambda call itself seems like self-serving functional wankery to me. Lambdas in C++ are nothing but unnamed classes with an () operator. They're blobs of captured values (or references), made immutable by default, that happen to have a function associated with them. If you want to recurse, give the damn thing a name, or rewrite the body in an iterative form.
- deleted 12y ago[deleted]
- userbinator 12y agounnamed classes with an () operator They do have a name, but unfortunately it's just a compiler-generated one that's not known beforehand. And you would think that because the body of the lambda is really inside an operator(), 'this' could naturally be used to refer to the lambda itself, but alas, it doesn't work: http://stackoverflow.com/questions/14531993/can-lambda-functions-be-recursive http://stackoverflow.com/questions/14531993/can-lambda-funct... This is one thing about lambdas that I think the standards folks messed up. Having a lambda call itself might not be such a compelling use case, but it comes from the more general fact that a lambda cannot refer to itself, even though there isn't any reason preventing it from doing so; e.g. being able to pass itself ('this') as a parameter to some other function can be very useful.
- mjevans 12y agoYou're asking for a persistent first class function; write it like one.
- pfultz2 12y agoI don't know about that link, but in general you would use a fix point combinator. The Fit library has a fix point combinator here: http://pfultz2.github.io/Fit/doc/html/fix/ http://pfultz2.github.io/Fit/doc/html/fix/ So you could implement a generic factorial like this: auto factorial = fit::fix([](auto self, auto x) -> decltype(x) { return x == 0 ? 1 : x * self(x-1); });
- deng 12y agoPrevious discussion: https://news.ycombinator.com/item?id=3896404 https://news.ycombinator.com/item?id=3896404
- walrus 12y agoSlightly off-topic: Does anyone know what happened to AltDevBlog? It's been gone for 2.5 months now.
- readerrrr 12y agoYou can find it on archive.org. http://web.archive.org/web/20140719095843/http://www.altdev.co/author/john-carmack/ http://web.archive.org/web/20140719095843/http://www.altdev....
- walrus 12y agoI'm aware. I'm just curious what happened to it and if it's coming back.
- walrus 12y agoI dug into it a bit, and based on what I found on Twitter, the site crashed hard and the owner hasn't gotten to recovering the data yet. (He mentioned possibly having to pull it from Archive.org.)
- rdc12 12y agoHope it does come back was some golden posts there.
- Arjuna 12y agoIn case you missed it, John discussed his functional programming adventures in Haskell at QuakeCon 2013... well worth a listen. "So what I set out to do was take the original Wolfenstein 3D, and re-implement it in Haskell." [...] "I've got a few conclusions coming from it. One of them is that, there's still the question about static vs dynamic. I know that there was a survey just coming out recently where the majority of programmers are still really not behind static typing. I know that there's the two orthogonal axes about whether types are strong or weak, and whether it's static or dynamic. I come down really pretty firmly, all my experience continues to push me towards this way, that strong, static typing has really significant benefits. Sometimes it's not comfortable, sometimes you have to build up a tight scaffolding to do something that should be really easy, but there are real, strong wins to it." https://www.youtube.com/watch?v=Uooh0Y9fC_M#t=4876 https://www.youtube.com/watch?v=Uooh0Y9fC_M#t=4876 (Starts at approximately 1:21:16 in case the direct link doesn't work correctly.)
- vog 12y agoAt at beginning he says that he is kind of sold on most Haskell, but doesn't know if lazy evaluation is so great. I wonder why he didn't try OCaml then. He doesn't even mention this possibility, he just goes on to compare Haskell to Lisp. Regarding issues with lazy evaluation, there may be some truth to it. This reminds of a great article by Robert Harper: https://existentialtype.wordpress.com/2012/08/26/yet-another-reason-not-to-be-lazy-or-imperative/ https://existentialtype.wordpress.com/2012/08/26/yet-another...
- nickbauman 12y agoI used to think that way too. I've met programmers who still don't write unit tests and are not test driven and remain brilliant. Carmack is one of these guys. I think the static / strong typing thing works well with them because they never developed the practices. If you're test-driven, you're basically building up your own, domain specific compiler as you go not having to play by a language-specific static type systems rules. Dynamic typing make writing code this way really easy. Static typing doesn't. In the end I want the types of my system to work they way my system needs to. I could care less about the type system of merely a language (as applied to my system). And types are just one way to enforce correctness. Lately I find with languages in the Lisp family, these other types of tools feel much more productive, easier to reason about and flexible to me than type systems. When I believed in static typing I felt very busy, but I was mostly spending my time making the compiler happy, rather than the other way around.
- huodon 12y agoYou can take a horse to the water but you cannot make him drink. (强扭的瓜不甜).
- vog 12y agoIs there any trascript of that speech? Or shownotes? Or at least a link list?
- pjmlp 12y agoC++14 can be a nice functional programming language, coupling algorithms, lambdas, automatic memory management and secure data structures like std::vector and std::string instead of bare bones C like data types. It is even possible to do pattern matching, http://www.stroustrup.com/OpenPatternMatching.pdf http://www.stroustrup.com/OpenPatternMatching.pdf https://www.youtube.com/watch?v=OkDS6hmU-w8&list=PLoswmertKw4d_lDpZGLXz8nXCIa4NuHyy https://www.youtube.com/watch?v=OkDS6hmU-w8&list=PLoswmertKw... So it can be a nice language when we have control over the codebase. However, the biggest problem is being able to do so in the industry at large. I am willing to bet that most C++ code in the wild is done in a pre-C++98 style, with developers unaware of what came afterwards. Specially bad in those companies where getting any software upgraded is a pain of bureaucracy.
- vog 12y agoIt would be interesting to hear what John Carmack has to say about functional reactive programming, as that is meant to have it strengths especially in game programming.
- codygman 12y agoIt probably hasn't been proven enough for him to deem worth of his time. I don't say that condescendingly, but he seems to have a pretty pragmatic approach to trying out new stuff. Unsurprising, given how busy he inevitably is.