From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Israelsson Tampe Newsgroups: gmane.lisp.guile.devel Subject: Re: Pausable continuations Date: Sun, 13 Feb 2022 11:31:41 +0100 Message-ID: References: Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="000000000000e8bdfa05d7e3ce5b" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="5418"; mail-complaints-to="usenet@ciao.gmane.io" Cc: guile-devel To: Mikael Djurfeldt Original-X-From: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Sun Feb 13 11:32:20 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 1nJCB2-00019w-FY for guile-devel@m.gmane-mx.org; Sun, 13 Feb 2022 11:32:20 +0100 Original-Received: from localhost ([::1]:55948 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nJCB0-0003yU-Oa for guile-devel@m.gmane-mx.org; Sun, 13 Feb 2022 05:32:18 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:56840) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nJCAe-0003uK-U5 for guile-devel@gnu.org; Sun, 13 Feb 2022 05:31:56 -0500 Original-Received: from [2607:f8b0:4864:20::42f] (port=37433 helo=mail-pf1-x42f.google.com) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nJCAc-00070M-L3 for guile-devel@gnu.org; Sun, 13 Feb 2022 05:31:56 -0500 Original-Received: by mail-pf1-x42f.google.com with SMTP id y5so24253612pfe.4 for ; Sun, 13 Feb 2022 02:31:53 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=qcV7W55K/eob3EOStMhc1WgTZbySbgJ24uiRQINaBVw=; b=coVJxIVIzlMsQPYe0aLu8iIdZgxq4GolXfpBr/p9luB/OpVZuWJTpXwwXNWSIPLdql ikE3AD/Rb1CQ0lH6s4uGxjBno6Pv96Yusr55rklm/wbC+o9qMBvDeDAcOMknadmK/W4p Gw9zt4TOzwdqpJAmMYwdLLKWbi7Wu+Mq2ugjKRzVlEy5aTYOBybq7CabhHjSy1tsm2Rx /wWSeGo/AnJ4sjMlH0u8PPMR2GBc6A1RIjtmDQIq+KkhOxCiiC9Qgv7+fktFQbUHoQrO cCLf66nEEoMYjRvlxanABlgs/XBYPVXXDoMdQx+gJZVXub6nSQE9eUP9HskzhQ3yLZrf T5gg== 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:from:date :message-id:subject:to:cc; bh=qcV7W55K/eob3EOStMhc1WgTZbySbgJ24uiRQINaBVw=; b=M1rwNfiyElAs3s9rj6sc4Igm4+Q0pTfpqZ5Pq+21htLwlqI5Sho1tfJ6QLRg/TjkGn pDa/CImMqBnC5uWlVqSgO2VghVdJE7LU3DiP/nptuKrQQbQHsg6c08LSMlYGi7d77dpu /LwjH7nf0oNnBo+fgWbucTxAF4xWfCzmoutPZka7UcBxjePFD+4EIhqJIjJCccRPs0V8 q+8FTqi+Njqt0lkojQj/y6fIuS1dQFdfMPkROASQZRhPNv+WWwZRZdN0hGQD935azx+k fiZxpPvnf36mm8Gbav/IkCybsLltMhuJUAgUoGrhd62OHHyMAWz6JzWRKIjjfeOGeHOX xkTw== X-Gm-Message-State: AOAM532d5oBAj3qYUBbzUuqTPyOxn5UC+Lxc1me2XdwmsnE3JIStRDNK P4YcMSUL3587NuPw43J/ScpAMeU7mOYa/6hhLxA0z4E8JNc= X-Google-Smtp-Source: ABdhPJx0Y6/IRfz0pVVvDqlL+mv/bp4Er9wt3Gze76Nv4tkbekiKvymBrZRcTrk38p+IT1IQmW91qpAWay+XN7HkrUE= X-Received: by 2002:a62:1ace:: with SMTP id a197mr9434514pfa.63.1644748312459; Sun, 13 Feb 2022 02:31:52 -0800 (PST) In-Reply-To: X-Host-Lookup-Failed: Reverse DNS lookup failed for 2607:f8b0:4864:20::42f (failed) Received-SPF: pass client-ip=2607:f8b0:4864:20::42f; envelope-from=stefan.itampe@gmail.com; helo=mail-pf1-x42f.google.com X-Spam_score_int: -12 X-Spam_score: -1.3 X-Spam_bar: - X-Spam_report: (-1.3 / 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, PDS_HP_HELO_NORDNS=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RDNS_NONE=0.793, 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:21111 Archived-At: --000000000000e8bdfa05d7e3ce5b Content-Type: text/plain; charset="UTF-8" (define (f x) (let lp ((i 0)) (if (< i 10) (begin (pk 'value-from-parent (pause x i)) (lp (+ i 1)))))) (define (test-1) (let ((x (make-pause-stack)) (ret 0)) (let lp ((i 0)) (let-values (((k x) (resume x (- i)))) (cond ((= k pause) (pk 'value-from-child x) (lp (+ i 1))) ((= k parent) (pk 'parent)) ((= k leave) (pk 'leave)) ((= k child) (pk 'child) (f x) (leave x) (set! ret i))))) (pk 'finish x) ret)) On Sun, Feb 13, 2022 at 11:27 AM Mikael Djurfeldt wrote: > 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 < > stefan.itampe@gmail.com> 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? >> >> >> >> >> >> >> >> >> >> >> >> . >> >> >> > --000000000000e8bdfa05d7e3ce5b Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
(define (f x)
=C2=A0 (let lp ((i 0))
=C2=A0 =C2=A0 (= if (< i 10)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 (begin
=C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 (pk 'value-from-parent (pause x i))
=C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 (lp (+ i 1))))))

(define (test-1)
=C2=A0 (le= t ((x =C2=A0 (make-pause-stack))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 (ret 0))=C2=A0 =C2=A0 (let lp ((i 0)) =C2=A0 =C2=A0 =C2=A0
=C2=A0 =C2=A0 =C2=A0= (let-values (((k x) (resume x (- i))))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 (con= d
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0((=3D k pause)
=C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 (pk 'value-from-child x)
=C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 (lp (+ i 1)))

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0((=3D k p= arent)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (pk 'parent))
=C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0((=3D k le= ave)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (pk 'leave))
=C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0((=3D k child= )
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (pk 'child)
=C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 (f x) =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0
=C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 (leave x)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (s= et! ret =C2=A0i)))))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0
=C2=A0 =C2=A0 =C2=A0
=C2=A0 =C2=A0 (pk 'fi= nish x)
=C2=A0 =C2=A0 ret))

On Sun, Feb 13, 2022 at 11:27 AM Mikael D= jurfeldt <mikael@djurfeldt.com> wrote:
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
<= br>
Den tor= s 10 feb. 2022 17:52Stefan Israelsson Tampe <stefan.itampe@gmail.com> skrev:
C= onsider a memory barrier=C2=A0idiom constructed from=C2=A0
0, (mk-stack= )
1. (enter x)
2. (pause x)
3. (leave x)<= /div>

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 a= rgument saving the current stack in x=C2=A0 and be in the 'child' s= tate and move to a paused position in case of a pause, when pausing stack x= , we=C2=A0will return to where after where entered saving the current posit= ion in stack and ip, and be in state 'pause' and when we leave we w= ill be in the state=C2=A0'leave and move to=C2=A0the old stack, using t= he current
ip. At first encounter the function=C2=A0stack frame i= s copied over hence there will be a fork limited to the function=C2=A0only.=

This means that we essentially can define a gener= ator 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<= /div>
=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
(define (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 'paus= e)
=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 s= tack cannot be paused, an entered=C2=A0stack cannot be entered and one cann= ot 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 delimited continuations that one does not need t= o copy the whole stack and potentially speed up generator=C2=A0like constru= cts. But not only this,=C2=A0writing efficient prolog code is possible as w= ell. 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=C2=A0 prolog code.=C2=A0The simplest = system is to use return the=C2=A0
alternate pause stack when succ= eeding things becomes very simple,

x=C2=A0 =C2=A0= =3D stack to pause to in case of failure
cc =3D the continuation<= /div>

(<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
<= div>=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 a= lso can use some heuristics to store already made stacks when=C2=A0
leaving a stack and reuse at the next enter which is a common theme in p= rolog,

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 tail calls here. So what you can do is the following= for an <and>,

(let ((xx (mk-stack)))
<= div>=C2=A0 =C2=A0 (case (enter xx)
=C2=A0 =C2=A0 =C2=A0 ((child)<= /div>
=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 ((pa= use xxx)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(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 ve= rsion guile working as a proof of concept.=C2=A0

T= he drawback with this is if a function uses a lot of stack, it will be a me= mory hog.

WDYT?











.

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=C2=A0
--000000000000e8bdfa05d7e3ce5b--