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

Covers OCR H446 1.2.4 Types of Programming Language · AQA 7517 4.12.2.1 Functional language programs · Eduqas A500QS 1.4 Principles of programming

Do this lesson in the simulator

Print it: worksheet (PDF) · answers (PDF) · as a web page

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.

Two calls of the impure count change a global and give 2 then 4; two calls of the pure count give 2 and 2impure: every call reads and changes countcount = 0count = 2count = 4call 1returns 2call 2returns 4pure: the answer depends only on the argumentsreadings, 40call 12readings, 40call 22nothing outside the function is read or changed
The impure count keeps its running total in a global, so the second call starts from 2 and returns 4. The pure count has no memory: the same arguments give 2 every time.

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.

With a list, log and backup name the same list, so appending changes both; with tuples, log names a new tuple and backup keeps the old onelist: backup = log, then log.append(15.0)tuple: backup = log, then log = log + (15.0,)logbackup[31.0, 51.0, 15.0]one list, changed in placebackup sees 15.0 toobackuplog(31.0, 51.0)(31.0, 51.0, 15.0)the old tuple, untoucheda new tuple
A name points at a value. With a list, both names point at one list, so a change through log shows up in backup. The tuple is never changed: + builds a new one, and only log moves to it.

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.

The loop overwrites one variable five times; total_of builds each answer from the call below itimperative: one variable, overwritten on every pass031.0+ 31.082.0+ 51.097.0+ 15.0141.0+ 44.0total after each pass: each new value replaces the one beforefunctional: each call makes a new value from the call below ittotal_of((31.0, 51.0, 15.0, 44.0))= 31.0 + 110.0 = 141.0total_of((51.0, 15.0, 44.0))= 51.0 + 59.0 = 110.0total_of((15.0, 44.0))= 15.0 + 44.0 = 59.0total_of((44.0,))= 44.0 + 0 = 44.0total_of(())= 0 base case
Both give 141.0. The loop gets there by changing total four times. total_of never changes anything: each call waits for the answer from a shorter tuple (green arrows) and adds its first item to 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.

distance() reads the world, speed_for decides, forward() changes the worlddistance()side effect: readspeed_for(cm)pure: decideforward(...)side effect: actcmspeededgeedgecoretested with no robot at all:speed_for(15.0) = 0speed_for(35.0) = 35speed_for(80.0) = 60
Only the two outer boxes touch the world. The decision in the middle is a pure function, so it can be checked with any numbers you like, and it gives the same answer every time.
# 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.

Imperative Functional
A program is statements run in order functions applied to values
Variables can be reassigned a name stands for one value
Data usually mutable immutable
Repetition loops that update state recursion and higher-order functions
Side effects anywhere avoided, or kept at the edges

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?