From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Joris van der Hoeven Newsgroups: gmane.lisp.guile.devel,gmane.lisp.guile.user Subject: Efficiency of continuations Date: Sun, 9 Feb 2003 12:42:56 +0100 (MET) Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Message-ID: NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Trace: main.gmane.org 1044790903 2089 80.91.224.249 (9 Feb 2003 11:41:43 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Sun, 9 Feb 2003 11:41:43 +0000 (UTC) Cc: guile-devel@gnu.org Return-path: Original-Received: from monty-python.gnu.org ([199.232.76.173]) by main.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 18hpqA-0000XY-00 for ; Sun, 09 Feb 2003 12:41:42 +0100 Original-Received: from localhost ([127.0.0.1] helo=monty-python.gnu.org) by monty-python.gnu.org with esmtp (Exim 4.10.13) id 18hpsC-0006ud-02 for guile-devel@m.gmane.org; Sun, 09 Feb 2003 06:43:48 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.10.13) id 18hpru-0006ph-00 for guile-devel@gnu.org; Sun, 09 Feb 2003 06:43:30 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.10.13) id 18hpri-0006JS-00 for guile-devel@gnu.org; Sun, 09 Feb 2003 06:43:22 -0500 Original-Received: from matups.math.u-psud.fr ([129.175.50.4]) by monty-python.gnu.org with esmtp (Exim 4.10.13) id 18hprV-0005MU-00; Sun, 09 Feb 2003 06:43:05 -0500 Original-Received: from anh.math.u-psud.fr (anh.math.u-psud.fr [129.175.50.156]) h19BgvU26756 ; Sun, 9 Feb 2003 12:42:57 +0100 (MET) Original-Received: from anh (anh [129.175.50.156]) by anh.math.u-psud.fr (Postfix) with SMTP id E213FB2C8; Sun, 9 Feb 2003 12:42:56 +0100 (MET) X-Sender: texmacs@anh Original-To: guile-user@gnu.org X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1b5 Precedence: list List-Id: Developers list for Guile, the GNU extensibility library List-Help: List-Post: List-Subscribe: , List-Archive: List-Unsubscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: main.gmane.org gmane.lisp.guile.devel:1905 gmane.lisp.guile.user:1614 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.devel:1905 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 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)))) _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel