The functional paradigm

Side effects, pure functions and referential transparency, immutability and statelessness, with the robot's side effects kept at the edges.

A13.1Functional programmingA level20 min

In lesson A1.6 you met the idea of a programming paradigm, and wrote procedural and object-oriented programs. Both are imperative: a program is a sequence of statements that change the program's state, the values in its variables, one step at a time. This module is about a different paradigm. In functional programming a program is built from functions, in the mathematical sense: a function takes values in and gives a value back, and does nothing else. Languages built for it include Haskell, F#, Erlang and Clojure. Python is not a functional language, but it supports the style, so you can try every idea here in Python and compare it with Haskell.

A function, in the mathematical sense

In maths, a function like f(x) = 2x + 1 always gives the same result for the same argument. f(3) is 7 today, tomorrow and every time. It does not print anything, does not change anything, and does not depend on anything except x.

At GCSE, a Python function could do all sorts of things besides returning a value. Anything a function does apart from returning its result is a side effect:

• changing a global variable, or a variable outside the function
• changing an object or list it was passed
• printing, or reading input
• reading or writing a file
• reading a sensor or driving a motor

A function with no side effects, whose result depends only on its arguments, is a pure function. Pure functions are referentially transparent: a call can be replaced by its value without changing what the program does. If area(20, 30) is 600, then everywhere it is written you could write 600 instead.

count = 0

def count_clear_impure(readings, limit):
    global count
    for cm in readings:
        if cm > limit:
            count = count + 1
    return count

def count_clear_pure(readings, limit):
    return len([cm for cm in readings if cm > limit])

readings = (31.0, 51.0, 15.0, 44.0)
print(count_clear_impure(readings, 40), count_clear_impure(readings, 40))
print(count_clear_pure(readings, 40), count_clear_pure(readings, 40))

Run this in the simulator

The impure version prints 2 4: the same call gave two different answers, because it changed a global variable that the next call read. You cannot understand one call without knowing every call that happened before it. The pure version prints 2 2, every time, whatever else the program has done.

Immutability

In a functional language, data is immutable: once a value is made, it can never be changed. To "add" to a list you make a new list that has the extra item, and the old one is still there, unchanged.

Python's lists are mutable and its tuples are immutable, and the difference matters when two names refer to the same value:

log = [31.0, 51.0]
backup = log                 # the same list, not a copy
log.append(15.0)             # changes the one list both names refer to
print(backup)

log = (31.0, 51.0)
backup = log
log = log + (15.0,)          # a new tuple; the old one is untouched
print(backup, log)

Run this in the simulator

The first print shows [31.0, 51.0, 15.0]: changing log quietly changed backup too. With tuples, log + (15.0,) built a new tuple, so backup still holds (31.0, 51.0). Immutable data cannot be changed behind your back, by another part of the program or by another processor running at the same time.

Statelessness

An imperative loop works by changing a variable over and over: total = total + cm. A functional program has no assignment that changes a value; a name, once bound to a value, stands for that value for good. This is statelessness: there is no state that changes as the program runs. Instead of a loop that updates a variable, a functional program uses recursion, or the higher-order functions you meet in lesson A13.5.

readings = (31.0, 51.0, 15.0, 44.0)

# imperative: the state (total) changes on every pass
total = 0
for cm in readings:
    total = total + cm
print(total)

# functional: the total of a tuple is its first item plus the total of the rest
def total_of(xs):
    if xs == ():
        return 0
    return xs[0] + total_of(xs[1:])

print(total_of(readings))

Run this in the simulator

Both print 141.0. total_of never changes a variable: each call works on a smaller tuple, and each result is built from the result of the call below it.

In Haskell there is no assignment statement at all. This defines two functions:

double x = 2 * x
totalOf []     = 0
totalOf (x:xs) = x + totalOf xs

double 7 is 14. totalOf is written as two equations, one for the empty list and one for a list with a first item x and the rest xs. Haskell picks whichever equation matches. Writing n = 5 in Haskell defines n; a second line n = 6 in the same program is an error, not a change.

Where the robot fits

distance() is not a function in the mathematical sense: call it twice and you can get two different answers, because the world changed. forward() exists only for its side effect. A robot is all side effects. So a well-designed functional program keeps them at the edges: a thin outer layer reads the sensors and drives the motors, and everything in between is pure functions that turn readings into decisions.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def speed_for(cm):              # pure: the answer depends only on cm
    if cm < 20:
        return 0
    return min(60, int(cm))

cm = distance()                 # side effect: read the world
speed = speed_for(cm)           # pure decision
print("distance", cm, "speed", speed)
if speed > 0:
    forward(speed, distance=10) # side effect: change the world

Run this in the simulator

speed_for can be tested with any number you like, without a robot, and it will always give the same answer. That is the pay-off of the functional style.

Task: make it pure

The starter has two impure functions. Rewrite both as pure functions, with no global and nothing changed in place:

• count_clear(readings, limit): readings is a tuple of distances in cm (floats), limit a number of cm. It returns how many readings are greater than limit, and gives the same answer however many times it is called.
• add_reading(log, cm): log is a tuple of floats and cm a float. It returns a new tuple with cm added at the end, and leaves log exactly as it was.

The main program (keep it as it is) prints clear: 2 twice, then before: (31.0, 51.0, 15.0, 44.0) and after: (31.0, 51.0, 15.0, 44.0, 60.0). Write the functions in the stateless style: no global, no for or while loop (use recursion, as total_of does), and no append, extend or += anywhere.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

READINGS = (31.0, 51.0, 15.0, 44.0)

count = 0
def count_clear(readings, limit):
    global count
    for cm in readings:
        if cm > limit:
            count = count + 1
    return count

def add_reading(log, cm):
    log = list(log)
    log.append(cm)
    return tuple(log)

print("clear:", count_clear(READINGS, 40))
print("clear:", count_clear(READINGS, 40))
new_log = add_reading(READINGS, 60.0)
print("before:", READINGS)
print("after:", new_log)

Challenges

1. Write a pure function furthest(readings) that returns the largest reading, using recursion and no loop.
2. Which of these are pure: len, print, random.randint, abs, input, heading? Say why for each.
3. Write add_reading in Haskell, using ++ to join lists. Why does Haskell not need a separate "copy" step?