______________________________
INFINITE PRIME SIEVE IN LISP
Leon Rische
______________________________
[20170901 Fri 15:48]
Table of Contents
_________________
1. Setup
2. Basic Syntax
3. Special Forms
4. Promises
5. Lists and Streams
6. Working with Streams
7. Fibonacci Numbers
8. Filtering Streams
9. An Infinite Prime Sieve
1 Setup
=======
The code examples are written in a [lisp] I'm working on.
To try it out, clone the git repo, make sure rust is installed and run
`cargo run repl' to get an interactive REPL or `cargo run run
example.scm' to evaluate a file.
[lisp]
2 Basic Syntax
==============
 Booleans: `true' and `false'
 The empty List: `nil' or `'()' or `(list)' (they are pretty much
equivalent)
 `(def a 1)' defines a variable named `a' with a value of `1'.
 `(set! a 2)' overwrites `a' with `2'
 `(fn (n div) (' 0 (% n div))= creates an anonymous function = with
two arguments `n' and `div' that checks if `n' is divisible by
`div'.
 `(defn name (arg1 arg2) body)' is syntax sugar for `(def name (fn
(arg1 arg2) body))' and can be used to define named functions
 `(cons 1 2)' creates a *pair* of two values
 `(if test consequent alternative)' is equivalent to `if (test) {
consequent } else {alternative }' in other languages
 `(do expr1 expr2 ...)' evaluates each of the arguments and returns
the result of the last one. It can be used to do more than one thing
inside the `consequent' of an `if' etc.
 `(inc n)' and `(dec n)' are equiv. to `(+ n 1)' and `( n 1)'
 `fst' and `rst' ("first" and "rest") are equivalent to `car' and
`cdr' in languages like [Chicken Scheme] and can be used to access
the first and second element of a `cons' pair
 `print' and `println' print values on the screen, without or with a
newline
[Chicken Scheme]
3 Special Forms
===============
Given an expression like `(println (+ 1 2))' the 'normal' way (in a
language that is not lazily evaluated) to treat it would be to
evaluate all elements (`println' to a function reference, `(+ 1 2)' to
`3') and then apply the rest of the elements to the first.
This is good enough most times, but consider this example:
,
 (defn unless (test consequent alternative)
 (if test
 alternative
 consequent))
`
Looks pretty harmless, but what happens if we try to use it like this?
,
 (def n 5)
 (unless (= 0 (% n 2))
 (println "n is odd")
 (println "n is even"))
`
The result will be something like
,
 n is odd
 n is even
 => undefined (ignored by the repl)
`
With the 'normal' way of evaluating expressions, the first step would
be to evaluate `(= 0 (% n 2))' to `true', `(println "n is odd")' to
`undefined' (because it does not return anything useful) and `(println
"n is even")' to `undefined', too.
The remaining expression is `(if true undefined undefined)' and that
evaluates to `undefined'.
To avoid this, `unless' (and some other syntax constructs like `if',
`delay') must be implemented as *special forms*.
Simplified this means they are called with 'raw', unevaluated
arguments and can choose when (and if) to evaluate them themselves.
An implementation of `unless' as special form would need to evaluate
the test first and then, depending on the result, evaluate either the
consequent or the alternative.
4 Promises
==========
`delay' and `force' can be used to delay the evaluation of an
expression.
A naive implementation would be to `(defn delay (body) (fn () body))'
(just wrap an anonymous function around the body) and `(defn force
(promise) (promise))' (call the underlying lambda).
Because of the reasons described in the section above, this would not
work as intended, `delay' needs to be a special form.
One other idiosyncracy is that once a promise was forced, it remembers
its value.
,
 (def a 1)
 (def promise (delay a))
 (set! a 2)
 (force a) ; => 2
 (set! a 3)
 (force a) ; => 2
`
5 Lists and Streams
===================
In Lisp, *lists* are built by nesting `cons'.
`(list 1 2 3)' is just syntactic sugar for `(cons 1 (cons 2 (cons 3
'())))'.
*Streams* are lazy lists, their elements are computed on demand they
can be infinitely long.
Let's start with a simple example:
,
 (def ones (cons 1 ones))
