This is why functional programming really matters:
it provides new options for incremental development.
How do we develop software? One line at a time.
All software development is incremental. We have learned to embrace this fact and use it to our advantage. We start small, seek feedback, learn fast, and change direction as we go.
This requires means to develop incrementally, which at first sight looks like a simple task. After all, software is soft and can be changed any time. But whenever we touch existing code we may introduce subtle new errors and we have therefore devised a whole series of methods and tools to mitigate that risk. Between them are:
- object encapsulation to limit the error scope,
- test-driven development,
- static code analysis, refactoring, and other tools.
When we have to change and recompile existing code in order to proceed, we call this approach intrusive.
Of course, the best would be if we could apply increments non-intrusively: without touching any existing code at all! This is sometimes possible.
- Modular architectures allow to just add new components or services.
- In object-oriented systems we can use subtyping to add new implementations for existing abstractions.
- With dynamic languages, we can add new capabilities to existing classes.
But all of these options have their limitations. They either work only for anticipated extensions or they come at the expense of increased complexity or weakened type safety, which in the future makes it harder to extend the extensions again.
We would certainly profit if we had more ways of extending software safely.
Functional programming comes with such new options as John Hughes has shown in his seminal paper “Why functional programming matters“. He puts it in terms of modularity and new “glue” for combining modules: high-order functions and lazy evaluation.
The paper is now 25 years old but still offers a lot of fresh insights. The examples are presented in the Miranda language and to fully appreciate them, I translated them to Frege (a Haskell for the JVM). His line of argumentation accumulates in the last example: a generic solution for playing board games. A running implementation plus the full source code for a simple tic tac toe game is available here.
Following the paper while implementing the game led to some unexpected experiences that we will talk about in this series of blog posts.
Episode One: Be infinitely lazy and defer all work
A board game is a series of mutual moves, each resulting in a new board position. Since there are many possible moves and a number of possible reactions by the opponent, the possible unfoldings of the game form a tree of board positions.
Depending on the game rules, that tree can be infinitely large.
The natural way of modeling this in a lazy functional language like Frege or Haskell is to not care about the size of the tree at all but only about how to construct it.
We keep focussed on generation task and defer the limitation work to later.
Here is the construction for an arbitrary payload “a”. Children of each node recursively arise from making Nodes for all the payloads that “a” can unfold to.
buildTree :: (a -> [a]) -> a -> Tree a
buildTree unfold a = Node a children where
children = map (buildTree unfold) (unfold a)
We do not care about a base case to stop the recursion or limit the size of the tree but note that calling buildTree will neither exhaust memory nor computation time.
Laziness in the language cares for constructing children only when needed.
This is now something that we can specialize for a given data type Board and a function moves that unfolds to all boards that result from applying a valid move.
gameTree :: Board -> Tree Board
gameTree board = buildTree moves board
The spezialization needs no subtyping and is yet fully type-safe.
We have extended the system non-intrusively and we will do so again for limiting the size of the game tree.
When an evaluation of the tree shall be limited to a depth “n” we simply prune the tree at that depth. That code is independent of our special game use case and can therefore work on nodes of arbitrary trees. Here is the recursive definition.
prune 0 (Node a children) = Node a 
prune n (Node a children) = Node a (map (prune (n-1)) children)
To make a pruned game tree we use function composition (.) for the generation:
prunedTree = prune 5 . gameTree
Note that we still haven’t materialized the tree! A user of the pruned tree can never look below level 5. No children below that level are ever evaluated, and thus – thanks to laziness – never get constructed.
Laziness allows us to work incrementally not only from generic tree generation to specialized logic and data types. We even apply pruning conditions non-intrusively “from the outside”. We didn’t need to anticipate the need for pruning.
We never had to go back to previous code to change it. We did not even re-compile!
This is it for episode one. Stay tuned for more episodes.