Stackless resumable functions
bitwise via Digitalmars-d
digitalmars-d at puremagic.com
Sun Feb 22 16:48:42 PST 2015
On Sunday, 22 February 2015 at 03:35:28 UTC, ketmar wrote:
> On Sat, 21 Feb 2015 21:19:32 +0000, bitwise wrote:
>
>> Input on this would be appreciated.
>
> it seems to me that you can "abuse" delegates for this (i mean
> the
> underlying "fat pointer"). resumable function can create
> closure (i think
> all the code for this is already here), "resume address"
> pointer (this
> can be added to closure), pointer to "real" delegate, hidden
> "yield
> point" address, and return a delegate which does something like
> this on
> call:
>
> * executes "real" delegate from "resume address".
> * "real" delegate yields by doing indirect call to "resume
> address"
> * assembler code at "resume address" stores new resume address
> (it's on
> stack now)
> * and returns from "wrapping delegate"
>
> so from the point of programmer this will look as an ordinary
> delegate,
> even with the same type, and it will be usable anywhere where
> ordinary
> delegate is usable.
I'm glad you mentioned "resume address". I guess I don't need a
jump table since the function is not switching on a user variable
;)
I don't like the idea of having a resumable function look like a
regular delegate. There would be no clean way to check when the
resumable function had finished. I've only skimmed the C++
proposal for resumable lambdas below, but it seems like their
solution is to introduce a 'stop_iteration' exception which gets
thrown when you try to call a resumable lambda that has run to
completion. So basically, all uses of delegates would have to be
wrapped in try/catch blocks..
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4244.pdf
The newest visual studio preview version has "generators". This
is an example from the visual studio blog:
generator<int> fib() {
int a = 0;
int b = 1;
for (;;) {
__yield_value a;
auto next = a + b;
a = b;
b = next;
}
}
So I'm assuming the above function would return something like
this:
template<class T>
struct generator
{
T value;
iterator begin() { /* executes function, stores value, and
returns iterator to first yield */ }
iterator end() { ... }
void operator++() { /* execute function to next yield and
store value */ }
T& operator*() { return value; }
};
I am considering something similar.
Please excuse my incoherent pseudocode :)
interface IResumableClosure {
// address of resumable function
// stack vars
// methods for initializing a new MethodRange(T)
}
struct Generator(T)
{
IResumableClosure closure;
Generator(IResumableClosure closure) {
this.closure = closure;
}
int opApply(int delegate(ref T) dg) {
foreach(value; MethodRange!T(closure))
if(dg(value)) return 1;
return 0;
}
MethodRange!T getRange() {
return MethodRange!T(closure);
}
}
struct MethodRange(T)
{
IResumableClosure closure;
// contains stack vars, resume address
// last returned value, and 'finished' flag
void *context;
MethodRange(IResumableClosure closure) {
this.closure = closure;
this.context = closure.createContext();
if(!context->finished)
this.value = invoke(context);
}
private T invoke(void* context) {
// run function until yield, store return address in context
}
T front() { return value; }
void popFront() { value = invoke(context); }
bool empty() { return context.finished; }
}
Generator!int myResumableFunction()
{
for(int i = 0; i < 10; ++i)
yield i;
return; // exits the resumable function
// return 1; // illegal inside resumable function, use yield
}
for(number; myResumableFunction())
writeln(number);
// or
auto gen = myResumableFunction();
auto metRang = gen.getRange(); // runs to first yield
while(!metRang.empty()) {
writeln(metRang.front);
metRang.popFront();
}
// or the caller could optionally return a MethodRange(T)
directly if they were
// ok with the function being invoked immediately.
MethodRange!int myResumableFunction() {
yield 1;
}
auto metRang = myResumableFunction(); // runs to first yield
while(!metRang.empty()) {
writeln(metRang.front);
metRang.popFront();
}
So like you said, I could wrap the resumable function in some
kind of specialized closure, but I could use that to optionally
initialize a MethodRange(T) or a Generator(T).
More information about the Digitalmars-d
mailing list