Design a program in Functional Way #1: Core concept and Bowling Example

Nowadays, functional programming gains much traction in the software engineering community. We have many articles and many enthusiastic talking about what are benefits functional programming brings to the table.

I believe in functional programming, and I want to contribute.

While there are many content out there talking about what functional programming exactly is, I still see that many early adopters design a program using a thought process that fits for an imperative or object-oriented program.

Hence, it become very hard an unintuitive.

So in this article series, I will talk about thought process behind writing a program in functional paradigm. Where do you start? What are the main strategy? What is problem solving pattern?

While I think this image from NDC conference is true, I think it is not helpful.

So let's break it down.

Core concept

The core idea of functional thinking is declarative code.

What is declarative code? Good question.

This is a mathematic definition of function

In mathematics, a function[note 1] is a binary relation between two sets that associates every element of the first set to exactly one element of the second set. Typical examples are functions from integers to integers, or from the real numbers to real numbers.

Basically, a function is a static map between the input to output. The function does not care how do you get a result. You might have a million if-else for every possible case. That is still a function.

So in functional programming, we want to have ability to say

Problem(inputs) => answer

In this article, we will use a bowling kata as an example.

So what we want to say is to have a function:

Bowling(game) => score

That's it. That is a functional programming in nutshell.

We have a design, let's implement this function.

Wait a minute....

So do you mean to write every logic inside this single function? Will we end up with 1000 lines of code? Would that be really hard to read and reason?

Now we are getting into the beefy part. How to breakdown the system?

Break down the problem

In the imperative and object-oriented paradigm, we have many patterns, heuristic, and standard thought process to break down the problem.

For example, object-oriented programming's most basic fundamental is to define a subsystem or data as an object. Then we define the operation we can do with that object, and then, we piece it together.

There are many design patterns and strategies to achieve that. Still, the basic building block and thought process of object-oriented is defining some smaller objects and making them work together.

But then how would we breakdown the system in a functional programming paradigm?

First of all, We need to establish a boundary between impure part of a system and the pure part. That will not be a focus for today. We will only focus on how to break down the pure part of a system.

Ok. How can we break it down?

Answer is the same: Write more functions!!

Wait. that is not helping. What kind of functions? More functions is a solution to every problem?

Come on..........

Ok, I will clarify it further. Here is the deal.

Let say you try to write a function between problem -> solution. If it is hard to write a function problem -> solution, then we just need to figure out any C that is easier to write a function problem -> C and C -> solution. Then, we write two easy functions

And that is what it means to "write more functions".

The thought process seems simple, but hard to sink in.

In this series, I will explain how to design a program in functional paradigm, starting by solving some programming kata.

Bowling Kata

The purpose of bowling kata, in functional term, is to write a function

getScore(game) -> score

Just from the first glance, I know that this function will be pretty long and complicated.

I decided to break it down.

Use this question: What is a data A in such that?

1. It is simpler to calculate a bowling game score from data A.
2. It is simpler to calculate the data A from bowling game.

(Please note that normally, it is hard to come up with A that satisfied both property at the same time. So in real-world, you might come up with A that intuitively satisfied only one of those property, and test if it satisfied the another)

So, I thought

Well, if I have a set of score of each bowling frame, then I can just sum it up and create a game score.

So I chose score of each game frame as an intermediate data.

const solution = (game) => somethingICannotFigureOut(game)
// Become
const solution = (game) => sum(frameScores(game)))

I knew that sum is easy to implement, and I assumed that frameScores should be easier to implement.

What's left for me now is to implement frameScores.

But before we go, to be on a same page, I will clarify data structure of game.

export type NumberScore = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
export type StrikeFrame = [10, null]
export type ScoreFrame = [NumberScore, NumberScore]
export type NormalFrame = StrikeFrame | ScoreFrame
export type LastFrame = [NumberScore, NumberScore, NumberScore | null]
export type NextFrames = Frame[]
export type Frame = NormalFrame | LastFrame
export type Game = [
  NormalFrame,
  NormalFrame,
  NormalFrame,
  NormalFrame,
  NormalFrame,
  NormalFrame,
  NormalFrame,
  NormalFrame,
  NormalFrame,
  LastFrame
]

This is the shape of the data. A game is a tuple consist of 9 NormalFrame and 1 LastFrame.

As I tried to implement frameScores, I found it hard to implement that in one go. Nothing came on top of my mind.

So I decided to break it down more.

