[prev in list] [next in list] [prev in thread] [next in thread]
List: sbcl-devel
Subject: Re: [Sbcl-devel] Viability of continuations (as an extension)
From: Mariano Montone <marianomontone () gmail ! com>
Date: 2014-08-24 19:14:23
Message-ID: CAHKx1MixuxJLpMg4cTMw_s_PXoR_KBmH91Qu+gzUAOJ5P4yDQQ () mail ! gmail ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
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}>)
>
>
[Attachment #5 (text/html)]
<div dir="ltr"><div><div>Wow. This looks great! Please finish it! \
:)<br><br></div>Looking forward to your \
updates.<br><br></div>Thanks<br><br>Mariano<br></div><div \
class="gmail_extra"><br><br><div class="gmail_quote">On Sun, Aug 24, 2014 at 3:53 PM, \
Jan Moringen <span dir="ltr"><<a href="mailto:jmoringe@techfak.uni-bielefeld.de" \
target="_blank">jmoringe@techfak.uni-bielefeld.de</a>></span> wrote:<br> \
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc \
solid;padding-left:1ex">Hi.<br> <div class=""><br>
On Sun, 2014-08-24 at 14:40 -0300, Mariano Montone wrote:<br>
<br>
> does anyone know if it would be viable to implement \
"real"<br> > continuations as an SBCL extension?.<br>
<br>
</div>I'm currently exploring the possibility of a "direct style"<br>
implementation of delimited multi-prompt continuations based on similar<br>
extensions for OCaml and Scheme [eg. 1, 2, 3]. I was going to write to<br>
sbcl-devel after having made more progress to not waste everybody's time<br>
with half-baked ideas, but for the sake of avoiding duplicated effort, I<br>
will briefly outline what I'm currently trying out.<br>
<br>
As I see it, implementing delimited continuations consists of the<br>
following parts:<br>
<br>
1. Establishing a recognizable marker at the RESET call site.<br>
2. Extracting the delimited control stack fragment at the SHIFT<br>
call site and capturing it.<br>
3. Unwinding to the RESET call site (in a coordinated manner w.r.t.<br>
control-sensitive mechanisms) and returning the reified<br>
continuation.<br>
4. Potentially splicing the captured stack (again in a coordinated<br>
manner) when the continuation is invoked.<br>
5. This ist not a sequential step but a cross-cutting concern:<br>
inform the garbage collector about continuations: objects can<br>
now be reachable through captured stack fragments.<br>
<br>
I implemented 1. and 2. via CATCH/THROW. The CATCH tag can also act as<br>
the prompt, if I'm not mistaken. A variant of THROW that manipulates<br>
UNWIND-PROTECT blocks and the binding stack differently may be needed<br>
later. I'm not sure about that.<br>
<br>
For 2. and 5., I added a new primitive object CONTINUATION which holds<br>
the control stack fragment. It should probably also hold the<br>
corresponding binding stack fragment. CONTINUATIONs have their own<br>
widetags and would be scanned by the gc like stacks of suspended threads<br>
(i.e., conservatively on x86[_64] IIUC). It would probably make sense to<br>
have a non-primitive object wrapping the CONTINUATION primitive object<br>
and holding the non-special data.<br>
<br>
For 4., I build a buffer containing the captured stack fragment and a<br>
bit of the control stack of the function which invokes continuations<br>
(EXECUTE-CONTINUATION below). I currently only rewrite return addresses.<br>
It will be necessary to link UNWIND-PROTECT blocks, re-build the binding<br>
stack as well as handler and restart clusters. After that, the stack<br>
frame of EXECUTE-CONTINUATION can be overwritten with the buffer and<br>
control can "return" into the spliced fragment.<br>
<br>
As I said, I planned to write about this later so please bear with me<br>
but be sceptical.<br>
<br>
Kind regards,<br>
Jan<br>
<br>
[1] Kiselyov, O. (2012): Delimited Control in OCaml, Abstractly and<br>
Concretely<br>
[2] Gasbichler, M. and Sperber, M. (2002): Final Shift for Call/cc:<br>
Direct Implementation of Shift and Reset<br>
[3] Flatt, M., Gang, Y., Findler, R. and Felleisen, M. (2007): Adding<br>
Delimited and Composable Control to a Production Programming Environment<br>
<br>
Example of the stack fragment capturing and buffer building part:<br>
calling G with the following definitions (the OTHER tag just<br>
demonstrates the ability to have multiple prompts, I hope)<br>
<br>
(defun h ()<br>
(shift (lambda (k) (execute-continuation k 5))))<br>
<br>
(defun g ()<br>
(sb-sys::without-gcing (reset (catch 'other (h)))))<br>
<br>
results in the following buffer being prepared in EXECUTE-CONTINUATION:<br>
<br>
B4DB86D8<br>
<br>
B4DB86D4 E 8B 06 D5 <- (CALL-WITH-RESET-RETURN-ADDRESS #<code object (XEP \
(LAMBDA () IN G)) {E8B011F}>)<br> B4DB86D0 B4 DB 87 0C <- \
CALL-WITH-RESET-BASE-POINTER<br> B4DB86CC E 8B 04 B5 <- \
(CALL-WITH-RESET-SINGLE-VALUE-RETURN-ADDRESS #<code object (XEP (LAMBDA () IN G)) \
{E8B011F}>)<br> B4DB86C8 B4 DB 86 D0 <- CALL-WITH-RESET-STACK-SLOTS-START<br>
B4DB86C4 B4 DB 86 8C<br>
B4DB86C0 E D9 4D 83<br>
B4DB86BC B4 DB 86 8C<br>
B4DB86B8 B4 DB A3 18<br>
B4DB86B4 B4 DB 86 EC<br>
B4DB86B0 B4 DB 86 EC<br>
B4DB86AC E 0D 20 8F<br>
B4DB86A8 E 57 B4 38 <- #<code object (ESCAPE-FUN EXIT-BLOCK-1) \
{E57B04F}><br> B4DB86A4 B4 DB 86 D0<br>
B4DB86A0 B4 DB 87 1C <- DELIMCC-CATCH-BLOCK<br>
B4DB869C E D9 4C AB<br>
B4DB8698 E D9 4C EB<br>
B4DB8694 E D9 4D 1B<br>
B4DB8690 E D9 4D 23<br>
B4DB868C E D9 4D 23 <- CALL-WITH-RESET-STACK-POINTER<br>
B4DB8688 E 57 B3 D7 <- #<code object (ESCAPE-FUN EXIT-BLOCK-1) \
{E57B04F}><br> B4DB8684 B4 DB 86 D0<br>
B4DB8680 B4 DB 86 50<br>
B4DB867C B4 DB A3 20<br>
B4DB8678 B4 DB 86 A0<br>
B4DB8674 B4 DB 86 A0<br>
B4DB8670 E 84 3F 37<br>
B4DB866C E 8B 05 A2 <- #<code object (XEP (LAMBDA () IN G)) {E8B011F}><br>
B4DB8668 B4 DB 86 84<br>
B4DB8664 B4 DB 87 1C <- CURRENT-CATCH-BLOCK<br>
B4DB8660 0<br>
B4DB865C 0<br>
B4DB8658 8<br>
B4DB8654 8<br>
B4DB8650 9 05 89 B8 <- #<code object (LAMBDA (&OPTIONAL (V) (K) &REST \
G107) IN ADD-BIGNUMS) {905882F}><br> <br>
B4DB864C E 8B 05 69 <- (H-RETURN-ADDRESS #<code object (XEP (LAMBDA () IN G)) \
{E8B011F}>)<br> B4DB8648 B4 DB 86 84 <- H-BASE-POINTER<br>
B4DB8644 B4 DB 86 24 <- H-SINGLE-VALUE-RETURN-ADDRESS<br>
B4DB8640 E D9 4E 8B <- H-STACK-SLOTS-START<br>
B4DB863C E D9 4E 93<br>
B4DB8638 E D9 4D 83<br>
B4DB8634 E D9 4D D3<br>
B4DB8630 E D9 4E 13<br>
B4DB862C E D9 4E 43<br>
B4DB8628 E D9 4E 4B<br>
B4DB8624 E D9 4E 8B<br>
B4DB8620 12 14 5B 87<br>
B4DB861C 4<br>
B4DB8618 10 10 10 10 <<br>
B4DB8614 10 10 10 10 <<br>
B4DB8610 10 10 10 10 < unrelated stack allocated array in H (not shown in example \
code above)<br> B4DB860C 10 10 10 10 <<br>
B4DB8608 10 10 10 10 <<br>
B4DB8604 50 <<br>
B4DB8600 9 60 DC 9A <- (H-STACK-POINTER #<code object CHAR-UPCASE \
{960DC5F}>)<br> B4DB85FC E 7F 9E 80 <- #<code object (LAMBDA \
(&OPTIONAL (CATCH-BLOCK) (BASE-POINTER) (STACK-POINTER) &REST G0) IN H) \
{E7F98EF}><br> B4DB85F8 B4 DB 86 D0 <- EXECUTE-CONTINUATION-BASE-POINTER<br>
B4DB85F4 E D9 80 39<br>
B4DB85F0 B4 DB 86 5C<br>
B4DB85EC B4 DB 86 A0<br>
B4DB85E8 14<br>
B4DB85E4 E 84 3F 37<br>
B4DB85E0 E 8B 05 A2 <- #<code object (XEP (LAMBDA () IN G)) {E8B011F}><br>
B4DB85DC B4 DB 86 84<br>
B4DB85D8 B4 DB 86 5C<br>
B4DB85D4 0<br>
B4DB85D0 E 57 B4 B7 <- (EXECUTE-CONTINUATION-STACK-POINTER #<code object \
(ESCAPE-FUN EXIT-BLOCK-1) {E57B04F}>)<br> <br>
</blockquote></div><br></div>
------------------------------------------------------------------------------
Slashdot TV.
Video for Nerds. Stuff that matters.
http://tv.slashdot.org/
_______________________________________________
Sbcl-devel mailing list
Sbcl-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/sbcl-devel
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic