Wow. This looks great! Please finish it! :)

Looking forward to your updates.

Thanks

Mariano


On Sun, Aug 24, 2014 at 3:53 PM, Jan Moringen <jmoringe@techfak.uni-bielefeld.de> wrote:
Hi.

On Sun, 2014-08-24 at 14:40 -0300, Mariano Montone wrote:

>         does anyone know if it would be viable to implement "real"
> continuations as an SBCL extension?.

I'm currently exploring the possibility of a "direct style"
implementation of delimited multi-prompt continuations based on similar
extensions for OCaml and Scheme [eg. 1, 2, 3]. I was going to write to
sbcl-devel after having made more progress to not waste everybody's time
with half-baked ideas, but for the sake of avoiding duplicated effort, I
will briefly outline what I'm currently trying out.

As I see it, implementing delimited continuations consists of the
following parts:

     1. Establishing a recognizable marker at the RESET call site.
     2. Extracting the delimited control stack fragment at the SHIFT
        call site and capturing it.
     3. Unwinding to the RESET call site (in a coordinated manner w.r.t.
        control-sensitive mechanisms) and returning the reified
        continuation.
     4. Potentially splicing the captured stack (again in a coordinated
        manner) when the continuation is invoked.
     5. This ist not a sequential step but a cross-cutting concern:
        inform the garbage collector about continuations: objects can
        now be reachable through captured stack fragments.

I implemented 1. and 2. via CATCH/THROW. The CATCH tag can also act as
the prompt, if I'm not mistaken. A variant of THROW that manipulates
UNWIND-PROTECT blocks and the binding stack differently may be needed
later. I'm not sure about that.

For 2. and 5., I added a new primitive object CONTINUATION which holds
the control stack fragment. It should probably also hold the
corresponding binding stack fragment. CONTINUATIONs have their own
widetags and would be scanned by the gc like stacks of suspended threads
(i.e., conservatively on x86[_64] IIUC). It would probably make sense to
have a non-primitive object wrapping the CONTINUATION primitive object
and holding the non-special data.

For 4., I build a buffer containing the captured stack fragment and a
bit of the control stack of the function which invokes continuations
(EXECUTE-CONTINUATION below). I currently only rewrite return addresses.
It will be necessary to link UNWIND-PROTECT blocks, re-build the binding
stack as well as handler and restart clusters. After that, the stack
frame of EXECUTE-CONTINUATION can be overwritten with the buffer and
control can "return" into the spliced fragment.

As I said, I planned to write about this later so please bear with me
but be sceptical.

Kind regards,
Jan

[1] Kiselyov, O. (2012): Delimited Control in OCaml, Abstractly and
Concretely
[2] Gasbichler, M. and Sperber, M. (2002): Final Shift for Call/cc:
Direct Implementation of Shift and Reset
[3] Flatt, M., Gang, Y., Findler, R. and Felleisen, M. (2007): Adding
Delimited and Composable Control to a Production Programming Environment

Example of the stack fragment capturing and buffer building part:
calling G with the following definitions (the OTHER tag just
demonstrates the ability to have multiple prompts, I hope)

(defun h ()
  (shift (lambda (k) (execute-continuation k 5))))

