From: Stefan Israelsson Tampe <stefan.itampe@gmail.com>
To: Mikael Djurfeldt <mikael@djurfeldt.com>
Cc: guile-devel <guile-devel@gnu.org>
Subject: Re: Pausable continuations
Date: Thu, 17 Feb 2022 07:07:15 +0100 [thread overview]
Message-ID: <CAGua6m31aTtBdH9-_J9=ZWD89D8Y03qN=yCBxBixpMMhB0EJcw@mail.gmail.com> (raw)
In-Reply-To: <CAGua6m2Lx9NuncoZoaqeBBx4BvCjWBrydqeXzypG8actSyKGJA@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 5333 bytes --]
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 <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
>>
>> 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
>>>
>>> (<and> (x cc) goal1 goal2)
>>> :: (cc (goal1 (goal2 x))
>>>
>>> (<or > (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 <and>,
>>>
>>> (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?
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> .
>>>
>>>
>>>
>>
[-- Attachment #2: Type: text/html, Size: 7649 bytes --]
next prev parent reply other threads:[~2022-02-17 6:07 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-02-10 13:07 Pausable continuations Stefan Israelsson Tampe
2022-02-10 15:19 ` Stefan Israelsson Tampe
2022-02-11 12:06 ` Stefan Israelsson Tampe
2022-02-11 12:10 ` Stefan Israelsson Tampe
2022-02-11 18:56 ` Vijay Marupudi
[not found] ` <CAGua6m24aa+goaczoX-UaDCsGnKEAE6sBfH8Xx-2ks0UjOyvUQ@mail.gmail.com>
2022-02-13 9:34 ` Fwd: " Stefan Israelsson Tampe
2022-02-13 9:34 ` Stefan Israelsson Tampe
2022-02-13 10:27 ` Mikael Djurfeldt
2022-02-13 10:31 ` Stefan Israelsson Tampe
2022-02-17 6:07 ` Stefan Israelsson Tampe [this message]
2022-02-17 16:37 ` Vijay Marupudi
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/guile/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAGua6m31aTtBdH9-_J9=ZWD89D8Y03qN=yCBxBixpMMhB0EJcw@mail.gmail.com' \
--to=stefan.itampe@gmail.com \
--cc=guile-devel@gnu.org \
--cc=mikael@djurfeldt.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).