Tromp's sieve

tromp_sieve.hvml

Y = λf (f (Y f))

(App n) = match n {
  0: λf λx x
  +: λf λx (App (/ n 2) λx(f (f x)) (match m = (% n 2) { 0: x; +: (f x) }))
}

B0 = λb0 λb1 b0
B1 = λb0 λb1 b1

cons = λx λxs λcons (cons x xs)
skip = λbs λf (bs λxλxs(cons B0 (f xs)))
keep = λbs λf (bs λxλxs(cons x  (f xs)))

// Slashers
S0 =   λfλp(skip p f)
SS = λsλfλp(keep p (s f))

sieve  = λs((Y (SS s)) (cons B1 (sieve (SS s))))
primes = (sieve S0)

Take = λn λxs match n {
  0: SNil
  +: (xs λxλxs (SCons (x '0' '1') (Take n-1 xs)))
}

Main = (Take 200 primes)

// S0 = λkλxλxs(P B0 (xs k))
// S1 = λkλxλxs(P x (xs (λxλxs(P B0 (xs k)))))
// S2 = λkλxλxs(P x (xs λxλxs(P x (xs (λxλxs(P B0 (xs k)))))))
// S3 = λkλxλxs(P x (xs λxλxs(P x (xs λxλxs(P x (xs (λxλxs(P B0 (xs k)))))))))

// primes = (pair B1 ((sieve (SS S0)) (Y (SS S0))))
// primes = (pair B1 ((pair B1 ((sieve (SS (SS S0))) (Y (SS (SS S0))))) (Y (SS S0))))
// primes = (pair B1 ((pair B1 ((pair B1 ((sieve (SS (SS (SS S0)))) (Y (SS (SS (SS S0)))))) (Y (SS (SS S0))))) (Y (SS S0))))

// sieve = (slash 1 (cons B1 (slash 2 (cons B1 (slash 3 (cons B1 (slash 4 (cons B1 ....