1

Playing with some 3d game stuff in my spare time in C++.

C++ doesn't really lend itself well to fast, simple functional programming, and games where there is a lot of necessarily shared state don't always either.

However some functional ideas still seem useful. For example my renderer is implemented as a single "pure" function that takes a 'Scene' object and a 'Camera' object and transforms them into a return value of a list of GPU commands that will render that scene. Is a nice abstraction.

But things like representing the world state isn't so easy. Conceptually I could write a pure function to take a WorldState and a ObjectIdentifer and a MovementSpeed and return a new WorldState with the object in it's new position.

Doing this literally is just not going to work well enough in C++ without a great deal of effort and fighting the language and there doesn't seem any simple workaround.

However what i can do is still conceptually have a function that takes a WorldState and a MovementSpeed and returns a new WorldState but in fact what it is returning is an updated version of the old world state. I know that the old state is never of any interest once it's been updated so as long as I disregard it I can still think of my function as transforming (WorldState, ObjectId, MovementSpeed) into a new WorldState

So does it have any value to think of my function in functional terms even though it's not really implemented that way? I am still mutating state in the WorldObject just not thinking of it like this.

Or is this not really helpful?

  • 2
    Does it really have to be purely functional, or can you mix in some classes that contain the required state? – Robert Harvey Sep 27 '17 at 14:49
  • 1
    These types of techniques (immutable data structures) are used especially to simplify multithreaded programming. The data structures are not easy to create in any language, but once you have them, they should be able to reuse most of the existing state, in an immutable structure, adding changes to it in an immutable way. I don't think you are fighting the language. It is suitable. But you will be fighting the optimization problems. – Frank Hileman Sep 27 '17 at 17:45
  • 1
    "Persistent data structures" is the term used these days. An example: news.ycombinator.com/item?id=13049843 – Frank Hileman Sep 27 '17 at 17:51
  • "Does it really have to be purely functional, " not at all. I just find that some of the ideas are useful in C++.I'm very happy to write "traditional" c++ taking on board any ideas when they make things better – JohnB Sep 28 '17 at 10:25
10

I am not an expert in functional programming. However, my understanding is that one of the advantages of the functional model is that it makes it easier to reason about the behavior of a program. If you see:

var x = 5;
var y = foo(x);

In a functional world, you know that x is unchanged. You may as well have written foo(5).

So if you have some function that modifies its parameter but also returns it... what good is that? You can't use traditional functional reasoning about the state of the system because the x in that scenario will have been changed.

One of the reasons for statelessness in functional programming is for composition:

func(foo1(x), foo2(x));

In C++, the order of those two expressions is undefined. In a functional language, the order is irrelevant, because it is impossible for either inner call to affect the other. So if both of the foos followed strictly functional rules, it'd be perfectly fine in both cases.

With your functional-in-form-only approach, you get the worst of both worlds. Since your two foo functions are not really functional, the order they're called in matters since they're affecting the same state. But since C++ doesn't define that order... oops.

If you're going to be functional, then be functional. If you're not going to be functional, don't pretend to be functional.

Do, or do not. There is no try.

  • 4
    And Finally no Catch, say Yoda. – user251748 Sep 27 '17 at 16:03
  • I don't disagree with what you are saying. Clearly there are issues with this. But in practice the function wouldn't be called 'foo1'and 'foo2', they'd be given names that suggested they both modified the "world state", so you'd have the hints you needed to be careful. – JohnB Sep 28 '17 at 10:38
6

Yes, it has value: it gives you greater ability to reason about the effects and invariants of your code, without sacrificing performance.

In fact this is an active area of research in functional programming: how to write conceptually pure functions that can nevertheless safely mutate a value in-place for performance.

What you’re expressing is that the reference to the world state is an affine type, an example of a substructural type. An affine type can’t be copied; if you have a mutable reference to the state, you want that to be the only reference (mutable or immutable). With that assumption, you can safely mutate it without any other code wrongly depending on the old value, or reading it while it’s being mutated and possibly in an invalid state.

