Continuation sets and order-independency

Continuation sets and order-independency

[David Kastrup]

Hi,

I was just wondering about the ability for using multiple continuations
in contexts that don't guarantee an order of execution.  Functions like
map, list and other structure builders.

If one uses those for building a structure, and some paths of execution
hit a call-with-current-continuation, is it feasible to have Guile
refrain from actually taking the continuation before all other paths of
execution have finished or reached a call-with-current-continuation as
well?

Meaning that if one takes the whole set of continuations as a template
for creating a data structure from values that are not known at the time
of building the template, that one can fill in the whole set with actual
values/actions/calculations, and have only the actions depending on
those variables be redone.

Sort of like constant expression folding (some sort of quasi-quoting
superset) on steroids.

-- 
David Kastrup

Re: Continuation sets and order-independency

[Noah Lavine]

Let me see if I understand what you mean. I think you're talking about
an expression like this:

  (cons (call/cc store-this-continuation) (call/cc store-this-continuation))

and you want a way to distinguish the first and the second call/cc, by
guaranteeing the order they are hit. This will let you choose which
value to put in the car and which to put in the cdr.

Is that right?

Noah

On Wed, Jan 4, 2012 at 8:16 AM, David Kastrup <dak@gnu.org> wrote:
>
> Hi,
>
> I was just wondering about the ability for using multiple continuations
> in contexts that don't guarantee an order of execution.  Functions like
> map, list and other structure builders.
>
> If one uses those for building a structure, and some paths of execution
> hit a call-with-current-continuation, is it feasible to have Guile
> refrain from actually taking the continuation before all other paths of
> execution have finished or reached a call-with-current-continuation as
> well?
>
> Meaning that if one takes the whole set of continuations as a template
> for creating a data structure from values that are not known at the time
> of building the template, that one can fill in the whole set with actual
> values/actions/calculations, and have only the actions depending on
> those variables be redone.
>
> Sort of like constant expression folding (some sort of quasi-quoting
> superset) on steroids.
>
> --
> David Kastrup
>
>

Re: Continuation sets and order-independency

[David Kastrup]

Noah Lavine <noah.b.lavine@gmail.com> writes:

>> On Wed, Jan 4, 2012 at 8:16 AM, David Kastrup <dak@gnu.org> wrote:
>>>
>>> Hi,
>>>
>>> I was just wondering about the ability for using multiple continuations
>>> in contexts that don't guarantee an order of execution.  Functions like
>>> map, list and other structure builders.
>>>
>>> If one uses those for building a structure, and some paths of execution
>>> hit a call-with-current-continuation, is it feasible to have Guile
>>> refrain from actually taking the continuation before all other paths of
>>> execution have finished or reached a call-with-current-continuation as
>>> well?
>>>
>>> Meaning that if one takes the whole set of continuations as a template
>>> for creating a data structure from values that are not known at the time
>>> of building the template, that one can fill in the whole set with actual
>>> values/actions/calculations, and have only the actions depending on
>>> those variables be redone.
>>>
>>> Sort of like constant expression folding (some sort of quasi-quoting
>>> superset) on steroids.
>
> Let me see if I understand what you mean. I think you're talking about
> an expression like this:
>
>   (cons (call/cc store-this-continuation) (call/cc store-this-continuation))
>
> and you want a way to distinguish the first and the second call/cc, by
> guaranteeing the order they are hit. This will let you choose which
> value to put in the car and which to put in the cdr.
>
> Is that right?

No.  I exactly _don't_ want to have an order dependency.  The end
application is more or less supposed to be similar to lambda with
everything not depending on a function parameter being preexecuted.
When doing sequential operations, the preexecution will stop at the
point in sequence where call/cc is hit the first time.  But when doing
parallelizable operations without a guaranteed order of operations, one
could let the preexecution continue on independent operations until
_every_ parallelizable operation has reached the point of call/cc.

-- 
David Kastrup

Re: Continuation sets and order-independency

[Noah Lavine]

Okay, let me see if this is right now.

In the expression

  (list (call-with-current-continuation func) (+ 4 14)),

you want the addition to be done before the
call-with-current-continuation, as opposed to being part of the
continuation.

Right?

Noah

