Lambda Calculus and Turing Machine

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:

  1. Functions are always anonymous. In JavaScript, the right side of const sum = (x, y) => x + y is the anonymous function expression (x, y) => x + y.
  2. 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 + y can 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.
  3. Functions are first-class, meaning that functions can be used as inputs to other functions, and functions can return functions.

Together, these features form a simple, yet expressive vocabulary for composing software using functions as the primary building block. In JavaScript, anonymous functions and curried functions are optional features. While JavaScript supports important features of lambda calculus, it does not enforce them.

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:



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s