sieve.py

import types

the_empty_stream = ()

def cons(x, y):
  return (x, y)

def cons_stream(x, y):
  assert isinstance(y, types.LambdaType)
  return cons(x, y)

def force(s):
  return s()

def head(x):
  return x[0]

def tail(x):
  return force(x[1])

def empty_stream(s):
  return s == the_empty_stream

def filter(pred, s):
  if empty_stream(s):
    return the_empty_stream
  elif pred(head(s)):
    return cons_stream(head(s), lambda: filter(pred, tail(s)))
  else:
    return filter(pred, tail(s))

def first(n, s):
  if n == 0 or empty_stream(s):
    return the_empty_stream
  else:
    return cons_stream(head(s), lambda: first(n-1, tail(s)))

def for_each(proc, s):
  if empty_stream(s):
    pass
  else:
    proc(head(s))
    for_each(proc, tail(s))

def print_stream(s):
  for_each(lambda x: print(x, end="\t"), first(100, s))
  print()

def integers_from(n):
  return cons_stream(n, lambda: integers_from(n+1))

def divisible(n, d):
  return n % d == 0

def sieve(s):
  return cons_stream(
    head(s),
    lambda: sieve(
      filter(
        lambda x: not divisible(x, head(s)),
        tail(s)
      )
    )
  )

integers = integers_from(1)
primes = sieve(integers_from(2))