This is an especially useful thing to enforce if you’re making use of concurrency and parallelism. The Rust programming language uses substructural types in exactly this way to enforce safe mutation and eliminate data races. Haskell is also adding substructural (linear) types soon, both for performance reasons and to help enforce invariants about state.

You can get a slightly weaker guarantee in C++ by passing around a unique_ptr<WorldState> by move—this helps you ensure that there’s only one reference to the WorldState.

// A linear function of the world state, formally of type:
//
//   ObjectId → MovementSpeed → WorldState ⊸ WorldState
//
// Where AB is the type of a linear function, consuming
// a value of type A and producing a value of type B.

std::unique_ptr<WorldState>
update(
  ObjectId                    object,
  MovementSpeed               speed,
  std::unique_ptr<WorldState> state
);

However, the type system of C++ won’t protect you from obtaining a raw pointer or reference to the state and making or observing changes from outside, so you would need to enforce that through your coding style instead.

  • Thank you this is interesting, particularly the part about something being the "only reference". As for the last paragraph, that's interesting too. Plus I think one of the advantages C++ has is that it lets you break the rules when necessary (and of course that's one of it's disadvantages too in the wrong hands ) – JohnB Sep 28 '17 at 10:30
  • I like the idea of unique_ptr for this. It will enforce the function taking ownership of the data, and passing ownership out of the function. So the example of calling "foo1" and "foo2" with the same data like in the other answer wouldn't arise as when you called the second the data would have been moved out and likely lead to a run time error at least. Pity that std::unique_ptr<MyThing> is so long and ugly but I guess there is typedef... – JohnB Sep 28 '17 at 10:40
2

Building a little on what Jon Purdy suggested, one way to deal with copying the state that doesn't change from the old to the new is to do something like the following.

Say you have a structure like this:

struct GameState {
    int bar;
    float baz;
    //... etc.
    Point playerPosition;
    Point playerVelocity;
};

You could put bar and baz, etc. into a separate structure and simply use a reference to it, or a pointer to it, or as Jon suggests, a std::unique_ptr<> if you know that it won't be re-used by anyone else. So something like this:

struct BarBaz {
    int bar;
    float baz;
    // ...etc.
};

struct GameState {
    std::unique_ptr<struct BarBaz> barBazState;
    Point playerPosition;
    Point playerVelocity;
};

When your game creates the new state, it's not actually copying barBazState, just the pointer to it, which is much faster. Since it's a std::unique_ptr<> you know that the new game state is the new owner of it.

0

I speak from JavaScript-land but as far as I've been able to ascertain, the benefit is this:

Reduced state when you need to reduce state.

Reducing state generally can be beneficial to architecture but I've had trouble adopting functional enthusiastically for the following reason.

State never bothered me. Like seriously, how hard is it to not make a !@#$-show out of state? State should be as simple and from one source of truth as much as humanly possible.

If you can derive from existing state, don't invent new state. Functional is helpful with that. But if you have state problems constantly as it is, it's not likely to help you. Learn to manage state. You can't sidestep that problem. I've seen people try.

0

I've implemented a library of immutable data structures in C with C++ wrappers on top. I can't share it as it's proprietary and it did require some elbow grease to build, but just took me a couple of weeks before I was writing a bunch of multithreaded test code that was able to just return transformed versions of these structures without a worry in the world about overlapping reads/writes and race conditions. Of course I've expanded it a lot since then but it doesn't take long to get started and see exciting results even if you're doing this from scratch.

Moreover I found it really simplified implementing undo systems when the undo system can just deep copy the entire data structure and know that it's not actually duplicating that much data beyond the parts that are different/unique (there's some balance of redundancy when designing persistent data structures efficiently where you want to avoid shallow copying the most granular data while simultaneously avoiding deep copies of overly coarse data -- for images/textures I broke them up into tiles to be shallow copied or deep copied based on what image tile becomes different through a transformation as a basic example).

