YIELDER and GENERATOR (and thinking about Coroutines)

[hostilefork]

The stackless model so far has been built on a generic and comprehensible building block called a YIELDER. I thought I'd walk through it a little.

To understand YIELDER, first look at GENERATOR

I think a generator is pretty easy to understand. It is like a function, but instead of RETURN it has something called YIELD. Each time YIELD is called the generator gives back the result but is left in a suspended state, and the next call to the generator will pick up right after the YIELD:

counter: generator [
     let n: 0
     cycle [
          n: n + 1
          yield n
     ]
]

>> counter
== 1

>> counter
== 2

Generators are building blocks, meant to be used with functions

Generators don't take parameters. So if you want to parameterize them, you should combine them with a function. Imagine you wanted to be able to specify a bump amount for your counter:

make-counter: func [bump] [
     return generator [
         let n: 0
         cycle [yield n: n + 1]
     ]
]

>> counter: make-counter 5

>> counter
== 1

>> counter
== 6

>> counter
== 11

But functions aren't limited to being just "generator makers"...

For instance: functions can be generator wrappers, that actually delegate to the generator...or perhaps even destroy it and make new ones. Consider making a resettable counter, as @giuliolunati has in his GENERATE usermode generator:

 counter: func [/reset <static> n (0) gen (null)] [
     if reset [n: 0, return]
     return reeval gen: default [
         generator [
             cycle [yield n: n + 1]
         ]
     ]
 ]

 >> counter
 == 1

 >> counter
 == 2

 >> counter/reset

 >> counter
 == 1

 >> counter
 == 2

This gives a lot of flexibility in the design of generator interfaces. Considering the above example alone: what if you are in a situation where you think the counter/reset should have returned 1 instead of being a separate step that had no return result? Or maybe you think it should have returned what the last generator value was.

By making generators a "simplistic" building block, you're in control of these interface choices.

The YIELDER hybridizes with functions for efficiency

I said that generators don't have parameters or a function spec, but that is because they are a specialization of a version that does have a spec... called a YIELDER.

weird-print: yielder [x] [
    cycle [
        print ["Odd print:" x]
        yield ~
        print ["Even print:" x]
        yield ~
    ]
]

>> weird-print "Hello"
Odd print: Hello

>> weird-print "Weird"
Even print: Weird

>> weird-print "World"
Odd print: World

This isn't anything you couldn't have achieved with a function that wrapped a generator, that held that generator statically and then sub-dispatched to it. It's just cleaner and more efficient. (Since GENERATOR is implemented as yielder [] [...generator body...] it's kind of like the DOES analogue to FUNC.)

But this kind of gives you a sense of the parts box you have for building relatively efficient generator-type things.

[hostilefork]

Note: This 2020 post was updated in 2024, some things have changed.

---

Generators are related to coroutines...and I thought I knew what they were . But looking at examples of Python coroutines made me wonder exactly what the difference was, and what (if anything) they could do that yielders + wrapping functions could not.

So I thought I'd try translating a coroutine example.

Python3 Example

A top hit for Python coroutines is apparently https://www.geeksforgeeks.org/coroutine-in-python/. I now take it this is out of date, and Python3 looks to have a much more JavaScript/C# async/await type feel to it.

# Python3 program for demonstrating
# coroutine chaining

def producer(sentence, next_coroutine):
    '''
    Producer which just split strings and
    feed it to pattern_filter coroutine
    '''
    tokens = sentence.split(" ")
    for token in tokens:
        next_coroutine.send(token)
    next_coroutine.close()

def pattern_filter(pattern="ing", next_coroutine=None):
    '''
    Search for pattern in received token 
    and if pattern got matched, send it to
    print_token() coroutine for printing
    '''
    print("Searching for {}".format(pattern))
    try:
        while True:
            token = (yield)
            if pattern in token:
                next_coroutine.send(token)
    except GeneratorExit:
        print("Done with filtering!!")
        next_coroutine.close()

def print_token():
    '''
    Act as a sink, simply print the
    received tokens
    '''
    print("I'm sink, i'll print tokens")
    try:
        while True:
            token = (yield)
            print(token)
    except GeneratorExit:
        print("Done with printing!")

pt = print_token()
pt.__next__()
pf = pattern_filter(next_coroutine = pt)
pf.__next__()