A frameScores is a score of each individual frame, so I needed to have a way to calculate individual frame score.

How can I do it? What are rules and logic here?

In each frame, the bowler gets up to two tries to knock down all the pins. There are basically four ways to calculate frame score:

1. If in two tries, he fails to knock them all down, his score for that frame is the total number of pins knocked down in his two tries.
2. If in two tries he knocks them all down, this is called a “spare” and his score for the frame is ten plus the number of pins knocked down on his next throw (in his next turn).
3. If on his first try in the frame he knocks down all the pins, this is called a “strike”. His turn is over, and his score for the frame is ten plus the simple total of the pins knocked down in his next two rolls.
4. If he gets a spare or strike in the last (tenth) frame, the bowler gets to throw one or two more bonus balls, respectively. These bonus throws are taken as part of the same turn. If the bonus throws knock down all the pins, the process does not repeat: the bonus throws are only used to calculate the score of the final frame.

That is the rules. I want to break down frameScore. What can I do?

Repeat the same question: What is a data A in such that?

1. It is simpler to calculate an individual frame score from data A.
2. It is simpler to calculate data A from the bowling game.

So I thought, what is dataset A?

I found that A will be a dataset consist of

• Numbers of pin knocked down in this frame
• Numbers of pin knocked down in the next two rolls

If I have all these data, I can easily implement frameScore like this

// Given frame and nextRolls
switch (getFrameType(frame)) {
    case FrameType.LastFrame:
      return frame[0] + frame[1] + (frame[2] || 0)
    case FrameType.Score:
      return frame[0] + frame[1]
    case FrameType.Spare:
      return frame[0] + frame[1] + nextRolls[0]
    case FrameType.Strike: {
      return frame[0] + nextRolls[0] + nextRolls[1]
    }
  }

Now I think it is simpler enough to implement, so I ended my breakdown here.

Done deal!! I have a program design.

Let's Recap the thought process

1. I wanted a function BowlingScore(game) => score, but I thought it is too hard to write.
2. So I came up with data A in a way that Something(game) => A and Another(A) => score is easier to write. That A is a score of each individual frame.
3. Now I wanted a function that given a game, can calculate score of each individual game. I thought it is still too hard to write.
4. So I came up with data A in a way that Something(game) => A and AnotherThing(A) => frameScore is easier to write. That A is a dataset consist of the frame itself, and a next two rolls.
5. So at the end we can calculate by basically

gameScore = game |> break_into_frame_and_two_rolls 
|> Map(frameScore) |> sum

As I tried implement all of these, I found that each of them is simple enough to write and reason about.

You want to see the end result? The implementation in TypeScript can be found here. And the implementation in Scala can be found here.

Conclusion

As I wrote thought process of functional programming design in pure function domain can simply be stated as:

Let say you try to write a function between problem -> solution. If it is hard to write a function between problem -> solution, then we just need to figure out any C that is easier to write a function between problem -> C and C -> solution. Then we simply write two easy functions

That's it. That is a very simple and yet very powerful way of thinking about a problem.

I show the example of what results from repeatedly asking myself the question and what kind of program I ended up.

It is very interesting to see what kind of program design can come from repeatedly asking that question. It is a simple and powerful question. I will show you more in the next article.

And I hope you understand now why a functional programming design can be as simple as "Write more functions!!" 😄

Thanks for reading!!

TypeScript full implementation: https://github.com/chrisza4/functional-bowling-ts
Scala full implementation: https://github.com/chrisza4/functional-bowling-scala

Some opinion pieces:

You might wondering about how this is different from imperative programming?

Thinking imperatively will lead you to a little but fundamentally different line of thought.

Most likely, you will get into this:

• Spare frame score is a frame with a little bit more
• Strike frame score is a frame with a little bit even more

But where is that little bit more come from? It comes from another frame in the game, so it is natural to think that the individual frame score must have access to the whole game, which is not true.

Most of the implementation I saw just embedded the whole game context in a single object. And both gameScore and frameScore methods consume that full game context, only to access that "a little bit more" data.

In functional line of thought, you will think of a function frameScore and it inputs, which lead to limited access.

And it is possible to use this approach to write an Object-oriented code. I did it in the Typescript implementation repository. You can check it out.

The main distinction is not the code it produces. The differences are the thought process. Do you break down a complicated logic by identifying a set of data + operations and create an object? Or Do you break down a complicated logic by identifying a data structure that closer to the solution?

Functional thinking patterns can be helpful, even if you don't use a functional programming language.