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

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