* Delimited continuations
@ 2017-12-09 9:06 John Wiegley
2017-12-10 16:53 ` Michael Heerdegen
2017-12-10 17:39 ` Real continuations (was: Delimited continuations) Michael Heerdegen
0 siblings, 2 replies; 13+ messages in thread
From: John Wiegley @ 2017-12-09 9:06 UTC (permalink / raw
To: emacs-devel
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
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Delimited continuations
2017-12-09 9:06 Delimited continuations John Wiegley
@ 2017-12-10 16:53 ` Michael Heerdegen
2017-12-10 19:59 ` John Wiegley
2017-12-11 16:47 ` Stefan Monnier
2017-12-10 17:39 ` Real continuations (was: Delimited continuations) Michael Heerdegen
1 sibling, 2 replies; 13+ messages in thread
From: Michael Heerdegen @ 2017-12-10 16:53 UTC (permalink / raw
To: emacs-devel
"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.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Real continuations (was: Delimited continuations)
2017-12-09 9:06 Delimited continuations John Wiegley
2017-12-10 16:53 ` Michael Heerdegen
@ 2017-12-10 17:39 ` Michael Heerdegen
2017-12-11 16:16 ` Real continuations Stefan Monnier
1 sibling, 1 reply; 13+ messages in thread
From: Michael Heerdegen @ 2017-12-10 17:39 UTC (permalink / raw
To: emacs-devel
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.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Delimited continuations
2017-12-10 16:53 ` Michael Heerdegen
@ 2017-12-10 19:59 ` John Wiegley
2017-12-12 14:27 ` Michael Heerdegen
2017-12-11 16:47 ` Stefan Monnier
1 sibling, 1 reply; 13+ messages in thread
From: John Wiegley @ 2017-12-10 19:59 UTC (permalink / raw
To: Michael Heerdegen; +Cc: emacs-devel
>>>>> "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
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Real continuations
2017-12-10 17:39 ` Real continuations (was: Delimited continuations) Michael Heerdegen
@ 2017-12-11 16:16 ` Stefan Monnier
0 siblings, 0 replies; 13+ messages in thread
From: Stefan Monnier @ 2017-12-11 16:16 UTC (permalink / raw
To: emacs-devel
> 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
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Delimited continuations
2017-12-10 16:53 ` Michael Heerdegen
2017-12-10 19:59 ` John Wiegley
@ 2017-12-11 16:47 ` Stefan Monnier
2017-12-12 14:17 ` Michael Heerdegen
1 sibling, 1 reply; 13+ messages in thread
From: Stefan Monnier @ 2017-12-11 16:47 UTC (permalink / raw
To: emacs-devel
[ 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
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Delimited continuations
2017-12-11 16:47 ` Stefan Monnier
@ 2017-12-12 14:17 ` Michael Heerdegen
2017-12-12 22:24 ` John Wiegley
0 siblings, 1 reply; 13+ messages in thread
From: Michael Heerdegen @ 2017-12-12 14:17 UTC (permalink / raw
To: Stefan Monnier; +Cc: emacs-devel
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.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Delimited continuations
2017-12-10 19:59 ` John Wiegley
@ 2017-12-12 14:27 ` Michael Heerdegen
0 siblings, 0 replies; 13+ messages in thread
From: Michael Heerdegen @ 2017-12-12 14:27 UTC (permalink / raw
To: emacs-devel
"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.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Delimited continuations
2017-12-12 14:17 ` Michael Heerdegen
@ 2017-12-12 22:24 ` John Wiegley
2018-01-02 18:39 ` Christopher Lemmer Webber
0 siblings, 1 reply; 13+ messages in thread
From: John Wiegley @ 2017-12-12 22:24 UTC (permalink / raw
To: Michael Heerdegen; +Cc: Stefan Monnier, emacs-devel
>>>>> "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
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Delimited continuations
2017-12-12 22:24 ` John Wiegley
@ 2018-01-02 18:39 ` Christopher Lemmer Webber
2018-01-02 22:29 ` John Wiegley
2018-01-03 16:01 ` Michael Heerdegen
0 siblings, 2 replies; 13+ messages in thread
From: Christopher Lemmer Webber @ 2018-01-02 18:39 UTC (permalink / raw
To: John Wiegley; +Cc: Michael Heerdegen, Stefan Monnier, emacs-devel
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
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Delimited continuations
2018-01-02 18:39 ` Christopher Lemmer Webber
@ 2018-01-02 22:29 ` John Wiegley
2018-01-03 16:01 ` Michael Heerdegen
1 sibling, 0 replies; 13+ messages in thread
From: John Wiegley @ 2018-01-02 22:29 UTC (permalink / raw
To: Christopher Lemmer Webber; +Cc: Michael Heerdegen, Stefan Monnier, emacs-devel
>>>>> 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
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Delimited continuations
2018-01-02 18:39 ` Christopher Lemmer Webber
2018-01-02 22:29 ` John Wiegley
@ 2018-01-03 16:01 ` Michael Heerdegen
2018-01-03 20:12 ` Stefan Monnier
1 sibling, 1 reply; 13+ messages in thread
From: Michael Heerdegen @ 2018-01-03 16:01 UTC (permalink / raw
To: Christopher Lemmer Webber; +Cc: John Wiegley, Stefan Monnier, emacs-devel
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.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Delimited continuations
2018-01-03 16:01 ` Michael Heerdegen
@ 2018-01-03 20:12 ` Stefan Monnier
0 siblings, 0 replies; 13+ messages in thread
From: Stefan Monnier @ 2018-01-03 20:12 UTC (permalink / raw
To: emacs-devel
>> 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
^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2018-01-03 20:12 UTC | newest]
Thread overview: 13+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2017-12-09 9:06 Delimited continuations John Wiegley
2017-12-10 16:53 ` Michael Heerdegen
2017-12-10 19:59 ` John Wiegley
2017-12-12 14:27 ` Michael Heerdegen
2017-12-11 16:47 ` Stefan Monnier
2017-12-12 14:17 ` Michael Heerdegen
2017-12-12 22:24 ` John Wiegley
2018-01-02 18:39 ` Christopher Lemmer Webber
2018-01-02 22:29 ` John Wiegley
2018-01-03 16:01 ` Michael Heerdegen
2018-01-03 20:12 ` Stefan Monnier
2017-12-10 17:39 ` Real continuations (was: Delimited continuations) Michael Heerdegen
2017-12-11 16:16 ` Real continuations Stefan Monnier
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.