Actually it trivialized the undo system arguably just as much if not more than the multithreading because I used to implement undo systems by storing granular deltas of each and every little thing that the user touched. When you can just store an entire immutable copy of an entire "scene" or application state without worrying about it being too expensive before the user begins some high-level operation, boy does it simplify things on the undo side. It does shift some additional complexity to the client code creating modified versions of the data, but I found the overall exchange results in less complexity than it adds and, beyond complexity, it makes it really, really easy to reason about the system's correctness without wading through endless code, however simple, that can cause side effects and therefore be a potential source of problems.

This still doesn't allow pure functional programming style so effectively since the language still can't recurse deeply without stack overflows, e.g., and it's still unwieldy even with lambdas in C++11 and beyond to write a lot of code in a functional programming style, but you can still get a great deal of the benefits of avoiding the human errors associated with complex state management, especially in a multithreaded context, without fighting the language so much if you build yourself some nice immutable data structures or grab some from a library.

There are libraries like these implemented in C++ which followed the same vein. https://sinusoid.es/immer/

Mine's not quite as sophisticated since I didn't put as much effort into trying to allow basic scalar operations. My design revolves around the client code expressing what changes to make to the data structures in bulky transactions to "commit" to get the new immutable copy and revolving more around the "transients" idea discussed in that "immer" library where a thread modifies a local mutable structure lock-free and then "commits" it to get a new persistent immutable. Example pseudocode:

Image transform_some_image(const Image& img)
{
    // Grab a transient raster object to mutate (basically
    // an array of pixels).
    TransientRaster raster = img.transform(some_rectangle);

    // Modify pixels in the raster.
    ...

    // Commit the raster, getting a new transformed image. This
    // does not modify the original, only gives back a new image
    // which shallow copies most of the data we didn't touch above.
    return img.commit(raster);
}

It also trivializes exception safety since so few parts of the application cause side effects that need to be rolled back in the event of an exception being thrown since the majority of code is just constructing immutable structures which can be tossed away (implicitly through destructors in C++) if the operation fails. That's similar to the undo system since writing exception-safe code is somewhat analogous to undo systems normally where you have to revert every little side effect unless you have immutable structures handy which reduce the number of places causing side effects to a minimum. If the above code threw an exception, the raster transient can be tossed aside and we have no side effects whatsoever since it doesn't touch the pixels of the original image.

The above function can also be parallelized to the smithereens without putting any thought into it since, again, it's not touching any state outside of states local to the function (no side effects, at least as far as the outside world is concerned). The only part that locks is the commit call to create a new immutable image which only deep copies the tiles modified by the transient raster.

It does result in the client code having to work with these transient objects a lot and some extra code all over the place to express what it wants to do as a "transaction", but actually not that much and possibly even less if you take into account all the things that have to be done for a particular piece of code to be both thread-safe and exception-safe, and it also trivializes the amount of thought you have to put in before you write a function that can achieve both of these.

Moreover, it doesn't solve design-level multithreading problems which is why I see the more practical benefit being in exception safety and undo systems and modifier stacks and node graphs which input something and output something new and things of this sort. For example, if two threads create two modified immutable versions of the same image, which one do we use to show to the user? Unless we have a way to consolidate the transformations meaningfully made by both threads or can just meaningfully ignore the results of one of them, then immutable structures do squat as far as solving the whiteboard issues of the design. However, it does make it so you can rest assured that you won't have some exotic race condition which only occurs when there's a full moon outside while a virgin is being deflowered and only for blonde users who happen to be working on something very important at the time. You can at least feel safe against those extremely obscure, mind-numbing edge cases that seem almost impossible to reproduce until that ultra rare moment you decide to try the application in a release build without a debugger handy and weren't even focused on trying to reproduce this problem.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.