After having written episodes 1, 2, and 3, I planned to close the series with some parting thoughts about what we have achieved and where I struggled along the way. But in the process of writing down my findings, it occurred to me that we have achieved an unusual state that we can leverage to our advantage:
All our code is purely functional
1) There is not a single 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.
When recognizing a = sign in the code the casual reader may be misinterpret this as an assignment, which it is not. It is a one-time definition that never changes. All is safe.
2) There are no side effects in the code.
3) You cannot imagine my surprise when I recognized that we don’t even have to consider 1) and 2) for the total of our code because the Frege type system validates our assumptions about purity automatically!
One often advertised advantage of functional programming is it’s improved support for parallel execution when compared to imperative solutions. And that claim is true – to some degree. The point is that “a little bit of functional style” only helps very little when going parallel. As long as you cannot guarantee that all your code that you are going to execute in parallel is MT safe, the ability of calling parallel versions of higher-order functions like map, filter, reduce, etc. is only of superficial syntactial help. With that approach, it remains the obligation of the programmer to inspect the whole call chain from all methods that are called from a inside concurrent operation (like map) down to their very last primitive statement to validate them for MT safety. And even if all the code is safe at the time of introducing the concurrent use, how about later changes where the maintainer is not aware that he has to keep that characteristic?
Tic Tac Toe in parallel
This is where the big difference between
“functional style” and
“pure functional” programming
becomes not only undeniably apparent but also of utmost practical relevance.
A new requirement comes up: go parallel
Let’s try to evaluate our Tic Tac Toe moves in parallel. There is one line where we map all boards that can arise from making a valid move to their evaluation, where probe is a function that is used for both, using the minimax algorithm for finding the best board and for returning the forecast:
evaluatedMoves = map (probe lookahead) possibleMoves
In order to make the mapping parallel, we can use the mapP function from the frege.lib.ForkJoin module:
evaluatedMoves = mapP (probe lookahead) possibleMoves
The superficial syntactical advantage is the opportunity to make the code parallel with one (!) additional character in the code.
While this is kind of cool in itself, the really impressive effect is that this change is guaranteed to be safe! This is fundamental and it works because of the way that purity is handled through the type system.
And this comes so: the type signature of map is
map :: ( α -> β ) -> [α] -> [β]
Let’s start with the first argument ( α -> β ).
It means that map‘s first argument 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 αs to produce a list of βs.
In our case f is (probe lookahead).
If (probe lookahead) would use any kind of state or use any kind of side effect, then type α or type β (or both types) would need to have a type constraint like State α or IO β .
In such a case, map (probe lookahead) would simply fail to compile.
In other words: the signature of map requires purity of f and the Frege type system enforces this down the whole call chain! We do not have to go back and check ourselves nor can any later intrusive change by a maintainer undermine our foundation.
Now, what happens when we go from map to mapP ? Here is the type signature of mapP :
mapP :: ( α -> β ) -> [α] -> [β]
That is exactly the same! The whole line of argumentation from above persists!
Let that sink in for a minute.
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 make that possible.
In all other popular JVM languages this would have been an immensly 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, that one should apply before blindly making all calls to map parallel:
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 concurrency 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 be done lazily since new threads should start working early enough to have the result ready when requested. But that approach would never finish when applied to infinite data structures on the top-most level of expressions. Therefore, mapP enforces the weak-head-normal-form (WHNF) of the given list. That still allows laziness at lower levels.
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 all on one line and we do not have to go further.
My personal experience was very strange when I applied concurreny 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.
I still have trouble believing it.
In the next episode, we may finally come to the parting thoughts.
The paper Why functional programming matters
The full source code. Play the game here.