Functional C++ talk by Kevlin Henney [video]

by adamnemecek • 11 years ago

49 4 11 years ago

krapht• 11 years ago

I watched the talk, not having a lot of exposure to functional programming, but having exposure to C++ through my job. I am still not sure I understand his presentation.

The beginning was straightforward and had some good takeaways. The message was, as he showed through some examples such as a date class, that if you can avoid mutating state, then do so. Prefer to construct immutable objects that support fast copying via move semantics. This way, you can preserve class invariants easily. This is something I agree with, and have started to try to do in my new code. I guess the other benefit is that you can avoid passing const ref& around, and just pass by value everywhere, and the compiler will optimize it for you via return value optimization and move semantics.

Kevlin spends the middle part of the presentation talking about how to implement an immutable list in C++ using the STL style. The main change seems to be he has added const modifiers to everything, pop_front/pop_back now return a new list minus one popped element, and he's added an internal shared_ptr to track references to the list, (I didn't quite follow why it was used - I'd probably have to rewatch the presentation). Then, at the end, he talks about asynchronous computation, and how functional programming is a better fit for concurrency because now you need no locks, since data is immutable, and lo, we have an immutable list. But I'm not sure how they go together to solve any of the typical problems I have with concurrency. Typically I want concurrency because I have a huge, compute intensive problem. With this list, suddenly, I have a huge explosion in memory requirements as each time the list is mutated, I have to store a new copy of the list. I guess I'd also then have to synchronize access to my new mutated list reference? I'd need a different algorithm. I feel like functional languages prefer recursive divide and conquer approaches.

So, in the end, I don't think I was the right audience for this talk, or I didn't have enough time to devote to understanding it. I watched the video and ended up more confused about functional C++. I did enjoy his last slide about the actor model. Being familiar with it, I agree that it is a good solution for certain types of concurrency. I see it as sort of a generalized solution to execution flows that can be pipelined.

pests• 11 years ago

I have just started watching the video but IIRC Facebook's Immutable.js library implements immutable lists and sets with some sort of tree data structure that allows non-mutated elements to be shared between copies. Maybe this does something similar?

dmeb• 11 years ago

Trees with a very high branching factor can be used to support immutable vectors which support effectively constant time insert/remove/indexed lookup. However, it's not necessary to use trees to implement immutable lists.

In scala:

  val xs = List(1, 2, 3) // i.e. 1 -> 2 -> 3 -> Nil
  val ys = 42 :: xs  // i.e. 42 -> xs

In this instance, ys is a reference to a "Cons" node consisting of the value 42 and a reference to the immutable list xs. As xs is immutable, there is no risk of ys.tail changing, so we don't have to copy xs but just make a reference to it. So creating the "new" list ys only incurs the O(1) memory required to create the new node (42,xs).

Now, if you instead did:

  val xs = List(1,2,3) // 1 -> 2 -> 3 -> Nil
  val zs = xs ++ List(42) // 1 -> 2 -> 3 -> 42 -> Nil

This would in fact trigger a copy of the entire list xs, as you are modifying the reference pointed to of the Cons node containing 3, requiring a copy of the entire xs so that your modification doesn't affect other references to the original xs.

Performance characteristics of different Scala collections: http://www.scala-lang.org/docu/files/collections-api/collect...

jfoutz• 11 years ago

Often, rather than changing the list you'll want some summary statistic about the list. total payroll or something like that. So that's trivial.

In other cases, you have a thread that depends on some other thread's result. Say a game engine with a list of positions. The render part needs to know the positions. rather than applying a transform to each element in place, apply the function as you traverse the list.

    for(Thing* p; p; p = p->next){
        render(transform(p));
    }

(i know it's contrived, but that's the gist)

finally, you can be pretty sneaky with other structures. If you have a binary tree with infrequent edits, you'll get away with log2(height) new nodes rather than a whole tree. If performance is critical, this is less good, but a few hundred bytes here and there for all the other good stuff immutability gets you (other threads keep using the old tree) might be worth it.

A big part of it is trying to think about how to structure your code to take advantage of immutability. If you're already changing stuff all over the place, it's not going to help much. but if you plan ahead, usually, you can build the structure with the right values up front.

Going back to the list example, you've got some data coming in. rather than many passes making many lists, you have one thread that reads data, passes it to n helpers that do all the work, then it reassembles the answers into a list. I guess that's more concurrent than parallel, but i think it captures the essence of what you're looking for.

Functional C++ talk by Kevlin Henney [video]

Related Stories