Converting callback result stream to iterator/generator/coro

C programming, build, interpreter/VM.
Target audience: MicroPython Developers.
Post Reply
pfalcon
Posts: 1155
Joined: Fri Feb 28, 2014 2:05 pm

Converting callback result stream to iterator/generator/coro

Post by pfalcon » Sat Jan 17, 2015 3:33 pm

This is intended to be continuation of sub-thread in ESP8266 porting ticket:
https://github.com/micropython/micropyt ... t-65945634 . I didn't continue it at that time, because the concepts are not exactly well-known and familiar, and while intuitively "it should work", the intuition may be wrong or missing some details, and the devil is in these details.

So, to clarify again, the talk is NOT about saving C stack and stuff. That way is obviously not scalable for embedded usage. The talk is about switching precisely calculated value stacks of Python functions.

As initial data, there's

Code: Select all

wifi.scan(callback)
, which schedules a wifi scan, returns immediately, and then calls "callback" as results for each individual AP available (yes, let's define it in such way).

What we'd like to achieve is to transform it into following usage, preferrably with native C means:

Code: Select all

for i in wifi.iterscan():
     print(i)

General intuitive idea to achieve that is to have "wifi.scan(lambda v: (yield v))". Well, that intuitive idea is immediately wrong, because in Python, a function with yield is a generator function, calling it produces generator. So, callback above will just produce void instances of generators. Even if that wasn't the case, Python allows to yield only from generator itself, not from any functions a generator calls (in particular, not from callback function).

Well, instead of using yield statement, let's use .send() function. Common sense interpretation of coroutine theory ;-) says that "yield v" is equivalent to "caller.send(v)". There're however more questions like which generator to send to. And thinking about it, it's only in formal theory yield and .send equivalent, with asymmetric Python coroutines, yield is like return and send is like call, and supporting iteration, generator should "return" values, not try to start another iteration of upstream receiver.

So, multiple deadends. Let's simplify task to convert just following simple Python function:

Code: Select all

def f(cb):
    i = 0
    while 1:
        cb(i)
        i += 1
So, any attempt to convert that to iterator in Python using appropriate callback appear to fail. What's more disappointing is that it's possible in obvious way in Lua:

Code: Select all

function f(n, cb)
    for i = 1, n do
        cb(i)
    end
end


f(10, function (i) print(i) end)

function iter_f(n)
    return coroutine.wrap(function ()
        f(n, coroutine.yield)
    end)
end

for a in iter_f(5) do
    print(a)
end
So, differences between Lua and Python: coroutine.yield is just a normal function, not a special form. So, Lua requires explicit conversion of a function to a coroutine with coroutine.wrap(). But most importantly, Lua allows to yield in recursively called functions. That's actually primary trait - Lua allows to yield from called functions, and then it allows to use yield anywhere (including in callbacks), which saves from the need to know whom to .send value instead of yield with implicit destination.
Awesome MicroPython list
Pycopy - A better MicroPython https://github.com/pfalcon/micropython
MicroPython standard library for all ports and forks - https://github.com/pfalcon/micropython-lib
More up to date docs - http://pycopy.readthedocs.io/

pfalcon
Posts: 1155
Joined: Fri Feb 28, 2014 2:05 pm

Re: Converting callback result stream to iterator/generator/

Post by pfalcon » Sat Jan 17, 2015 4:00 pm

Thinking more about it, there's some difference between simple f() above and original wifi.scan(). With f(), we start up iteration by calling the function itself. It's not like that with wifi.scan(cb). We call from Python into scan(), and it return backs. But then "cb" is never called from Python - it's always called from outside. So, I don't think that even Lua can abstract iteration for such function - there's simply no notion to start iteration upon - .scan() just schedules would-be iteration, but it's not explicitly present to pull values from. And iteration is explicitly a pull-generation. However with wifi.scan(cb) we have push-generation. On low-level, it means that C stack when calling wifi.scan() is different from when calling cb. And Lua's coroutine implementation of course doesn't switch C stacks. So, while Lua implementation appears to be more powerful, in the end it's still not enough to implement arbitrary control flow transformations.


And note that not allowing yields in recursively called functions, unless they are, well, explicitly allowed is actually feature and design goal of Python coroutine implementation. The problem with such yields is that user may never know when context switch may occur - literally, it may happen on every function call. That means that user either have to overinsure with synchronization/locking or risk hard to debug inconsistent shared state updates. In other words, coroutines implemented in such way have many drawbacks of pre-emptive threads, while coroutines are usually used exactly to avoid them.
Awesome MicroPython list
Pycopy - A better MicroPython https://github.com/pfalcon/micropython
MicroPython standard library for all ports and forks - https://github.com/pfalcon/micropython-lib
More up to date docs - http://pycopy.readthedocs.io/

pfalcon
Posts: 1155
Joined: Fri Feb 28, 2014 2:05 pm

Re: Converting callback result stream to iterator/generator/

Post by pfalcon » Sat Jan 17, 2015 4:23 pm

So, where do we end with actual tasks we have?

So, we have callback-taking function:

Code: Select all

def f(cb):
    i = 0
    while 1:
        cb(i)
        i += 1
Let's intoduce helper:

Code: Select all

def feed(prod, cons):
    c = cons()
    next(c)
    prod(lambda x: c.send(x))
Then we can "iterate" over orignal f in following way:

Code: Select all

def pr():
    while 1:
        v = yield
        print(v)

feed(f, pr)

That's instead of what we wanted to achieve originally:

Code: Select all

for v in make_iter(f):
        print(v)
Granted, syntactic difference is obvious. But semantically, they're pretty close. We could make a decorator an it would be:

Code: Select all

@yield_from_callback(f)
def pr():
    while 1:
        v = yield
        print(v)
Then the only difference is essentially the need to define a function. But that's crucial enough difference - the original motivation for all this work is to avoid "callback mess". Granted, we got rid of explicit callbacks. But there's still "function mess". But there doesn't seem to be a way to do away with that with "thin" abstractions - after all, originally there's a callback which gets passed values from different context, and the way to have different context is to have different functions.

It should be possible to capture context differences at another level, and have more continuous context for user function - at the expense of some additional overhead of routing results of different context into single user context. That would be asyncio-like event loop, and how to implement it for esp8266 port would be another good thing to consider.
Awesome MicroPython list
Pycopy - A better MicroPython https://github.com/pfalcon/micropython
MicroPython standard library for all ports and forks - https://github.com/pfalcon/micropython-lib
More up to date docs - http://pycopy.readthedocs.io/

pfalcon
Posts: 1155
Joined: Fri Feb 28, 2014 2:05 pm

Re: Converting callback result stream to iterator/generator/

Post by pfalcon » Sat Jan 17, 2015 4:27 pm

Questions:

1. Rebuttal of the claim that converting callback to generator is generally not possible with Python.
2. Otherwise, what changes to do to Python semantics and uPy implementation to make to support that.
3. What other cute changes can be made so uPy supported more general coroutines (essentially turning it into Stackless MicroPython).
Awesome MicroPython list
Pycopy - A better MicroPython https://github.com/pfalcon/micropython
MicroPython standard library for all ports and forks - https://github.com/pfalcon/micropython-lib
More up to date docs - http://pycopy.readthedocs.io/

pfalcon
Posts: 1155
Joined: Fri Feb 28, 2014 2:05 pm

Re: Converting callback result stream to iterator/generator/

Post by pfalcon » Sat Jan 17, 2015 8:10 pm

Lua references:
Thinking how to call an idea of getting rid of "callback mess", term "inversion of inversion of control" comes to mind, googling for it, this idea came to mind to few people, yeah:
Most other hits are however misnomers and actually mean "Internalizing of dependency injection". Here's another publication which uses term in the intended meaning (and which once again shows that JavaScript generators are modeled after Python's):
Awesome MicroPython list
Pycopy - A better MicroPython https://github.com/pfalcon/micropython
MicroPython standard library for all ports and forks - https://github.com/pfalcon/micropython-lib
More up to date docs - http://pycopy.readthedocs.io/

