====================================================
  Stackless / Continuation discussion group
====================================================

Bert Freudenberg, Jacob Hallèn, Adrien di Mascio,
Valentino Volonghi, Christian Tismer

Introduction to current ideas
------------------------------

We had a small introduction about Stackless Python and
its implementation. We compared that to PyPy for similarities
and differences.

The idea is to keep recursion and stack usage as an efficient
approach using the C compiler and current processor.
The whole problem of making PyPy stackless is solved by providing
RPython with a mechanism to unwind and save this stack structure.

An implementation of an example was written by Armin. This
is thought as a template of how the generated code (c|sh)ould look like.


This approach supports

- full continuations, because we can clone the saved block structures
- restartable exceptions (yet only at the RPython level)
- pickling program state
- unlimited recursion
- context switching
- garbage collection with explicit knowledge of all roots


General impressions
--------------------

The proposed stackless extension of the existing framework
might be easier to implement than a new approach using
continuation passing style. But we might want to try
examples for both and compare performance.

Needed independently of the backend:
being able to capture variables of a block.
This could work on the annotated flowgraph, but probably makes
more sense after all the backend optimizations. It is still
the same for all backends.

Needed action:
Find the set of necessary structures to describe the status of all blocks.
Generate types for all the variants of blocks. The concrete implementation
may vary. The current simple approach is a block number that encodes
function, arity, return type of the function and relative block
number. Different encodings are possible and may vary per backend.
(In assembly, one would probably add descriptor info right before
the function entrypoint...)

Aliveness considerations, partially related to the backend:
The state blocks take over the role of the stack. The stack may
instead be considered as a cache for the state blocks. State
blocks are actually a synonym for continuations.


Backend:

Tasks for implementation:

- generating the structures for saving the blocks
- generate extra code for function re-entry
- write extra support for detecting stack overflows.

  + have extra info about the stack size of every function.

Thinking about re-use of the existing exception handling code,
which is there for every function call. Adding yet another case
might be cheap. See if this is simpler or more complex
than using extra variables.

Observations:
-------------

We can use this mechanism to produce restartable exceptions. But this
is not about Python-level exceptions without further support.

This approach appears to give us full continuations for free.


Exposing an interface to RPython
--------------------------------

Here is a tentative design of a minimal interface that might be good
enough to implement, say, app-level greenlets or tasklets as a mixed
module.

We introduce an RPython type ``frame_stack_top`` and a built-in function
``yield_current_frame_to_caller()`` that work as follows (see example below):

* The built-in function ``yield_current_frame_to_caller()`` causes the current
  function's state to be captured in a new ``frame_stack_top`` object that is
  returned to the parent.  Only one frame, the current one, is captured this
  way.  The current frame is suspended and the caller continues to run.  Note
  that the caller is only resumed once: when
  ``yield_current_frame_to_caller()`` is called.  See below.

* A ``frame_stack_top`` object can be jumped to by calling its ``switch()``
  method with no argument.

* ``yield_current_frame_to_caller()`` and ``switch()`` themselves return a new
  ``frame_stack_top`` object: the freshly captured state of the caller of the
  source ``switch()`` that was just executed, or None in the case described
  below.

* the function that called ``yield_current_frame_to_caller()`` also has a
  normal return statement, like all functions.  This statement must return
  another ``frame_stack_top`` object.  The latter is *not* returned to the
  original caller; there is no way to return several times to the caller.
  Instead, it designates the place to which the execution must jump, as if by
  a ``switch()``.  The place to which we jump this way will see a None as the
  source frame stack top.

* every frame stack top must be resumed once and only once.  Not resuming
  it at all causes a leak.  Resuming it several times causes a crash.

* a function that called ``yield_current_frame_to_caller()`` should not raise.
  It would have no implicit parent frame to propagate the exception to.  That
  would be a crashingly bad idea.

The following example would print the numbers from 1 to 7 in order::

    def g():
        print 2
        frametop_before_5 = yield_current_frame_to_caller()
        print 4
        frametop_before_7 = frametop_before_5.switch()
        print 6
        return frametop_before_7

    def f():
        print 1
        frametop_before_4 = g()
        print 3
        frametop_before_6 = frametop_before_4.switch()
        print 5
        frametop_after_return = frametop_before_6.switch()
        print 7
        assert frametop_after_return is None

    f()