State and Side Effects
State and Side Effects
Program state
The current state of a given program is composed of many different parts, some
of which are clear, others which are more opaque. The
most obvious state is the values of all the current variables in the scope. Take
this code snippet:
int y = 3; int x = 2; x = y;
Here we have two variables
x
and y
with initial values, when the last line
is executed the state is updated so that x
now has the value 3. We can clearly see this from the code given, but it can be less obvious when this code is hidden in a function:void my_cool_function(int& x, const int y) { x = y; } int main () { int y = 3; int x = 2; my_cool_function(x, y); }
Now imagine we have a global variable defined elsewhere that is updated by
my_cool_function
, this is not even passed into the function so it is even
more unclear that this is being updated. The global variable and function might
even be declared in a separate file and brought in via a #include
int z = 3; void my_cool_function(int& x, const int y) { x = y; z++; } int main () { int y = 3; int x = 2; my_cool_function(x, y); }
Finally, any interaction with the Operating System is yet another, even more
opaque, part of the current state. This includes memory allocations, and file
IO.
std::vector<BigType> data(1000); // do we have enough RAM available for this? ofstream myfile; myfile.open ("example.txt", ios::out); // does this file exist? Do I have write permissions? std::string line; std::getline(myfile, line); // did I open this for reading? std::getline(myfile, line); // Same call to getline, but result is different!
The main downside of having a state that is constantly updated is that it makes
it harder for us to reason about our code, to work out what it is doing.
However, the main upside is that we can use state to make calculations more
efficient, for example to sum up the values in a vector we use a single variable
sum
to hold the state of the computationstd::vector<int> data = {1, 2, 3, 4}; int sum = 0; for (const auto& x: data) { sum += x; }
Side Effect and Pure Functions
Functional computations only rely on the values that are provided as inputs to a
function and not on the state of the program that precedes the function call.
They do not modify data that exists outside the current function, including the
input data - this property is referred to as the immutability of data. This
means that such functions do not create any side effects, i.e. do not perform
any action that affects anything other than the value they return. A pure function is therefore the
computational version of a mathematical function.
For example: printing text, writing to a file, modifying the value of an input argument, or
changing the value of a global variable. Functions without side affects that
return the same data each time the same input arguments are provided are called
pure functions.
Pure Functions
Which of the following are pure functions? Can you explain why or why not?
int increment_and_return_x(const int& x) { return x + 1; } int increment_and_return_x(const int& x) { std::cout << "Incrementing x = " << x << std::endl; return x + 1; } void increment_x(int& x) { x += 1; } int one = 1; void increment_x(int& x) { x += one; }
Conway's Game of Life
Conway's Game of Life is a popular cellular automaton that simulates the
evolution of a two-dimensional grid of cells. In this exercise, you will
refactor a Python program that implements Conway's Game of Life. The basic rules of the game of life are:
- Any live cell with fewer than two live neighbors dies, as if caused by underpopulation.
- Any live cell with two or three live neighbors lives on to the next generation.
- Any live cell with more than three live neighbors dies, as if by overpopulation.
The code has a bug related to the improper management of the program
state, which you will fix. Refactor the code so that the
step
function is a pure function.#include <iostream> #include <vector> void step(std::vector<std::vector<int>>& grid) { int rows = grid.size(); int cols = grid[0].size(); for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { std::vector<int> neighbors = get_neighbors(grid, i, j); int count = 0; for (int neighbor : neighbors) { count += neighbor; } if (grid[i][j] == 1) { if (count == 2 || count == 3) { grid[i][j] = 1; } } else if (count == 3) { grid[i][j] = 1; } } } } std::vector<int> get_neighbors(const std::vector<std::vector<int>>& grid, int i, int j) { int rows = grid.size(); int cols = grid[0].size(); std::vector<std::pair<int, int>> indices = {{i - 1, j - 1}, {i - 1, j}, {i - 1, j + 1}, {i, j - 1}, {i, j + 1}, {i + 1, j - 1}, {i + 1, j}, {i + 1, j + 1}}; std::vector<int> neighbors; for (const auto& idx : indices) { int row = idx.first; int col = idx.second; if (row >= 0 && row < rows && col >= 0 && col < cols) { neighbors.push_back(grid[row][col]); } } return neighbors; } int main() { std::vector<std::vector<int>> grid = {{0, 0, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 0}}; step(grid); // Print the grid for (const auto& row : grid) { for (int cell : row) { std::cout << cell << " "; } std::cout << std::endl; } return 0; }
Benefits of Functional Code
There are a few benefits we get when working with pure functions:
- Testability
- Composability
- Parallelisability
Testability indicates how easy it is to test the function - usually meaning
unit tests. It is much easier to test a function if we can be certain that a
particular input will always produce the same output. If a function we are
testing might have different results each time it runs (e.g. a function that
generates random numbers drawn from a normal distribution), we need to come up
with a new way to test it. Similarly, it can be more difficult to test a
function with side effects as it is not always obvious what the side effects
will be, or how to measure them.
Composability refers to the ability to make a new function from a chain of
other functions by piping the output of one as the input to the next. If a
function does not have side effects or non-deterministic behaviour, then all
of its behaviour is reflected in the value it returns. As a consequence of
this, any chain of combined pure functions is itself pure, so we keep all these
benefits when we are combining functions into a larger program.
Parallelisability is the ability for operations to be performed at the same
*time (independently). If we know that a function is fully pure and we have got
*a lot of data, we can often improve performance by splitting data and
*distributing the computation across multiple processors. The output of a pure
*function depends only on its input, so we will get the right result regardless
*of when or where the code runs.
There are other advantageous properties that can be derived from the functional
approach to coding. In languages which support functional programming, a
function is a first-class object like any other object - not only can you
compose/chain functions together, but functions can be used as inputs to, passed
around or returned as results from other functions (remember, in functional
programming code is data). This is why functional programming is suitable for
processing data efficiently - in particular in the world of Big Data, where code
is much smaller than the data, sending the code to where data is located is
cheaper and faster than the other way round. Let's see how we can do data
processing using functional programming.
Key Points
- Program state is composed of variables' values, including those modified by functions and interactions with the Operating System.
- Functional computations rely only on input values, are immutable, and do not create side effects. Pure functions are testable, composable, and parallelizable.