programming in the
twenty-first century

It's not about technology for its own sake. It's about being able to implement your ideas.

Messy Structs/Classes in a Functional Style

There are two major difficulties that get ignored in introductions to functional programming. One is how to build interactive programs like games (see Purely Functional Retrogames). The other is how to deal with arbitrary conglomerations of data, such as C structs or C++ classes.

Yes, yes, you can create composite data types in functional languages, no problem. What happens in C, though, is that it's easy to define a struct, then keep putting things in there as needed. One day you realize that this structure contains dozens of flags and counters and other necessary things, which sounds bad--and technically is bad--except that it sure was nice to just add them and not worry about it. You can do the same thing in a functional language, but it's a poor match for immutability. "Change" one of those hundred fields and they all get copied. When interactively testing it's hard to see what's different. There are just these big 50-field data types that get dumped out.

I have a couple of guidelines for dealing with messy struct/class-like data in Erlang, and I expect they will apply to other languages. I've never seen these mentioned anywhere, so I want to pass them along. Again, the key word is messy. I'm not talking about how to represent an RGB tuple or other trivial cases. Set perfection aside for the moment and pretend you're working from a C++ game where the "entity" type is filled with all kinds of data.

The first step is to separate the frequently changed fields from the rest. In a game, the position of an entity is something that's different every frame, but other per-entity data, like the name of the current animation, changes only occasionally. One is in the 16-33 millisecond time frame, the other in seconds or tens of seconds. Using Erlang notation, it would be something like this:

{Position, Everything_Else}

The technical benefit is that in the majority of frames only Position and the outer tuple are created, instead of copying the potentially dozens of fields that make up Everything_Else. This factoring based on frequency of change provides additional information for thinking about the problem at hand. Everything_Else can be a slower to rebuild data structure, for example.

The other rule of thumb I've found helpful is to determine which fields are only used in certain cases. That is, which are optional most of the time. In this oversized entity, there might be data that only applies if the character is swimming. If the character is on-foot most of the time, don't add the water-specific data to the core structure. Now we've got something like:

{Position, Most_Everything_Else, Optional_Stuff}

In my code, the optional stuff is an Erlang property list, and values come and go as needed (were I to do it today I might use a map instead). In a real game, I found that almost everything was optional, so I ended up with simply:

{Position, Optional_Stuff}

(If you liked this, you might enjoy A Worst Case for Functional Programming?)

permalink February 7, 2016

archives

twitter / mail

I'm James Hague, a recovering programmer who has been designing video games since the 1980s. Programming Without Being Obsessed With Programming and Organizational Skills Beat Algorithmic Wizardry are good starting points. For the older stuff, try the 2012 Retrospective.

Where are the comments?