A question to understand functional programming

Let's assume I write a game in pure FP style. I'm not allowed to mutate a state, like the position of a player.

Instead I have to store each input since a player joined the game in a looooong list and I have to calculate the current position based on the starting position and each move the player takes (or to be more precise, each force applied to the player)

Have I understood it correctly so far?

You cannot mutate data, but you can compute new data from function inputs. That means that you can take a list of positions, a list of keyboard inputs, and compute a new list of positions. There is no need to keep all data around forever.

2 Likes

That’s one approach, and there are systems set up to optimize incremental computations like that. I think a more natural version would be something like:

fn game(state, input_stream, gfx) -> state {
    let ins = first(input_stream)
    let state1 = update(state, ins)
    draw(state1, gfx)
    game(state1, rest(input_stream), gfx)

If you have tail-call optimization this is just a loop since nothing happens in the function after the recursive call to game. I’m assuming input_stream is a lazy stream and draw() has side effects but there are pure ways to handle output as well.

That's the part that melts my brain. You call the game recursively. But that means the old data is still somewhere in the memory. So if a game runs long enough you are running out of memory.

Or do I get something wrong here?

Edit: ah, ok. The answer is the tail call recursion. That's new to me

Tail-call optimization is what prevents OOM events. As @JosephOsborn said, the compiler is smart enough to sometimes transform tail recursion to a loop, which prevent memory use from exploding.

You may be interested in this series of articles describing how to write a Pac-Man clone in a purely-functional style (written in Erlang, not Rust):

1 Like

Thanks for the answers. I think I got it.

But I assume there is a point where even this doesn't work.

If you have a game like Minecraft and you have megabytes of map data you can't really copy them as a new state to the next loop efficiently.

There are ways to make it moderately efficient. One approach is to store the world data in a tree structure and share the unchanged nodes between the the old and new states.

The power of immutable data structures is that they don’t need to be copied in order to modify them. Modifying a leaf in a tree-like data structure only requires re-creating all nodes on the path from the root to the leaf, everything else can be re-used.

Here’s a random picture from the internet of what that looks like (Tree B is obtained by "modifying" Tree A):

1 Like

By the way, there is this lovely website code.world (mainly intended to be used for teaching kids math) that allows you to write small games (or just generate pictures) in the web-browser, in a pure functional programming style, based on (slightly modified) Haskell. I’ve included a game I’ve just created for demonstration purposes in the link above.

Edit: If the blinking cursor makes the question text jiggle in the game I linked above, try this updated version :wink:
another noteworthy point is that the website allows for easy creation of multiplayer games, like this example ^^

The approach followed there is that a generic game-loop (as well as some picture drawing primitives) are library-provided and it takes a function of type (T, Event) -> T as a parameter, where T can be any type you like to store your game-state in. Two more parameters are a displaying function T -> Picture and a function to create an initial state.

Fun fact: The creator of the website/tool made sure that the library does not provide any functions with verb-names, in order to not confuse kids into thinking that functions are supposed to "do" anything (pure functional programming == no side effects, you know? :wink: )

5 Likes

Ok, thanks so far. It's time to code now.

Yep.

On the face of it, speaking as an old school "normal" programming guy since ALGOL to C and C++, the whole idea of FP is barking mad. I mean really, my programs are made of functions/methods, if I cannot mutate state globally or in some object how on Earth is my program supposed to make any progress and do anything useful?

The FP guys say we can't do that. They say that every function should produce the same output for a given input no matter how many times it is called. That it cannot mutate state outside of itself.

So we might think an FP game becomes:

    new_game_state  = do_game_step(old_game_state, user_input);

Which, as far as I can tell it does. That is of course nuts, it will involve a lot of copying of game state, waste a huge pile of memory and be very slow. Right?

Except, those FP guys are cunning. They cheat!

They say "What if new_game_state is only slightly different than `old_game_sate'"?. And "What if instead of copying all of new to old we arrange that only the differences are noted, such that someone with a handle to new_game_state sees the changes but someone with handle on old game_state does not?

That idea seems to be quite doable when game_state is a complex mess of data in lists and trees, as it likely is. For example the same linked list will look different to someone with a pointer to head as it does to someone with a pointer into the middle of the list, that they think is head. See steffahn's tree example above.

This FP fraud became clear to me recently after watching:

"Monoids, Monads, and Applicative Functors: Repeated Software Patterns - David Sankel - CppCon 2020": https://www.youtube.com/watch?v=giWCdQ7fnQU
and:
"Postmodern immutable data structures - Juan Pedro Bolivar Puente [C++ on Sea 2019]": https://www.youtube.com/watch?v=y_m0ce1rzRI

Impressive stuff. Sounds like a useful idea to have in ones tool kit. Although my old brain is still not sure how or where.

My apologies to anyone sensitive for my use of the words "cheat" and "fraud". They are there only for dramatic effect. In much the same way I might say the "structured programming" guys who banned goto then had to cheat by replacing goto with case/switch, break, continue, exceptions and recently generators.

2 Likes

It's even better than that. Very often the compiler knows that nobody can ever see the old version. In that case, it is free to make the change in place as would a non-functional language. There's no harm done as long as it maintains the functional semantics.

A good example of something purely functionnal and with a very complex state is git. And it's effectively functionnal, since creating a new commit doesn't change the state of any previous commit. Every commit is a snapshot, but a repository like Linux doesn't takes hundred of petabytes even if the number of commit is humongous. It's because it uses Merkle trees internaly.

1 Like

OMG, I have to get my son to try this at some point. How cool would it be to learn Haskell as a first programming language (after Scratch). I wonder what that would do to his brain, having that as a foundation instead of 80s BASIC. (Only trouble is that then I'd have to learn Haskell as well to help him out.) Thanks for the link! It appears to be open-source.

1 Like

Logo might be a better start

There’s a few presentations about it from the creator on YouTube, too, like this one:

(the sound quality is not the best)

There’s also a small number of short introduction/teaching videos here.

1 Like

In the video, he does cover what it does to students' brains, in the sense of separating abstract meaning of functions (in a mathematical sense) from imperative implementation, and that that gives them an advantage at higher levels of study (according to some research he quoted). I think I've found our holiday project. It will all be a good foundation for Rust later on too.

Also, I think people shouldn't underestimate what children are capable of. Ours was doing geometry proofs in DragonBox Elements at the age of 5, and I wasn't simplifying my language when discussing it with him. (This is another example of a "manipulative" as he described in the video, probably intermediate between physical blocks and the higher-level abstractions of code.world.) With the right environment, and few unnecessary impediments, they can learn a lot.

(Incidentally, I have a testing app similar to yours, but in Lua. Repetition through randomised testing in short concentrated bursts daily works wonders. Getting them used to concentrated training in this way will allow us to demolish most of the memorization required in school, and has also already helped a lot with neural net training such as reading. I wonder about sharing my app sometime, but it's in a state of continuously being hacked on. It's kind of similar to some stuff that's already out there, but I've tuned it to exactly the patterns that work best for us. I was thinking of rewriting in Rust, but ... no time.)

Everyone else -- sorry for the brief off-topic detour into education.

2 Likes