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: Thu, 17 Feb 2022 07:07:15 +0100 Message-ID: References: Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="00000000000095eb4b05d8309415" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="24760"; 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 Thu Feb 17 07:08:56 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 1nKZyJ-0006Ev-8S for guile-devel@m.gmane-mx.org; Thu, 17 Feb 2022 07:08:55 +0100 Original-Received: from localhost ([::1]:41612 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nKZyI-0004Dr-3w for guile-devel@m.gmane-mx.org; Thu, 17 Feb 2022 01:08:54 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:53640) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nKZww-000265-Up for guile-devel@gnu.org; Thu, 17 Feb 2022 01:07:30 -0500 Original-Received: from [2607:f8b0:4864:20::435] (port=33332 helo=mail-pf1-x435.google.com) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nKZwu-0006Wj-Fi for guile-devel@gnu.org; Thu, 17 Feb 2022 01:07:30 -0500 Original-Received: by mail-pf1-x435.google.com with SMTP id d17so4157483pfl.0 for ; Wed, 16 Feb 2022 22:07:27 -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=rXznNB7wae7I6TNsfA1EInrdva2nr0SiOmHdq5vzCMI=; b=P0yTu08d57PCiTGjkSBkY7E9Er6GEPK87szSQNEq6F+0va5NrJYzNaa/58xiImhIlj t0AIdmkip519Ucejkey2FKyl54ICXHasevdB17jUCkOGg8TkWTGhB7+VrZfm4N7SUqhx +9B5t/ckQX3cTi9VoPvnBCLqjtUxT5m4c6CUL0oYWYMtv+TA8mJqLDsWSomSXi+4X0rq BjlU8DCH45G/Oh3kZcLvXQwVS3TL7Km4WEtFCtC1oI1LSMxc4i4Bs2p8xFqgVniZR7rv SlvCgbF/aI2E7wju5iZRcegbbR8Pi4oyDevMemYgO1/ta06XLD0kGh7m7Brr6Tfk4nLI Vddg== 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=rXznNB7wae7I6TNsfA1EInrdva2nr0SiOmHdq5vzCMI=; b=ibtsqyvxbpcPP2IZk6t1dTkwZVWt3sMmbnf9ipQJovjP8PWrepPIGEv/aNfXYdVajx E/6DJb+xRYfIZgPrIOf09RXXPN5yx0eYDc2wzYfPpgkiOh444wP1UQ0Cgi9kXQCoHk2L 9t0xbwU68EZi9DeM3f5z+2qVVXvc5dYCsBURBNOWeaDrZ8RnXQhntpiP0MCLxJay0oNR 10atvZNItObaaKhTr7HyhUWxq75sJZ8F+lbd1Z7kPurVYuNrcPxhSUnHxRKkB/1iW2sC TPAAo5iz4NsG0J42G/KDimxzKJqIHZnUZZqZFeyatJjWeq2PeMPF6X7/9KhKIEv/9ofd 0FEA== X-Gm-Message-State: AOAM531FONXswha2vJVGJ9m8ataaYb2GPYWsWhrNQqXgXSlS+JnUkEmq xc0hJGCAfkQPsmOU7HbmJZ29Qbh4FAhoS6szHwelRwxskFQ= X-Google-Smtp-Source: ABdhPJzYhIzxqWeqe0qc+ZjytWzH986Lsye2a79pVt/+x7cFmS5J45pfXFWXk3SbfWxZ9DfA9fSuLocg16XUnbtmnUU= X-Received: by 2002:a63:555b:0:b0:365:8be:3d18 with SMTP id f27-20020a63555b000000b0036508be3d18mr1249206pgm.471.1645078046434; Wed, 16 Feb 2022 22:07:26 -0800 (PST) In-Reply-To: X-Host-Lookup-Failed: Reverse DNS lookup failed for 2607:f8b0:4864:20::435 (failed) Received-SPF: pass client-ip=2607:f8b0:4864:20::435; envelope-from=stefan.itampe@gmail.com; helo=mail-pf1-x435.google.com X-Spam_score_int: -2 X-Spam_score: -0.3 X-Spam_bar: / X-Spam_report: (-0.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.978, 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:21125 Archived-At: --00000000000095eb4b05d8309415 Content-Type: text/plain; charset="UTF-8" I have been working on improving the interface, And this works (define gen (make-generator (lambda (x) (let lp ((i 0)) (when (< i 20000000) (return x i) (lp (+ i 1))))))) (define (test) (let ((g (gen))) (let lp ((s 0)) (let ((i (next g))) (if (eq? i 'finished) s (lp (+ s i))))))) This nice funktional interface runs with no measurable speed overhead compared to old cases. Also this is essentially python generators and this code runs in 0.3s where a python generator example runs in 0.5s, using delimited continuation we are talking about 6-7s. On Sun, Feb 13, 2022 at 11:31 AM Stefan Israelsson Tampe < stefan.itampe@gmail.com> wrote: > (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? >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> . >>> >>> >>> >> --00000000000095eb4b05d8309415 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
I have been working on improving the interface, And t= his works
(define gen
=C2=A0 (make-generator
=C2=A0 =C2=A0(lambd= a (x)
=C2=A0 =C2=A0 =C2=A0(let lp ((i 0))
=C2=A0 =C2=A0 =C2=A0 =C2=A0= (when (< i 20000000)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(return x i)=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(lp (+ i 1)))))))

(define (test)=
=C2=A0 (let ((g (gen)))
=C2=A0 =C2=A0 (let lp ((s 0))
=C2=A0 =C2= =A0 =C2=A0 (let ((i (next g)))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 (if (eq? i &#= 39;finished)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 s
=C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (lp (+ s i)))))))

Th= is nice funktional interface runs with no measurable speed overhead compare= d to old cases. Also this is essentially python generators and this code ru= ns in 0.3s where a python generator example runs in 0.5s, using delimited c= ontinuation we are talking about 6-7s.

On Sun, Feb 13, 2022 at 11:31 A= M Stefan Israelsson Tampe <st= efan.itampe@gmail.com> wrote:
(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 (te= st-1)
=C2=A0 (let ((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 (cond
=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 parent)
=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 leave)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (pk 'lea= ve))
=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)<= br>=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 (set! 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 'finish x)
=C2=A0 =C2=A0 ret))

On Sun, Feb 13, 2022 at 11= :27 AM Mikael Djurfeldt <mikael@djurfeldt.com> wrote:
Hi,

I'm trying to understand this.

The example of a generator which y= ou give below counts upwards, but I don't see how the value of n is pas= sed out of the generator.

Could you give another example of a generator which does pass out the val= ues, along with a usage case which prints out the values returned by the ge= nerator?

Best regards,
Mikael

Den tors 10 feb. 2022 17:52Stefan Israelsson = Tampe <stef= an.itampe@gmail.com> skrev:
Consider a memory barrier=C2=A0idiom co= nstructed from=C2=A0
0, (mk-stack)
1. (enter x)
2. (p= ause x)
3. (leave x)

The idea is t= hat we create a separate stack object and when entering it, we will swap th= e 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 position in= case of a pause, when pausing stack x, we=C2=A0will 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=C2=A0'leave a= nd move to=C2=A0the old stack, using the current
ip. At first enc= ounter the function=C2=A0stack frame is copied over hence there will be a f= ork limited to the function=C2=A0only.

This means = 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
(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 '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))))))))
<= div>
A paused or leaved stack cannot be paused, an entered=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 delimited= continuations that one does not need to copy the whole stack and potential= ly speed up generator=C2=A0like constructs. But not only this,=C2=A0writing= 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 p= rolog code significantly.

How would we approach th= e=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 case of fail= ure
cc =3D the continuation

(<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 heuristics to store = already made stacks when=C2=A0
leaving a stack and reuse at the n= ext enter which is a common theme in prolog,

Anyho= w we have an issue, consider the case where everythings succeds=C2=A0foreve= r. Then we will blow the stack . There is no concept=C2=A0of tail calls her= e. 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))))

This enable cut= s so that a cutted and (and!) in kanren lingo will use
(goal2 x c= c)

And we have tail calls!


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

The drawback with this is if a functi= on uses a lot of stack, it will be a memory hog.

W= DYT?




=




=

.

=C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0=C2=A0
--00000000000095eb4b05d8309415--