Delimited continuations

Delimited continuations

[John Wiegley]

It just occurred to me this evening that lexical-binding makes delimited
continuations (https://en.wikipedia.org/wiki/Delimited_continuation) trivial
to implement in Emacs Lisp:

  ;; -*- lexical-binding: t -*-
  
  (defun shift (k entry)
    (if (eq (nth 0 k) 'outer)
        (throw (nth 1 k)
               (funcall entry #'(lambda (val)
                                  (funcall (nth 2 k)
                                           (list 'inner val)))))
      (nth 1 k)))
  
  (defun reset (thunk)
    (let ((bound (make-symbol "reset--bound")))
      (catch bound
        (funcall thunk (list 'outer bound thunk)))))
  
  (reset
   #'(lambda (_)
       (+ 4 (reset
             #'(lambda (p)
                 (* 2 (shift p #'(lambda (k)
                                   (funcall k (funcall k 4))))))))))
  ;; (+ 4 (* 2 (* 2 4)))
  ;; => 20
  
  (reset
   #'(lambda (q)
       (+ 4 (reset
             #'(lambda (_)
                 (* 2 (shift q #'(lambda (k)
                                   (funcall k (funcall k 4))))))))))
  ;; (+ 4 (* 2 (+ 4 (* 2 4))))
  ;; => 28

This can handy when coding something that naturally lends itself to "inversion
of control", when it's easier to code the inner structure of something up
front, and then refer to that structure -- possibly repeating it and
transforming it -- to build up the resulting data:

  (let ((data '(1 2 3)))
    (reset
     #'(lambda (p)
         (list 'a 'b (shift p #'(lambda (k)
                                  (append (funcall k 0)
                                          (mapcar (apply-partially k)
                                                  data))))))))
  ;; => (a b 0
  ;;     (a b 1)
  ;;     (a b 2)
  ;;     (a b 3))

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: Delimited continuations

[Michael Heerdegen]

"John Wiegley" <johnw@gnu.org> writes:

>   ;; -*- lexical-binding: t -*-
>   
>   (defun shift (k entry)
>     (if (eq (nth 0 k) 'outer)
>         (throw (nth 1 k)
>                (funcall entry #'(lambda (val)
>                                   (funcall (nth 2 k)
>                                            (list 'inner val)))))
>       (nth 1 k)))
>   
>   (defun reset (thunk)
>     (let ((bound (make-symbol "reset--bound")))
>       (catch bound
>         (funcall thunk (list 'outer bound thunk)))))
   
This seems to be clever.

But one little disadvantage seems to be that a part of the code (the
part of the `reset' thunk that is evaluated until `shift' is reached) is
processed twice: once till the `shift' is reached (which `throw's and
hasn't access to this calculation, so that part of the calculation is
thrown away) and a second time when the delimited continuation is
called.

E.g. in

#+begin_src emacs-lisp
(reset (lambda (p)
         (+ (+ 1 2)
            (shift p (lambda (k) (funcall k 1))))))
#+end_src

(+ 1 2) is executed twice.  I think this isn't necessarily so?


BTW, I wonder what one can potentially do with this stuff.


Michael.

Re: Delimited continuations

[John Wiegley]

>>>>> "MH" == Michael Heerdegen <michael_heerdegen@web.de> writes:

HM> (+ 1 2) is executed twice. I think this isn't necessarily so?

Yes, except if you think about it, this "initial evaluation" whose results
are thrown away can be used to establish lexical bindings to be captured
by the lambda passed to shift; or to influence which shift is used within
a complicated reset block.

HM> BTW, I wonder what one can potentially do with this stuff.

Although it's in Haskell, this is my favorite article on motivating the
expressive power of delimited continuations:

http://blog.moertel.com/posts/2005-09-13-scope-herding-with-delimited-continuations.html

Note that rather than simply using shift/reset lexically -- which *could* be
replaced by a lambda form parameterized over the insertion points -- it uses
shift/reset as the power behind a helper function.

Even his example, however, is a bit less meaningful in a context where side-
effects and dynamic binding are freely available.

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: Delimited continuations

[Michael Heerdegen]

"John Wiegley" <johnw@gnu.org> writes:

> HM> (+ 1 2) is executed twice. I think this isn't necessarily so?
>
> Yes, except if you think about it, this "initial evaluation" whose
> results are thrown away can be used to establish lexical bindings to
> be captured by the lambda passed to shift; or to influence which shift
> is used within a complicated reset block.

This can be done in the "first run".  I think it's the "second run" that
is "too much" because it doesn't belong to the limited continuation of
the context of `shift'.


Michael.

Re: Delimited continuations

[Stefan Monnier]

[ For some reason, while I had no trouble getting an intuitive
  understanding of continuations and can happily write and reason
  about CPS style code, I must admit that I still haven't managed to
  really wrap my head around delimited continuations.
  You've been warned.  ]

> (reset (lambda (p)
>          (+ (+ 1 2)
>             (shift p (lambda (k) (funcall k 1))))))
[...]
> (+ 1 2) is executed twice.  I think this isn't necessarily so?

Right, but since (+ 1 2) is pure the problem is minor (and also because
whether (+ 1 2) was already computed or not depends on evaluation order
of arguments, which is defined in Elisp but would still be within the
scope of "acceptable quirks" in my book if it's not 100% obeyed).

Things get more interesting with side-effects:

   (defvar fwdc nil)
   (reset (λ (p)
      (if fwdl 3
        (setq fwdc t)
        (shift p (λ (k) (k 5))))))

since we end up re-computing the `if` test and hence not using the `5`
provided to `k`.  I think this case is a clear "bug" (because, IIUC,
(shift _ (λ (k) (k v))) should be equivalent to just `v`).

BTW, John:
>   (defun shift (k entry)
>     (if (eq (nth 0 k) 'outer)
>         (throw (nth 1 k)
>                (funcall entry #'(lambda (val)
>                                   (funcall (nth 2 k)
>                                            (list 'inner val)))))
>       (nth 1 k)))

It means that `entry` is evaluated within the dynamic context of `shift`
rather than within the dynamic context of `reset` (because you call
`entry` before calling `throw`).

This has a clear downside: we use extra stack space during evaluation of
`entry` (the extra stack space is equal to the stack space used between
`reset` and `shift`).  But I guess this is not too terrible.

It also means that dynamic-bindings (and other unwind-protects such as
with-current-buffer) applied within `k` up to now will still be active
during evaluation of `entry`.  Whether that's The Right Thing or not is
a good question but is beyond what my poor brain can take right now.


        Stefan

Re: Delimited continuations

[Michael Heerdegen]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> Things get more interesting with side-effects:
>
>    (defvar fwdc nil)
>    (reset (λ (p)
>       (if fwdl 3
>         (setq fwdc t)
>         (shift p (λ (k) (k 5))))))
>
> since we end up re-computing the `if` test and hence not using the `5`
> provided to `k`.  I think this case is a clear "bug" (because, IIUC,
> (shift _ (λ (k) (k v))) should be equivalent to just `v`).

Or we just don't call it continuation, which is misleading given the
suggested implementation which gives you more something like a delimited
re-execution.

Anyway, my personal opinion is to make such stuff available so that
people can experiment with it.


Michael.

Re: Delimited continuations

[John Wiegley]

>>>>> "MH" == Michael Heerdegen <michael_heerdegen@web.de> writes:

HM> Or we just don't call it continuation, which is misleading given the
MH> suggested implementation which gives you more something like a delimited
MH> re-execution.

HM> Anyway, my personal opinion is to make such stuff available so that people
HM> can experiment with it.

I'll create some examples in Haskell to determine what the intended semantics
should be, and then see how to efficiently replicate that behavior in Elisp.

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: Delimited continuations

[Christopher Lemmer Webber]

John Wiegley writes:

>>>>>> "MH" == Michael Heerdegen <michael_heerdegen@web.de> writes:
>
> HM> Or we just don't call it continuation, which is misleading given the
> MH> suggested implementation which gives you more something like a delimited
> MH> re-execution.

The term "prompts" are often also used for delimited continuations in
Scheme-land at least: https://www.gnu.org/software/guile/manual/html_node/Prompts.html

(But they are continuations... they're delimited rather than
undelimited... that's a big advantage though because delimited
continuations compose)

> HM> Anyway, my personal opinion is to make such stuff available so that people
> HM> can experiment with it.
>
> I'll create some examples in Haskell to determine what the intended semantics
> should be, and then see how to efficiently replicate that behavior in Elisp.

May be even easier to show how delimited continuations work in schemes
like Guile or Racket, since that looks a bit more native.  In Scheme
examples you also don't need to manually do the CPS conversion... it's
done for you.

But I guess that leads to something I was unclear on: John, are you
suggesting that we make delimited continuations part of the language
(with automatic CPS conversion)?  If that's possible, it would be a big
win.  But maybe you were just demo'ing how to do delimited continuations
manually?

IMO manual CPS is cool to know how to do, but it's much nicer if your
language can do it for you :)

Go go delimited continuations!
 - Chris

Re: Delimited continuations

[John Wiegley]

>>>>> Christopher Lemmer Webber <cwebber@dustycloud.org> writes:

> But I guess that leads to something I was unclear on: John, are you
> suggesting that we make delimited continuations part of the language (with
> automatic CPS conversion)? If that's possible, it would be a big win. But
> maybe you were just demo'ing how to do delimited continuations manually?

Just manual, not making it part of Emacs Lisp per se.

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: Delimited continuations

[Michael Heerdegen]

Christopher Lemmer Webber <cwebber@dustycloud.org> writes:

> IMO manual CPS is cool to know how to do, but it's much nicer if your
> language can do it for you :)

AFAIK generator.el does automatic cps rewriting (though the goal is a
bit different).


Michael.

Re: Delimited continuations

[Stefan Monnier]

>> IMO manual CPS is cool to know how to do, but it's much nicer if your
>> language can do it for you :)
> AFAIK generator.el does automatic cps rewriting (though the goal is a
> bit different).

Indeed.  [ Tho it doesn't handle 100% of Elisp.  ]


        Stefan

Real continuations (was: Delimited continuations)

[Michael Heerdegen]

Hi,

btw, would it be practical to support real first class continuations in
Elisp?

When you exit a recursive edit, isn't what you get (internally) more or
less already the execution of some kind of continuation?


Michael.

Re: Real continuations

[Stefan Monnier]

> btw, would it be practical to support real first class continuations in
> Elisp?

Real first-class continuations require reifying the stack as an object
reachable from the heap and that can be copied.  There are many
different ways to do that to try and keep the benefits of the normal
representation of the stack, but I think it could prove difficult to
implement something like call/cc given the current code base.

> When you exit a recursive edit, isn't what you get (internally) more or
> less already the execution of some kind of continuation?

Indeed catch/throw do provide some of the functionality of call/cc, as
do threads.  Together they cover a large part of what call/cc is
typically used for, but they still don't provide call/cc.


        Stefan