Coroutines

The basic concept

A coroutine is a 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)

Sending data into a coroutine

A coroutine, that we can send data to, takes an additional argument. If this argument x is made optional, the coroutine may be used like an ordinary generator:

g = |a,b| fn*|x=null|
   for k in a..b
      yield [x,k]
   end
end

g(1,4).each(print)

# Output:
# [null, 1]
# [null, 2]
# [null, 3]
# [null, 4]

Now, let us send data into it:

i = g(1,2)
print(i("a"))
print(i("b"))
print(i("c"))
print(i("d"))

# Output:
# ["a", 1]
# ["b", 2]
# empty
# empty

It may be used this way:

i = g(1,4)
for x in "a".."z"
   y = i(x)
   if y==empty then break end
   print(y)
end

Or more elaborately:

for x in ("a".."z").map(g(1,4))
   print(x)
end

# Output:
# ["a", 1]
# ["b", 2]
# ["c", 3]
# ["d", 4]

Reaching the upper bound of the range fed into coroutine g(1,n) implicates the iterator to be exhausted too:

for x in ("a".."d").map(g(1,100))
   print(x)
end

# Output:
# ["a", 1]
# ["b", 2]
# ["c", 3]
# ["d", 4]

Coroutine calls

A coroutine is able to call another coroutine in such a way that only the control flow reaches it, but the call stack is not consumed, overcoming the otherwise limited recursion depth. We say, the coroutine yields to another coroutine. Moss does not allow such a kind of call directly. Nevertheless, it is possible in an indirect way using a device called trampoline.

The coroutine call

yield to coroutine with argv

will be written:

yield coroutine, argv

A standard example consists of a producer and a consumer, both yielding to each other mutually.

class Exit = {}

function exit(x=null)
   raise table Exit{value = x}
end

function produce()
   return fn*||
      while true
         s = input("# ")
         yield consume,[s]
      end
   end
end

function consume()
   return fn*|s|
      while true
         if s=="exit" then exit() end
         print("Obtained input: ",s)
         yield produce,[]
      end
   end
end

function call(f,argv,dispatch)
   try
      while true
         f,argv = dispatch[f](*argv)
      end
   catch e if e: Exit
      return e.value
   end
end

call(produce,[],{
   produce: produce(),
   consume: consume()
})

The trampoline is the main loop inside of call.

Coroutines are a good tool when it comes to implement a state machine. Furthermore, the given example may be regarded as such a machine. The construction is easily modified to give it a more natural shape for a state machine.

class Machine = {
   function call()
      f = self.entrance
      while true
         f = f(self;)
         if f is empty then break end
      end
   end
}

function new_state_machine()
   state = table Machine{
      function* produce()
         while true
            self.s = input("# ")
            yield self.consume
         end
      end,
      function* consume()
         while true
            if self.s=="exit" then break end
            print("Obtained input: ",self.s)
            yield self.produce
         end
      end
   }
   state.entrance = state.produce
   return state
end

state = new_state_machine()
state.call()