sentence = "Bob is running behind a fast moving car"
producer(sentence, pf)`

(This does look like it's leading toward async/await, which as I mentioned is what the Python3 stuff looks like. As I shuffle around how this kind of producer/consumer pattern might be managed more legibly, I feel a resonance with the writeup of "What Color is Your Function". That author's conclusion seems like mine and maybe others which is that Go's channels and "goroutines" are probably a better answer than trying to emulate these other more bizarre coroutine examples.)

Ren-C Version of That Example

Here is what I put together, without changing names (just adding a couple of comments):

/producer: func [sentence [text!] next-coroutine [action?]] [
    let tokens: split sentence space
    for-each 'token tokens [
        next-coroutine token  ; Python says `next_coroutine.send(token)`
    ]
    next-coroutine null  ; Python says `next_coroutine.close()`
]

/pattern-filter: func [next-coroutine [action?] :pattern [text!]] [
    pattern: default ["ing"]

    return yielder [token [~null~ text!]] [
        print ["Searching for" pattern]
        while [token] [  ; Python does a blocking `token = (yield)`
            if find token pattern [
                next-coroutine token
            ]
            yield ~  ; yield to producer, so it can call w/another token
        ]
        print "Done with filtering!!"
        next-coroutine null
        yield:final ~
    ]
]

/emit-token: yielder [token [~null~ text!]] [
    print ["I'm sink, I'll print tokens"]
    while [token] [  ; Python does a blocking `token = (yield)`
        print token
        yield ~  ; yield to pattern-filter, so it can call w/another token
    ]
    print "Done with printing!"
    yield:final ~
]

/et: emit-token/
/pf: pattern-filter et/

sentence: "Bob is running behind a fast moving car"
producer sentence pf/

The output matches the example.

What's Different?

They're similar, though I think the Ren-C version is more elegant (modulo the YIELD:FINAL, which I think we may want to fix, but I'll discuss that in a minute.)

You'll notice that a key difference is that Python uses YIELD as a method of getting input.

while True:
    token = (yield)
    if pattern in token:
        next_coroutine.send(token)

This strikes me as... weird. The idea is that you "send" the generators what they will experience as the return value of their yield.

With a Ren-C yielder, you "send" it the argument just by calling it as a function...and that can be any number of arguments, received normally in the frame. Then the YIELD just gives you the opportunity to return a value to that call (which we don't need in this case).

It makes a lot more sense, because here you just think of it as a function that the next time you call it, will still be in the same state. YIELD is just morally equivalent to RETURN.

What's the YIELD:FINAL for?

So this is related to the idea that when you make a call to a generator and the body finishes, that typically means it has no generated value to give back... so it gives you a definitional raised error, that's the end signal. This is part of enabling a full-band generator result.

But when you're calling a coroutine as a value sink and not a value source, you don't want the last call you make to the sink to return a raised error. Because then you'd have to suppress the error at the callsite.

This does point to something a bit odd about YIELDER, which is that since you're passing them values, they are either not going to ever run out of values (and are just processing what you give them in a loop), or one of the values you pass them is a "close yourself" signal...and here we're using NULL. If there's more than one parameter, this means your close signal would have to have some kind of dummy values to those parameters.

I think this probably means that there needs to be a way to send this close signal without passing parameters. close next-coroutine/ may or may not be a good syntax for it.

But, then we have to ask what kind of a clean exception model this would give. One idea could be that if it's in a suspended state, then when it becomes unsuspended, then instead of returning the yielded value, it would return a raised error. If you needed to handle being closed out from under yourself, then reacting to that exception would be the place to do it.

However...if you didn't have any exception handling on your YIELD, then the CLOSE would result in an abrupt failure. Basically, you can only CLOSE yielders that are prepared to receive the message.

Subtle. Anyway, this wasn't a super huge priority in 2020...and it still isn't here in 2024... but it's interesting to look at, and keep in mind.

[hostilefork]

@hostilefork

That author's conclusion seems like mine and maybe others which is that Go's channels and "goroutines" are probably a better answer than trying to emulate these other more bizarre coroutine examples.

I took a day to tinker and see what I could manage to mock up Goroutines, standing on the shoulders of the stackless work.

Based on that, here's a reimagining of this sample in the style of Go:

producer: func [sentence [text!]] [ 
    let out: make-chan
    let tokens: split sentence space 

    go (func [] [
        for-next t tokens [  ; FOR-EACH is not stackless (yet), so...
            send-chan out t/1  ; ...FOR-EACH can't unwind when this blocks
        ]
        close-chan out
    ])

    return out
]
  
pattern_filter: func [in "channel" /pattern [text!]] [
    pattern: default ["ing"]
    print ["Searching for" mold pattern]

    let out: make-chan

    go (func [<local> token] [
        while [token: receive-chan in] [
            if find token pattern [
                send-chan out token
            ]
        ]
        close-chan out
        print "Done with filtering!!"
    ])

    return out
]

print_token: func [in] [
    print ["I'm sink, i'll print tokens"]

    let done: make-chan
    go (func [<local> token] [
        while [token: receive-chan in] [
            print [token]
        ]
        close-chan done

        print "Done with printing!"
    ])

    return done
]

  
let sentence: "Bob is running behind a fast moving car"

unfiltered: producer sentence
filtered: pattern_filter unfiltered
done: print_token filtered

receive-chan done

This replaces the idea of coroutines speaking to each other directly with the idea that they synchronize and communicate through "channels".

• The producer isn't itself a "coroutine" but an ordinary function that instantiates a goroutine, and returns a channel object that represents its stream of produced tokens.
• The filter also isn't a coroutine... again an ordinary function, but one that takes a channel as an input parameter...returns a filtered channel as an output. To get the filtered channel, it instantiates a goroutine whose job it is to take items from in and decide which ones to send to out.
• The printer once again is an ordinary function that creates a goroutine to dump out a channel that it receives.

You get the desired output:

Searching for "ing"
I'm sink, i'll print tokens
running
moving
Done with filtering!!
Done with printing!

This seems a much smarter path than trying to deal with a contortion of generators like "special yielding syntax"! Does it look clear?

Note: I didn't have to write it as functions that run goroutines and return channels... in fact, most examples you see in Go aren't styled this way. Instead the main code makes the channel and then calls go on a goroutine that is parameterized with the channels. But I thought it made responsibility clearer who was doing what, e.g. to have the producer both make the channel and close it--vs being given a pre-made channel to fill.

[hostilefork]

@hostilefork

As I shuffle around how this kind of producer/consumer pattern might be managed more legibly, I feel a resonance with the writeup of "What Color is Your Function". That author's conclusion seems like mine and maybe others which is that Go's channels and "goroutines" are probably a better answer than trying to emulate these other more bizarre coroutine examples.

So the Rebol-like Rye Language is written in Go, and actually has a go native.

There is a reddit post announcing some of the work, with this picture:

This area isn't something I'm currently focused on, but it will be interesting to see what the bridge between Go and a Rebol-like winds up being.