Re: Continuation sets and order-independency

[Mark H Weaver]

Hi David,

David Kastrup <address@hidden> writes:

> Noah Lavine <address@hidden> 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


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