Functional programming in C++ (2012)(gamasutra.com)

Functional programming in C++ (2012)

http://www.gamasutra.com/view/news/169296/Indepth_Functional_programming_in_C.php

11 comments

This guy helped invent the FPS genre and all the technology it took to make it, back in the MSDOS days - which is pretty incredible if you knew what he had to work with in terms of CPU and memory back in those days. Like Dave Cutler, never a guy to toot his own horn much either. Well done John, thank you for all your contributions to the tech and the craft.

the_af8 anni fa

> This guy helped invent the FPS genre

I find it curious, but perhaps inevitable, that someone like John Carmack requires this introduction. If you played videogames in the 90s / early 00s or were at all interested in 3D programming, it was impossible not to have heard of him. He was (is?) probably one of the cleverest programmers of his time.

This article of his gets reposted time and time again to HN, which makes sense because it's very interesting. This is the first time I've noticed people not knowing who the author was.

I wonder if a few decades from now, tech-minded people will wonder who Linus Torvalds, Brian Kernighan or Dennis Ritchie were. I suppose they will!

_57jb8 anni fa

I don't think it's uncommon for people to learn from the top down and after some time and a bit if passion find themselves digging into the roots of it.

It came across as a tad condescending although I can easily believe it wasn't meant that way and you are just open mindedly sharing perspective as is the point of all this.

I reply not to just make that comment but actually to recommend a book (that many may have possibly already read) which gives a rich history well worth it.

https://www.amazon.com/Hackers-Computer-Revolution-Steven-Le...

They dive into East and West coast history as well as the influences of gaming which I think ties to this threads closest.

Its long, engaging, and the audiobook is just a kick.

If you are on that cusp of wanting to learn a bit more of where we come from with an Americana feel, they have done a fantastic job here.

52-6F-628 anni fa

> Brian Kernighan or Dennis Ritchie

I think we're already there in a lot of cases.

Personal disclaimer: I had no idea who John Carmack was until this post. :P

bryondowd8 anni fa

While I knew of Carmack and Torvalds, I only recently read a bit about Kernighan and Ritchie. And that was only because I got roped into doing some maintenance on a rather old system, programmed in C, which used a syntactic style that I hadn't encountered before. A bit of research on some of the structures I saw lead me to pre-ISO standardization of the C language, where the closest thing to a standard was a book written by those two, and the resulting pseudo-standard referred to as K&R C.

I bailed out of that project as soon as humanly possible, by the way. Not just because of the ancient language, but the entire organizational structure of both the codebase and the team itself.

AnIdiotOnTheNet8 anni fa

I too am getting some real "get off my lawn" feels from these comments.

yesbabyyes8 anni fa

The first blog I followed (before Slashdot) was Carmack's .plan

    % finger [email protected]

It's even the example in the finger(1) man page on Slackware. https://www.slackbook.org/html/basic-network-commands-finger...

satysin8 anni fa

Dave Cutler really flies under the radar but he is a god damn wizard and up there with some of the greatest programmers in history imho.

abvr8 anni fa

Wouldn't label him a GOAT as such as he merely created Windows NT. OTOH, Carmack is on a whole other level altogether, it is unfair to list both of them together.

kryptiskt8 anni fa

He did VMS too, and the hypervisor for Azure, and the hypervisor for XBox One.

"Soon after, and a few months before his 70th birthday, Cutler joined the team. He soon “set the bar for how hard people should work and how high they should hold the quality bar,” Multerer said. Two years later, on Nov. 22, 2013, Xbox One shipped in North America.

“Dave designed and wrote the hypervisor for Xbox One,” Multerer said, with an obvious sense of awe. “He wrote the entire bottom of the stack. Because the hypervisor is there, Xbox games can run on Windows. That’s why apps run on Xbox One. The impact of that work is phenomenal. And the amount of work he did was phenomenal.”"

https://news.microsoft.com/features/the-engineers-engineer-c...

retro648 anni fa

Thanks for posting this. For myself, as an aging coder who has zero plans of moving into management, I find his story inspiring.

satysin8 anni fa

I am not 100% but I believe he was also involved in the Xbox 360 on Xbox One emulator.

stingraycharles8 anni fa

Somehow I feel like this comment greatly undervalues the design and impact that Windows NT had.

mhh__8 anni fa

Even if it were only windows NT, that's quite the CV already

runevault8 anni fa

I've been reading the book about the Wolf3d engine lately to remind me how insane those days were. The way he made it all work is staggering. I wonder how different video games would be if Carmack never took up the mantle he did. Would someone else have filled in, and if so how many years later would it have been?

meheleventyone8 anni fa

For that time period Ultima Underworld was developed at the same time as Wolf3d and had a more feature packed if less performant renderer so not long is the answer. Then System Shock only came out a year or so later!

