map :: ( α -> β ) -> [α] -> [β]
Episode Four: Going safely parallel
So far we have incrementally developed
-
a general solution for playing board games with mutual moves,
-
a specialization for the rules of tic-tac-toe, and
-
an extra forecast feature to see how the computer thinks that the game will develop.
All that code turns out to be purely functional. There is not an assignment in the code, no state that needs to get updated, and therefore also no shared mutable state that could impose any issues when going parallel. Furthermore, there are no side effects in the code.
Since we have just written the code, we remember that we have not written anything impure. But we can even be sure about the purity characteristic without any prior knowledge of the implementation: the type system tells us so!
Map is pure
And this comes so: the main entry point to our solution is a call to the map
function and
the type signature of map is
Let’s start with the first argument ( α → β )
.
It means that the first argument to map
is a function from any unconstrained type α
to any unconstrained type β
. Let’s call that function f.
The map
function applies its argument function f to all elements of a list of
α
values to produce a list of β
values, not knowing any specifics about f.
In our case f happens to be (probe lookahead)
. We are probing each board, looking
no further than the given lookahead where probing can be either the valuation of the
board or the detection of the forecast.
Mapping any function f over a list of α
values cannot possibly perform a side effect.
The closest possibility would be a specific function f that returns an IO action as type β
.
But even in that case, the IO action is only created, not performed.
No implementation of map
would ever be able to perform such an action since map
cannot assume
anything about β
- particularly it cannot assume that β
is an action.
In other words: the signature of map
asserts purity of map f
and the
Frege type system enforces this down the whole call chain!
We do not have to go back and check the code ourselves for possible purity breaches
nor can any maintainer accidentally undermine our foundation through subsequent changes.
Now, what happens if we go parallel and use mapP
(the parallel version of map
)
instead of map
? Here is the type signature of mapP
:
mapP :: ( α -> β ) -> [α] -> [β]
That is exactly the same! The whole line of argumentation about purity of map f
equally applies to mapP f
!
Parallelism as an increment
With Frege, we can again apply a non-intrusive increment: from sequential to parallel execution in an absolutely safe manner. Purity and its handling in the type system makes that possible. In all other popular JVM languages this would have been an immensely intrusive change (even if old code was not edited at all - changing its mode of operation is intrusive) with a huge potential to introduce hard-to-detect errors.
And again, we were able to apply this non-intrusive increment without having planned for it. We just did what is usual in Frege and it turned out to just fit.
We can almost always safely go from map to mapP.
There are two considerations, however, that we should apply before blindly making all calls to map parallel:
1) Granularity We applied parallel execution on the top-most layer of the evaluation only, not down to all splits of possible boards. That is a usual performance concern for data-parallel code where we weigh the relative overhead of thread scheduling against the size of the unit of work.
2) Infinite data structures Parallel execution makes usually no sense to work lazily since new threads should start working eagerly to have the result ready when requested. But that approach would never finish when applied to infinite data structures.
But those considerations are fully inside our mental context when applying our increment. We are in the position to decide about granularity and we know that possibleMoves is a finite list. It is a reasoning that is local to one single increment.
My personal experience was very strange when I applied parallelism to the tic tac toe game. I went from map to mapP, let the code run, and enjoyed the speedup. Then I fell back into my old habit of paranoid concurrency thinking: what could possibly go wrong?
And for the first time ever in such a situation, I couldn’t think of any possible issue.
References
John Hughes | |
Tic Tac Toe |