(defun g ()
  (sb-sys::without-gcing (reset (catch 'other (h)))))

results in the following buffer being prepared in EXECUTE-CONTINUATION:

B4DB86D8

B4DB86D4  E 8B 06 D5 <- (CALL-WITH-RESET-RETURN-ADDRESS #<code object (XEP (LAMBDA () IN G)) {E8B011F}>)
B4DB86D0 B4 DB 87 0C <- CALL-WITH-RESET-BASE-POINTER
B4DB86CC  E 8B 04 B5 <- (CALL-WITH-RESET-SINGLE-VALUE-RETURN-ADDRESS #<code object (XEP (LAMBDA () IN G)) {E8B011F}>)
B4DB86C8 B4 DB 86 D0 <- CALL-WITH-RESET-STACK-SLOTS-START
B4DB86C4 B4 DB 86 8C
B4DB86C0  E D9 4D 83
B4DB86BC B4 DB 86 8C
B4DB86B8 B4 DB A3 18
B4DB86B4 B4 DB 86 EC
B4DB86B0 B4 DB 86 EC
B4DB86AC  E 0D 20 8F
B4DB86A8  E 57 B4 38 <- #<code object (ESCAPE-FUN EXIT-BLOCK-1) {E57B04F}>
B4DB86A4 B4 DB 86 D0
B4DB86A0 B4 DB 87 1C <- DELIMCC-CATCH-BLOCK
B4DB869C  E D9 4C AB
B4DB8698  E D9 4C EB
B4DB8694  E D9 4D 1B
B4DB8690  E D9 4D 23
B4DB868C  E D9 4D 23 <- CALL-WITH-RESET-STACK-POINTER
B4DB8688  E 57 B3 D7 <- #<code object (ESCAPE-FUN EXIT-BLOCK-1) {E57B04F}>
B4DB8684 B4 DB 86 D0
B4DB8680 B4 DB 86 50
B4DB867C B4 DB A3 20
B4DB8678 B4 DB 86 A0
B4DB8674 B4 DB 86 A0
B4DB8670  E 84 3F 37
B4DB866C  E 8B 05 A2 <- #<code object (XEP (LAMBDA () IN G)) {E8B011F}>
B4DB8668 B4 DB 86 84
B4DB8664 B4 DB 87 1C <- CURRENT-CATCH-BLOCK
B4DB8660           0
B4DB865C           0
B4DB8658           8
B4DB8654           8
B4DB8650  9 05 89 B8 <- #<code object (LAMBDA (&OPTIONAL (V) (K) &REST G107) IN ADD-BIGNUMS) {905882F}>

B4DB864C  E 8B 05 69 <- (H-RETURN-ADDRESS #<code object (XEP (LAMBDA () IN G)) {E8B011F}>)
B4DB8648 B4 DB 86 84 <- H-BASE-POINTER
B4DB8644 B4 DB 86 24 <- H-SINGLE-VALUE-RETURN-ADDRESS
B4DB8640  E D9 4E 8B <- H-STACK-SLOTS-START
B4DB863C  E D9 4E 93
B4DB8638  E D9 4D 83
B4DB8634  E D9 4D D3
B4DB8630  E D9 4E 13
B4DB862C  E D9 4E 43
B4DB8628  E D9 4E 4B
B4DB8624  E D9 4E 8B
B4DB8620 12 14 5B 87
B4DB861C           4
B4DB8618 10 10 10 10 <
B4DB8614 10 10 10 10 <
B4DB8610 10 10 10 10 < unrelated stack allocated array in H (not shown in example code above)
B4DB860C 10 10 10 10 <
B4DB8608 10 10 10 10 <
B4DB8604          50 <
B4DB8600  9 60 DC 9A <- (H-STACK-POINTER #<code object CHAR-UPCASE {960DC5F}>)
B4DB85FC  E 7F 9E 80 <- #<code object (LAMBDA (&OPTIONAL (CATCH-BLOCK) (BASE-POINTER) (STACK-POINTER) &REST G0) IN H) {E7F98EF}>
B4DB85F8 B4 DB 86 D0 <- EXECUTE-CONTINUATION-BASE-POINTER
B4DB85F4  E D9 80 39
B4DB85F0 B4 DB 86 5C
B4DB85EC B4 DB 86 A0
B4DB85E8          14
B4DB85E4  E 84 3F 37
B4DB85E0  E 8B 05 A2 <- #<code object (XEP (LAMBDA () IN G)) {E8B011F}>
B4DB85DC B4 DB 86 84
B4DB85D8 B4 DB 86 5C
B4DB85D4           0
B4DB85D0  E 57 B4 B7 <- (EXECUTE-CONTINUATION-STACK-POINTER #<code object (ESCAPE-FUN EXIT-BLOCK-1) {E57B04F}>)