Coroutines

The basic concept

A coroutine is function that can be stopped at some state and resumed later. At its stop it yields a value.

An easy example:

g = || fn*||
  yield 1
  yield 2
  yield 1
  yield 4
end

This is used as follows:

> i = g()
> i(), i(), i(), i(), i()
[1, 2, 1, 4, empty]

> g().list()
[1, 2, 1, 4]

Generators

The following is a simple prime number test:

isprime = |n| (1..n).count(|k| n%k==0)==2

We can make it a little bit faster:

isprime = |n| n>1 and (2..).until(|k| k*k>n).all(|k| n%k!=0)

Now we want to state a function that filters elements from an iterable object by a given predicate p.

Iterable.filter = fn|a;p|
  y = []
  for x in a
    if p(x)
      y.push(x)
    end
  end
  return y
end

Let us test it out:

> (1..20).filter(isprime)
[2, 3, 5, 7, 11, 13, 17, 19]

But what if we want to calculate the first 10 prime numbers? One could provide a test range with upper bound, large enough, and take 10 of them afterwards:

> (1..100).filter(isprime).list(10)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

But the more primes we want, the larger this upper bound has to be. The problem is, that we must know how large it is in before. For prime numbers there are mathematical results. To be more precise, we would need to invert the prime number counting function π(n). This means we want to solve the equation π(n)=10. A known mathematical result in case of n≥17 is

n/ln(n) < π(n).

By transitivity of inequalities we have

a < π(n) and 10 ≤ a implies 10 < π(n)

for all a. We place in a:=n/ln(n) and obtain

10 ≤ n/ln(n) implies 10 < π(n).

The first such n is 36 with π(36)=11.

This was somewhat complicated, and there are mathematical problems that are much more complicated. In general, we simply don't know how large such a range has to be.

The solution is, not to know the range in before. In order to do that, we use a coroutine.

Iterable.filter = |a;p| fn*||
  for x in a
    if p(x)
      yield x
    end
  end
end

Let us test it out:

> (1..).filter(isprime).list(10)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

The prime numbers will be printed instantly:

for p in (1..).filter(isprime)
  print(p)
end

Or for convenience:

(1..).filter(isprime).each(print)