John Carmack: Functional programming in C++ (2012)

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

by cpeterso • 12 years ago

143 89 12 years ago

amelius3• 12 years ago

Here 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-lamb...

readerrrr3• 12 years ago

The article talks mostly about purity, and that is easily achieved.

tromp• 12 years ago

You 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

   Most functional
   Freek Wiedijk - Y combinator

We'll have to patiently await publication of the source though...

readerrrr3• 12 years ago

Do you have any code examples?

amelius3• 12 years ago

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

pmelendez2• 12 years 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

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• 12 years ago

Why is it inefficient with recursion? I know that at least non-recursive usage of std::function is generally well-optimized by most compilers.

amelius3• 12 years ago

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

psykotic2• 12 years ago

You can easily write a fixed-point combinator for this: 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). In C++ you wrap it in a struct.

nly3• 12 years ago

Why 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

nly3• 12 years ago

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

userbinator2• 12 years ago

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

pfultz22• 12 years ago

I 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/

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• 12 years ago

Previous discussion:

https://news.ycombinator.com/item?id=3896404

walrus3• 12 years ago

Slightly off-topic: Does anyone know what happened to AltDevBlog? It's been gone for 2.5 months now.

readerrrr3• 12 years ago

You can find it on archive.org.

http://web.archive.org/web/20140719095843/http://www.altdev....

walrus3• 12 years ago

I'm aware. I'm just curious what happened to it and if it's coming back.

walrus3• 12 years ago

I 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• 12 years ago

Hope it does come back was some golden posts there.

Arjuna• 12 years ago

In 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

(Starts at approximately 1:21:16 in case the direct link doesn't work correctly.)

nickbauman10• 12 years ago

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

illumen• 12 years ago

Nicely put.

I'd also argue that the divide between dynamic, and static typing systems has fallen down. Almost completely.

Java/C# and even Haskell have dynamic typing. They even sort of have a scripting feel.

However, you can also statically type dynamic languages, and dynamic languages are getting static typing too. For example, JavaScript with asm.js. Lots of type inference is done by IDEs and lint systems now. Even with python, static type checking is very possible (both at the C level, and at the python level).

sbergot• 12 years ago

Except that to perform the level of checks that a compiler does with a good type system, you would have to write a large amount of tests. Code is a liability, and testing code is no exception.

Writing tests in static languages is still required. You just have to write a smaller amount of them. What's more, type checking is enforced in a more systematic way. With tests, you have to rely on people to write them. If a type system is well designed, people will use it to model their code, and the type checking is done automatically.

What's more, types should not be reduced to the type checking phase. Types are a way to provide a high level model/structure. You still need this if you are working in a medium/large project. With static types, this model have nicer semantics, and is more useful.

Dewie• 12 years ago

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.

And now you're busy writing tests instead?

lmm4• 12 years ago

I've had just the opposite experience. I used to write a lot of tests, but now I can usually encode my constraints in the type system, where I get a lot for free thanks to the structure - often I just need to compose a couple of existing things specialized to the right types. All the useful ways I've found to enforce correctness boil down to types in one guise or another.

When I was writing tests I felt busier because I spent more time typing; now I spend more time thinking and less time writing code, but I'm ultimately more productive.

codygman8• 12 years ago

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. I could care less about the type system of merely a language (as applied to my system).

These two sentences are contradictory. You are merely making up your own language-specific static type system rules instead of learning how to use the one already provided by static type systems.

I will agree that languages with less flexible type systems to get in the way, but languages like Haskell, Ocaml, and other ML do a lot of the work for you.

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.

Dynamic typing makes this easier for you to start writing code, not necessarily to get your end result faster. Dynamic typing allows you to build your own "type system of merely a language (as applied to your system)", and you can apply your lines of thought to it.

Static typing will require that you think about the types/type system of the language you are using and will inevitably slow you down at first. However it's not much different than the trade-off of using an existing library for a programming task or writing your own.

The marked difference is that I don't trust myself or many others to recreate a comprehensive type system rivalling that of mature compilers and people most likely much smarter than us.

The end result is that you have an ad-hoc type or effect system that isn't well defined, and the quality/correctness is assured through brute force by way of writing all the unit tests you can think of.

I assure you that you can't brute force test more edge conditions than your computer.

This post is getting long, but I feel like it really hits on why many "real world programmers" use Haskell and stronger static type systems: We don't trust ourselves, have been slapped in the face by our limitations and mistakes, so we would like to offload a ton of complexity to the compiler.

virtualwhys• 12 years ago

and for the whole picture vis-a-vis game dev:

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

We have cross-platform issues, proprietary tool chains, certification gates, licensed technologies, and stringent performance requirements on top of the issues with legacy codebases and workforce availability that everyone faces." [0]

Which may be why we haven't heard a peep from Carmack on the subject since. Could see pure FP languages entering performance critical domains like game development in the not too distant future, but for now the state of the art isn't quite there.

[0] http://gamasutra.com/view/news/169296/Indepth_Functional_pro...

m_mueller2• 12 years ago

I'm doing HPC work for a few years now and I'm familiar with FP concepts, use it (albeit never purely so far) in non performance critical code where maintainability and testability is more important. My question: How could it even work in performance critical domains? Most of the time memory bandwidth is the limiting factor, thus copying memory and cleaning up unused memory are very expensive. With pure FP, all I can do is hope the compiler won't create all the copies I'm instructing it to do and optimize it back to procedural in-place update. When that doesn't work all I can do is reimplement it procedurally. How does anyone think that this programming concept can be applied for high performance domains? What am I missing?

thesteamboat• 12 years ago

Another possible reason we haven't heard a peep from Carmack on the subject since is that he joined OculusVR and has a bunch of interesting hardware problems to work on.

vog3• 12 years ago

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

fulafel• 12 years ago

Notice that he stresses there are benefits, but nowhere does he say that the costs necessarily outweigh the benefits.

huodon• 12 years ago

You can take a horse to the water but you cannot make him drink. (强扭的瓜不甜).

pjmlp2• 12 years ago

C++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

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.

vog3• 12 years ago

Is there any trascript of that speech? Or shownotes? Or at least a link list?

vog3• 12 years ago

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

codygman8• 12 years ago

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

John Carmack: Functional programming in C++ (2012)

Related Stories