From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Tomas Hlavaty Newsgroups: gmane.emacs.devel Subject: Re: continuation passing in Emacs vs. JUST-THIS-ONE Date: Mon, 03 Apr 2023 02:39:06 +0200 Message-ID: <875yad240l.fsf@logand.com> References: <627090382.312345.1678539189382@office.mailbox.org> <87sfe7suog.fsf@gmail.com> <1c6fedae-10b4-5d97-5036-eaa736e1b816@gmail.com> <87mt4c6xju.fsf@logand.com> <87a6001xm0.fsf@logand.com> <87tty78fwg.fsf@logand.com> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="20551"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Jim Porter , Karthik Chikmagalur , Thomas Koch , "emacs-devel@gnu.org" To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Mon Apr 03 02:40:18 2023 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1pj8F7-0005BL-En for ged-emacs-devel@m.gmane-mx.org; Mon, 03 Apr 2023 02:40:17 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1pj8EO-0003EJ-DC; Sun, 02 Apr 2023 20:39:32 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pj8EK-0003E0-VQ for emacs-devel@gnu.org; Sun, 02 Apr 2023 20:39:28 -0400 Original-Received: from logand.com ([37.48.87.44]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pj8EI-0003vM-Dr for emacs-devel@gnu.org; Sun, 02 Apr 2023 20:39:28 -0400 Original-Received: by logand.com (Postfix, from userid 1001) id E492919E638; Mon, 3 Apr 2023 02:39:15 +0200 (CEST) X-Mailer: emacs 28.2 (via feedmail 11-beta-1 I) In-Reply-To: Received-SPF: pass client-ip=37.48.87.44; envelope-from=tom@logand.com; helo=logand.com X-Spam_score_int: -18 X-Spam_score: -1.9 X-Spam_bar: - X-Spam_report: (-1.9 / 5.0 requ) BAYES_00=-1.9, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.devel:305054 Archived-At: 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: () 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 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 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