Carmack definitely deserves all the praise he gets but there were a lot of other people pushing the technical boundaries in all sorts of ways.

newnewpdro8 anni fa

I think it's easy to overstate the impact first-movers have on any given industry. The 3D FPS genre was already being explored in the 70s and it's a somewhat obvious direction to explore on the PC as the hardware becoming ubiquitous in American homes matured enough to make it possible.

Carmack is a smart guy but it's not like there wasn't going to be a competitive PC game industry in his absence. Ken Silverman or Tim Sweeney come to mind as alternative first-movers in the space, I don't think it would have been much later.

The games might have been less violent for a bit longer without id though.

redisman8 anni fa

> The games might have been less violent for a bit longer without id though.

Probably not. They were just channeling the culture which was a lot of heavy metal and horror/action movies. Personally for me in my early teens it was a nice outlet for feeling powerful in a game rather than bullying some kids at school or whatever.

AJ0078 anni fa

Releasing the source code for Wolfenstein, Doom, Quake, Quake 2, Quake 3 was very much a Carmack thing. Source code releases for extremely successful, closed, commercial projects remains very uncommon (though it is fair to point out that the current Unreal Engine code is published.)

mattsfrey8 anni fa

We'll never know is the real answer. How sooner would the modern lightbulb have been invented without Edison, the affordable automobile without Ford, etc. He put in the work and made it happen before anyone else, and that's damned important IMO.

[deleted]8 anni fa

kristianp8 anni fa

Looks like there's a 2nd edition of the book out [1] it's called, the Game Engine Black Book Wolfenstein 3D.

[1] http://fabiensanglard.net/gebbwolf3d/

popnroll8 anni fa

First time I hear about this guy. Interesting.

jchoca8 anni fa

If you haven't heard of John Carmack I highly recommend this book https://en.m.wikipedia.org/wiki/Masters_of_Doom

FPGAhacker8 anni fa

Quote > The factors that allow programs in functional languages to sometimes be more concise than imperative implementations are pretty much orthogonal to the use of pure functions — garbage collection, powerful built-in types, pattern matching, list comprehensions, function composition, various bits of syntactic sugar, etc. For the most part, these size reducers don't have much to do with being functional, and can also be found in some imperative languages.

—

Amen. I think people new to functional programming are thrown by this, and I think some long time adherents of functional programming have adopted these “factors” as part of the definition.

Definitions change, that’s fine, but the confusion of ideas isn’t good.

Anyway, are there functional data structures widely available to c++? I assume there are. Without them, functional programming has a heavy cost.

Clojure, for one, would not be very attractive without having adopted Bagwell’s data structure concepts.

fro01168 anni fa

The challenge then, as with essentially every language that doesn't use persistent data structures _as the default_, is having to recursively convert to and from those persistent data structures at the edges of your system where you need to interact with third party libraries that likely won't be consuming/producing those data structures natively.

Unfortunately this is where the value proposition of a non-standard data structure library usually breaks down for general usage. That recursive translation layer sitting at the edge of your system is generally enough to completely blow up your performance budget and many times leave you worse off than if you had just used the default mutable data structures and made naive shallow copies everywhere in the first place.

The best case study for this is JavaScript, which by now has a fairly substantial following of functional programmers, and has an excellent persistent data structures library in ImmutableJS, but the vast majority of functional codebases in JS just end up doing shallow-copy-on-write using the default mutable data structures regardless, because of the difficulty of taking proper advantage of the performance benefits of persistent data structures in an ecosystem that overwhelmingly deals in mutable data structures. That said, the fact that C++ is not a garbage collected language and the associated developer ergonomics costs of having to manually clean up your own shallow copies might skew the value proposition a bit, but given that if you're writing in C++ you're probably in it for the raw performance in the first place, it's unlikely to be enough to tip the scales.

derriz8 anni fa

The problem is that some of those features - function composition, stream/LINQ type APIs, list comprehensions, etc. - become very difficult to reason about/debug when used with side-effecting code.

Yes you get the conciseness but you can create some truly obfuscated behavior when used with non-functional code.

Don't get me wrong - I'm delighted to see such features available in more languages. But they don't all work nicely with the typical abstractions (e.g. objects holding state) available in non-functional languages.

Tarean8 anni fa

Immutable data structures become a lot harder without gc, though. To update an immutable structure you don't want to copy parts that haven't changed. But this requires sharing and without gc this requires refcounting. Which in turn makes accidental cycles leak memory so you have to deal with weakrefs and have to think about this and multithreading isn't as nice as it could be and...

nestorD8 anni fa

Regarding data structure there is the Immer library : https://sinusoid.es/immer/#contents

