The Rise and Fall and Rise of Functional Programming (Composing Software)
<< Start over at Part 1 | Next >
When I was about 6 years old, I spent a lot of time playing computer games with my best friend. His family had a room full of computers. To me, they were irresistible. Magic. I spent many hours exploring all the games. One day I asked my friend, “how do we make a game?”
He didn’t know, so we asked his dad, who reached up on a high shelf and pulled down a book of games written in Basic. So began my journey with programming. By the time public school got around to teaching algebra, I already knew the topic well, because programming is basically algebra. It can be, anyway.
The Rise of Functional Programming
In the beginning of computer science, before most of computer science was actually done on computers, there lived two great computer scientists: Alonzo Church, and Alan Turing. They produced two different, but equivalent universal models of computation. Both models could compute anything that can be computed (hence, “universal”).
Alonzo Church invented lambda calculus. Lambda calculus is a universal model of computation based on function application. Alan Turing is known for the turing machine. A turing machine is a universal model of computation that defines a theoretical device that manipulates symbols on a strip of tape.
Together, they collaborated to show that lambda calculus and the turing machine are functionally equivalent.
Lambda calculus is all about function composition. Thinking in terms of function composition is a remarkably expressive and eloquent way to compose software. In this text, we’re going to discuss the importance of function composition in software design.
There are three important points that make lambda calculus special:
const sum = (x, y) => x + yis the anonymous function expression
(x, y) => x + y.
- Functions in lambda calculus only accept a single input. They’re unary. If you need more than one parameter, the function will take one input and return a new function that takes the next, and so on. The n-ary function
(x, y) => x + ycan be expressed as a unary function like:
x => y => x + y. This transformation from an n-ary function to a unary function is known as currying.
- Functions are first-class, meaning that functions can be used as inputs to other functions, and functions can return functions.
The classic function composition takes the output from one function and uses it as the input for another function. For example, the composition:
f . g
Can be written as:
compose2 = f => g => x => f(g(x))
Here’s how you’d use it:
double = n => n * 2
inc = n => n + 1
compose2() function takes the
double function as the first argument, the
inc function as the second, and then applies the composition of those two functions to the argument
3. Looking at the signature of
3. The function call,
compose2(double)(inc)(3), is actually 3 different function invocations:
- The first passes
doubleand returns a new function.
- The returned function takes
incand returns a new function.
- The next returned function takes
f(g(x)), which is now
3and gets passed into
8gets returned from the function.
When software is composed, it can be represented by a graph of function compositions. Consider the following:
append = s1 => s2 => s1 + s2
You could represent it visually:
Lambda calculus was hugely influential on software design, and prior to about 1980, many very influential icons of computer science were building software using function composition. Lisp was created in 1958, and was heavily influenced by lambda calculus. Today, Lisp is the second-oldest language that’s still in popular use.
I was introduced to it through AutoLISP: the scripting language used in the most popular Computer Aided Design (CAD) software: AutoCAD. AutoCAD is so popular, virtually every other CAD application supports AutoLISP so that they can be compatible. Lisp is also a popular teaching language in computer science curriculum for three reasons:
- Its simplicity makes it easy to learn the basic syntax and semantics of Lisp in about a day.
- Lisp is all about function composition, and function composition is an elegant way to structure applications.
- The best computer science text book I know of uses Lisp: Structure and Interpretation of Computer Programs.
The Fall of Functional Programming
Somewhere between 1970 and 1980, the way that software was composed drifted away from simple algebraic math, and became a list of linear instructions for the computer to follow in languages like K&R C (1978) and the tiny BASIC interpreters that shipped with the early home computers of the 1970s and early 1980s.
In 1972, Alan Kay’s Smalltalk was formalized, and the idea of objects as the atomic unit of composition took hold. Smalltalk’s great idea about component encapsulation and message passing got distorted in the 80s and 90s by C++ and Java into a horrible idea about inheritance hierarchies and is-a relationships for feature reuse.
Even though Smalltalk was a functional OOP language, when C++ and Java took over mindshare, functional programming was relegated to the sidelines and academia: The blissful obsession of the geekiest of programming geeks, professors in their ivy towers, and some lucky students who escaped the Java force-feeding obsession of the 1990s — 2010.
For most of us, creating software was a bit of a nightmare for 30 years. Dark times. ;)
Note: I learned to code with Basic, Pascal, C++, and Java. I used AutoLisp to manipulate 3D graphics. Only AutoLisp is functional. For the first several years of my programming career, I didn’t realize functional programming was a practical option outside the realm of vector graphics programming.
The Rise of Functional Programming
Functional Programming Has Always Been Alive and Well
In spite of this tongue-in-cheek stab at popular languages, functional programming has always been alive and well. Lisp and Smalltalk were among C’s biggest competitors in the industrial landscape of the 1980s and 1990s. Smalltalk was a popular enterprise software solution at fortune 500 companies including JPMorgan Chase, and Lisp was used at NASA JPL to program Mars rovers.
Lisp was and is still used at Stanford Research Institute (SRI) for artificial intelligence and bioinformatics research. (SRI is where the technology behind Apple’s SIRI virtual assistant was developed). YCombinator, one of the most influential venture capital firms in Silicon Valley was cofounded by Paul Graham, who is an influencer in the Lisp community. The popular tech news site, Hacker News was written in Ark, a dialect of Lisp.
Clojure, a Lisp dialect, was created by Rich Hickey in 2007 and quickly gained popularity and use at major tech companies including Amazon, Apple, and Facebook.
Erlang is a popular functional programming language developed at Ericsson for use in telephone exchanges. It’s still used in mobile networks by T-Mobile. Amazon uses Erlang for cloud technologies including SimpleDB and Elastic Compute Cloud (EC2).
He spends most of his time in the San Francisco Bay Area with the most beautiful woman in the world.