23 July, 2024

What is Functional Programming?

Explore Functional Programming by applying it to a real-world problem

What is Functional Programming?
Available in:
 English
 Vietnamese
Reading time: 17 min.
Table of content

    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
    • x and y are the coordinates of the snake's head
    • food contains the coordinates of the food
    • If the snake eats food, maxCells increases
    • If a button is pressed, dx and dy will change depending on whether the button is up, down, right or left

    Although this method works, it has the following problems:

    1. All coordinates use pixel units, but the actual coordinates of the snake are in cell units (one cell equals many pixels)
    2. 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:

    • x and y are the coordinates of the snake's head, but clearly cells already has this information
    • maxCells can be calculated by the length of cells, or cells.length
    • dx and dy can actually be replaced by a single variable snakeDirection, 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 occupies
    • snakeDirection: takes one of 4 values: up, down, right or left
    • food: 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!

    Want to receive latest articles from my blog?
    Follow on
    Related articles