From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Lynn Winebarger Newsgroups: gmane.emacs.devel Subject: Re: continuation passing in Emacs vs. JUST-THIS-ONE Date: Fri, 21 Apr 2023 22:48:33 -0400 Message-ID: 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> Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="0000000000001131b005f9e3d0d9" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="13864"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Tomas Hlavaty , Jim Porter , Karthik Chikmagalur , Thomas Koch , emacs-devel To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Sat Apr 22 04:49:41 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 1pq3Jk-0003QV-QP for ged-emacs-devel@m.gmane-mx.org; Sat, 22 Apr 2023 04:49:41 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1pq3J0-0008N7-AT; Fri, 21 Apr 2023 22:48:54 -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 1pq3Iy-0008Mj-9U for emacs-devel@gnu.org; Fri, 21 Apr 2023 22:48:52 -0400 Original-Received: from mail-lf1-x12e.google.com ([2a00:1450:4864:20::12e]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1pq3Iv-0006K6-9M for emacs-devel@gnu.org; Fri, 21 Apr 2023 22:48:52 -0400 Original-Received: by mail-lf1-x12e.google.com with SMTP id 2adb3069b0e04-4eed6ddcae1so10437143e87.0 for ; Fri, 21 Apr 2023 19:48:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1682131727; x=1684723727; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=8ZVvKWjNR5UUJvbFyM4DxZwTUT8ztAyRCzXC7vpv79A=; b=Cgf40cZiLS+mnotlHaFOvb6E2qZ4tnp8baacWGC7q9TCasJHNicV3zG0XWyvVF/1P6 98hxePc+c2+pJhyVUD5MKY8TK8ES3OdkgOWCtuOSqjZBTV+6/MYhorHk8S9ghqWwAOG+ 38t9PP6ibuwcIw+H0X+XG2rq+HlD/YphMPNEbmfULeN2Kv3rR7ZJyKjKTWDg2WA+0DES 7kGGej/p+TuR13mjp+6jf4BaoHCwXEDsfTlb5lWLl9WG5h0OltRhyfsb7ai8vnZZK0Rb nqGFXo355Kp6dvkRuPawAdpgyQdrBnIDqN3DF9KC85xF8TZxM/FKLNecLlaWhFK4vIGY 9oMA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1682131727; x=1684723727; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=8ZVvKWjNR5UUJvbFyM4DxZwTUT8ztAyRCzXC7vpv79A=; b=WfmuHBSzbmi74AtUMvURh9JiaqtKO+hOw8WOwfXwboCCgShes06e8x9spWGpO5TyKq GVMFra+hGUVG8WkT3QcSwXzvt0VFarF2hlNBKY8kL29+MTuwxco1I0ZWPUKuvGzSmGNc IHO1r0NO6DHe0S2+BQitmFSdKRpzNZrRYuXwcrjVcQw5UeaYIbCnD42E9u1FWlB1d8ai TQW5eP4CE3gM9YoiHzCIlacNNulYG/2DcJ7jZK6SA3vr/frPzhhUg5HaQvj41PUdhbmD KxWQz0mbZXSO6aSMUAl/o04noI++rtdyaMw3COavi7yLfe03+w4BBZcDHk6GTqGmPGhJ YWeA== X-Gm-Message-State: AAQBX9cazeJ3wcIyFehTY+dbmtQ5wdJTAgZ9auJXaOmopICan9Aq7NvF NJHt+4HL0LERunTtFsIoqpjoewZZXpyJ2cZjwYY= X-Google-Smtp-Source: AKy350ZgekH5OeFvy9+jjn0iCmGRvxfvaxT/oLLWWoSg+wCQpaQ9cEfcOLisr1cKhAhGw4ZOK/3aYH6rTWvPixpv36o= X-Received: by 2002:a05:651c:1026:b0:2a7:8301:a968 with SMTP id w6-20020a05651c102600b002a78301a968mr1084917ljm.12.1682131727232; Fri, 21 Apr 2023 19:48:47 -0700 (PDT) In-Reply-To: Received-SPF: pass client-ip=2a00:1450:4864:20::12e; envelope-from=owinebar@gmail.com; helo=mail-lf1-x12e.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 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:305567 Archived-At: --0000000000001131b005f9e3d0d9 Content-Type: text/plain; charset="UTF-8" On Mon, Apr 17, 2023, 11:48 PM Stefan Monnier wrote: > > I wrote that incorrectly - I meant that primitive operations would add > > a continuation to the future and return a future for their result. > > Basically, a computation would never block, it would just build > > continuation trees (in the form of futures) and return to the > > top-level. Although that assumes the system would be able to allocate > > those futures without blocking for GC work. > > I think this would end up being extremely inefficient, since for every > tiny operation you'd end up creating a future, linked to the > previous computation (basically a sort of fine-grained dataflow graph). > I'm sure in theory it can be made tolerably efficient, but it'd need > a very different implementation strategy than what we have now. > Furthermore I expect it would lead to surprising semantics when used > with side-effecting operations. > Figuring those surprises out might be useful in determining what should be saved. IOW you can probably create a usable system that uses this approach, but > with a different language and a different implementation :-) > I'm not advocating for it. It would be like RABBIT with inverted continuation construction, but less sophisticated - dynamically constructing the closures from Plotkin's CPS transform without the optimizations of RABBIT or subsequent compilers. And that proviso about the GC not blocking seems like a significant challenge. Instead, I view it as an exercise in trying to understand what a syntax for working with futures as a semantics is supposed to represent - how to condense the shape of the computation into the shape of the expression. > `futur.el` instead forces the programmer to be somewhat explicit about > the concurrency points, so they have *some* control over efficiency and > interaction with side-effects. > > > At some point in this thread you stated you weren't sure what the > > right semantics are in terms of the information to save, etc. I posed > > this implicit semantics as a way to think about what "the right thing" > > would be. Would all operations preserve the same (lisp) machine > > state, or would it differ depending on the nature of the operator? [ > > is the kind of question it might be useful to work out in this thought > > experiment ] > > I can't imagine it working sanely if the kind of state that's saved > depends on the operation: the saved-state is basically private to the > continuation, so it might make sense to do it differently depending on > the continuation (tho even that would introduce a lot of complexity), > but not depending on the operation. > Am I right in thinking that the only real question is around the buffer state and buffer-local variables? Global variables are something users can easily define locks for, and dynamically bound variables are already thread-local, but buffer state is particularly subject to I/O events and buffer local variables don't really have a strong thread semantics - in one context a variable might be global and in another buffer-local, and the programmer would have to figure out whether to use a buffer-local lock or global lock on the fly. Or, maybe it would be fair to say that we would expect most interesting asynchronous code to involve work on buffers so that use-case is worth special consideration? > The coders will need to know what is saved and what isn't, so the > more complex this rule is, the harder it is to learn to use this > tool correctly. > I feel like I have read you refer to using purely functional data structures for concurrency in emacs (or elsewhere), but I don't have any concrete reference. So, I don't think my suggestion that buffers might be extended or replaced with a functional data structure + merging of asynchronous changes per https://lists.gnu.org/archive/html/emacs-devel/2023-04/msg00587.html is novel to you. For all I know, it reflects something you wrote in the past as munged through my memory. In any case, synchronizing though immutable data structures and merging is probably a lot easier and more performant path to concurrent buffers that going through the existent code trying to impose fine-grained synchronization. I don't know if some kind of buffer-rope based on the existing buffer code is a feasible path, or if there would need to be a wholesale reimplementation, but that kind of buffer would not only be good for asynchronous/concurrent editing with non-preemptive threading, but also between multiple in-process lisp machines with shared memory or even multi-process "collaborative" editing. If an emacs developer just wanted to get something going to see how it might work, though, maybe there's a kluge involving overlays with embedded temporary buffers, where the main buffer could be made read-only when it was being accessed asynchronously, and "copy-on-write" used when an error is thrown when one of the asynchronous functions attempts to write to the buffer. Then the async function would merge its changes on yield or return or something - this is one place you could provide explicit control over synchronization. > > The way you've defined future-let, the variable being bound is a > > future because you are constructing it as one, but it is still a > > normal variable. > > > > What if, instead, we define a "futur-abstraction" (lambda/futur (v) > > body ...) in which v is treated as a future by default, and a > > future-conditional form (if-available v ready-expr not-ready-expr) > > with the obvious meaning. If v appears as the argument to a > > lambda/future function object it will be passed as is. Otherwise, the > > reference to v would be rewritten as (futur-wait v). Some syntactic > > sugar (futur-escape v) => (if-available v v) could be used to pass the > > future to arbitrary functions. > > Seems complex, and I'm not sure it would buy you anything in practice. > It might not be much - I'm thinking it is one way to find a middle-ground between full-blown CPS-conversion and "stackless" coroutines. Plus, a future is essentially an operator on continuations, so it's not too wacky to define a class of operators on futures. Given the correspondence of futures to variables bound by continuations, maybe Felleisen's representation of "holes" in evaluation contexts would be visually helpful. Square brackets aren't convenient, but angular or curly brackets could be used to connote when a variable is being referenced as a future rather than the value returned by the future. I would consider that to be a concise form of explicitness. So, maybe "future-bind" could be replaced by "{}<-", and the "<-" in "future-let*" by {}<-. Somehow I suspect ({x} <- ...) being used to bind "x" would be over the lispy line, but that could be interesting. Either way, in the body, "{x}" would refer to the future and "x" to the value yielded by the future. Or maybe it should be the other way around. Either way, the point of the syntax is to visually represent the flow of the future to multiple (syntactic) contexts. I'm not sure how else that inversion of control can be concisely represented when it *doesn't* happen in a linear fashion. > > It would be easier if elisp threads were orthogonal to system threads, > > so that any elisp thread could be run on any available system thread. > > Currently, only one thread can run ELisp at a time. Whether that's > implemented using several system threads or not is largely an > internal detail. > > > Multiprocessing could be done by creating multiple lisp VMs in a > > process (i.e. lisp VM orthogonal to a physical core), > > Yes, "could". > I would go so far as to say it's the safest approach, especially if preserving the semantics of existing programs is a goal. I don't think attempting to make the lisp multiprocessing semantics slavishly replicate the host multiprocessing semantics is a good idea at all. At least with portable dumps/loads, there is a path to creating independent VMs (where the symbol table is local to the VM, and probably "headless" to start) in the same process space. It's not too hard to come up with a design that makes sense, indeed, the > problem is to actually do the work of bringing the current code to > that design. > True enough. There are shorter paths than (whether naive or sophisticated) attempts to impose fine-grained locking on the emacs run-time to replicate the native facilities for parallelism. I am under the impression that the latter is the prevailing view of what it would mean to bring efficient parallelism to emacs, which is unfortunate if the impression is correct. Lynn --0000000000001131b005f9e3d0d9 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Mon, Apr 17, 2023, 11:48 PM Stefan Monnier= <monnier@= iro.umontreal.ca> wrote:
>= ; I wrote that incorrectly - I meant that primitive operations would add > a continuation to the future and return a future for their result.
> Basically, a computation would never block, it would just build
> continuation trees (in the form of futures) and return to the
> top-level.=C2=A0 Although that assumes the system would be able to all= ocate
> those futures without blocking for GC work.

I think this would end up being extremely inefficient, since for every
tiny operation you'd end up creating a future, linked to the
previous computation (basically a sort of fine-grained dataflow graph).
I'm sure in theory it can be made tolerably efficient, but it'd nee= d
a very different implementation strategy than what we have now.
Furthermore I expect it would lead to surprising semantics when used
with side-effecting operations.

Figuring those surprises out might be useful= in determining what should be saved.

IOW= you can probably create a usable system that uses this approach, but
with a different language and a different implementation :-)

I'm not adv= ocating for it.=C2=A0 It would be like RABBIT with inverted continuation co= nstruction, but less sophisticated - dynamically constructing the closures = from Plotkin's CPS transform without the optimizations of RABBIT or sub= sequent compilers.=C2=A0 And that proviso about the GC not blocking seems l= ike a significant=C2=A0challenge.

Instead, I view it as an exercise in trying to= understand what a syntax for working with futures as a semantics is suppos= ed to represent - how to condense the shape of the computation into the sha= pe of the expression.
=C2=A0
`futur.el` instead forces the programmer to be somewhat explicit about
the concurrency points, so they have *some* control over efficiency and
interaction with side-effects.

> At some point in this thread you stated you weren't sure what the<= br> > right semantics are in terms of the information to save, etc.=C2=A0 I = posed
> this implicit semantics as a way to think about what "the right t= hing"
> would be.=C2=A0 Would all operations preserve the same (lisp) machine<= br> > state, or would it differ depending on the nature of the operator?=C2= =A0 [
> is the kind of question it might be useful to work out in this thought=
> experiment ]

I can't imagine it working sanely if the kind of state that's saved=
depends on the operation: the saved-state is basically private to the
continuation, so it might make sense to do it differently depending on
the continuation (tho even that would introduce a lot of complexity),
but not depending on the operation.

