3. Session 2 : Iterated Prisoners Dilemma - Declarative Programming - Functional Design Patterns#
3.1. Session Overview#
In this session you are asked to start devloping ideas and code for simulating Iterated Prisoners Dilemma (IPD) . As directed Session 1 you should of read an overview of IPD in Chapter 12 of Richard Dawkins book The Selfish Gene.
As a starting point I recommend that you sketch out how such a simulation might be formed from various smaller components, such as strategies, rounds (legs, matches), tournaments, and so on. Then you could start thinking about how to code a strategy, use it, and (importantly), share it with others so that they can “pit it” against their own strateg(ies).
I would like you to do this as part of a (somewhat uncharted) process of discovery. What kind of things might you discover ? Here are some ideas
How to break programming problems into smaller problems
How to decide what the smaller problems do
How do smaller problems compose together to solve bigger problems
How to describe code declarativley
How to reduce specific (but related) problems to a single generic one
How to write imperitave code to computational solve problems without introducing dependancies on other solutions
You may want to for definitions (in the context of computer programming) of some of the above terms.
The remainder of these notes are designed to provide an introduction to some basic concepts that might help you on your journey. They are in the form of generic patterns that serve as templates for generic solutions to a wide range of problems. They are drawn fron the functional school of programming - which means they should work (at least in part) in pretty much all modern programming systems.
Have fun !! And remember …
3.1.1. Premise 6#
Quality software is composed from many specialised instances of a few generic patterns.
“good software = small things, that do one thing well, combined with other small things, that know nothing of each other”
Anony Mouse - January 2026
3.2. Declarative and Imperative Programming#
3.2.1. Basic Concepts#
Wikipedia provides a good starting point for gaining an understanding of Declarative and Imperative programming and how they relate to eah other.
3.2.2. Notation#
As with pseudo code, and other ways of describing methods of computation, there is no standard notation associated with declarative programming. However, strong statically typed languages offer several good templates using the language syntax itself. Functional programming systems, such as prolog, haskell, ocaml, and f sharp, are particular good here since their syntax is very close to the traditional mathematical notation (see Premise 3 in Session 1).
3.2.2.1. Examples#
3.2.2.1.1. english#
f maps a list of integers and an integer to an boolean
3.2.2.1.2. mathematics#
\(f : \left[\mathbb{Z}\right] \rightarrow \mathbb{Z} \rightarrow \left\{ true,false \right\}\)
3.2.2.1.3. haskell#
f :: [Integer] -> Integer -> Bool
3.2.2.1.4. ocaml#
val f : [int] -> int -> bool
3.2.2.1.5. python#
from typing import List # needed to indicate a list
def f(x : List[int] , y : int) -> bool : ...
Feel free to use any of the above as you see fit, just try and be consistent when describing multiple things.
Personally, I find it useful to distinguish between functions
\(\left[\mathbb{Z}\right] \rightarrow \mathbb{Z} \)
and relations
\(\left[\mathbb{Z}\right] \times \mathbb{Z}\)
Why do think this might be ?
Also, feel free to do other things like introduce new types, for example
\(\mathbb{B} = \left\{true,false\right\}\)
3.2.2.2. Exercise#
Start using your own notation for declarative “whiteboard” programming. How does your notation allign with pythons notation ?
3.3. Functional Patterns#
Functional programming means thinking in terms of mathematical functions. Strict functional programming languages, such as Haskell, Idris, F#, OCaml, and scala provide abstractions for functions which a very similar to their mathematical counterparts. However, most programming languages do not do this so well. Does this mean that the idea of modelling our abstractions in terms of mathematical functions is inappropriate when using these languages ?
A basic assumption of this course is that, at least for many modern programming languages, this is not the case. The key to making this approach work is to understand the differences between a mathematical function and a function within the language being used, and then find effective ways of working around these differences.
What then are the minimal requirements of a programming language for it to be able to support the use of functional patterns ? The primary requirement is the availablity of Higher Order Programming.
3.4. Higher Order Programming#
Higher Order Programming perhaps sounds more impressive than it actually is. Put simply it means that functions and other “higher order” types can be passed to and returned from functions in the same way as more traditional data e.g. floating point numbers and strings.
3.4.1. Example#
from math import sin,pi
def g(f,x) :
return f(x)
g(sin,pi/6)
0.49999999999999994
3.4.2. Example#
def f(a) :
def g(x) :
return x + 2
return g if a == 1 else sin
f(2)(5)
-0.9589242746631385
Notice that in the second example a new function g is defined inside an enclosing function f.
When higher order programming is available most of the main functional design patterns can be implemented in some form.
3.5. Pattern 1 - Currying#
In mathematics a function \(f\) can be completely specified in terms of its graph \(\Gamma_{f}\). The graph is a (possibly infinite) set of ordered pairs, for example
\(\Gamma_{f} = \left\{ (1,1),(2,4),(3,9) \right\}\)
Conceptually the graph shows how to map the first element of a given pair to the second. This is emphasised through the notation \(f(1) = 1\) and \(f(3) = 9\) and so on.
3.5.1. Exercise#
Give a small example of a graph of function of the form \(f(x,y)\).
Write a function in python that implements it.
How many “arguments” does the mathematical function “take” ?
How many “arguments” does your python function “take” ?
So, mathematical functions map single entities to single entities. To make python functions behave in this way they can be curried. Here is an example.
Note - You may have to install the PyMonad library.
3.5.2. Example#
from pymonad.tools import curry
Define a curried function using curry from pymonad.tools
@curry(2)
def f(x,y) :
return x + y
The function can be used as normal …
f(2,3)
5
… but it can be used with a single argument to produce a new function of a single argument
g = f(2)
g(3)
5
Note - the @curry(2) notation is shorthand for
def f(x,y) :
return x + y
f = curry(2,f)
Currying allows a programmer to provide a way of adding extra parameters to a function whilst still allowing it to be Reused in other code. A strategy in an IPD simulation provides an excellent example of a use case for the curry pattern.
3.5.3. Exercise#
Try and use curried strategies in your IPD competition code.
3.5.4. Exercise#
Check you understand the concept of a decorator by applying curry directoy to your curried IPD strategy.
3.6. Pattern 2 - Partial Application#
Closely related to Currying, partial application accepts a function, freezes one or more of its arguments , and returns a new function with a reduced number of arguments. The frozen arguments are often referred to as the “bound” arguments or “bound” values.
3.6.1. Example#
def f(a,b,c) :
return (2**a)*(3**b)*(5**c)
f(2,3,2)
2700
from functools import partial
g = partial(f,b=3)
g(a=2,c=2)
2700
3.6.2. Exercise#
How does partial application differ from Currying ?
What effect does the position of the “bound” arguments have on the way the partially applied function is used ?
3.7. Pattern 3 - Composition#
3.7.1. Exercise#
Write a function compose which accepts two functions f and g and returns a function h where $\(h(x) = f(g(x))\)$
3.7.2. Solution#
def compose(f,g) :
def h(x) :
return f(g(x))
return h
def f(x) :
return 2*x
def g(x) :
return x + 2
h = compose(f,g)
print(h(3))
h = compose(g,f)
print(h(3))
10
8
3.7.3. A more versatile compose#
from functools import reduce # reduce is covered later in this session
def compose(*funcs):
return reduce(lambda f,g : lambda x : f(g(x)), funcs, lambda x : x)
h = compose(f,g,sin,g,f)
h(3)
5.978716493246764
3.8. Pattern 4 - Classes and Objects#
3.8.1. Motivating Problem#
Here is a simple function
def f(x) :
return 2*x
Now imagine you want to keep track of how many times this function gets used as part of a large program.
count = 0
for i in range(10) :
f(i)
count = count + 1
# ... lots more code
# ...
# somewhere else in your program
y = f(8)
count = count + 1
# ... lots more code
# ...
# somewhere else in your program
z = f(3)/2
count += 1
# ... lots more code
# ...
### and finally
print("f was called " + str(count) + " times")
f was called 12 times
3.8.1.1. Exercise#
What are the potential problems with this solution ?
Broadly speaking, how would you score this solution with respect to the 5Rs ?
3.8.1.2. Exercise#
Design an alternative approach counting the number of times f gets used.
Does your approach have any advantages over the original solution ?
How would you rate your solution with respect to the 5Rs
3.8.2. Closures, Classes, and Objects#
Consider the following function
def logger(f) :
count = 0
def call(x) :
nonlocal count
count += 1
return f(x)
def log() :
nonlocal count
return count
return call,log
3.8.2.1. Exercise#
How do you think the logger function might be used ?
How does using the logger function rate as a solution to the motivating problem ?
What problem(s) does using the logger function present ?
Can you modify the logger function to overcome this problem(s) ?
3.8.2.2. Solution#
call,log = logger(f)
for i in range(10) :
call(i) ## function gets used in the same way as the original
# ... lots more code
# ...
# somewhere else in your program
y = call(8)
# ... lots more code
# ...
# somewhere else in your program
z = call(3)/2
# ... lots more code
# ...
log()
12
3.8.3. Closures, Classes, and Objects#
The function logger is called a closure. It is a function. However, it is a function with extra information. The extra information is provided by the enclosing scope of the function, (in this case the extra information is the function f), within which the (nested) functions call and log are defined.
In general, a function that returns other functions is called a class, and the functions returned are called objects. If the objects have access to the data inside the scope of the class then they are closures. Note a closure is not a nested function, it is the object that corresponds to the nested function that is the closure.
A program that makes use of classes and objects employs the programming paradigm known as object based programming.
3.9. Pattern 5 - Memoisation#
Most implementations of functional patterns in non-functional programming systems make use of object based programming. Here is example.
def memoise(f) :
cache=dict()
def mf(x) :
nonlocal cache
if not x in cache :
cache[x] = f(x)
return cache[x]
return mf
3.9.1. Exercise#
Can you work out what this pattern is designed to do ?
Experiment with the following code to see what memoisation does.
def f(x) :
print("calling f")
return 2*x
y = f(3)
print(y)
y = f(3)
print(y)
calling f
6
calling f
6
mem_f = memoise(f)
y = mem_f(3)
print(y)
y = mem_f(3)
print(y)
calling f
6
6
3.9.2. Exercise#
Think of, and describe, some use cases for memoisation.
3.9.3. A more robust implementation of memoisation#
from functools import cache
@cache
def g(x,y) :
print("adding !!")
return x + y
g(1,2)
g(3,4)
g(1,2)
adding !!
adding !!
3
3.10. Pattern 6 - Map, Filter, Reduce#
Map, Filter and Reduce are conceptually strongly associated with each other so they are presented as a single “collective”” pattern.
3.10.1. Map#
Map is a higher order function that applies a function to each member in a sequence
\({\bf map} : (X \rightarrow Y) \times [ X ] \rightarrow [ Y ]\)
Pythons implementation of map returns an iterator type which can be used to construct a sequence of the required type from the iterator.
3.10.1.1. Exercise#
What do yo think the result of the following code will be ?
@curry(2)
def f(x,y) :
return x + y
list(map(f(3),[1,2,3,4,5]))
[4, 5, 6, 7, 8]
The application of the map pattern has several advantages over an imperative loop. Firstly, it can be composed with other functions. Secondly, since it is a function it can be curried over its first arguments to provide a “vectorised” form of the underlying function. And thirdly, it is readily parallelisable.
Note - You may have to install the multiprocess library for the following example to work.
#### setup a pool of processors
from multiprocess import Pool
p = Pool(4) # use 4 processors
list(p.map(f(3),[1,2,3,4,5])) # executes f in parallel
[4, 5, 6, 7, 8]
#### free up the processors
p.close()
It might be difficult to appreciate the above example since each call of the underlying function takes very little time to run.
3.10.1.2. Exercise#
Try running the following function using parallel map. How long do you expect it to take ?
@curry(2)
def f(t,x) :
from time import sleep
sleep(t)
return 3*x
3.10.1.3. Solution#
You might find this article useful.
p = Pool(5) # use 5 processors
results = list(p.map(f(5),[1,2,3,4,5,6,7,8,9,10,11])) # executes f in parallel
p.close
print(results)
[3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33]
3.10.2. Reduce#
Reduce is a higher order function that uses a binary operator to combine the values in a sequence into a single value.
\({\bf reduce} : (X \times X \rightarrow X) \times [ X ] \rightarrow X\)
Pythons implementation of reduce returns an iterator type which can be used to construct a sequence of the required type from the iterator.
3.10.2.1. Exercise#
Predict the result of running the following code.
from functools import reduce
def g(x,y) :
print(x,y)
return x + y
reduce(g,[4,3,2,1])
4 3
7 2
9 1
10
3.10.3. Filter#
The filter pattern removes elements form a sequence depending on the value of a predicate function.
\({\bf filter} : X \rightarrow \left\{true,false\right\} \times [X] \rightarrow [X]\)
Pythons implementation of filter returns an iterator type which can be used to construct a sequence of the required type from the iterator.
3.10.3.1. Exercise#
Predict the result of running the following code.
def h(a) :
return a > 5
list(filter(h,[1,2,3,4,5,6,7,8,9]))
[6, 7, 8, 9]
3.10.4. Combining Map, Reduce, and Filter#
The utility of map, filter, and reduce becomes very apparent when they are curried.
cmap = curry(2,map)
creduce = curry(2,reduce)
cfilter = curry(2,filter)
3.10.4.1. Exercise#
Predict the result of running the following code.
method = compose(creduce(g),cfilter(h),cmap(f(1)))
method([1,2,3,4,5,6,7,8,9])
6 9
15 12
27 15
42 18
60 21
81 24
105 27
132
3.10.4.2. Exercise#
Implement the above example using an imperative style (i.e. for loops, no composotion, no currying, ….
A parallel version of map can also be curried. For example.
@curry(3)
def pmap(f,cores,args) :
with Pool(cores) as p:
result = p.map(f, args)
p.close()
return result
3.10.4.3. Example#
The parallelised solution to the previous exercise then becomes
method = compose(creduce(g),cfilter(h),pmap(f(1))(5))
method([1,2,3,4,5,6,7,8,9])
6 9
15 12
27 15
42 18
60 21
81 24
105 27
132
You are invited to reflect on how concise and readable the previous example is given what it achieves. Notice how much more “declarative”” the actual code becomes once a functional approach is adopted.
“good software = small things, that do one thing well, combined with other small things, that know nothing of each other”
3.11. Practical Considerations#
As some of the examples above demonstrate, it is certainly possible to employ certain functional patterns using programming systems which, in themselves, do not have all the characteristics of a fully functional system. However, it is important to note certain limitations that arise in non-functional systems. In particular, most “fully” functional languages have the following
pure functions
immutable data structures
strong type systems
For now, the first two are the most important to consider.
3.11.1. Pure Functions#
What are pure functions ? A pure function does not modify any existing data or arguments. As a consequence they are like a mathematical functions in that they always give the same outputs for the same inputs, and they do not change anything when evaluated. For example, the following function is not pure.
3.11.1.1. Example#
def impure_function(X) :
X.append(1)
return X
X = [1,2,3,4,5]
print(X)
Y = impure_function(X)
print(Y)
print(X)
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5, 1]
[1, 2, 3, 4, 5, 1]
Not all languages behave in this way. For example, compare the following R version of the above function
pure_function <- function(X)
{
X <- c(X,5)
return(X)
}
X = list(1,2,3,4)
head(X)
Y <- pure_function(X)
head(Y)
head(X)
3.11.2. Immutability#
In most functional programming languages data is immutable. Once a value has been created and assigned to a variable it cannot be changed - ever !!
How can this possibly work ? Every time you need to change some data you have to have a function that takes the data and generates a modified copy of it - simples !!
But how can this possible be efficient ? Behind the scenes a full copy is not actually made, just a record of the modification and which parts of the program can see this modification. In fact, this is how the R version of pure_function works (the original data in the list will not have been copied). To achieve this, R uses a model called copy on write, or COW.
3.11.2.1. Exercise#
In this section, Map, Reduce, and Filter were described declaratively. Can you do the same for the other patterns ? Have a go at doing this for compose.
3.12. Directed Reading#
This session has introduced a lot of new programming ideas, patterns, and “paradigms”. It is probably too much to be able to understand in one session. However, we will be using the notes in this session quite extensivley in the sessions 3 and 4 as well. Consequently you should
Work through and study all of the different functional design patterns introduced in this session with view to appying at least some of them in your IPD simulation code during the course of the next two sessions.