26th August 2023
In this blog post I hope to explain the most important programming paradigms a learning software engineer needs to know.
It is a subject which is very difficult for young software engineers to get their teeth into because there's loads of information available but it's very hard to put it into context and understand what it all means.
The challenges of programming von Neumann computers
Before we talk about solutions to problems, we need to understand what our problems are.
As (almost) all our computers are von Neumann computers so essentially the question is, what are the challenges of programming von Neumann computers?
There is a lot we could talk about here:
- control flow
- memory management
So that this blog-post does not turn into a book we will focus on the first two as these are the ones that affect all programmers. Both of these affect our ability to write code which is well structured and easy to reason about.
Problem 1: Jumping
Control flow (not to be confused with "flow control") is the way the execution sequence of the program is managed.
Fundamentally, von Neumann computers do this by jumping from one place to another. Indeed in early von Neumann computers the only control flow available was jump instructions (conditional or unconditional).
These jump instructions even found their way into many high-level programming languages in the form of GOTO.
However this causes the code to be an unreadable mess. Edgar Dijkstra wrote about this in the famous 1968 article Go To Statement Considered Harmful. However I will try to summarise it in one paragraph:
Essentially it makes the control flow extremely hard to reason about. Imagine you are looking at some code which is part of a larger program, and you want to know when this code will be executed. Since any other part of the program may "teleport" the control to anywhere at any time, you cannot answer that question without reading the entire program and anticipating every possible execution path.
Solutions to this problem were developed very early-on (1950s) with Procedural Programming and Structured Programming. Essentially we organise into blocks of code called procedures, which have a single entry and exit point, and these procedures call each-other. Once the procedure completes, control returns to the calling procedure.
This encourages a hierarchical program structure, so it is much easier to reason about how the program execution will proceed.
If you wonder what is the difference between Procedural vs Structural programming, you should research it but suffice to say that structural programming is a stricter subset of procedural programming which forbids GOTO in favour of modern control flow constructs such as if-else and looping.
Problem 2: Global mutable state
Alright so Procedural Programming and Structured Programming have solved our problems around control flow. But what about memory management?
von Neumann computers use a type of memory called "RAM" which stands for Random Access Memory. It means that any part of your program's code can access or modify any memory address at any time.
This results in us having "global mutable state".
This extreme flexibility can undermine some of the structure we introduced with Structured Programming.
For instance let's imagine we have a procedure which has variable behaviour depending on the contents of a memory address. Because that memory address could be modified at any time by any code anywhere in the program so it means you cannot know how that procedure will behave when it's called without reading the entire program and and anticipating every possible execution path.
So essentially we have a similar problem that we had with using jumps for control flow. So what's the fix for this?
We have three main levels of solution:
variables, scope and lifetimes, parameters, compound data structures
These concepts were introduced in the first high level programming languages and can be considered cross-paradigm.
- variables give names to memory addresses or data structures
- scope and lifetimes for variables essentially means we can have variables which are local to a procedure, which can't be accessed globally
- parameters allow us to pass variables into a procedure when we call it
- compound data structures provide convenient implementations of things like arrays etc
If we strictly use these features as much as possible, and avoid global state, this does clearly help, for these reasons:
- when we see a local variable definition we immediately know it will not be accessible to any other code (unless it is passed to the code with a procedure call)
- we can tell what data each procedure will be using
However, it does not solve all of our problems. This is because:
- if there are lots of parts of your program that need to interact with a certain piece of data, you just end up passing it as a parameter to every single procedure call, making it defacto global
- our data is still mutable so given the previous point, we haven't solved anything
OO (Object Oriented) programming
People make a big deal out of Object Oriented programming but I think it's often over-explained which makes it seem a lot more complicated than it is.
All you really need to understand is classes. Think of a class as a container which encapsulates data and behaviour together. A class contains:
- some private data structures which are not directly accessible outside the class
- some methods which are essentially procedures which are how other pieces of code interact with the class.
To put it in a single sentence it's a bag of procedures with cached data.
A class has an instantiation method which creates whatever internal data structures it has, and once it has been instantiated you have an object.
What problem does this solve? Well it allows us to control access to data. This is called Encapsulation. So for instance let's imagine we have a number but we want to ensure that it can only be incremented (not decremented) and it always has to be a prime number, we can make a class thus:
#!/usr/bin/env python3 class PrimeNumber: def __init__(self, start=2): """ Initialize the class with a prime number. If the given number isn't prime, it will find the next prime number. """ self.number = start while not self.is_prime(self.number): self.number += 1 def is_prime(self, n): """Check if a number is prime.""" if n < 2: return False for i in range(2, int(n**0.5) + 1): if n % i == 0: return False return True def view(self): """Return the current prime number.""" return self.number def increment(self): """Increment the number to the next prime number.""" self.number += 1 while not self.is_prime(self.number): self.number += 1
This can be super useful as sometimes you do want to associate certain behaviour with certain data.
However I would argue it doesn't actually do anything to solve the structural problems with our code. This class's methods can still be called from dozens of different places in our code, so it's potentially just another form of globally mutable state.
Furthermore a disadvantage of using OO as a program design philosophy (like in Java where you use classes for everything) is that every class potentially contains state so you end up with state in dozens of different places which creates a lot of cognitive load trying to understand where everything is.
Like OO, the definition of Functional Programming has changed over the years and means different things to different people. But I am not giving a history lesson or writing an enormous book, rather trying to explain things concisely so they can be understood. So I will define it for you thusly:
In Functional Programming we simply never mutate data.
- we do not re-assign variables, we just make new ones
- we do not add items to arrays. Rather we generate a new array which is a superset of the original.
Your procedures are now called functions, they (usually) take an input, and they return an output which is derived or modulated by the input. Please read about Pure functions.
What is the benefit of this?
Well it's not really the right question. Immutable data isn't just an enhancement which brings a set of benefits. It's a paradigm-shift which throws out all the problems of the old paradigm and introduces a whole load of new ones.
With Imperative Programming (the alternative to functional) it's like having a massive canvas (the RAM) with dozens of minions (the procedures) working on it.
With functional it's like a mathematical equation where data doesn't have a place but just moves between one expression to the next.
Therefore programming in a functional style is a completely different experience than Imperative Programming.
One massive advantage of Functional Programming is how it can help with parallel programming. Parallel Programming makes it (very) necessary to carefully manage your state, which we already do with functional programming.
The other advantage is we are adopting a style which encourages us to think carefully about what patterns we use. In Imperative Programming you don't have to think carefully about your patterns, you can just write code until you get the result you want.
Also anecdotally I have found that functional code is much easier to refactor that imperative code. Changing the structure of an imperative program tends to cause the whole thing to collapse the moment you move one piece. However in functional programming you can move things about at will (like re-arranging an equation in algebra).
The disadvantage of Functional Programming is that it is very abstracted from the reality of how the computers work.
The paradigm of the computer is Imperative Programming, and in Functional Programming we are relying heavily on the abstractions our high-level language provides to hide that fact.
This means that Functional Programming is not suitable for applications where you need to be close to the metal. For performance reasons or perhaps because you are coding a microcontroller.
What is the "best" programming paradigm
It is important to emphasise that different paradigms are useful for different things and there is no one "best" paradigm.
I think the reason Object Oriented gets so much hate is because it's massively overused and ends up in places it really doesn't belong.
People act as if Functional Programming is an alternative to OO but I am perfectly happy to use a mixture of both in one program.
I think a good programmer understands all the paradigms and knows what is the best situation to use each. There is a good video about that here.
Also there is an enormous amount of overlap between different paradigms. Most programming languages that are used for app development are very cross-paradigm. According to Wikipedia Java is generic, object-oriented, functional, imperative, reflective and concurrent.
There are around 70 programming paradigms listed on the Wikipedia page about programming paradigms, but you don't have to learn all of them.
IMO the most useful and accessible declarative languages are config management and IAC languages like Ansible and Terraform. You declare what result you want and the language figures out how to achieve it. These tools are designed for platform engineers rather than software engineers but if you plan to do any infrastructure work at-all you will find them useful.
Logic programming is used for solving mathematical and logic problems but isn't suitable for application development.
Clarification on memory protection
When I was talking about RAM and Global Mutable State earlier, one thing I didn't mention is that modern computers do have "memory protection" features to stop programs on a timesharing operating system accessing each-other's memory.
These features have been around since early mainframes from the 1960s.
Additional notes on functional programming
I am very biased as I love functional programming, so I want to include some extra notes around that paradigm.
One implication of functional is that since we are not mutating any existing data structures, data is being passed in both directions through the hierarchical structure of our control flow. Therefore it becomes very important how we manage our parameters, and document what parameters a function is expecting.
Also note that global state and function side-effects are not entirely avoidable. A database is essentially global state even if it's not part of your program. And function side-effects are required to interact with the outside world. But we try to keep the core of our program functional and compartmentalise the non-functional parts.
Do you need a functional language?
Functional Programming can actually be implemented as a discipline or self-enforced style on-top of many high-level programming languages. However languages which are designed for functional programming have a lot of benefits.
Firstly functional languages have a lot of performance optimisations particularly around recursion and data structures which help mitigate the problems with operating at such a high level of abstraction.
Secondly, because mutable state can't be entirely avoided, a functional language may provide certain tools to help us manage mutable state in a controlled way. For instance Clojure's Atoms and Refs provide controlled mechanisms to manage mutable state.
Thirdly, Functional Programming languages emphasise those patterns which work well with the functional approach. Like map, filter, reduce etc.