`
This doesn't work because at the time the body `(cons 1 ones)' is
being evaluated, `ones' is not yet defined in the parent environment.
On the other hand,
,
 (def ones (cons 1 (delay ones)))
`
works perfectly fine, because the evaluation of `ones' in the `cons'
is being delayed until we actually access it (and evaluating `def' is
completed).
,
 (fst ones) ; => 1
 (rst ones) ; => promise(?), a promise that has not yet been evaluated
 (force (rst ones) ; => (1 . promise(?))
`
To keep the code as simple as possible, I added a special form
`(streamcons foo bar)' that is equivalent to `(cons foo (delay bar)'
and a method `(streamrst stream)'[1] that forces the `rst' of
`stream'.
,
 (def ones (streamcons 1 ones))
 (streamrst ones) ; => (1 . promise(?))
`
6 Working with Streams
======================
Before we continue, it would be nice to have some way to display
streams (up to some fixed, finite length).
,
 (defn streamprint (limit stream)
 (if (> limit 0)
 (do
 (println (fst stream))
 (streamprint (dec limit) (streamrst stream)))))
`
`streamprint' checks if the limit is greater than `0', prints the
`fst' of the stream and calls itself recursively with `(dec limit)'
(`limit  1') and the forced `rst' (`streamrst') of the stream.
,
 (streamprint 5 ones)
 ; 1
 ; 1
 ; 1
 ; 1
`
To do some more interesting things, we need ways to combine and
manipulate streams.
`streammap' creates a new stream with the results of applying `fun'
to the elements of `stream'.
,
 (defn streammap (fun stream)
 (streamcons
 (fun (fst stream))
 (streammap fun (streamrst stream))))
`
,
 (streamprint 4 (streammap inc ones))
 ; 2
 ; 2
 ; 2
 ; 2
`
,
 (defn streamcombine (fun s1 s2)
 (streamcons
 (fun s1 s2)
 (streamcombine fun (streamrst s1) (streamrst s2))))

 (defn streamadd (s1 s2)
 (streamcombine + s1 s2))
`
,
 (streamprint 4 (streamadd ones ones))
 ; 2
 ; 2
 ; 2
 ; 2
`
Still pretty boring, how about a stream of natural numbers (excluding
0)?
,
 (def naturalnumbers
 (streamcons
 1
 (streamadd naturalnumbers ones)))
 (streamprint 4 naturalnumbers)
 ; 1
 ; 2
 ; 3
 ; 4
 ; 5
`
This might be a little hard to understand, especially if you have
never worked with streams or lazy evaluation before.
,
 naturalnumbers = 1, (naturalnumbers[0] + 1), (naturalnumbers[1] + 1), ...
`
An alternative implementation that might be easier to understand:
,
 (defn naturalnumbersfrom (n)
 (streamcons
 n
 (naturalnumbersfrom (inc n))))

 (def naturalnumbers (naturalnumbersfrom 1))
`
7 Fibonacci Numbers
===================
The [Fibonacci Numbers] are defined as
 `(fib 0) = 0'
 `(fib 1) = 1'
 `(fib n) = (+ (fib ( n 1)) (fib ( n 2)))'
This is equivalent to adding the `fib' stream its `rst', a version of
itself that is shifted by one.
,
 0 1 1 2 3 5 8 13 ...
 + _ 0 1 1 2 3 5 8 ...
 = 0 1 2 3 5 8 13 21 ...
`
,
 (def fibs
 (consstream 0
 (consstream 1
 (streamadd fibs (streamrst fibs)))))

 (streamprint 10 fibs)
 ; 0
 ; 1
 ; 1
 ; 2
 ; 3
 ; 5
 ; 8
 ; 13
 ; 21
 ; 34
`
[Fibonacci Numbers]
8 Filtering Streams
===================
,
 (defn streamfilter (pred stream)
 (if (pred (fst stream))
 (streamcons
 (fst stream)
 (streamfilter pred (streamrst stream)))
 (streamfilter
 pred
 (streamrst stream))))
`
Filtering over streams is more involed than `map'.
If the result of `(pred (fst stream))' is true, we construct a new
stream with `(fst stream)' and the *delayed* result of filtering the
rest of the stream. Otherwise, we call `streamfilter' again with the
rest of the stream, skipping `fst'.
To better understand what is happening when forcing elements of the
filtered stream, let's build a stream that displays a message when one
of its elements is forced.
,
 (def debugstream
 (streammap
 (fn (n) (do (print "Forcing ")
 (println n)
 n))
 (naturalnumbersfrom 0)))
 ; Forcing 0
`
Only one line is being printed, the rest of the new stream will only
be evaluated when we need it.
,
 (defn ismultipleof (div)
 (fn (n) (= 0 (% n div))))

 (def multiplesoffive
 (streamfilter
 (ismultipleof 5)
 debugstream))

 (fst multiplesoffive) ; => 0
`
No new lines are being printed, the first element `0' is already a
multiple of `5'.
When we try to output more elements of the stream, something strange
happens:
,
 (println (fst (streamrst multiplesoffive)))
 ; Forcing 1
 ; Forcing 2
 ; Forcing 3
 ; Forcing 4
 ; Forcing 5
 5
`
`streamfilter' starts forcing elements of the stream until it finds
the next one that satisfies `pred', in this case `5'.
9 An Infinite Prime Sieve
=========================
The [Sieve of Erathosthenes] works by taking a list of numbers
(starting with 2), going to the first element, removing all its
multiples from the list (4, 6, 8, ...) and then repeating these steps
with the next elements in the list (first 3, then 5) over and over
again.
Once this process has reached the end of the list, only prime numbers
remain.
Based on `(naturalnumbersfrom 2)' we can use the same algorithm to
create a (infinite) stream of primes!
Start with removing all multiples of the first element from a stream:
,
 (defn isnotmultipleof (div)
 (fn (n) (!= 0 (% n div))))

 (defn removemultiplesoffirst (stream)
 (streamcons
 (fst stream)
 (streamfilter
 (isnotmultipleof (fst stream))
 (streamrst stream))))

 (streamprint 6 (removemultiplesoffirst (naturalnumbersfrom 2)))
 ; 2
 ; 3
 ; 5
 ; 7
 ; 9
 ; 11
 ; 13
 ; 15
 ; 17
 ; 19
`
We are nearly there, the first few numbers are already primes but `9'
is a multiple of `3', `15' is a multiple of `5', ...
What is missing is the next step of the algorithm, > ... and then
repeating these steps with the next elements in the list > (first 3,
then 5) over and over again.
,
 (defn removemultiplesoffirst (stream)
 (streamcons
 (fst stream)
 (removemultiplesoffirst
 (streamfilter
 (isnotmultipleof (fst stream))
 (streamrst stream)))))

 (def primes (removemultiplesoffirst (naturalnumbersfrom 2)))

 (streamprint 10 primes)
 ; 2
 ; 3
 ; 5
 ; 7
 ; 11
 ; 13
 ; 17
 ; 19
 ; 23
 ; 29
`
The change in the code was pretty minor but now
`removemultiplesoffirst' applies itself recursively to the new,
filtered stream, completing the prime sieve.
To make sure, we can define a method that returns the nth[2] element
of a stream and check agains a [list of primes].
,
 (defn streamnth (n stream)
 (if (= n 0)
 (fst stream)
 (streamnth (dec n) (streamrst stream))))
 (streamnth 49 primes)
 ; => 229, which is in fact the 50th prime
`
[Sieve of Erathosthenes]
[list of primes]
Footnotes
_________
[1] There is no need to have something like `streamfst', the `fst' of
the stream is not a promise.
[2] `(streamnth 49 primes)' is the 50th element of the stream because
it is 0indexed