keymone8 anni fa

> Clojure, for one, would not be very attractive without having adopted Bagwell’s data structure concepts.

i don't think Clojure ever "adopted" Bagwell's data structures, it was designed around them and few other concepts.

pmarreck8 anni fa

The key points he makes:

"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.

"No matter what language you work in, programming in a functional style provides benefits. You should do it whenever it is convenient, and you should think hard about the decision when it isn't convenient."

lsh8 anni fa

Excellent read, I still remember a lot of it. There is also the accompanying Quakecon presentation where John Carmack talks at length about all this: https://www.youtube.com/watch?v=1PhArSujR_A

oever8 anni fa

Ivan Čukić wrote a book about this last year.

https://www.manning.com/books/functional-programming-in-c-pl...

The book is well written and it has useful techniques for if you want to do mostly functional programming and want to stick to C++.

mattsfrey8 anni fa

Wow, I never saw this. I independently migrated to functional programming once exposed many years back and definitely couldn't imagine doing software any other way at this point, awesome to see my childhood hero endorse it though none the less.

dadrian8 anni fa

I saw this when it was originally written back in 2012. This article is amazing, and had a larger impact on me than anything else I've ever read about software engineering.

waynecochran8 anni fa

One tiny baby step towards functional programming in C++ is to avoid assignment statements as much as possible and instead use const initialization:

     const type foo = value;

Assignment statements mutate state, whereas 'foo' above is an alias or cached value which can not mutate state. This is much like the ‘let’ keyword in Lisp or Swift. It is much easier for both the programmer and the compiler to reason about non-mutating expressions. Many compiler suites (e.g., LLVM) use static single assignment (SSA) for their intermediate form which opens the door for a lot of optimization. Anyway, it is a small thing and can act as a "canary in the mine" if you find you can not refactor your code into this form.

pmarreck8 anni fa

