23 July, 2024
What is Functional Programming?
Explore Functional Programming by applying it to a real-world problem
Functional Programming (abbreviated as FP) is a programming method that applies mathematical function theories. It sounds quite grand and difficult to understand, but in reality, we encounter FP everywhere without realizing it.
Many programmers believe that because their code base uses classes entirely, they use OOP (Object-oriented Programming) and not FP. However, it's not that we don't use it, but that we use it unintentionally without fully understanding it.
So what exactly is Functional Programming? In this article, we'll try to apply mathematical thinking to solve a practical problem.
I'm not afraid of the programmer who creates 10,000 programs once, but I'm afraid of the one who practices programming one program 10,000 times
Problem Statement: Nokia Snake Game
The legendary Nokia Snake Game needs no introduction. Our problem statement is simply as follows:
- The screen is divided into 25x25 equal cells
- The game starts with a snake 3 cells long
- Each time the snake eats food, the score increases by 1 and the snake grows by 1 cell
- If the snake touches the screen edge, it will "return" from the opposite side (also known as wrap screen)
- The snake dies if it bites itself
The "naive" approach
The simplest way is to google "simple snake game js"
I found quite a few different pages, but the general method is similar to this:
var grid = 16; // length and width of a cell, in pixels
var snake = {
x: 160,
y: 160,
// snake's direction
// can change dx, dy depending on the current direction
dx: grid,
dy: 0,
// stores all cells that the snake occupies
cells: [],
// number of cells the snake currently has
maxCells: 3
};
var food = {
x: 320,
y: 320
};
The logic is roughly as follows:
- When the snake moves, the elements in cells will change, specifically:
- The new coordinates of the snake's head will be added to
cells - The oldest coordinates (tail) will be removed
- The new coordinates of the snake's head will be added to
xandyare the coordinates of the snake's headfoodcontains the coordinates of the food- If the snake eats food,
maxCellsincreases - If a button is pressed,
dxanddywill change depending on whether the button is up, down, right or left
Although this method works, it has the following problems:
- All coordinates use pixel units, but the actual coordinates of the snake are in cell units (one cell equals many pixels)
- Many redundant data variables (will be explained in the later section), the code must synchronize between these variables
Rearranging the data
The first important element of Functional Programming is to minimize the list of input variables, avoiding information duplication.
The "naive" approach above has many redundant data variables, for example:
xandyare the coordinates of the snake's head, but clearlycellsalready has this informationmaxCellscan be calculated by the length ofcells, orcells.lengthdxanddycan actually be replaced by a single variablesnakeDirection, taking one of 4 values: up, down, right or left
Thus, our problem now has only 3 variables left:
snakeCells: stores all cells that the snake occupiessnakeDirection: takes one of 4 values: up, down, right or leftfood: stores the coordinates of the food
Additional note: All coordinates in the calculation logic will use cell units (values from 0 to 24) instead of pixel units. The conversion between cell coordinates and pixels will be done by a specific function (will be explained later)
Rearranging the logic
The next element to consider in Functional Programming is identifying the interdependencies of the logic parts.
A basic mathematical function can be written as follows:
y = f(x)
Now, we want to "model" the interdependence between data in mathematical form.
For example from the previous section, we know that the score always depends on the length of the snake:
score = f(cells.length)
We know that initially the snake is 3 cells long, so we won't count these 3 cells. The function f(x) above is simply:
function f(cells) {
return cells.length - 3;
}
score = f(cells);
For easier remembering, we can call the function f(x) above getScore:
function getScore(snakeCells) {
return snakeCells.length - 3;
}
NOTE: You might wonder what the difference is between the method above and directly reading snakeCells from global variable. For example:
var snakeCells = ...;
// This is the INCORRECT way
// snakeCells is read from global variable, not passed as an argument
function getScore() {
return snakeCells.length - 3;
}
However, this is not a pure function, because getScore depends on a global variable, not an argument. In other words, because getScore depends on snakeCells, snakeCells must be an argument of the function.
Nevertheless, if the variable is a (const) function, then this is not a problem:
const SPAWN_CELLS = 3;
// Correct, because SPAWN_CELLS never changes
function getScore(snakeCells) {
return snakeCells.length - SPAWN_CELLS;
}
Snake movement logic
Similarly to the reasoning above, we can build the necessary logic for moving the snake.
For example, we can get the coordinates of the snake's head by taking the last element of snakeCells:
function getCurrentHead(snakeCells) {
return snakeCells[snakeCells.length - 1];
}
Then move the snake's head based on snakeDirection, we calculate newHead as the new position of the snake's head:
function getNewHead(currentHead, snakeDirection) {
if (snakeDirection == 'r') { // right
return { x: currentHead.x + 1, y: currentHead.y };
} else if (snakeDirection == 'l') { // left
return { x: currentHead.x - 1, y: currentHead.y };
} else if (snakeDirection == 'u') { // up
return { x: currentHead.x, y: currentHead.y - 1 };
} else if (snakeDirection == 'd') { // down
return { x: currentHead.x, y: currentHead.y + 1 };
}
}
But what if the snake's head goes out of the screen? Simple, we just need to check if the coordinate is negative, or if it has gone out of the maximum number of cells:
function wrapScreen(cell) {
// if x, y are out of screen, we bring it back to the opposite side
return {
x: cell.x < 0 ? grid-1 : (cell.x % grid),
y: cell.y < 0 ? grid-1 : (cell.y % grid),
};
}
Additionally, we also need a function to check if the snake's head is "biting" its body:
function isEatingSelf(snakeCells, newHead) {
// i = 1 is to skip the last cell at the snake's tail
for (let i = 1; i < snakeCells.length; i++) {
if (newHead.x == snakeCells[i].x && newHead.y == snakeCells[i].y) {
return true;
}
}
return false;
}
Now, we need a function to change snakeCells, by removing the last element and adding a new element (value taken from getNewHead):
// WRONG approach
function getNewSnake(snakeCells, newHead) {
snakeCells.shift(); // remove the element at the snake's tail
snakeCells.push(newHead); // add element at the snake's head
}
But why is the above approach incorrect? Because the shift and push functions will change the value of the snakeCells variable, which is an input variable.
IMPORTANT: In FP, a function should never directly change the value of an input variable. If it wants to change, it must create a copy
// CORRECT approach
function getNewSnake(snakeCells, newHead) {
const newSnake = [...snakeCells]; // create a copy
newSnake.shift(); // remove the element at the snake's tail
newSnake.push(newHead); // add next cell
return newSnake; // return the modified copy
}
In fact, we will only need to remove the element at the snake's tail if the snake is moving. If the snake eats food, we don't remove it, so the snake naturally grows longer:
function getNewSnake(snakeCells, newHead, isLonger) {
const newSnake = [...snakeCells]; // create a copy
if (!isLonger) {
// if we DON'T want the snake to grow longer, we remove the element at the snake's tail
newSnake.shift();
}
newSnake.push(newHead); // add next cell
return newSnake; // return the modified copy
}
Logic for food
Start with a simple function: check if the snake's head is eating food:
function isEatingFood(food, newHead) {
return newHead.x == food.x && newHead.y == food.y;
}
Now we need to create a random position for the food. In the "naive" approach above, people just randomly choose and if the coordinate happens to fall on a point on the snake's body, we take another point.
However, the "naive" approach will encounter problems as the snake grows larger: The total number of empty cells will decrease. At some point, the algorithm will have to randomly generate many points, but they all fall on cells containing the snake's body. The complexity will gradually increase to nearly O(N^2), and the game may lag.
To solve this problem, we will proactively find all empty cells on the screen. My following algorithm uses a dictionary, so it will only have a complexity of O(N*log(N)):
function getEmptyCells(snakeCells) {
const cells = {};
// list all possible cells on the screen
for (let y = 0; y < grid; y++) {
for (let x = 0; x < grid; x++) {
cells[`${x}_${y}`] = { x, y };
}
}
// remove cells occupied by the snake
for (const cell of snakeCells) {
delete cells[`${cell.x}_${cell.y}`];
}
// the remaining cells are empty cells, we convert the dictionary to an array
return Object.values(cells);
}
And then, we simply randomly choose one of the empty cells:
function getNewFood(emptyCells) {
// randomly get a cell from the array
return emptyCells[Math.floor(Math.random()*emptyCells.length)];
}
Logic for rendering
In graphics programming, the term "render" can be understood as the action of converting "data" into "display" form. Separating the logic of "data" and "display" helps make the software structure more differentiated, easier to pinpoint when errors occur.
For example in this problem, because all calculation logic uses coordinates by cell (values from 0 to 24), we need a render function to convert to pixel units and draw on the canvas:
function render(snakeCells, food) {
context.clearRect(0, 0, canvas.width, canvas.height);
// draw food
context.fillStyle = 'red';
context.fillRect(food.x*pixelPerCell, food.y*pixelPerCell, pixelPerCell - 1, pixelPerCell - 1);
// draw snake, cell by cell
for (const cell of snakeCells) {
context.fillStyle = 'green';
context.fillRect(cell.x*pixelPerCell, cell.y*pixelPerCell, pixelPerCell - 1, pixelPerCell - 1);
}
}
With pixelPerCell can be adjusted as desired without affecting the rest of the game logic.
Putting it all together
After assembling all the parts above, we get a logic that is easy to understand right from the code:
const currentHead = getCurrentHead(snakeCells);
const newHead = getNewHead(currentHead, snakeDirection);
// check if the snake is biting itself
if (isEatingSelf(snakeCells, newHead)) {
alert(`Game over! Score: ${getScore(snakeCells)}`);
snakeCells = null; // reset game
return;
}
if (isEatingFood(food, newHead)) {
// if the snake is eating food, extend it by one segment
snakeCells = getNewSnake(snakeCells, newHead, true);
const emptyCells = getEmptyCells(snakeCells);
food = getNewFood(emptyCells);
} else {
// if the snake is not eating food, we just move the snake
snakeCells = getNewSnake(snakeCells, newHead, false);
}
// call the render function to draw the snake and food on the screen
render(snakeCells, food);
To see the full code, click here
Try the demo below:
Go beyond
Not just stopping at "making it work". When you've mastered this way of thinking, there are many things you can apply to simplify complex software:
Testing
For testing, because functions always return a fixed set of values, you can test each function separately without having to "reconstruct" all the data variables. For example:
assert(isEatingFood({ x: 7, y: 8 }, { x: 7, y: 8 }) === true);
assert(isEatingFood({ x: 1, y: 2 }, { x: 7, y: 8 }) === false);
For functions with randomness like getNewFood, you can add a fake random function (which always returns a specific value), and make it an input of getNewFood
function realRandom() {
return Math.random();
}
function fakeRandom() {
return 0;
}
function getNewFood(emptyCells, randomFunction) {
return emptyCells[Math.floor(randomFunction()*emptyCells.length)];
}
// in game
getNewFood(emptyCells, realRandom);
// in test
getNewFood(emptyCells, fakeRandom);
Higher-order functions
Actually, I've just accidentally explained what a Higher-Order Function (HOF) is above.
The getNewFood function accepts another function, randomFunction, as an argument. Therefore, getNewFood is a higher-order function compared to randomFunction.
This idea is often widely used in array.map or array.filter, which accept a user-provided function as an argument.
Composed functions
This is quite a powerful idea in mathematics, but it wasn't until later that I knew it was applied in FP. For example, if you have two functions f(x) and g(x), then there exists a function h(x) that satisfies:
h(x) = (f ∘ g)(x)
This idea initially sounds meaningless, but it's actually very useful if f(x) and g(x) are both multi-step calculation functions (for example, two loops). Combining them might result in only one loop (might: only if you find a way to optimize).
A typical example of this optimization is in modern Machine Learning libraries. Sometimes, calculating matrix A multiplied by matrix B will require calculating the transpose of B. I'll take an example with the ggml library in C language:
// C = A multiplied by the transpose of B
C = ggml_mul_mat_slow(A, ggml_transpose(B));
Although this method works fine, in the long run it takes a lot of time, because 9 out of 10 times, users need to transpose before multiplying. So in reality, we can find a function ggml_mul_mat that directly accepts the argument as matrix B without transposition:
// f = ggml_mul_mat_slow
// g = ggml_transpose
// h = (f ∘ g) = ggml_mul_mat
// B doesn't need to be transposed anymore
C = ggml_mul_mat(A, B);
The special point is that inside ggml_mul_mat, it DOESN'T call ggml_transpose, but simply reverses the order of calculations. Therefore, the complexity is reduced by half, and the code runs much faster.
Conclusion
Through this article, we've explored Functional Programming, a programming thinking approach using mathematical functions.
In reality, there is no software that is purely FP or purely OOP. A powerful software is one that knows how to use the strengths of both FP and OOP.
For example, with the Angular library, classes are used to store state (view state), then when it needs to be displayed on the screen, the rendering process will be performed. This rendering process relies heavily on FP thinking.
Another example, when you play a game, actually the GPU's shader takes a function and performs that function in parallel on multiple data at once. This helps perform matrix calculations much faster than using CPU, allowing us to use 2D/3D graphics smoothly. These functions are all designed according to FP thinking.
I hope you find this article useful!
