unofficial mirror of guile-devel@gnu.org 
 help / color / mirror / Atom feed
* Pausable continuations
@ 2022-02-10 13:07 Stefan Israelsson Tampe
  2022-02-10 15:19 ` Stefan Israelsson Tampe
  2022-02-13 10:27 ` Mikael Djurfeldt
  0 siblings, 2 replies; 11+ messages in thread
From: Stefan Israelsson Tampe @ 2022-02-10 13:07 UTC (permalink / raw)
  To: guile-devel

[-- Attachment #1: Type: text/plain, Size: 2979 bytes --]

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: 4270 bytes --]

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Pausable continuations
  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-13 10:27 ` Mikael Djurfeldt
  1 sibling, 1 reply; 11+ messages in thread
From: Stefan Israelsson Tampe @ 2022-02-10 15:19 UTC (permalink / raw)
  To: guile-devel

[-- Attachment #1: Type: text/plain, Size: 4217 bytes --]

I did some benchmark, consider this code below. Let's turn off the jit. Then
a 20M loop using normal delimited continuations yields,

;; 7.866898s real time, 14.809225s run time.  9.652291s spent in GC

With a pausing continuation or generator we end up with,
;; 0.965947s real time, 0.965588s run time.  0.000000s spent in GC.

python 3's similar generator example is executing at 0.5s for the same
looop.
so using delimited continuations to model pythons generators we have an
overhead of around 15X.

With jit,
;; 6.678504s real time, 13.589789s run time.  9.560317s spent in GC.

So we can't really get any speedup help from guile's jit here. The paused
jit version is not available as I have not figured out how to do this jet.

(define prompt (list 1))
(define (f)
  (let lp ((i 0))
    (when (< i 20000000)
      (begin
        (abort-to-prompt prompt)
        (lp (+ i 1))))))

(define (test2)
  (let lp ((k f))
    (call-with-prompt prompt k lp)))



On Thu, Feb 10, 2022 at 2:07 PM Stefan Israelsson Tampe <
stefan.itampe@gmail.com> wrote:

> 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: 6633 bytes --]

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Pausable continuations
  2022-02-10 15:19 ` Stefan Israelsson Tampe
@ 2022-02-11 12:06   ` Stefan Israelsson Tampe
  2022-02-11 12:10     ` Stefan Israelsson Tampe
  0 siblings, 1 reply; 11+ messages in thread
From: Stefan Israelsson Tampe @ 2022-02-11 12:06 UTC (permalink / raw)
  To: guile-devel

[-- Attachment #1: Type: text/plain, Size: 4788 bytes --]

I managed to make jitted code work for an example, speeds up the code up
2x. So in 1s ther is 40M ops per s
overhead in the generator construct, that's essentially 4x slower the
fastest it can do in a very simple loop. And matches
pythons generators and are 15x faster than the example code I have above.

On Thu, Feb 10, 2022 at 4:19 PM Stefan Israelsson Tampe <
stefan.itampe@gmail.com> wrote:

> I did some benchmark, consider this code below. Let's turn off the jit.
> Then
> a 20M loop using normal delimited continuations yields,
>
> ;; 7.866898s real time, 14.809225s run time.  9.652291s spent in GC
>
> With a pausing continuation or generator we end up with,
> ;; 0.965947s real time, 0.965588s run time.  0.000000s spent in GC.
>
> python 3's similar generator example is executing at 0.5s for the same
> looop.
> so using delimited continuations to model pythons generators we have an
> overhead of around 15X.
>
> With jit,
> ;; 6.678504s real time, 13.589789s run time.  9.560317s spent in GC.
>
> So we can't really get any speedup help from guile's jit here. The paused
> jit version is not available as I have not figured out how to do this jet.
>
> (define prompt (list 1))
> (define (f)
>   (let lp ((i 0))
>     (when (< i 20000000)
>       (begin
>         (abort-to-prompt prompt)
>         (lp (+ i 1))))))
>
> (define (test2)
>   (let lp ((k f))
>     (call-with-prompt prompt k lp)))
>
>
>
> On Thu, Feb 10, 2022 at 2:07 PM Stefan Israelsson Tampe <
> stefan.itampe@gmail.com> wrote:
>
>> 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: 7354 bytes --]

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Pausable continuations
  2022-02-11 12:06   ` Stefan Israelsson Tampe
@ 2022-02-11 12:10     ` Stefan Israelsson Tampe
  2022-02-11 18:56       ` Vijay Marupudi
  2022-02-13  9:34       ` Stefan Israelsson Tampe
  0 siblings, 2 replies; 11+ messages in thread
From: Stefan Israelsson Tampe @ 2022-02-11 12:10 UTC (permalink / raw)
  To: guile-devel