There are some corner-cases where immutable data still fails algorithmically... for example I do not know of a performant quicksort that is written in an immutable language (but please, someone correct me if I'm wrong!). It's so wrong, too, because the code for functional quicksort is so beautiful... here it is in Haskell

    quicksort [] = []
    quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
        where (lesser, greater) = partition (< p) xs

and here it is in Elixir

    defmodule QuickSort do
      def qsort([]), do: []
      def qsort([pivot | rest]) do
        { left, right } = Enum.partition(rest, fn(x) -> x < pivot end)
        qsort(left) ++ [pivot] ++ qsort(right)
      end
    end

Tarean8 anni fa

You can write the imperative quicksort in haskell and wrap the mutation so it can't escape.

This forces you to copy of the incoming array but optimizations can remove intermediate copies. This is similar to r-values in c++, for instance

    quicksort (fromList [10, 9..1])

would only do one allocation with optimizations.

    freeze . quicksortMutable . copy . new . New.unstream $ Bundle.fromList [10,9..1]
    new . modify quicksortMutable . New.unstream $ Bundle.enumFromStepN 10 (-1) 10

Also, what you posted is tree sort not quick sort.

pmarreck8 anni fa

Isn't quicksort a type of tree sort? (having just googled both, but not finding said statement)

jcelerier8 anni fa

The haskell quicksort is also wrong : https://stackoverflow.com/questions/7717691/why-is-the-minim...

Here's the correct version taken from one of the SO answers :

    import qualified Data.Vector.Generic as V 
    import qualified Data.Vector.Generic.Mutable as M 

    qsort :: (V.Vector v a, Ord a) => v a -> v a
    qsort = V.modify go where
    go xs | M.length xs < 2 = return ()
          | otherwise = do
            p <- M.read xs (M.length xs `div` 2)
            j <- M.unstablePartition (< p) xs
            let (l, pr) = M.splitAt j xs 
            k <- M.unstablePartition (== p) pr
            go l; go $ M.drop k pr

pmarreck8 anni fa

Well according to the reasoning here, no purely functional quicksort will ever be "true quicksort" due to the apparent requirement that the sort be done in-place (mutably). Haskell may have well-thought-out mechanisms in place to do mutation "purely" (which are quite admirable IMHO) but this won't be the case with something like Elixir (Erlang).

This code is also considerably more complex/less beautiful.

I don't know what to call non-in-place Quicksort, but it deserves a name; in the meantime I will simply put it in quotes.

It does seem possible to write an Elixir "quicksort" that does not consume gobs more space than "proper" quicksort, based on the comments there.

waynecochran8 anni fa

The following algorithm does not need any mutations:

    quicksort (list)
      if null(list) or else length(list) <= 1
         return list
      else
         p = findpivot(list)
         (lo, hi) = split(p, list)
         return concat(quicksort(lo), quicksort(hi))

I still call it quicksort.

waynecochran8 anni fa

I am not sure what you mean by "fails algorithmically," but I do know functional code that performs no (logical) mutations is often dependent on a really smart compiler to do "the right thing" (e.g. convert tail recursion to iteration, re-use memory, etc..).

A "functional" quick-sort in C++ that is also performant sounds like a hard challenge. In this case I am no purest -- I'll use a mutating version -- I suppose that is why Common Lisp provides a destructive version of sort.

If you do create a non-destructive quick sort, you get reentrancy for free so it is easily parallelizable. Writing concurrent routines using non-mutating code (as Carmack says) is much easier to get right.

usgroup8 anni fa

Out of interest:

Has anyone made anything non-trivial in an FP style in C++ ?

If so, what frameworks did you use? What would you recommend?

Have you tried easyLambda, or used it in production?

Also, is a dynamic data structure library you'd recommend for C++? Something that makes on the fly maps and things like that easy to implement?

rurban8 anni fa

He advises to use more copy by value, fine, but C++ is not the right language to do that. It is even by far the worst language to that.

Better functional languages do have the optimizations needed to work in such a style, such as a generational GC, safe stack allocation, an optimizing compiler (for that problem, not C++ problems) and a proper type system. Good functional languages outperform C++ with OpenMP in performance, readability, maintainability and safety. And they explicitly disallow all the problems which do come with C++.

charlysl8 anni fa

I am by no means an expert, but I find this article to be very superficial, and not very useful for people new to this in terms of learning the core concepts. For instance there is no mention of the Interpreter, Visitor and Composite GoF design patterns, which are crucial to doing functional programming in OO languages. If you are curious about this, it is very well explained in some of the lectures (10, 11, 13, 14, 15) of the OCW MIT course "Elements of Software Construction" 2008 version [1].

For a much more in depth and accurate discussion of the trade offs between functional and OO programming, I recommend the book "Concepts, Techniques, Models of Computer Programming". For instance, this book explains the technique of Impedance Matching to deal with programs where different components have different degrees of what the article's author (very losely) calls "purity".

[1] https://ocw.mit.edu/courses/electrical-engineering-and-compu...

jpz8 anni fa

DoF design patterns is Java bollocks IMO.

It's only Java developers and to a lesser extent C# developers that really go nuts for this stuff. Visitor is clearly a framework for expressing multimethods - thus one can say Visitor is merely a workaround for the constriction of expressiveness of a given language - which is a claim made about many of the GoF patterns.

Singletons as a pattern? How is that different to global variables? It isn't.

LgWoodenBadger8 anni fa

A singleton guarantees that one-and-only-one instance of that type/thing is instantiated.

One can create as many global variables of that type/thing as one wants. Whether one refers to the same, singular instance everywhere is not something a global variable guarantees.

One may use a global variable to implement a singleton, but they aren't the same at all.

charlysl8 anni fa

Design patterns are just a convention; I would be as uncomfortable overusing them as jumping on the current pattern bashing fad.

The Interpreter pattern is just a technique for doing what amounts to pattern matching but in an OO language, the Visitor is its dual, and Composite is handy to represent arbitrary arity trees.

They allow you to represent algebraic types in an OO language, and I guess that they are design patterns because they can be applied systematically in any domain without having to reinvent the wheel, given that designing with them is driven by the information's structure only, just like in regular FP languages.

Abusing them is just as bad as abusing any other design technique, but when applied correctly they greatly improve program structure and maintainability.

Visitors have nothing to do with multimethods. Their purpose, in this context, is to improve maintainability when in a given functional program written in an OO language you would be more likely to add new functions rather than data type variants; Interpreter would be preferable when the opposite is the case.

Do you know of better ways of systematically doing FP design in C++? The article doesn't mention any.

nurettin8 anni fa

The article isn't about design patterns, it is about using the new functional programming primitives which C++ relatively recently acquired through the standardization process.

Suggesting to use a syntax for lambda or currying or transferring closure parameters or making copies of data in order to avoid thread problems is not remotely within the same category as "visitor pattern".

charlysl8 anni fa

> it is about using the new functional programming primitives which C++ relatively recently acquired through the standardization process.

Sorry, I couldn't find any mention of such new primitives in the article. Which are they?

nurettin8 anni fa

I understand `constexprs`, returning deep copies, `[]()()`s, std::bind, simd and OMP when he talks about purity, lambdas, currying and parallelization. What do you understand?

charlysl8 anni fa

Thank you

lsh8 anni fa

> ... not very useful for people new to this in terms of learning the core concepts

> For a much more in depth and accurate discussion of the trade offs between functional and OO programming, I recommend the book

think of it as a short and in-depth exploration of functional programming practices by an imperative programming luminary.