Accidentally Introducing Side Effects into Purely Functional Code

It's easy to taint even purely functional languages by reintroducing side-effects. Simply have each function take an additional parameter representing the global state of the world--a tree of key/value pairs, for example--and have each function return a new state of the world. This is not news. It's an intentionally pathological case, not something I'd ever consider implementing.

What's more surprising is how easy it is to accidentally introduce side-effects.

For the Purely Functional Retrogames series, I wrote code that operated on a list of game entities:

[A, B, C, D,...]

Each element was a self-contained unit of sorts: an ID, x/y position, current state. Using this list of entities to build a new version for the next game frame was a simple map operation. The ID and state for each entity were used to call the correct transformation function for that entity.

Each of these transformations had three possible outcomes: a new entity would be returned with a different position and/or state, an entity could delete itself, or an entity could create some new entities (think of dropping a bomb or firing a shot). All three of these can be handled by having each transformation function return a list.

For example, if the original list was:

[A, B, C, D]

and entity "B" deleted itself, and entity "C" created four new entities in addition to a new version of itself, then the returned values might look like this:

A => [A1]
B => []
C => [C1, New1, New2, New3, New4]
D => [D1]

and the new overall list of entities would be:

[A1, C1, New1, New2, New3, New4, D1]

Well, that's not quite right. It's actually a list of lists:

[A1, [], [C1, New1, New2, New3, New4], [D1]]

and the individual lists need to be appended together to give the proper result. The append operation creates a brand new list, which means that the time and memory spent creating the individual result lists were wasted. They were just stepping stones to the real result. This almost certainly isn't going to be a significant inefficiency, but there's a pretty way around it: pass an accumulator list in and out of each transformation function. Now the three cases listed above neatly map to three operations:

1. To transform an entity into the next version of itself, simply prepend the new entity to the accumulator list.

2. To delete an entity, do nothing. Simply return the accumulator.

3. To create new entities, prepend each one to the accumulator.

No extra work is involved. We never build-up temporary lists and discard them immediately.

But this pretty little solution has one unintended flaw. By passing in the accumulator list, we're giving full access to previous computations to each of the entity transformation functions. Even worse, each of these functions can arbitrarily transform this list, not only prepending values but also removing existing values or changing the order of them. (No destructive updates need occur, just the returning of a different list.) In theory we could write code that uses the list to make decisions: if the head of the accumulator is an entity of type "E," then spawn a new entity at the same position as E. Now the entire process is order dependent...ugh.

In theory. The "flaw" here assumes that each function is going to do more than either leave the accumulator untouched or prepend values to it, that the programmer of a function may intentionally go rogue and look to sabotage the greater good. It still could open the door to bugs: imagine if a dozen people were all writing these transformation functions independently. Someone will make a mistake at some point.

Either way, the same side effects possible in imperative languages were accidentally introduced into pure functions.

permalink December 14, 2008

Accidentally Introducing Side Effects into Purely Functional Code

previously

archives