Am I right in thinking that the only real question is= around the buffer state and buffer-local variables?=C2=A0 Global variables= are something users can easily define locks for, and dynamically bound var= iables are already thread-local, but buffer state is particularly subject t= o I/O events and buffer local variables don't really have a strong thre= ad semantics - in one context a variable might be global and in another buf= fer-local, and the programmer would have to figure out whether to use a buf= fer-local lock or global lock on the fly.=C2=A0 Or, maybe it would be fair = to say that we would expect most interesting asynchronous code to involve w= ork on buffers so that use-case is worth=C2=A0special consideration?
<= div dir=3D"auto">

The coders will need to know what is saved and what isn't, so the
more complex this rule is, the harder it is to learn to use this
tool correctly.

I feel like I have read= you refer to using purely functional data structures for concurrency in em= acs (or elsewhere), but I don't have any concrete reference.=C2=A0 So, = I don't think my suggestion that buffers might be extended or replaced = with a functional data structure=C2=A0+ merging of asynchronous changes per= =C2=A0https://lists.gnu.org/archive/html/emacs-devel/2023-04/msg00587= .html is novel to you.=C2=A0 For all I know, it reflects something you = wrote in the past as munged through my memory.

In = any case, synchronizing though immutable data structures and merging is pro= bably a lot easier and more performant path to concurrent buffers that goin= g through the existent code trying to impose fine-grained synchronization.= =C2=A0 I don't know if some kind of buffer-rope based on the existing b= uffer code is a feasible path, or if there would need to be a wholesale rei= mplementation, but that kind of buffer would not only be good for asynchron= ous/concurrent editing with non-preemptive threading, but also between mult= iple in-process lisp machines with shared memory or even multi-process &quo= t;collaborative" editing.