On Wed, Jan 4, 2012 at 9:00 AM, David Kastrup <dak@gnu.org> wrote:
> Noah Lavine <noah.b.lavine@gmail.com> writes:
>
>>> On Wed, Jan 4, 2012 at 8:16 AM, David Kastrup <dak@gnu.org> wrote:
>>>>
>>>> Hi,
>>>>
>>>> I was just wondering about the ability for using multiple continuations
>>>> in contexts that don't guarantee an order of execution.  Functions like
>>>> map, list and other structure builders.
>>>>
>>>> If one uses those for building a structure, and some paths of execution
>>>> hit a call-with-current-continuation, is it feasible to have Guile
>>>> refrain from actually taking the continuation before all other paths of
>>>> execution have finished or reached a call-with-current-continuation as
>>>> well?
>>>>
>>>> Meaning that if one takes the whole set of continuations as a template
>>>> for creating a data structure from values that are not known at the time
>>>> of building the template, that one can fill in the whole set with actual
>>>> values/actions/calculations, and have only the actions depending on
>>>> those variables be redone.
>>>>
>>>> Sort of like constant expression folding (some sort of quasi-quoting
>>>> superset) on steroids.
>>
>> Let me see if I understand what you mean. I think you're talking about
>> an expression like this:
>>
>>   (cons (call/cc store-this-continuation) (call/cc store-this-continuation))
>>
>> and you want a way to distinguish the first and the second call/cc, by
>> guaranteeing the order they are hit. This will let you choose which
>> value to put in the car and which to put in the cdr.
>>
>> Is that right?
>
> No.  I exactly _don't_ want to have an order dependency.  The end
> application is more or less supposed to be similar to lambda with
> everything not depending on a function parameter being preexecuted.
> When doing sequential operations, the preexecution will stop at the
> point in sequence where call/cc is hit the first time.  But when doing
> parallelizable operations without a guaranteed order of operations, one
> could let the preexecution continue on independent operations until
> _every_ parallelizable operation has reached the point of call/cc.
>
> --
> David Kastrup
>
>

Re: Continuation sets and order-independency

[David Kastrup]

Noah Lavine <noah.b.lavine@gmail.com> writes:

> Okay, let me see if this is right now.
>
> In the expression
>
>   (list (call-with-current-continuation func) (+ 4 14)),
>
> you want the addition to be done before the
> call-with-current-continuation, as opposed to being part of the
> continuation.
>
> Right?

This is part of it, yes.  If you think as "(list expr1 expr2 ...)" as

(call-with-values (parallel expr1 expr2 ...) list)

and each of the expr might suspend its thread (and record the thread
somewhere for waking up), then you have parallel execution that
continues until all paths have reached completion or suspension.

Now instead of parallel execution, it would be ok to have the
serialization of call/cc but still continue in all paths to completion
or suspension.

Of course, a single call/cc just stores away a single continuation, and
whatever continuation while evaluating "list" was reached, one can't
prod Scheme into taking up another branch without letting that
continuation continue, so obviously something is missing in this
picture.

-- 
David Kastrup

Re: Continuation sets and order-independency

[Mark H Weaver]

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

Hi David,

David Kastrup <dak@gnu.org> writes:

> Noah Lavine <noah.b.lavine@gmail.com> writes:
>
>> Okay, let me see if this is right now.
>>
>> In the expression
>>
>>   (list (call-with-current-continuation func) (+ 4 14)),
>>
>> you want the addition to be done before the
>> call-with-current-continuation, as opposed to being part of the
>> continuation.
>>
>> Right?
>
> This is part of it, yes.  If you think as "(list expr1 expr2 ...)" as
>
> (call-with-values (parallel expr1 expr2 ...) list)
>
> and each of the expr might suspend its thread (and record the thread
> somewhere for waking up), then you have parallel execution that
> continues until all paths have reached completion or suspension.
>
> Now instead of parallel execution, it would be ok to have the
> serialization of call/cc but still continue in all paths to completion
> or suspension.
>
> Of course, a single call/cc just stores away a single continuation, and
> whatever continuation while evaluating "list" was reached, one can't
> prod Scheme into taking up another branch without letting that
> continuation continue, so obviously something is missing in this
> picture.

