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