skulpt/skulpt — pull request #286 by meredydd (2014-09-21 23:18:05+00:00)
Title: Add Suspensions to Skulpt

This pull request adds a new feature to Skulpt: "Suspensions", which allow
Python execution to be paused and resumed. This sort of functionality has
been discussed before (h/t @LeszekSwirski issue #150), and the general
consensus is that it was desirable, so here's a working implementation
with tests.

--------

Suspensions are continuations, generated on demand by returning an instance
of Sk.misceval.Suspension from a function. They allow Python execution to be
suspended and subsequently resumed, allowing simulation of blocking I/O,
time-slicing to keep web pages responsive, and even multi-threading.

Normally, a suspension is initiated by a callee (Javascript) function,
but there is also a 'debugging' option (passed to Sk.configure()) which
causes the compiler to generate a suspension before each statement.
As each suspension also captures all stack frames and local variables,
this can be used to implement a single-step debugger. An optional
breakpoints() callback (also passed to Sk.configure()) allows the user
to dynamically filter which of these suspensions actually happen.

Suspensions have a 'data' property, which is an object indicating the reason
for the suspension (and under what circumstances it may be resumed).
'data.type' is a string; current suggested values are:

'timer': Resume after a delay. 'data.delay' is the delay in seconds
before resuming. time.sleep() emits 'timer' suspensions.
'promise': Resume when the Javascript Promise 'data.promise' resolves or
yields an error.
'debug': A suspension cause by the 'debugging' option (see above)

Suspensions also have an 'optional' property. If set to true, this suspension
may be resumed immediately if it is not convenient to wait. 'debug'
suspensions have 'optional' set, so they are ignored rather than causing
errors in non-suspendable call stacks (see below).

Example: --------------------------------------------------------------------

Here is some suspension-aware Javascript code that calls a Python function
that might suspend, and gives the result as a Javascript promise:

function callAsync(pyFunction) {
var p = Promise.defer();

var handleResponse = function(r) {

if (r instanceof Sk.misceval.Suspension) {

var doResume = function() {
var newR = r.resume();
handleResponse(newR);
}

switch (r.data.type) {
case 'timer':
setTimeout(doResume, r.data.delay*1000);
break;

case 'promise':
r.data.promise.then(doResume, doResume);
break;

default:
if (r.optional) {
doResume(); // immediately
} else {
p.reject("Unknown suspension type " + r.data.type);
}
}

} else { // It's not a suspension, just a regular return value

p.resolve(r);
}
};

var r = Sk.misceval.callsimOrSuspend(pyFunction);
handleResponse(r);
}

(Note, this is an example: A real implementation would catch exceptions
thrown by callsim(pyFunction) or r.resume() so they don't get lost in the
event loop. This code has been omitted for clarity.)

Implementation notes: -------------------------------------------------------

* Not every Javascript calling context can handle getting a suspension
instead of a return value. There are many awkward cases within the Skulpt
codebase, let alone existing users of the library. Therefore, uses of
Sk.misceval.callsim()/call()/apply() do not support suspensions, and will
throw a SuspensionError if their callee tries to suspend non-optionally.
(Likewise, suspending part-way through a class declaration will produce
an error.)

Other APIs which call into Python, such as import and Sk.abstr.iternext(),
now have an extra parameter, 'canSuspend'. If false or undefined, they
will throw a SuspensionError if their callee suspends non-optionally. If
true, they may return a Suspension instead of a result.

If a Suspension with the 'optional' flag is returned in a non-suspendable
context, its resume() method will be called immediately rather than
causing an error.

* Suspensions save the call stack as they are processed. This provides a
Python stack trace of every suspension. This could be used to provide
stack traces on exceptions, which is currently a missing feature.

* Likewise, suspensions would be a natural way of implementing generators.
The current generator implementation is quite limited (it does not support
varargs or keyword args) and not quite correct (it does not preserve
temporaries between calls - see below), so would benefit from unification.

* Suspensions would also be a good way of implementing timeouts, as well as
keeping the browser responsive during long computations. I have not
changed the existing timeout code, which still throws errors. A
suspension-based timeout should first return optional suspensions (in case
the timeout triggers on a non-suspendable stack), and then, after a grace
period, issue a non-optional suspension that will terminate a
non-suspendable stack.

Reliability and testing notes: ----------------------------------------------

* Deliberate suspensions are tested by the (newly implemented) time.sleep()
function, which is exercised by the new tests t544.py and t555.py.

* We test that a wide variety of generated code is robust to being suspended
by running the entire test suite in 'debugging' mode (see above). This
causes suspensions and resumptions at every statement boundary, giving us
good confidence that any feature exercised by the test suite is robust to
suspension. "./skulpt.py testdebug" is the command for this.

Of course, the test suite must also be run in normal mode, to verify that
it works when *not* suspending at every statement boundary.

Performance notes:

* Essential overhead in the fast case (ie code that does not suspend) is
kept quite low, at two conditionals per function call (one by the caller,
to check whether a call completed or suspended, and one by the callee,
to check whether this is a normal call or a suspension being resumed).
Given the number of conditionals and nested function calls in
Sk.misceval.call/callsim/apply, this is probably negligible.

* There is additional implementation-dependent overhead (ie overhead that
can be whittled down if it proves too much, and would not require global
changes to implementations strategy to mitigate). I have not attacked
these too aggressively, as the indications are that the performance hit
already isn't that bad (~5% on the test suite on my machine, but of course
we'd need bigger benchmarks to say for sure). Still, here are some
pointers for future improvement:

- Sk.misceval.call/apply and friends are now wrappers around
applyOrSuspend, with an additional check for suspensions (to throw an
error)

- Each function call creates a new block for "after this function
returns" (this is where we resume to if that function call suspends),
and jumps to it via the normal continue-based mechanism. With more
invasive modification to the block generator, we could use switch-case-
fallthrough to remove this penalty for ordinary function returns.

- Any temporary that might be required to persist across *any* suspension
in a scope (ie any function call) is saved on *every* suspension. This
is conservative but correct (unlike existing generator support, which
just breaks if you try something like x = str((yield y)), as the
temporary used to look up 'str' is not preserved). However, this does
impede the compiler's ability to infer variable lifetimes. This
could be mitigated by generating separate save and resume code for
each suspension site, but that again requires intrusive modification
to the block system.