[-- Attachment #1: Type: text/plain, Size: 5517 bytes --]

Hmm, I can improve the delimited continuation speed slightly by doing the
below code


(define prompt (list 1))
(define (f2)
  (let lp ((i 0))
    (when (< i 20000000)
      (begin
        (abort-to-prompt prompt)
        (lp (+ i 1)))))
  #f)

 ; 5.906402s real time, 12.297234s run time.  8.894807s spent in GC.

So we are actually around 12X faster.

(define (test2)
  (let lp ((k f2))
    (let ((k (call-with-prompt prompt k (lambda (k) k))))
      (if k (lp k) #f))))


On Fri, Feb 11, 2022 at 1:06 PM Stefan Israelsson Tampe <
stefan.itampe@gmail.com> wrote:

> I managed to make jitted code work for an example, speeds up the code up
> 2x. So in 1s ther is 40M ops per s
> overhead in the generator construct, that's essentially 4x slower the
> fastest it can do in a very simple loop. And matches
> pythons generators and are 15x faster than the example code I have above.
>
> On Thu, Feb 10, 2022 at 4:19 PM Stefan Israelsson Tampe <
> stefan.itampe@gmail.com> wrote:
>
>> I did some benchmark, consider this code below. Let's turn off the jit.
>> Then
>> a 20M loop using normal delimited continuations yields,
>>
>> ;; 7.866898s real time, 14.809225s run time.  9.652291s spent in GC
>>
>> With a pausing continuation or generator we end up with,
>> ;; 0.965947s real time, 0.965588s run time.  0.000000s spent in GC.
>>
>> python 3's similar generator example is executing at 0.5s for the same
>> looop.
>> so using delimited continuations to model pythons generators we have an
>> overhead of around 15X.
>>
>> With jit,
>> ;; 6.678504s real time, 13.589789s run time.  9.560317s spent in GC.
>>
>> So we can't really get any speedup help from guile's jit here. The paused
>> jit version is not available as I have not figured out how to do this jet.
>>
>> (define prompt (list 1))
>> (define (f)
>>   (let lp ((i 0))
>>     (when (< i 20000000)
>>       (begin
>>         (abort-to-prompt prompt)
>>         (lp (+ i 1))))))
>>
>> (define (test2)
>>   (let lp ((k f))
>>     (call-with-prompt prompt k lp)))
>>
>>
>>
>> On Thu, Feb 10, 2022 at 2:07 PM Stefan Israelsson Tampe <
>> stefan.itampe@gmail.com> wrote:
>>
>>> 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: 8681 bytes --]

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Pausable continuations
  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       ` Stefan Israelsson Tampe
  1 sibling, 1 reply; 11+ messages in thread
From: Vijay Marupudi @ 2022-02-11 18:56 UTC (permalink / raw)
  To: Stefan Israelsson Tampe, guile-devel

This is exciting work, thanks for sharing! Maybe non-continuable
exceptions could be based on pausing continuations.

~ Vijay



^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Pausable continuations
  2022-02-11 12:10     ` Stefan Israelsson Tampe
  2022-02-11 18:56       ` Vijay Marupudi
@ 2022-02-13  9:34       ` Stefan Israelsson Tampe
  1 sibling, 0 replies; 11+ messages in thread
From: Stefan Israelsson Tampe @ 2022-02-13  9:34 UTC (permalink / raw)
  To: guile-devel

[-- Attachment #1: Type: text/plain, Size: 5983 bytes --]

The case with A simple loop of 20M operations are now down to 0.3 s that's
almost 20X improvements over
the best delimited continuation example (6s). Cpython takes 0.5s!

On Fri, Feb 11, 2022 at 1:10 PM Stefan Israelsson Tampe <
stefan.itampe@gmail.com> wrote:

> Hmm, I can improve the delimited continuation speed slightly by doing the
> below code
>
>
> (define prompt (list 1))
> (define (f2)
>   (let lp ((i 0))
>     (when (< i 20000000)
>       (begin
>         (abort-to-prompt prompt)
>         (lp (+ i 1)))))
>   #f)
>
>  ; 5.906402s real time, 12.297234s run time.  8.894807s spent in GC.
>
> So we are actually around 12X faster.
>
> (define (test2)
>   (let lp ((k f2))
>     (let ((k (call-with-prompt prompt k (lambda (k) k))))
>       (if k (lp k) #f))))
>
>
> On Fri, Feb 11, 2022 at 1:06 PM Stefan Israelsson Tampe <
> stefan.itampe@gmail.com> wrote:
>
>> I managed to make jitted code work for an example, speeds up the code up
>> 2x. So in 1s ther is 40M ops per s
>> overhead in the generator construct, that's essentially 4x slower the
>> fastest it can do in a very simple loop. And matches
>> pythons generators and are 15x faster than the example code I have above.
>>
>> On Thu, Feb 10, 2022 at 4:19 PM Stefan Israelsson Tampe <
>> stefan.itampe@gmail.com> wrote:
>>
>>> I did some benchmark, consider this code below. Let's turn off the jit.
>>> Then
>>> a 20M loop using normal delimited continuations yields,
>>>
>>> ;; 7.866898s real time, 14.809225s run time.  9.652291s spent in GC
>>>
>>> With a pausing continuation or generator we end up with,
>>> ;; 0.965947s real time, 0.965588s run time.  0.000000s spent in GC.
>>>
>>> python 3's similar generator example is executing at 0.5s for the same
>>> looop.
>>> so using delimited continuations to model pythons generators we have an
>>> overhead of around 15X.
>>>
>>> With jit,
>>> ;; 6.678504s real time, 13.589789s run time.  9.560317s spent in GC.
>>>
>>> So we can't really get any speedup help from guile's jit here. The
>>> paused jit version is not available as I have not figured out how to do
>>> this jet.
>>>
>>> (define prompt (list 1))
>>> (define (f)
>>>   (let lp ((i 0))
>>>     (when (< i 20000000)
>>>       (begin
>>>         (abort-to-prompt prompt)
>>>         (lp (+ i 1))))))
>>>
>>> (define (test2)
>>>   (let lp ((k f))
>>>     (call-with-prompt prompt k lp)))
>>>
>>>
>>>
>>> On Thu, Feb 10, 2022 at 2:07 PM Stefan Israelsson Tampe <
>>> stefan.itampe@gmail.com> wrote:
>>>
>>>> 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: 9256 bytes --]

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Fwd: Pausable continuations
       [not found]         ` <CAGua6m24aa+goaczoX-UaDCsGnKEAE6sBfH8Xx-2ks0UjOyvUQ@mail.gmail.com>
@ 2022-02-13  9:34           ` Stefan Israelsson Tampe
  0 siblings, 0 replies; 11+ messages in thread
From: Stefan Israelsson Tampe @ 2022-02-13  9:34 UTC (permalink / raw)
  To: guile-devel

[-- Attachment #1: Type: text/plain, Size: 951 bytes --]

---------- Forwarded message ---------
From: Stefan Israelsson Tampe <stefan.itampe@gmail.com>
Date: Sat, Feb 12, 2022 at 5:04 AM
Subject: Re: Pausable continuations
To: Vijay Marupudi <vijay@vijaymarupudi.com>


I would say that they represent the same idea but that using separate
stacks is an optimization and I intended to explore what to
gain with such a construct and possible variants. The final interface and
implementation will most likely differ, if we decide that
we want this, and be more well designed and integrated. But I intend to put
it in use in different applications and try to take
it to it's limits. Let me know if I shall publish the branch I'm working in
and what's the best way to publish it.

Regards
Stefan

On Fri, Feb 11, 2022 at 7:56 PM Vijay Marupudi <vijay@vijaymarupudi.com>
wrote:

> This is exciting work, thanks for sharing! Maybe non-continuable
> exceptions could be based on pausing continuations.
>
> ~ Vijay
>

[-- Attachment #2: Type: text/html, Size: 1645 bytes --]

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Pausable continuations
  2022-02-10 13:07 Pausable continuations Stefan Israelsson Tampe
  2022-02-10 15:19 ` Stefan Israelsson Tampe
@ 2022-02-13 10:27 ` Mikael Djurfeldt
  2022-02-13 10:31   ` Stefan Israelsson Tampe
  1 sibling, 1 reply; 11+ messages in thread
From: Mikael Djurfeldt @ 2022-02-13 10:27 UTC (permalink / raw)
  To: Stefan Israelsson Tampe; +Cc: guile-devel

[-- Attachment #1: Type: text/plain, Size: 3600 bytes --]

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: 5193 bytes --]

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Pausable continuations
  2022-02-13 10:27 ` Mikael Djurfeldt
@ 2022-02-13 10:31   ` Stefan Israelsson Tampe
  2022-02-17  6:07     ` Stefan Israelsson Tampe
  0 siblings, 1 reply; 11+ messages in thread
From: Stefan Israelsson Tampe @ 2022-02-13 10:31 UTC (permalink / raw)
  To: Mikael Djurfeldt; +Cc: guile-devel

[-- Attachment #1: Type: text/plain, Size: 4421 bytes --]

(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: 6501 bytes --]

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Pausable continuations
  2022-02-13 10:31   ` Stefan Israelsson Tampe
@ 2022-02-17  6:07     ` Stefan Israelsson Tampe
  2022-02-17 16:37       ` Vijay Marupudi
  0 siblings, 1 reply; 11+ messages in thread
From: Stefan Israelsson Tampe @ 2022-02-17  6:07 UTC (permalink / raw)
  To: Mikael Djurfeldt; +Cc: guile-devel

[-- 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 --]

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Pausable continuations
  2022-02-17  6:07     ` Stefan Israelsson Tampe
@ 2022-02-17 16:37       ` Vijay Marupudi
  0 siblings, 0 replies; 11+ messages in thread
From: Vijay Marupudi @ 2022-02-17 16:37 UTC (permalink / raw)
  To: Stefan Israelsson Tampe, Mikael Djurfeldt; +Cc: guile-devel


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

That's quite amazing! An order of magnitude difference!

~ Vijay



^ permalink raw reply	[flat|nested] 11+ messages in thread

end of thread, other threads:[~2022-02-17 16:37 UTC | newest]

Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
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
2022-02-17 16:37       ` Vijay Marupudi

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