I'm still not entirely clear on what you want, but perhaps you're
looking for delimited continuations, a.k.a composable continuations,
partial continuations, or _prompts_.  They are not yet part of standard
Scheme, but some advanced implementations have them, including Guile
2.0.  (They are not available in Guile 1.8).

  http://www.gnu.org/software/guile/manual/html_node/Prompts.html

I've attached a small example module that might do what you want.
Here's an example session, starting with the highest-level syntax:

  scheme@(guile-user)> ,use (mhw suspendable)
  scheme@(guile-user)> (%% list 1 2 3 (begin (suspend) 4) 5)
  $1 = ((completed 1) (completed 2) (completed 3) (suspended #<partial-continuation 10541cd0>) (completed 5))
  scheme@(guile-user)> (map final-values $1)
  $2 = (1 2 3 4 5)
  scheme@(guile-user)> 

This is based on some lower-level primitives: (suspendable <expr> ...)
evaluates the expressions and returns a <suspension>.

A <suspension> is a simple list structure:

  (completed . <return-values>), or
  (suspended <partial-continuation> . <args>)

The latter is returned if (suspend <arg> ...) is called within the
dynamic extent of the `suspendable' form.

A suspension can be resumed as follows:

  (resume <suspension>)

`resume' returns another <suspension>, which is not necessarily
completed, because `suspend' may be called multiple times.  To
repeatedly resume a suspension until it completes, and return its values
nicely, use:

  (final-values <suspension>)

For example:

  scheme@(guile-user)> (suspendable (begin (for-each suspend '(1 2 3)) 'done))
  $3 = (suspended #<partial-continuation 1055eec0> 1)
  scheme@(guile-user)> (resume $3)
  $4 = (suspended #<partial-continuation 10564db0> 2)
  scheme@(guile-user)> (resume $4)
  $5 = (suspended #<partial-continuation 1058bc60> 3)
  scheme@(guile-user)> (resume $5)
  $6 = (completed done)
  scheme@(guile-user)> (suspendable (begin (for-each suspend '(1 2 3)) 'done))
  $7 = (suspended #<partial-continuation 1059a230> 1)
  scheme@(guile-user)> (final-values $7)
  $8 = done

Basically what the high-level `%%' syntax does is to call a procedure,
but automatically evaluate all of its operands as parallel suspendable
computations.  The suspensions are passed to the procedure, which may
resume them (or ask for their final-values) as desired.

(Actually, the operator is evaluated in the same way as the operands, in
the tradition of Scheme.)

For example, (%% list 1 2 3 (begin (suspend) 4) 5) expands to:

  (call-with-values
      (lambda () (parallel (suspendable list)
                           (suspendable 1)
                           (suspendable 2)
                           (suspendable 3)
                           (suspendable (begin (suspend) 4))
                           (suspendable 5)))
    (lambda (proc . args)
      (apply (final-values proc) args)))

Is this what you're looking for, or something close to it?

   Regards,
     Mark



[-- Attachment #2: suspendable.scm --]
[-- Type: text/plain, Size: 1444 bytes --]

(define-module (mhw suspendable)
  #:use-module (ice-9 threads)
  #:export (start-suspendable-thunk
            completed? suspended?
            suspend resume final-values)
  #:export-syntax (suspendable %%))

(define suspend-tag (make-prompt-tag "suspend"))

(define (start-suspendable-thunk thunk)
  (resume-suspendable-thunk
   (lambda ()
     (call-with-values thunk
       (lambda results
         `(completed ,@results))))))

(define (resume-suspendable-thunk thunk)
  (call-with-prompt
   suspend-tag
   thunk
   (lambda (resume . args)
     `(suspended ,resume ,@args))))

(define-syntax-rule (suspendable e0 e ...)
  (start-suspendable-thunk (lambda () e0 e ...)))

(define (completed? s) (and (pair? s) (eq? (car s) 'completed)))
(define (suspended? s) (and (pair? s) (eq? (car s) 'suspended)))

(define (suspend . args)
  (apply abort-to-prompt suspend-tag args))

(define (resume s)
  (cond ((suspended? s) (resume-suspendable-thunk (cadr s)))
        ((completed? s) s)
        (else (error "resume: invalid argument"))))

(define (final-values s)
  (cond ((suspended? s) (final-values (resume s)))
        ((completed? s) (apply values (cdr s)))
        (else (error "finalize: invalid argument"))))

(define-syntax-rule (%% op operand ...)
  (call-with-values
      (lambda () (parallel (suspendable op)
                           (suspendable operand) ...))
    (lambda (proc . args)
      (apply (final-values proc) args))))

Re: Continuation sets and order-independency

[David Kastrup]

Mark H Weaver <mhw@netris.org> writes:

> I'm still not entirely clear on what you want,

Well, I said there were elements missing in the picture, so it is not
like I am entirely clear on it myself.

> but perhaps you're looking for delimited continuations, a.k.a
> composable continuations, partial continuations, or _prompts_.  They
> are not yet part of standard Scheme, but some advanced implementations
> have them, including Guile 2.0.  (They are not available in Guile
> 1.8).
>
>   http://www.gnu.org/software/guile/manual/html_node/Prompts.html
>
> I've attached a small example module that might do what you want.
> Here's an example session, starting with the highest-level syntax:
>
>   scheme@(guile-user)> ,use (mhw suspendable)
>   scheme@(guile-user)> (%% list 1 2 3 (begin (suspend) 4) 5)
>   $1 = ((completed 1) (completed 2) (completed 3) (suspended #<partial-continuation 10541cd0>) (completed 5))
>   scheme@(guile-user)> (map final-values $1)
>   $2 = (1 2 3 4 5)
>   scheme@(guile-user)> 
>
> This is based on some lower-level primitives: (suspendable <expr> ...)
> evaluates the expressions and returns a <suspension>.

I assume that the above list could contain more than a single call of
(suspend).

> Basically what the high-level `%%' syntax does is to call a procedure,
> but automatically evaluate all of its operands as parallel suspendable
> computations.  The suspensions are passed to the procedure, which may
> resume them (or ask for their final-values) as desired.
>
> (Actually, the operator is evaluated in the same way as the operands, in
> the tradition of Scheme.)
>
> For example, (%% list 1 2 3 (begin (suspend) 4) 5) expands to:
>
>   (call-with-values
>       (lambda () (parallel (suspendable list)
>                            (suspendable 1)
>                            (suspendable 2)
>                            (suspendable 3)
>                            (suspendable (begin (suspend) 4))
>                            (suspendable 5)))
>     (lambda (proc . args)
>       (apply (final-values proc) args)))
>
> Is this what you're looking for, or something close to it?

Not really.  The above uses "parallel", and if I remember correctly,
this implies multi-threaded execution and true asynchronicity
(preemptive scheduling).  I was rather thinking about avoiding the
overhead and work things off serially but without stopping if one part
runs into suspension, but rather commencing with another part of the
expression until every branch has run into suspension.  Effectively
multithreading without preemption and the associated costs.

-- 
David Kastrup

Re: Continuation sets and order-independency

[Mark H Weaver]

David Kastrup <dak@gnu.org> writes:
> I assume that the above list could contain more than a single call of
> (suspend).

Yes, of course.

>> For example, (%% list 1 2 3 (begin (suspend) 4) 5) expands to:
>>
>>   (call-with-values
>>       (lambda () (parallel (suspendable list)
>>                            (suspendable 1)
>>                            (suspendable 2)
>>                            (suspendable 3)
>>                            (suspendable (begin (suspend) 4))
>>                            (suspendable 5)))
>>     (lambda (proc . args)
>>       (apply (final-values proc) args)))
>>
>> Is this what you're looking for, or something close to it?
>
> Not really.  The above uses "parallel", and if I remember correctly,
> this implies multi-threaded execution and true asynchronicity
> (preemptive scheduling).  I was rather thinking about avoiding the
> overhead and work things off serially but without stopping if one part
> runs into suspension, but rather commencing with another part of the
> expression until every branch has run into suspension.  Effectively
> multithreading without preemption and the associated costs.

That's easy enough.  Simply changing `parallel' to `values' in the
definition of %% would be enough to get rid of the parallelism, but
here's a simpler definition for a non-parallel %%:

  (define-syntax-rule (%% op operand ...)
    (op (suspendable operand) ...))

With this one change, I think this now does what you are describing.

      Mark