It’s nearly two years since I wrote anything on this series – or anything else, so I think it is time to resurrect this blog.
This post will be the last post discussing the traditional Lambda Calculus. We will be using the Lambda Calculus to find lists of primes using the Sieve of Eratosthenes. If you are unfamiliar with the Sieve of Eratosthenes, here is how it works.
- First create a list of consecutive numbers, starting with 2. For example: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
- The first number in the list is a prime number. Add it to the list of primes and cross it and all of its multiples off of your unsieved list. Now we have: primes = 2; unsaved = 3, 5, 7, 9, 11
First create a list of consecutive numbers, starting with 2. Call it your “unsieved” list. Create a second list called “primes” which is empty.
Take the first number from the unsieved list and add it to the primes list. Cross it and all of its multiples off of the unsieved list.
Repeat the previous step until the unsieved list is empty.
Let’s try it with the above list of numbers
Unsieved: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
Primes: <Empty>
The first number in Unsieved is 2, so add it to Primes
Primes: 2
Remove 2 and all its multiples from Unsieved
Unsieved: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
This gives us
Primes: 2
Unsieved: 3, 5, 7, 9, 11
The next number in Unsieved is 3, so add it to Primes and remove it and all of its multiples from Unsieved.
Primes: 2, 3
Unsieved: 5, 7, 11
It should be fairly obvious now that we are going to end up with 2, 3, 5, 7, 11 in our primes list.
One subtle point that a lot of people miss when implementing this algorithm is how to determine if a number is a multiple of a prime. Many people will divide each number in unsieved by the prime and check if the remainder is zero. However, this is cheating. The Sieve of Eratosthenes only uses addition. We find the multiples of each prime simply by doing repeated addition. Any implementation that uses division or modulus or remainder, or even multiplication is wrong.
Let’s see what this looks like in the Lambda Calculus
let sieve = Y (λf.λl.isEmpty l nil (cons (head l) (f (filterMultiples (head l) (head l) l))))That looks pretty simple but it’s actually quite opaque. Firstly, it uses the Y combinator to achieve recursion. The first parameter f represents the seive function itself. The second parameter l represents the unsieved list.
If l is empty, we just get back an empty list. This should be obviously correct – an empty list of numbers contains no primes.
If l is not empty, we construct a new list whose head is the head of l and whose tail is
f (filterMultiples (head l) (head l) l)
Remember f is a placeholder for sieve itself in the Y combinator. So this runs sieve on
filterMultiples (head l) (head l) l
filterMultiples is a function that takes three arguments:
- a number
n - a “step”
s - a list
l
It removes n from the list l, then it recursively removes n + s from what’s left off l, then n + s + s and so on. Here’s its definition.
let filterMultiples = Y (λf.λn.λs.λl.isEmpty l nil (λlistHead.λlistTail.lt listHead n (cons listHead (f n s listTail)) (gt listHead n (f (sum n s) s l) (f (sum n s) s listTail))) (head l) (tail l))
Again it uses the Y combinator to achieve recursion. Again, f is a placeholder for the function itself.
It first tests to see if the list is empty. If it is, it just returns an empty list – job done.
Then there is a three way choice. If the list’s head is less than n, then it needs to be in our final returned result along with the result of
filterMultiples n s (tail l)
If the list’s head is greater than n, we need to return the filter on n + s, s and the list.
filterMultiples (sum n s) s l
There’s also a function called makeList which just creates a list of consecutive numbers to act as our unsieved list.
Putting it all together, we get the following:
> sieve (makeList 2 7)
3952759 reductions in 52.66050775 = 75061.1638377148 reductions per second
: λl.l 2 (λl.l 3 (λl.l 5 (λl.l 7 (λl.true))))
It’s quite slow but it works. We have, just using the principle of beta reduction, built a function that does something fairly sophisticated. The Lambda Calculus is quite powerful despite its simplicity. In fact, it is provably Turing Complete and I think it is a cleaner, more elegant abstraction of computation than the more famous Turing Machine.
The code used to create the sieve program is tagged 3.5.0. The definitions are in defannot.txt.
Sincere Flattery 