From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Mikael Djurfeldt Newsgroups: gmane.lisp.guile.devel Subject: Re: Pausable continuations Date: Sun, 13 Feb 2022 11:27:43 +0100 Message-ID: References: Reply-To: mikael@djurfeldt.com Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="000000000000c2d22705d7e3c033" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="28706"; mail-complaints-to="usenet@ciao.gmane.io" Cc: guile-devel To: Stefan Israelsson Tampe Original-X-From: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Sun Feb 13 11:28:28 2022 Return-path: Envelope-to: guile-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 1nJC7H-0007KL-N7 for guile-devel@m.gmane-mx.org; Sun, 13 Feb 2022 11:28:27 +0100 Original-Received: from localhost ([::1]:54390 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nJC7G-0002iP-9j for guile-devel@m.gmane-mx.org; Sun, 13 Feb 2022 05:28:26 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:56162) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nJC73-0002hB-TG for guile-devel@gnu.org; Sun, 13 Feb 2022 05:28:14 -0500 Original-Received: from mail-ua1-f48.google.com ([209.85.222.48]:34340) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nJC6z-0006Lf-QZ for guile-devel@gnu.org; Sun, 13 Feb 2022 05:28:11 -0500 Original-Received: by mail-ua1-f48.google.com with SMTP id 60so6718420uae.1 for ; Sun, 13 Feb 2022 02:27:55 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:reply-to :from:date:message-id:subject:to:cc; bh=oQLLI7PtYwZqgPgttxXOmc9bH3CKaGAyWVUXBcqaMLs=; b=oDCjY9A0odf9mb/0Cuduca5R9agYCjYkghgYDMhH7IUXOPM0bo5EElZSfxcLEmAuvl zlaSTY4z/MDTIge3dXAgrD8DEHhODECa5pc2/0ytepyVWTlBZz1Nn4qV26WUmbIx0+Dj d7Q5BI0n99ED6B+r1QAlBfxiHsBU+zqWDXro3GkXdUAO5ewgKQU0pSKpETOTE9/GJEVK jgfUcLkCuUcVxNzAwujSXznMDS+lFaT2+YlUuQ0ldE81/5yHmsRp40GifMQgitPBlEyi tRO91zT9n6ShM918A2OQw1IHEU6ogu172hXbjuI4TYOZhge6MePl5+IQG2E1MAuf2M1g rV7w== X-Gm-Message-State: AOAM533fS/egOOXDQTdP3RelJzMIIuVHFPdBDO5NtTlObtYYWGDJgajK 9QtTuebog7R+KndEX7OnYigMTYKnNc8mI3RXxbmgxlFXIqo= X-Google-Smtp-Source: ABdhPJx+xu9IDODpP4rz9hzHEmkra0i35WdzE2U03WtvB5DwlKZxc96V/2kLQrdaFcN4MLtiNWSpYS8ORDZdE+6f1cA= X-Received: by 2002:ab0:3045:: with SMTP id x5mr2587990ual.17.1644748075091; Sun, 13 Feb 2022 02:27:55 -0800 (PST) In-Reply-To: Received-SPF: pass client-ip=209.85.222.48; envelope-from=mdjurfeldt@gmail.com; helo=mail-ua1-f48.google.com X-Spam_score_int: -13 X-Spam_score: -1.4 X-Spam_bar: - X-Spam_report: (-1.4 / 5.0 requ) BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.249, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.248, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=no autolearn_force=no X-Spam_action: no action X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Original-Sender: "guile-devel" Xref: news.gmane.io gmane.lisp.guile.devel:21110 Archived-At: --000000000000c2d22705d7e3c033 Content-Type: text/plain; charset="UTF-8" Hi, I'm trying to understand this. The example of a generator which you give below counts upwards, but I don't see how the value of n is passed out of the generator. Could you give another example of a generator which does pass out the values, along with a usage case which prints out the values returned by the generator? Best regards, Mikael Den tors 10 feb. 2022 17:52Stefan Israelsson Tampe skrev: > Consider a memory barrier idiom constructed from > 0, (mk-stack) > 1. (enter x) > 2. (pause x) > 3. (leave x) > > The idea is that we create a separate stack object and when entering it, > we will swap the current stack with the one in the argument saving the > current stack in x and be in the 'child' state and move to a paused > position in case of a pause, when pausing stack x, we will return to where > after where entered saving the current position in stack and ip, and be in > state 'pause' and when we leave we will be in the state 'leave and move > to the old stack, using the current > ip. At first encounter the function stack frame is copied over hence there > will be a fork limited to the function only. > > This means that we essentially can define a generator as > (define (g x) > (let lp ((n 0)) > (if (< n 10) > (begin > (pause x) > (lp (+ n 1)))))) > > And use it as > (define (test) > (let ((x (mk-stack))) > (let lp () > (case (enter x) > ((pause) > (pk 'pause) > (lp)) > ((child) > (g x) > (leave x)))))))) > > A paused or leaved stack cannot be paused, an entered stack cannot be > entered and one cannot leave a paused stack, but enter a leaved stack. > > Anyhow this idea is modeled like a fork command instead of functional and > have the benefit over delimited continuations that one does not need to > copy the whole stack and potentially speed up generator like constructs. > But not only this, writing efficient prolog code is possible as well. We > could simplify a lot of the generation of prolog code, speed it up and also > improve compiler speed of prolog code significantly. > > How would we approach the prolog code. The simplest system is to use > return the > alternate pause stack when succeeding things becomes very simple, > > x = stack to pause to in case of failure > cc = the continuation > > ( (x cc) goal1 goal2) > :: (cc (goal1 (goal2 x)) > > ( (x cc) goal1 goal2) > :: (let ((xx (mkstack))) > (case (enter xx) > ((child) > (cc (goal2 xx))) > > ((pause) > (cc (goal2 x))))) > > Very elegant, and we also can use some heuristics to store already made > stacks when > leaving a stack and reuse at the next enter which is a common theme in > prolog, > > Anyhow we have an issue, consider the case where everythings > succeds forever. Then we will blow the stack . There is no concept of tail > calls here. So what you can do is the following for an , > > (let ((xx (mk-stack))) > (case (enter xx) > ((child) > (goal1 x (lambda (xxx) (pause xx xxx))) > > ((pause xxx) > (goal2 xxx cc)))) > > This enable cuts so that a cutted and (and!) in kanren lingo will use > (goal2 x cc) > > And we have tail calls! > > > I have a non jitted version guile working as a proof of concept. > > The drawback with this is if a function uses a lot of stack, it will be a > memory hog. > > WDYT? > > > > > > > > > > > > . > > > --000000000000c2d22705d7e3c033 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi,

I&#= 39;m trying to understand this.

The example of a generator which you give below counts upwards, b= ut I don't see how the value of n is passed out of the generator.
=

Could you give another exampl= e of a generator which does pass out the values, along with a usage case wh= ich prints out the values returned by the generator?

Best regards,
Mikael
Den= tors 10 feb. 2022 17:52Stefan Israelsson Tampe <stefan.itampe@gmail.com> skrev:
Consider a memory barrier=C2=A0idi= om constructed from=C2=A0
0, (mk-stack)
1. (enter x)
= 2. (pause x)
3. (leave x)

The idea= is that we create a separate stack object and when entering it, we will sw= ap the current stack with the one in the argument saving the current stack = in x=C2=A0 and be in the 'child' state and move to a paused positio= n in case of a pause, when pausing stack x, we=C2=A0will return to where af= ter where entered saving the current position in stack and ip, and be in st= ate 'pause' and when we leave we will be in the state=C2=A0'lea= ve and move to=C2=A0the old stack, using the current
ip. At first= encounter the function=C2=A0stack frame is copied over hence there will be= a fork limited to the function=C2=A0only.

This me= ans that we essentially can define a generator as
(define (g x)
=C2=A0 (let lp ((n 0))
=C2=A0 =C2=A0 (if (< n 10)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 (begin
=C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0(pause x)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0(lp (+ n 1))))))

And use it as
(de= fine (test)
=C2=A0 =C2=A0 (let ((x (mk-stack)))
=C2=A0 = =C2=A0 =C2=A0 =C2=A0 (let lp ()
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0(case (enter x)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0((pause)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(pk 'pause)
=C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(lp))
=C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 ((child)
=C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(g x)
=C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(leave x))))))))=

A paused or leaved stack cannot be paused, an ent= ered=C2=A0stack cannot be entered and one cannot leave a paused stack, but = enter a leaved stack.

Anyhow this idea is modeled = like a fork command instead=C2=A0of functional and have the benefit over de= limited continuations that one does not need to copy the whole stack and po= tentially speed up generator=C2=A0like constructs. But not only this,=C2=A0= writing efficient prolog code is possible as well. We could simplify a lot = of the generation of prolog code, speed it up and also improve compiler spe= ed of prolog code significantly.

How would we appr= oach the=C2=A0 prolog code.=C2=A0The simplest system is to use return the= =C2=A0
alternate pause stack when succeeding things becomes very = simple,

x=C2=A0 =C2=A0=3D stack to pause to in cas= e of failure
cc =3D the continuation

(&l= t;and> (x cc)=C2=A0 goal1 goal2)=C2=A0=C2=A0
=C2=A0 =C2=A0 =C2= =A0:: (cc (goal1 (goal2 x))

(<or >=C2=A0 =C2= =A0(x cc)=C2=A0 goal1 goal2)=C2=A0=C2=A0
=C2=A0 =C2=A0 ::=C2=A0 (= let ((xx (mkstack)))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0(case (enter xx)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0((child)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 (cc (goal2 xx)))

=C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 ((pause)
=C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(cc (goal2 x))))= )

Very elegant, and we also can use some heuristic= s to store already made stacks when=C2=A0
leaving a stack and reu= se at the next enter which is a common theme in prolog,

Anyhow we have an issue, consider the case where everythings succeds= =C2=A0forever. Then we will blow the stack . There is no concept=C2=A0of ta= il calls here. So what you can do is the following for an <and>,

(let ((xx (mk-stack)))
=C2=A0 =C2=A0 (case (= enter xx)
=C2=A0 =C2=A0 =C2=A0 ((child)
=C2=A0 =C2=A0 = =C2=A0 =C2=A0(goal1 x (lambda (xxx) (pause xx xxx)))
=C2=A0 =C2= =A0 =C2=A0 =C2=A0
=C2=A0 =C2=A0 =C2=A0 ((pause xxx)
=C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(goal2 xxx cc))))

T= his enable cuts so that a cutted and (and!) in kanren lingo will use
<= div>(goal2 x cc)

And we have tail calls!


I have a non jitted version guile working as= a proof of concept.=C2=A0

The drawback with this = is if a function uses a lot of stack, it will be a memory hog.
WDYT?



<= br>




<= br>


.

=C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=C2=A0
--000000000000c2d22705d7e3c033--