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: Pausable continuations Date: Thu, 10 Feb 2022 14:07:04 +0100 Message-ID: Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="000000000000236c4d05d7a9a131" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="6682"; mail-complaints-to="usenet@ciao.gmane.io" To: guile-devel Original-X-From: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Thu Feb 10 17:52:53 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 1nICgf-0001b9-0S for guile-devel@m.gmane-mx.org; Thu, 10 Feb 2022 17:52:53 +0100 Original-Received: from localhost ([::1]:45986 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nICgd-0002kz-L2 for guile-devel@m.gmane-mx.org; Thu, 10 Feb 2022 11:52:51 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:38998) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nI9AR-000443-P9 for guile-devel@gnu.org; Thu, 10 Feb 2022 08:07:27 -0500 Original-Received: from [2607:f8b0:4864:20::1031] (port=55826 helo=mail-pj1-x1031.google.com) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nI9AM-0005NL-R1 for guile-devel@gnu.org; Thu, 10 Feb 2022 08:07:20 -0500 Original-Received: by mail-pj1-x1031.google.com with SMTP id om7so5090093pjb.5 for ; Thu, 10 Feb 2022 05:07:17 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:from:date:message-id:subject:to; bh=623UNnoVfj+j1flwqIvwasq5Vp0NpFgH8l3O8DlrZqM=; b=RFuxhfRj9ChLNuoh0kFsBiy8MnVXkiCPG6OEJCYUlwBU2VnTOGBlN74aVRgQ3pXQL9 kvVeoheuZCGG2lJL0ZezoZZd3j4hP+Wy83IEfsMkN4d5vDdXqDukbh0jRobN3IT49JWh zENRscOkrqH2IQrwRCEsxLXcC3OdJGIUg01s/xrMRHjyvlYHopfCTqDsSbcY2efRgj0Q CaI/MPpnXdtHEaNxfpyU+M/IHWQnhvW6cuiw8MOyNfMU6M8g+Oy6Bn2XTzxIorXLb7JP qYayd/vD1RZGDnuKfknX0qnj/wV0ehtOTfVsyrdMt8D9PCJ164UDZmH4rkeFPzHMqx2M +p4Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=623UNnoVfj+j1flwqIvwasq5Vp0NpFgH8l3O8DlrZqM=; b=X20SlDr1Fd9q9szn7NpL0XhYG2g/Pi3F7IP3kFtsdHMgslNvqPyIoeIgTtGxKI3CAJ JHu/61UkUavv/f/zVS5tiNxpIkCT17uxYOMozgG0OWGUmOcwhQK9kMUrn5fAsUE40mJ7 erYVpOWrfoHZZXixNtO7qYcRjy8PvgsyhSpUxjYOMmB6emo5g6yFplbidSrO56LvlfOJ ct4FIMNWksLi02Z8ig73RfDFuYza+WnFIcCGxpBR76334fTM4DFSLvabyRTHsVfiBz25 zwmuN/PEXSD05OdGrfagrICHx4+uk67B2vpI+sWTBgAsNQkk/MIe3JPEAMwa2/r5DrR+ Jy8w== X-Gm-Message-State: AOAM531eRy6mCqSUkkRVFdgUYSwfFTYmbRJJlFe3gfDVJvtFWWS5lHi8 Vs55Vxq5uJY37d0Zfa+NWtLivnmV0BfHyBSSEdR1O3jPH3s= X-Google-Smtp-Source: ABdhPJyn4YIjS1+FivN7vhC+Fi3u2dv28DsGBq9frro7TPYb+t36KCS0x9UOJeqaH6rT52a25FOeoa8q/S7OZZbFGb4= X-Received: by 2002:a17:902:a508:: with SMTP id s8mr7479841plq.173.1644498436450; Thu, 10 Feb 2022 05:07:16 -0800 (PST) X-Host-Lookup-Failed: Reverse DNS lookup failed for 2607:f8b0:4864:20::1031 (failed) Received-SPF: pass client-ip=2607:f8b0:4864:20::1031; envelope-from=stefan.itampe@gmail.com; helo=mail-pj1-x1031.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:21087 Archived-At: --000000000000236c4d05d7a9a131 Content-Type: text/plain; charset="UTF-8" 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? . --000000000000236c4d05d7a9a131 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Consider a memory barrier=C2=A0idiom constructed from=C2= =A0
0, (mk-stack)
1. (enter x)
2. (pause x)
3. (leave x)

The idea is that we create a s= eparate stack object and when entering it, we will swap the current stack w= ith the one in the argument saving the current stack in x=C2=A0 and be in t= he '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 savi= ng the current position in stack and ip, and be in state 'pause' an= d when we leave we will be in the state=C2=A0'leave and move to=C2=A0th= e old stack, using the current
ip. At first encounter the functio= n=C2=A0stack frame is copied over hence there will be a fork limited to the= function=C2=A0only.

This means that we essentiall= y can define a generator as
(define (g x)
=C2=A0 (let l= p ((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(pa= use x)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(lp (+ n 1))))))<= /div>

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))))))))

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 inste= ad=C2=A0of functional and have the benefit over delimited continuations tha= t one does not need to copy the whole stack and potentially speed up genera= tor=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 prol= og code, speed it up and also improve compiler speed of prolog code signifi= cantly.

How would we approach the=C2=A0 prolog cod= e.=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 failure
cc = =3D the continuation

(<and> (x cc)=C2=A0 goa= l1 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 goal= 2)=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 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 tail calls here. So what you can d= o 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 cuts so that a cutte= d 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.=C2=A0

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

WDYT?








.

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0
--000000000000236c4d05d7a9a131--