Efficiency of continuations

[Joris van der Hoeven]

Hi,

One of the major adavantages of a language like scheme is the possibility
of having a clean call-with-current-continuation (CCC) construct with
a fast implementation (constant time). However, when reading the Guile manual,
I discovered that the guile implementation is not fast because possible
interactions with the glue :^( and that exceptions are not implemented
using continuations for this reason :^(

Could someone give some more detailed explanations about the efficiency
of continuations in relation to the copying of stacks? What exactly is
being copied and when (at the call of CCC or when using the break function)?

The main use I currently make of continuations is split/join constructs
for non-deterministic programs: 'split' non deterministically evaluates
a list of several possibile cases and 'join' collects the results of
a non deterministic evaluation in a list (see below for the implementation).
Now the non-deterministic evaluation actually never calls glued code and
the join instruction limits the depth at which the stack needs to
be remembered. So there should be no reason for a possible slowdown
(like in the case of exceptions).

More generally, it should be possible to implement a fast CCC under
certain precautions, like the assumption that glued code being called
does not recall scheme code or/and the assumption that you never
descend in the stack until a level where you reach a function call
from the glue. Would it be possible to implement a fast low-level CCC,
which would be correct under certain precautions?

Best wishes, Joris


-----------------------------------------------------------
Joris van der Hoeven <address@hidden>
http://www.texmacs.org: GNU TeXmacs scientific text editor
http://www.math.u-psud.fr/~vdhoeven: personal homepage
-----------------------------------------------------------


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; MODULE      : split.scm (part of GNU TeXmacs)
;; DESCRIPTION : the non-deterministic control structures 'split' and 'join'
;; COPYRIGHT   : (C) 2002  Joris van der Hoeven
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; This software falls under the GNU general public license and comes WITHOUT
;; ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for details.
;; If you don't have this file, write to the Free Software Foundation, Inc.,
;; 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;;   The control structure 'split' takes a list of expressions exp1 ... expn
;; as its arguments and evaluates them in a non-deterministic way.
;; If n=0 then the current non-deterministic branch is killed.
;; The 'split' control structure should be used inside the 'join' command,
;; which retrieves the results of all non-deterministic branches and
;; returns the list with all these results. A simple example which
;; demonstrates the usage is (join (+ (split 1 2 3) (split 100 200)))
;;   For the implementation, we use scheme continuations.
;; The variable 'process-list' contains all commands which correspond
;; to the still-to-evaluate non-deterministic branches of the innermost join.
;; The variable 'process-results contains the results of all
;; already-evaluated branches. The variable 'process-break'
;; contains a continuation to be executed in case of failure.
;; The variable 'process-history' contains the information related
;; to the non-innermost joins.
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Global variables
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define process-list '())
(define process-results '())
(define process-break (lambda (x) (error "Invalid break")))
(define process-history '())

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Splitting
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (process-add exit l)
  (if (not (null? l))
      (begin
        (process-add exit (cdr l))
        (set! process-list (cons (list #f exit (car l)) process-list)))))

(define (split-body head . tail)
  (call-with-current-continuation
   (lambda (exit)
     (process-add exit tail)
     (eval head))))

(define (quote-all l)
  (if (null? l) l
      (cons `',(car l) (quote-all (cdr l)))))

(define-macro split
  (lambda l
    (if (null? l)
        (list 'process-break #f)
        (cons 'split-body (quote-all l)))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Passing control to the next branch
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (process-next)
  (let* ((next (car process-list))
         (first? (car next)))
    (set! process-list (cdr process-list))
    (if first?
        (eval (cadr next))
        ((cadr next) (eval (caddr next))))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Joining
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (join-all)
  (if (not (null? process-list))
      (begin
        (call-with-current-continuation
         (lambda (exit)
           (set! process-break exit)
           (let ((next-value (process-next)))
             (set! process-results (cons next-value process-results)))))
        (join-all))))

(define (join-body expr)
  (set! process-history
        (cons process-list
              (cons process-results
                    (cons process-break process-history))))
  (set! process-list (list (list #t expr)))
  (set! process-results '())
  (join-all)
  (let ((result (reverse process-results)))
    (set! process-list (car process-history))
    (set! process-results (cadr process-history))
    (set! process-break (caddr process-history))
    (set! process-history (cdddr process-history))
    result))

(define-macro join
  (lambda expr
    `(join-body '(begin ,@expr))))