Lisp: Infinite Prime Sieve
The code examples are written in a lisp I’m working on currently.
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.
Basic Syntax

Booleans:
true
andfalse

The empty List:
nil
or'()
or(list)
(they are pretty much equivalent) 
(def a 1)
defines a variable nameda
with a value of1
. 
(set! a 2)
overwritesa
with2

(fn (n div) (= 0 (% n div))
creates an anonymous function = with two argumentsn
anddiv
that checks ifn
is divisible bydiv
. 
(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 toif (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 theconsequent
of anif
etc. 
(inc n)
and(dec n)
are equiv. to(+ n 1)
and( n 1)

fst
andrst
(“first” and “rest”) are equivalent tocar
andcdr
in languages like Chicken Scheme and can be used to access the first and second element of acons
pair 
print
andputs
print values on the screen, without or with a newline
Special Forms
Given an expression like (puts (+ 1 2))
the ‘normal’ way (in a language that is not lazily evaluated)
to treat it
would be to evaluate all elements
(puts
=> some anonymous function, (+ 1 2)
=> 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))
(puts "n is odd")
(puts "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
,
(puts "n is odd")
to undefined
(because it does not return anything useful)
and (puts "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.
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 force
d, it remembers its value.
(def a 1)
(def promise (delay a))
(set! a 2)
(force a) ; => 2
(set! a 3)
(force a) ; => 2
and they still feel all so wasted on myself
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(?))
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
(puts (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))
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
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 ")
(puts 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:
(puts (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
.
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 n
th^{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