Functional Programming in C++(altdevblogaday.com)
altdevblogaday.com
Functional Programming in C++
http://www.altdevblogaday.com/2012/04/26/functional-programming-in-c/
10 comments
"hold in your head" == minimizing complexity by minimizing the state space. "Mathematical" == stateless, pure functions.
If the states are fewer, the code is simpler. I can only hold simple things in my head :)
I think everyone's basically saying the same thing.
If the states are fewer, the code is simpler. I can only hold simple things in my head :)
I think everyone's basically saying the same thing.
Functional programming is not "minimizing" state. The point is that it makes state "explicit". The minimization is done by the programmer because she is lazy and longs for conciseness.
Maybe you write FP code differently to me, but I'm constantly trying to minimize the complexity of the code, so that it only contains the essential complexity.
I gave a talk on how FP approaches force you to minimize accidental complexity recently, capturing this view, http://code.haskell.org/~dons/talks/padl-keynote-2012-01-24....
I gave a talk on how FP approaches force you to minimize accidental complexity recently, capturing this view, http://code.haskell.org/~dons/talks/padl-keynote-2012-01-24....
Functional programming has a lot of state minimization in it, at least in the stronger forms. A function in Haskell of Int -> Int can only be affected by the input Int. A function in C of int function(int) can be affected by arbitrary state from throughout the system; it may decrement or increment depending on global variables. It may write files. It may open connections to remote servers and read stuff off the internet. It has a vastly huger potential state space in theory and often vastly huger state spaces in practice.
I go into this more explicitly in http://www.jerf.org/iri/post/2908 .
I go into this more explicitly in http://www.jerf.org/iri/post/2908 .
>> The minimization is done by the programmer because
>> she is lazy and longs for conciseness.
http://www.folklore.org/StoryView.py?project=Macintosh&s... "He thought his goal was to write as small and fast a program as possible, and that the lines of code metric only encouraged writing sloppy, bloated, broken code.'
http://c2.com/cgi/wiki?LinesOfCode "Measuring software productivity by lines of code is like measuring progress on an airplane by how much it weighs."- Bill Gates
A good programmer is a lazy programmer.
I find this statement outrageously offending. Why do you assume the programmer is a "she"? It might as well be a "he". Or it might as well not want to be associated with any gender (consider a transexual, asexual, or an alien from Mars).
I think s/h/it is the correct pronoun to use to cover all those cases.
(yes, it's /s. When I see "she" used to imply the author is oh, so progressive and non-sexist, I resort to sarcasm).
I think s/h/it is the correct pronoun to use to cover all those cases.
(yes, it's /s. When I see "she" used to imply the author is oh, so progressive and non-sexist, I resort to sarcasm).
To me, "easier to hold in your head" is "easier to reason about". I can also imagine someone describing functional style (the thing Carmack says makes state presented to your code explicit) as "more mathematical".
I wasn't saying that the example arguments I gave were necessarily invalid, only that they are remarkably uncompelling. Is functional style the only way to achieve concise code? Is "mathematical" code really the standard to which we ought to aspire? These questions, among others, are left unanswered.
Essentially, a bad argument for functional programming says, "here is what functional programming does well; here is why that helps you". A good argument for functional programming says, "here is a very real problem that you have encountered; here is the remarkably effective way in which functional programming addresses it". Note the inversion, especially the focus on solving problems rather than on justifying paradigms.
Essentially, a bad argument for functional programming says, "here is what functional programming does well; here is why that helps you". A good argument for functional programming says, "here is a very real problem that you have encountered; here is the remarkably effective way in which functional programming addresses it". Note the inversion, especially the focus on solving problems rather than on justifying paradigms.
Why do people still associate FP with Lisp even though HN is supposed to be a lisper hangout :P
I was under the impression that Lisp makes it easier to write functional code?
Your impression is right. And nuje's question is also right. The goal of Lisp is to make it easier to write all kinds of code, including functional.
Common Lisp is a a lot like other dynamic languages in that department. Some lispy languages have more FP
support (eg. Scheme says implementations must perform
tail call optimization so you can recurse without blowing your stack, which is useful when doing FP).
Thanks to lambdas in C++11, coupled with STL algorithms, there are a lot of possibilities to do functional programming in modern C++.
One just has to take care to minimize mutability, as Carmack wrote on his blog entry.
One just has to take care to minimize mutability, as Carmack wrote on his blog entry.
I wish the lamba stuff would finally land in Xcode. I think of all the features in C++11 that's going to change the way I write C++ code the most.
[deleted]
I thought c++11's lambda's would be great until I tried to pass one into std::transform.
One of his comments kind of stuck out when I read it.
... but many object[s] are large enough to constitute a sort of global state all their own, blunting some of the clarity benefits of pure functions.
I think we've all run into (and probably coded) our fair share of objects that were basically this - there is only one of them, and it has a lot of state associated with it. I never thought of it before as basically just encapsulating global state into an object. It almost seems... unavoidable, or at least really hard to avoid.
Also this was hilarious.
As an extreme example, you can write a pure DrawTriangle() function that takes a framebuffer as a parameter and returns a completely new framebuffer with the triangle drawn into it as a result. Don’t do that.
... but many object[s] are large enough to constitute a sort of global state all their own, blunting some of the clarity benefits of pure functions.
I think we've all run into (and probably coded) our fair share of objects that were basically this - there is only one of them, and it has a lot of state associated with it. I never thought of it before as basically just encapsulating global state into an object. It almost seems... unavoidable, or at least really hard to avoid.
Also this was hilarious.
As an extreme example, you can write a pure DrawTriangle() function that takes a framebuffer as a parameter and returns a completely new framebuffer with the triangle drawn into it as a result. Don’t do that.
This is probably the best summary of functional programming, written by the best "pragmatical" programmer of the world. I wonder how much Haskell code Carmack must have written to reach this kind of knowledge... and whether it is open source. It would be a good read for the weekends.
BTW, I think the pure keyword in C++ would be great. I wrote some C++ in school, and even I can tell that const, as applied to functions, could use some retirement. It's nonsense to keep this unmodified, stateless so to speak, but allow global variable assignation, and so on.
BTW, I think the pure keyword in C++ would be great. I wrote some C++ in school, and even I can tell that const, as applied to functions, could use some retirement. It's nonsense to keep this unmodified, stateless so to speak, but allow global variable assignation, and so on.
Not entirely nonsense—immutability is helpful even in the absence of referential transparency—but still, a “pure” keyword would be great. Now, what I’d really like is for the type system to be flipped on its head with respect to immutability: make “const” the default and explicitly qualify mutable types with “mutable”. A guy can dream…
Perhaps you should take a look at Rust.[1] It's a pretty compelling union of functional and procedural paradigms, plus: immutability by default, the ability to annotate functions as pure, pattern matching, option types, good C compatibility, strong support for concurrency, high-level memory management that guarantees memory safety and that doesn't require tedious memory micromanagement (while retaining the option to just GC everything and forget about it), and a lot more. Still alpha software at the moment, though.
[1] http://www.rust-lang.org/
[1] http://www.rust-lang.org/
I’ve looked into it. Seems like a promising language, and it does quite a few things right. Still, I feel a bit uncomfortable endorsing it wholesale while I work on my own linguistic magnum opus. ;)
yeah, i'm excited about rust. i'm currently diving into d, and while it is a lot nicer than c++ (and i've barely started discovering all its features), i really miss pattern matching, option types and everything-is-an-expression, which i've gotten used to from other languages. it looks like rust supports all three of those features, which already puts it closer to my sweet spot.
GCC has a 'pure' attribute. I don't know if it's only used for optimization, but it also serves as a kind of comment for whoever looks at the function in the future.
"pure" and "const" are GCC function attributes which are supposed to help the optimizer. Confusingly enough "const" demands a higher level of purity than "pure"..
I would never use those attributes except - maybe - in the most critical loops and then only with a big "WARNING!!!" sign. Why? GCC does not / cannot enforce the guarantees given by "const" and "pure" yet the optimizer always assumes they are true. I.e. accidentally reduce the purity of a function decorated in this way.. and you might create very hard to find bugs.
This is a general problem in C and C++, those languages simply weren't designed to enforce such contracts. C99's "restrict" has the same problem.
I would never use those attributes except - maybe - in the most critical loops and then only with a big "WARNING!!!" sign. Why? GCC does not / cannot enforce the guarantees given by "const" and "pure" yet the optimizer always assumes they are true. I.e. accidentally reduce the purity of a function decorated in this way.. and you might create very hard to find bugs.
This is a general problem in C and C++, those languages simply weren't designed to enforce such contracts. C99's "restrict" has the same problem.
Since when is "const" a GCC function attribute?
http://gcc.gnu.org/onlinedocs/gcc/Function-Attributes.html
This is, of course, in addition to its other meanings in the language.
This is, of course, in addition to its other meanings in the language.
const has legacy reasons for its behavior, some of them relating to DMA and embedded environments.
I really liked this point:
"Most developers are not very good at predicting the future time integrated suffering their changes will result in."
So given a graph with time on the x axis and maintenance effort on the y axis, the area under the curve is the amount of suffering caused. That's a pretty good take-away.
"Most developers are not very good at predicting the future time integrated suffering their changes will result in."
So given a graph with time on the x axis and maintenance effort on the y axis, the area under the curve is the amount of suffering caused. That's a pretty good take-away.
I would argue for a discounting rate similar to the one economists use.
This is true at all levels.
Acute damage gains much more attention than diffuse damage. Thus you have a common problem of developers taking "shortcuts" and accruing huge amounts of long-term technical debt in exchange for temporary short-term advantages, and you have the equally common problem of internal tooling that just barely gets the job done but also introduces massive amounts of waste of time and effort across the entire institution.
Acute damage gains much more attention than diffuse damage. Thus you have a common problem of developers taking "shortcuts" and accruing huge amounts of long-term technical debt in exchange for temporary short-term advantages, and you have the equally common problem of internal tooling that just barely gets the job done but also introduces massive amounts of waste of time and effort across the entire institution.
For anyone wondering about adapting real world
problems to FP style, here's an article about someone
reimplementing pacman in FP: http://prog21.dadgum.com/23.html
I love the comment on here:
"I do believe that there is real value in pursuing functional programming, but it would be irresponsible to exhort everyone to abandon their C++ compilers and start coding in Lisp, Haskell, or, to be blunt, any other fringe language. To the eternal chagrin of language designers, there are plenty of externalities that can overwhelm the benefits of a language, and game development has more than most fields."
"I do believe that there is real value in pursuing functional programming, but it would be irresponsible to exhort everyone to abandon their C++ compilers and start coding in Lisp, Haskell, or, to be blunt, any other fringe language. To the eternal chagrin of language designers, there are plenty of externalities that can overwhelm the benefits of a language, and game development has more than most fields."
I disagree. Of course not _everybody_ can abandon C++ but some really can. I have developed C and C++ software for many years but with Racket Scheme (a functional language) I am MUCH more productive now. This works because I think and code functionally which is a totally different approach to the way how coding in C++ is done.
I doubt that functional programming in C++ will be as elegant and effective as in a real functional language where everything is functional. The approach of C++ seems to be and to support "everything". But will that support more maintainable code? I don't think so. Quo vadis, C++?
Btw Implementations like LuaJIT demonstrate that virtual machines have become amazingly fast. So, even for performance you don't need to be stuck to C++.
I doubt that functional programming in C++ will be as elegant and effective as in a real functional language where everything is functional. The approach of C++ seems to be and to support "everything". But will that support more maintainable code? I don't think so. Quo vadis, C++?
Btw Implementations like LuaJIT demonstrate that virtual machines have become amazingly fast. So, even for performance you don't need to be stuck to C++.
Great article, I love the way Carmack communicates.
Can someone please explain how much of these performance worries is mitigated by C++11 move semantics? To me it seems like the functional style is becoming a possibility when one doesn't have to worry about the penalty of copy operations.
Can someone please explain how much of these performance worries is mitigated by C++11 move semantics? To me it seems like the functional style is becoming a possibility when one doesn't have to worry about the penalty of copy operations.
Not that much unless you're very disciplined in how you writ your code. Anything with more than one reference to it won't be usefully moveable.
Funny he doesn't quote Tim Sweeney :)
http://lambda-the-ultimate.org/node/1277
http://lambda-the-ultimate.org/node/1277
This headline isn't very descriptive; more useful might be "John Carmack discusses the practical benefits (and limitations) of a functional programming style."
I like this a lot because it summarizes the direction my own C++ has taken since I first learned about FP. I've found that making a member method functional (i.e. changing usage of member variables into passed parameters where reasonable - I never use globals) makes it more reusable from an OO point of view. The biggest gains by far have been in multithreaded programming.
"My pragmatic summary: A large fraction of the flaws in software development are due to programmers not fully understanding all the possible states their code may execute in. In a multithreaded environment, the lack of understanding and the resulting problems are greatly amplified, almost to the point of panic if you are paying attention. Programming in a functional style makes the state presented to your code explicit, which makes it much easier to reason about, and, in a completely pure system, makes thread race conditions impossible."
Too often I've seen functional proponents, when asked why we ought to use functional languages, rely on facile arguments such as "it makes your code more concise, therefore easier to hold in your head" or "it makes your code more mathematical, and therefore easier to reason about". Like Rich Hickey, Carmack gets it right.