In this series Eonics consultant Rutger van Velzen will lead us down the rabbit hole of Functional Programming. In this first part he provides us with a little historical background. Links to the other parts can be found at the bottom of this article. You can also dive into Rutger’s previous hack night on functional programming in Java.
Prologue
A few decades before the first electrical programmable computer was invented, mathematicians tried to solve the halting problem: can a theoretical machine that operates on mathematical instructions, figure out if a given calculation will stop within a finite time or simply go on forever?
In 1936, mathematicians Alonzo Church and Alan Turing used a completely different perspective to come up with the same answer to this very question. Both papers were released just a month after each other; both stating that it is not mathematically possible to prove if an instruction will halt within a finite time or not. Church’s work on Lambda calculus proved this with the use of functions, while Turing used the concept of an abstract machine, also known as a Turing Machine, that could read and write on an infinite amount of tape.
These two ways of looking at the same problem would continue to influence the programming paradigms until this very day. Watch excellent explanations of both paradigms by the YouTube channel Computerphile below:
Programming Paradigms
The first programming languages were tightly coupled to the way a CPU operates and used the fetch, decode, execute, and store cycle. This type of low level code quickly becomes difficult to maintain as an application grows larger or more complex. So naturally, a higher level of abstraction was added, a new programming language to make life easier. Not long after, we ended up with the so-called imperative paradigm. This was popular for a long time but rightfully brought down by one of the most famous Dutch computer scientist Edsger Dijkstra after this infamous critique on the goto operator: “Go To Statement Considered Harmful”.
Edsger Dijkstra, 1994 in Zurich
Imperative was replaced with a new paradigm, known as structured programming. No more jumping from one line to another, but it uses scopes instead. The if, else, and for code blocks we still use today. But even though structured programming was a big improvement, there was more to come.
Procedural programming was the next paradigm in line, taking structured programming as it is but adding… surprise surprise: procedures! You might know the same concept under names like routines, subroutines, or functions.
You can probably guess what comes next as we are coming closer to the current day and age. Object oriented programming added another level of abstraction by introducing the concept of objects; data structures with methods, similar to procedures but bound to the scope of the object. This is still the most common paradigm to this day.
Object Oriented programming has now mostly replaced procedural programming
Functional beginnings
There is something remarkable about the relation between Lambda calculus and the Turing machine. On the scale of abstraction, the Turing Machine sits at one end, where Lambda Calculus sits at the other. Two extremes, yet with lots in common: there is no problem one can solve that the other one cannot.
With every new programming paradigm, we seem to step further away from the physical machine and closer to pure abstractions. This pattern was spotted early on and led to the first functional programming language in 1958 called Lisp, arriving in the period where structured programming was the dominant paradigm. While Lisp was promising and kicked off the first area of machine learning, it was way ahead of its time and was not able to shift the dominant paradigm.
The GNU Emacs system uses Lisps and is still widely used
What also played a role is that with a functional programming style you use resources differently. It uses less resources from the CPU but much more memory instead. This was the late 60’s, so memory cost a dollar per bit, and this did not change much until the late 80’s.
Since memory is now plentiful and cheap, now is a better time than ever to start using a functional programming language. The machines are ready for it, but are we? Let’s find out more in part 2 of this series.
Functional programming: the complete series
New articles in this series will be added to this list as soon as they are published.
- Part 1: historical context
- Part 2: pure functions & lazy evaluation
- Part 3: first-class functions, higher-order function and deferred execution
- Part 4: coming soon!
For feedback, questions or comments feel free to drop Rutger an e-mail.