Damien
Site Admin
Posts: 647
Joined: Mon Dec 09, 2013 5:02 pm

Re: Converting callback result stream to iterator/generator/

Post by Damien » Sat Jan 17, 2015 10:34 pm

pfalcon wrote:That's actually primary trait - Lua allows to yield from called functions, and then it allows to use yield anywhere (including in callbacks), which saves from the need to know whom to .send value instead of yield with implicit destination.
And Lua implements it by essentially having support for threads in its core. Granted they are "pure Lua" threads (ie don't allow to save C stack frame), but still need to allocate a whole new interpreter state for each coroutine. This interpreter state includes allocation of a new stack, which seems to be set at a magic number (40 stack entries by default), irrespective of how much stack the coroutine will actually need. This is a pretty heavy-weight coroutine.

In contrast in Python, since we know if a function can yield or not we know if we need to preallocate its stack on the heap, and we know exactly how much stack to allocate.

pfalcon
Posts: 1155
Joined: Fri Feb 28, 2014 2:05 pm

Re: Converting callback result stream to iterator/generator/

Post by pfalcon » Sat Jan 17, 2015 11:01 pm

Damien wrote: And Lua implements it by essentially having support for threads in its core. Granted they are "pure Lua" threads (ie don't allow to save C stack frame), but still need to allocate a whole new interpreter state for each coroutine. This interpreter state includes allocation of a new stack, which seems to be set at a magic number (40 stack entries by default), irrespective of how much stack the coroutine will actually need. This is a pretty heavy-weight coroutine.
I'm not sure about "whole new interpreter state". But it definitely needs allocating new VM state. But in this case, we allocate new VM state for each function call (https://github.com/micropython/micropython/issues/1036). They allocate linear stack instead of linked stacked frames for access efficiency, but then it's of course pain to grow it, so they conservatively allocate it big to avoid reallocations. Surely, Lua's memory usage is nowhere near uPy - I remember reading eLua docs where they say that normal Lua interpreter needs at least 20K heap to startup. In eLua they were able to hack it down to 5K. I'm not sure if that includes interactive shell. uPy works well in 2K (for things which can fit in that) and starts up even with lower heap (though conservative GC and pointer aliasing may exhaust such smaller heaps).
In contrast in Python, since we know if a function can yield or not we know if we need to preallocate its stack on the heap, and we know exactly how much stack to allocate.
Well, yep, I find exact stack size calculation pretty amazing feature. Dunno how many other interpreters practice that though.
Awesome MicroPython list
Pycopy - A better MicroPython https://github.com/pfalcon/micropython
MicroPython standard library for all ports and forks - https://github.com/pfalcon/micropython-lib
More up to date docs - http://pycopy.readthedocs.io/

mikulurimi
Posts: 1
Joined: Thu Apr 27, 2017 7:26 pm

Re: Converting callback result stream to iterator/generator/coro

Post by mikulurimi » Thu Apr 27, 2017 7:30 pm

If you don't know anything about python yield, I recommend this tutorial to understand yield in python (https://tutorials.technology/tutorials/ ... ained.html).
Sorry if this sound offtopic, but I started with micrpython recently and I don't knwo anything about python

Post Reply