If an emacs develop= er just wanted to get something going to see how it might work, though, may= be there's a kluge involving overlays with embedded temporary buffers, = where the main buffer could be made read-only when it was being accessed as= ynchronously, and "copy-on-write" used when an error is thrown wh= en one of the asynchronous functions attempts to write to the buffer.=C2=A0= Then the async function would merge its changes on yield or return or some= thing - this is one place you could provide explicit control over synchroni= zation.
=C2=A0
> The way you've defined future-let, the variable being bound is a > future because you are constructing it as one, but it is still a
> normal variable.
>
> What if, instead, we define a "futur-abstraction" (lambda/fu= tur (v)
> body ...) in which v is treated as a future by default, and a
> future-conditional form (if-available v ready-expr not-ready-expr)
> with the obvious meaning.=C2=A0 If v appears as the argument to a
> lambda/future function object it will be passed as is.=C2=A0 Otherwise= , the
> reference to v would be rewritten as (futur-wait v).=C2=A0 Some syntac= tic
> sugar (futur-escape v) =3D> (if-available v v) could be used to pas= s the
> future to arbitrary functions.

Seems complex, and I'm not sure it would buy you anything in practice.<= br>

It might not be much - I'm thinking= it is one way to find a middle-ground between full-blown CPS-conversion an= d "stackless" coroutines.=C2=A0 Plus, a future is essentially an = operator on continuations, so it's not too wacky to define a class of o= perators on futures.

Given the correspondence of f= utures to variables bound by continuations, maybe Felleisen's=C2=A0repr= esentation of "holes" in evaluation contexts would be visually he= lpful.=C2=A0 Square brackets aren't convenient, but angular or curly br= ackets could be used to connote when a variable is being referenced as a fu= ture rather than the value returned by the future.=C2=A0 I would consider t= hat to be a concise form of explicitness.

So, mayb= e "future-bind" could be replaced by "{}<-", and the= "<-" in "future-let*" by {}<-.=C2=A0 Somehow I s= uspect ({x} <- ...) being used to bind "x" would be over the l= ispy line, but that could be interesting.
Either way, in the body= , "{x}" would refer to the future and "x" to the value = yielded by the future.=C2=A0 Or maybe it should be the other way around.=C2= =A0 Either way, the point of the syntax is to visually represent the flow o= f the future to multiple (syntactic) contexts.=C2=A0 I'm not sure how e= lse that inversion of control can be concisely represented when it *doesn&#= 39;t* happen in a linear fashion.
=C2=A0
> It would be easier if elisp threads were orthogonal to= system threads,
> so that any elisp thread could be run on any available system thread.<= br>
Currently, only one thread can run ELisp at a time.=C2=A0 Whether that'= s
implemented using several system threads or not is largely an
internal detail.

> Multiprocessing could be done by creating multiple lisp VMs in a
> process (i.e. lisp VM orthogonal to a physical core),

Yes, "could".

I would go so f= ar as to say it's the safest approach, especially if preserving the sem= antics of existing programs is a goal.=C2=A0 I don't think attempting t= o make the lisp multiprocessing semantics slavishly replicate the host mult= iprocessing semantics is a good idea at all.=C2=A0 At least with portable d= umps/loads, there is a path to creating independent VMs (where the symbol t= able is local to the VM, and probably "headless" to start) in the= same process space.

It&= #39;s not too hard to come up with a design that makes sense, indeed, the problem is to actually do the work of bringing the current code to
that design.

True enough.=C2=A0 =C2=A0T= here are shorter paths than (whether naive or sophisticated) attempts to im= pose fine-grained locking on the emacs run-time to replicate the native fac= ilities for parallelism.=C2=A0 I am under the impression that the latter is= the prevailing view of what it would mean to bring efficient parallelism t= o emacs, which is unfortunate if the impression is correct.

<= /div>
Lynn
=C2=A0
--0000000000001131b005f9e3d0d9--