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.
I don't believe I'm the Ian Davies you're looking for :)

On 7 Oct 2014, at 18:05, Meredydd Luff <notifications@github.com> wrote:

> In src/misceval.js:
> 
> > +                } catch(e) {
> > +                    reject(e);
> > +                }
> > +            })(r);
> > +
> > +        } catch (e) {
> > +            reject(e);
> > +        }
> > +    });
> > +};
> > +goog.exportSymbol("Sk.misceval.asyncToPromise", Sk.misceval.asyncToPromise);
> > +
> > +Sk.misceval.applyAsync = function (suspHandlers, func, kwdict, varargseq, kws, args) {
> > +    return Sk.misceval.asyncToPromise(function() {
> > +        return Sk.misceval.applyOrSuspend(func, kwdict, varargseq, kws, args);
> > +    });
> Yeah, @iandavies just pointed that out too :) We also have a bug with suspending generators if they're explicitly called via the next() method. Expect a revision tomorrow.
> —
> Reply to this email directly or view it on GitHub.
>