Re: continuation passing in Emacs vs. JUST-THIS-ONE

[Tomas Hlavaty <tom@logand.com>]

Hi Stefan,

thank you for your time, your discussion helps me to clear my thinking.

This works with asynchronous processes, threads and iter (cps
rewriting):

(defun await (future)
  (let (z)
    (while (eq 'EAGAIN (setq z (funcall future)))
      (accept-process-output)
      (sit-for 0.2))
    z))

(defun await-in-background (future &optional callback secs repeat)
  (let ((z (funcall future)))
    (if (eq 'EAGAIN z)
        (let (timer)
          (setq timer (run-with-timer
                       (or secs 0.2)
                       (or repeat 0.2)
                       (lambda ()
                         (let ((z (funcall future)))
                           (unless (eq 'EAGAIN z)
                             (cancel-timer timer)
                             (when callback
                               (funcall callback z))))))))
      (when callback
        (funcall callback z)))
    z))

(defmacro await-iter (future)
  (let ((f (gensym)))
    `(let ((,f ,future))
       (let (z)
         (while (eq 'EAGAIN (setq z (funcall ,f)))
           (iter-yield 'EAGAIN))
         z))))

(defmacro async (&rest body)
  (declare (indent 0))
  (let ((z (gensym))
        (e (gensym)))
    `(let (,e (,z 'EAGAIN))
       (cl-flet ((yield (x) (setq ,z x))
                 (fail (string &rest args) (setq ,e (cons string args))))
         ,@body)
       (lambda () (if ,e (signal 'error ,e) ,z)))))

(defmacro async-thread (&rest body)
  (declare (indent 0))
  (let ((z (gensym))
        (e (gensym)))
    `(let (,e (,z 'EAGAIN))
       (cl-flet ((yield (x) (setq ,z x))
                 (fail (string &rest args) (setq ,e (cons string args))))
         (let ((thread (make-thread (lambda () (yield (progn ,@body))))))
           (lambda ()
             (thread-join thread)
             (if ,e (signal 'error ,e) ,z)))))))

(defun buffer-string2 (buffer)
  (with-current-buffer buffer
    (buffer-string)))

(defun async-process (command)
  (async
    (let* ((n (format "*%s" command))
           (b (generate-new-buffer n t))
           (e (generate-new-buffer (format "%s-stderr" n) t)))
      (condition-case c
          (make-process
           :name n
           :command command
           :buffer b
           :stderr e
           :sentinel (lambda (proc _event)
                       (unless (process-live-p proc)
                         (let ((x (process-exit-status proc)))
                           (if (and (eq 'exit (process-status proc))
                                    (zerop x))
                               (yield (buffer-string2 b))
                             (fail 'async-process
                                   :command command
                                   :code x
                                   :stderr (buffer-string2 e)
                                   :stdout (buffer-string2 b))))
                         (kill-buffer b)
                         (kill-buffer e))))
        (error
         (kill-buffer b)
         (kill-buffer e)
         (signal (car c) (cdr c)))))))

(defmacro async-iter (&rest body)
  (declare (indent 0))
  `(let ((i (iter-make (iter-yield (progn ,@body))))
         (z 'EAGAIN))
     (setq z (iter-next i))
     (lambda ()
       (when (eq 'EAGAIN z)
         (setq z (iter-next i)))
       (unless (eq 'EAGAIN z)
         (iter-close i))
       z)))

There are two sides using the future: producer and consumer.  Producer
runs asynchronously and is delimited by an async macro.  Consumer
synchronously waits for the value of the future using an await function
or macro.

Consumer options:

- await is a general await function which polls for the future in
  foreground.  It does not expect anything from the future and/or
  producer.

- await-in-background is a background version of await probably makes
  sense only as a top-level await together with callback.

- await-iter is used inside async-iter producers.  plain await above is
  needed at the top-level.

Producer options:

- async is a general async macro which sets the value or error of the
  future.

- async-thread runs the producer in a new thread and has more efficient
  await.

- async-process runs a command in an asynchronous process and sets the
  future value to the output of the process if successful.

- async-iter cps rewrites the producer so that it can be executed
  iteratively without the need for threads or processes.

It seems to me that the fundamental difference compared to futur.el is
that futur.el tries to manually wire up the links between producers and
consumers and wraps it together in complex macro futur-let* together
with future constructors.  I leave this to the lisp compiler and have to
implement only how consumers pull the data (await*) and how the
producers are constructed and push the data (async*).


Here is a non-trivial promise pipelining example from capnproto:
The client wants to compute:

   ((5 * 2) + ((7 - 3) * 10)) / (6 - 4)

The client decomposes the problem into API functions + - * /, names the
immediate results and sends everything to the server in one request.
Here the client sends the following to the server:

   A = (* 5 2)
   B = (- 7 3)
   C = (- 6 4)
   D = (* B 10)
   E = (+ A D)
   F = (/ E C)
   F = ?

In lisp:

   ((A * 5 2)
    (B - 7 3)
    (C - 6 4)
    (D * B 10)
    (E + A D)
    (F / E C)
    F)

Server runs the batched request: subtitutes the named immediate results
with the computed value and sends the result to the client.

Response:

    (<value of F>)

In lisp:

(defun promise-pipelining-client (expr)
  (let (z zk)
    (cl-labels ((rec (x)
                     (if (atom x)
                         x
                       (cl-destructuring-bind (op l r) x
                         (cl-ecase op
                           ((+ - * /)
                            (let ((ll (rec l))
                                  (rr (rec r))
                                  (k (gensym)))
                              (setq zk k)
                              (push (list k op ll rr) z)
                              k)))))))
      (rec expr))
    (nreverse (cons zk z))))

(promise-pipelining-client '(/ (+ (* 5 2) (* (- 7 3) 10)) (- 6 4)))
=> ((g3488 * 5 2) (g3489 - 7 3) (g3490 * g3489 10) (g3491 + g3488 g3490)
(g3492 - 6 4) (g3493 / g3491 g3492) g3493)

(defun promise-pipelining-server0 (req)
  (funcall
   (byte-compile-sexp
    `(lambda ()
       (let* (,@(cl-loop
                 for x in req
                 unless (atom x)
                 collect (cl-destructuring-bind (k op l r) x
                           `(,k (,op ,l ,r)))))
         ,(car (last req)))))))

(promise-pipelining-server0 (promise-pipelining-client '(/ (+ (* 5 2) (*
(- 7 3) 10)) (- 6 4))))
=> 25

Lets say now that it takes 5sec for the server to compute the number 5
etc.  I can use async/await on the server to run slow computations in
parallel.

Here using threads:

(defun slowly-thread (sec) ;; slowly computes sec in async thread
  (async-thread (or (sleep-for sec) sec)))

(defun promise-pipelining-server3 (req)
  (funcall
   (byte-compile-sexp
    (let (f v z)
      (dolist (x req)
        (if (atom x)
            (push x z)
          (cl-destructuring-bind (k op l r) x
            (let ((ll (if (symbolp l)
                          l
                        (let ((lk (gensym)))
                          (push `(,lk (slowly-thread ,l)) f)
                          `(await ,lk))))
                  (rr (if (symbolp r)
                          r
                        (let ((rk (gensym)))
                          (push `(,rk (slowly-thread ,r)) f)
                          `(await ,rk)))))
              (push `(,k (,op ,ll ,rr)) v)))))
      `(lambda ()
         (let ,(nreverse f)
           (let* ,(nreverse v)
             (list ,@(nreverse z)))))))))

(promise-pipelining-server3 (promise-pipelining-client '(/ (+ (* 5 2) (*
(- 7 3) 10)) (- 6 4))))
=> (25)

Here using processes:

(defun async-emacs (expr)
  (async-process
    `("emacs" "-Q" "--batch" "--eval" ,(cl-prin1-to-string `(print ,expr)))))
  
(defun await-emacs (future)
  (car (read-from-string (await future))))

(defun slowly-emacs (sec) ;; slowly computes sec in async sub-emacs
  (async-emacs `(or (sleep-for ,sec) ,sec)))

(defun promise-pipelining-server4 (req)
  (funcall
   (byte-compile-sexp
    (let (f v z)
      (dolist (x req)
        (if (atom x)
            (push x z)
          (cl-destructuring-bind (k op l r) x
            (let ((ll (if (symbolp l)
                          l
                        (let ((lk (gensym)))
                          (push `(,lk (slowly-emacs ,l)) f)
                          `(await-emacs ,lk))))
                  (rr (if (symbolp r)
                          r
                        (let ((rk (gensym)))
                          (push `(,rk (slowly-emacs ,r)) f)
                          `(await-emacs ,rk)))))
              (push `(,k (,op ,ll ,rr)) v)))))
      `(lambda ()
         (let ,(nreverse f)
           (let* ,(nreverse v)
             (list ,@(nreverse z)))))))))

(promise-pipelining-server4 (promise-pipelining-client '(/ (+ (* 5 2) (*
(- 7 3) 10)) (- 6 4))))
=> (25)

Expanded server code for that req looks something like this:

(let ((g710 (slowly-emacs 5))
      (g711 (slowly-emacs 2))
      (g712 (slowly-emacs 7))
      (g713 (slowly-emacs 3))
      (g714 (slowly-emacs 10))
      (g715 (slowly-emacs 6))
      (g716 (slowly-emacs 4)))
  (let* ((g704 (* (await-emacs g710) (await-emacs g711)))
         (g705 (- (await-emacs g712) (await-emacs g713)))
         (g706 (* g705 (await-emacs g714)))
         (g707 (+ g704 g706))
         (g708 (- (await-emacs g715) (await-emacs g716)))
         (g709 (/ g707 g708)))
    (list g709)))

First it starts all asynchronous processes, then awaits them as needed
and finally returns the result.

It uses (length '(5 2 7 3 10 6 4)) = 7 emacs sub-processes
where 'slowly sleeps in background so it takes
(max 5 2 7 3 10 6 4) = 10sec parallel
instead of (+ 5 2 7 3 10 6 4) = 37sec sequential.

On Wed 29 Mar 2023 at 15:00, Stefan Monnier <monnier@iro.umontreal.ca> wrote:
>> (defun await (future)
>>   (let (z)
>>     (while (eq 'EAGAIN (setq z (funcall future)))
>>       ;; TODO poke sit-for/io on yield?  how?
>>       (sit-for 0.2))
>>     z))
>
> This blocks, so it's the equivalent of `futur-wait`.
> I.e. it's the thing we'd ideally never use.

I think that futur-wait (or wrapper future-get) aka await is essential
but what futur.el provides is not sufficient.  There need to be
different await ways depending on use-case (process, thread, iter).

await is necessary for waiting at top-level in any case.  For top-level
waiting in background, use await-in-background instead.

>> Assuming alet (async let) macro, which binds var when async process
>> finishes with the value of its output:
>
> I.e. what I called `future-let*`.
>
>> (alet p1 '("which" "emacs")
>>   (when p1
>>     (alet p2 `("readlink" "-f" ,p1)
>>       (when p2
>>         (message "@@@ %s" p2)))))

alet was just a macro to turn a body into a callback which is then
plugged into process sentinel.  It has nothing to do with futures, async
or await.  This example also shows, that futures are not necessary in
this case (the futur.el example) and actually make things more
comlicated.

> Your syntax is more concise because it presumes all your async objects
> run commands via `make-process`, but other than that it seems to be
> doing basically the same as my code, yes.
>
>> or even await async process inside async process:
>>
>> (await
>>  (async
>>    (alet p `("readlink" "-f" ,(await
>>                                (async
>>                                  (alet p '("which" "emacs")
>>                                    (when p
>>                                      (yield p))))))
>>      (when p
>>        (yield p)))))
>
> You use `await` which will block Emacs :-(

I think that the promise pipelining example above shows better what
futures are about.

Calling await immediately after async is useless (simply use blocking
call).  The point of future is to make the distance between those calls
as big as possible so that the sum of times in the sequential case is
replaced with max of times in the parallel case.

>> I think this provides nicer interface for async code than futur.el and
>> even comes with a working example.
>
> I think you just reinvented the same thing, yes :-)

I think it is quite different.  What is the point of futur-deliver,
futur-fail, futur-pure, futur--bind, futur--join, futur-let*,
futur-multi-bind when the lisp can figure those automatically?  Some are
cosmetic but all the manual wiring is fundamentally unnecessary.  It
seems like lots of superficial code can be easily eliminated and the
result will be better because the lisp primitives like let or let* are
already brilliant :-)

>>>    (concat foo (future-wait (futur-let* (...) ...)))
>>
>> Looking at other languages, they do it explicitly.  The reason is, that
>> one might want to save the future, do something else and await the
>> future later at some point.  Not await it immediately:
>>
>>    (let ((future (futur-let* (...) ...)))
>>      ...
>>      (concat foo (future-wait future)))
>
> I suspect that a better option would be instead of:
>
>     (let ((future (futur-let* (BINDS...) BODY)))
>       ...
>       (concat foo (future-wait future)))
>
> to use
>
>     (futur-let* (BINDS...
>                  (s BODY))
>       (concat foo s))
>
> The difference is that it doesn't return a string but a `futur`, so if
> you want the string you need to use `future-let*` or `futur-wait`.
> The advantage is that you still have the choice to use `future-let*`
> rather than `futur-wait`.

Sorry I should have not used the terminology from futur.el which
is confusing.

I meant:

   (let ((future (async BODY)))
     ...do as much as possible in parallel...
     (concat foo (await future)))

The point is that waiting for the future has to be explicit, otherwise
there is no way to distinguish between passing the future around and
waiting for the future.

I do not see where future-let* would do anything useful.  A future is a
first class value after all so I can pass it around as such, e.g. to
mapcar:

(defun acurl (url)
  (async-process `("curl" ,url)))

(seq-reduce ;; compute total length, parallel (faster)
 #'+
 (mapcar (lambda (x) (length (await x)))
         (mapcar 'acurl '("https://dipat.eu"
                          "https://logand.com"
                          "https://osmq.eu")))
 0)

(seq-reduce ;; compute total length, sequential (slower)
 #'+
 (mapcar (lambda (x) (length (await (acurl x))))
         '("https://dipat.eu"
           "https://logand.com"
           "https://osmq.eu"))
 0)

On Wed 29 Mar 2023 at 14:47, Stefan Monnier <monnier@iro.umontreal.ca> wrote:
>>> Part of the issue is the management of `current-buffer`: should the
>>> composition of futures with `futur-let*` save&restore
>>> `current-buffer` to mimic more closely the behavior one would get
>>> with plain old sequential execution?  If so, should we do the same
>>> with `point`?  What about other such state?
>>
>> I do not think there is a good implicit solution.
>> Either it would save too much state or too little,
>> or save it the wrong way.
>
> Currently it doesn't save anything, which is "ideal" in terms of
> efficiency, but sometimes leads to code that's more verbose than
> I'd like.
>
> Someone suggested to save as much as threads do, but that's not
> practical.

A future is a single value, not a stream of values.

I think that one needs to decide what the use-case actually is,
i.e. what the value of the future is supposed to be.

For example, if I am talking about a future for an asynchronous process
and I am interested in its output, then there is no state to worry
about, simply return the buffer-string of the process buffer when the
process finishes.

Other use-cases would do something different, but once the future is
computed, it does not change so there is no state to maintain between
changes of the future.

>>> But as you point out at the beginning, as a general rule, if you want to
>>> avoid rewritings in the style of `generator.el`, then the code will tend
>>> to feel less like a tree and more "linear/imperative/sequential",
>>> because you fundamentally have to compose your operations "manually"
>>> with a monadic "bind" operation that forces you to *name* the
>>> intermediate value.
>>
>> That's what I suspected.
>> Being forced to name the values leads to very bad code.
>
> That's not my experience.  It's sometimes a bit more verbose than
> strictly necessary, but it's quite rare for it to make the code
> less readable.

I think there is no need for anything monadic in connection with
futures.  Plain lisp is pretty good for composing operations.


Also cps rewriting has nothing to do with futures.  For example, there
is no need for it with threads or asynchronous processes.  cps rewriting
is only needed if one wants to fake running something in parallel
without threads or asynchronous processes.

It is also pretty bad way of doing it.  Any function boundary stops the
rewriting process so I cannot yield from things like defun, cl-flet,
cl-labels so any useful factoring goes out of the window.  I cannot even
unify my async/await interface to yield = iter-yield and fail = error so
the iter case looks quite different from the thread or process cases.

For example, how would one implement sleep-iter as a function?
It works as a macro:

(defmacro sleep-iter (sec)
  `(let ((x ,sec))
     (let ((end (+ (float-time (current-time)) x)))
       (while (< (float-time (current-time)) end)
         (iter-yield 'EAGAIN)))))

I found only this solution:

(defun sleep-iter3 (sec)
  (async-iter
    (let ((end (+ (float-time (current-time)) sec)))
      (while (< (float-time (current-time)) end)
        (iter-yield 'EAGAIN)))
    (iter-yield sec)))

and that has to be called using await-iter like this:

   (await-iter (sleep-iter3 3))

where the extra await-iter is annoying.

It seems to me that my async-iter and await-iter are needed to make it
possible to factor nontrivial code which wants to iter-yield.


One more thing: Is futur-abort a good idea?

Cheers

Tomas