More on Co-Routines
From:
"andrew cooke" <andrew@...>
Date:
Wed, 11 Feb 2009 18:31:57 -0300 (CLST)
Nope, that's not right. I need to first define how I start
things running.
So, assume the trampoline starts by invoking some function.
That will either return a value, in which case it wasn't
expecting to be started by the trampoline, or a generator.
If it returns a generator then either it wasn't expecting to
be called by the trampoline system and that's an actual
result, or the generator is something that should be managed
by the trampoline.
Assuming it should be managed by the trampoline, the
trampoline calls next().
If it receives a ToRun() value then it pushes the generator
on the stack and runs the "subroutine".
If the subroutine returns a non-generator value then it
wasn't expecting to be called by the trampoline, but no
worries, we can send back the value anyway.
If the subroutine returns a generator then we need to
assume that it was expecting to be invoked by the
trampoline. We take next from the generator and look at
the value. If it's a ToRun then we can repeat as before.
If it's not a ToRun then we must assume that it contains a
value that is being "returned" by being yielded. We have
to assume this because a generator can't simply return.
So if sometihng is going to call via the trampoline (it
contains a yield ToRun) then it can only yield, not
return.
(Although another option would be to raise some special
kind of exception to return values, I guess).
Anywya, that assumption is OK - the generator is discarded
and the value sent back to the previous caller from the
stack.
The problem is: how to return a generator? I gues it just
yields a generator. That may not be a big issue - I'm
just worried that
Next problem, then. We can handle things that don't expect
to be called by the trampoline. But other things cannot
handle things that expect to have been called by the
trampoline, because they will receive a generator instead of
a value.
So there has to be a strict division between functions that
are called normally and those that are trampolined.
How about if we say that matchers are the only things that
should be trampolined? But that means they must yield
generators. Because if they yield directly the trampoline
has broken the generator before it knows it's not a ToRun.
Unless the trampoline itself wraps generators. Then it
could return that value.
Would that work? We can wrap generators automatically.
This won't work for "normal" functions (if they return
normally they can't yield, so can't call out via the
trampoline). But that's OK because they'll just work
normally.
So what I'm saying is that only generators can trampoline.
This isn't necessarily a strong constraint, I'm just
choosing it to simplify things. Well, no it is a strong
constraint, because we're trampolining between coroutines.
I guess what I mean is that I am not going to look at
automatic handling on non-generators and I am going to avoid
issues with bootstrapping from the initial non-generator
call by isolating the generators themselves.
This has the side effect of starting the trampolinging at
the first found generator, rather than at the initial call.
I don't think that's an issue.
OK, so most of the above is incorrect (or at least
incomplete). We only trampoline once generators are "up and
running" within normal code. We then intercept the value
returned from a generator via a wrapper and detect flagged
call values. These are handled by the normal trampoline
process.
That might sound like we're back in the same description as
above, but we no longer assume that the return value from
the called function is trampoline aware. Instead, we call
it normally and get some function back. Ah, crap - that
doesn't work because we're back where we started. If we
simply send the returned value then we've not intercepted
any later calls.
OK, so backstep and try again. The trampoline is at the top
level and is asked to evaluate a matcher. The matcher is
guaranteed to return a generator. The tampoline invokes the
matcher and receives the generator. It calls next on the
generator and, if it's a normal value returns it as the
matcher's first result. Otherwise, if it's tagged, it's a
call to a new matcher. That matcher is invoked similarly
(from the top level).
That works. What has changed?
There's a weird asymmetry required. It only works if you
start with a function that returns a generator. It's not
the generator that's wrapped, it's the entire matcher.
After-work beer is kicking in. Time to let that soak for a
while.
Andrew
Trampolining Code
From:
"andrew cooke" <andrew@...>
Date:
Wed, 11 Feb 2009 21:38:14 -0300 (CLST)
So this is, I think, now pretty specific to LEPL, but it clearly works.
Typical output was
1336,1335,1334,1333,1332,1331,1330,1329,13...
2060,2059,2058,2057,2056,2055,2054,2053,20...
221,220,219,218,217,216,215,214,213,212,21...
742,741,740,739,738,737,736,735,734,733,73...
308,307,306,305,304,303,302,301,300,299,29...
1559,1558,1557,1556,1555,1554,1553,1552,15...
678,677,676,675,674,673,672,671,670,669,66...
4039,4038,4037,4036,4035,4034,4033,4032,40...
107,106,105,104,103,102,101,100,99,98,97,9...
418,417,416,415,414,413,412,411,410,409,40...
921,920,919,918,917,916,915,914,913,912,91...
2683,2682,2681,2680,2679,2678,2677,2676,26...
947,946,945,944,943,942,941,940,939,938,93...
2089,2088,2087,2086,2085,2084,2083,2082,20...
304,303,302,301,300,299,298,297,296,295,29...
3399,3398,3397,3396,3395,3394,3393,3392,33...
421,420,419,418,417,416,415,414,413,412,41...
3956,3955,3954,3953,3952,3951,3950,3949,39...
1949,1948,1947,1946,1945,1944,1943,1942,19...
3488,3487,3486,3485,3484,3483,3482,3481,34...
0 100 200 300 400 500 600 700 800 900 Traceback ...
So the apparent stack depth of 1000 was easily exceeded.
from random import uniform
class Next(object):
# This is the 'tag' class used to indicate that a value being
# yielded is actually a coroutine that should be evaluated.
def __init__(self, next):
self.next = next
def generator(level=0, p=0.001):
# This returns it's own level with probability p.
# Otherwise, it constructs a child at a lower level and calls
# the child (twice, just to make sure children are persistent)
while True:
if uniform(0, 1) < p:
yield str(level)
else:
child = generator(level+1, p)
yield (yield Next(child)) + ',' + str(level)
yield (yield Next(child)) + ',' + str(level)
def trampoline(main):
# A yield is either a 'real' yield to the parent coroutine,
# or a new coroutine to generate. The stack only tracks
# the pending chain of coroutines - many others may exist,
# but are managed via references internal to other coroutines.
stack = [main]
while stack:
try:
value = next(stack[-1])
while not isinstance(value, Next) and len(stack) > 1:
stack.pop()
value = stack[-1].send(value)
if isinstance(value, Next):
stack.append(value.next)
else:
yield value
except StopIteration:
stack.pop()
if __name__ == '__main__':
t = trampoline(generator())
for i in range(20):
print(next(t))
def stack_size(depth=0):
if 0 == depth % 100:
print(depth, ' ', end='')
stack_size(depth+1)
stack_size()
I'd like the main loop (in trampoline) to be neater.
Note in particular how object creation is now in-line.
Andrew