Alonzo Church, and Alan Turing 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:
append = s1 => s2 => s1 + s2 append('Hello, ')('world!')
You could represent it visually: