schemecontinuationsguiledelimited-continuations

early exiting a recursive procedure


Watching this video (11:56)

It shows a recursive procedure that multiplies the numbers contained in a list

The idea is that if the list contains a zero, the whole stack of recursive calls can be discarded and 0 can be returned

So to save some multiplications

It does so by early exiting the procedure with delimited continuations

I'd like to reproduce this in Guile Scheme and I wrote this code

(define (times numbers)
  (define (times-iter numbers)
    (match numbers
      ((a-number rest ...) 
         (* a-number (times rest)))
      ('() 1)
      ((0 rest ...) (shift k 0) )
      ))
  (reset (times-iter numbers))
    )

it multiplies correctly but if I pass it a list containing a zero and I trace such call, I get

scheme@(guile-user)> ,trace (times2 '(1 3 0 4))
trace: |  (times2 (1 3 0 4))
trace: |  |  (default-prompt-tag@@ice-9/control)
trace: |  |  (_)
trace: |  |  ("prompt")
trace: |  |  (_)
trace: |  |  |  (list? (3 0 4))
trace: |  |  |  #t
trace: |  |  |  (times (3 0 4))
trace: |  |  |  |  (list? (0 4))
trace: |  |  |  |  #t
trace: |  |  |  |  (times (0 4))
trace: |  |  |  |  |  (list? (4))
trace: |  |  |  |  |  #t
trace: |  |  |  |  |  (times (4))
trace: |  |  |  |  |  |  (list? ())
trace: |  |  |  |  |  |  #t
trace: |  |  |  |  |  |  (times ())
trace: |  |  |  |  |  |  1
trace: |  |  |  |  |  4
trace: |  |  |  |  0
trace: |  |  |  0
trace: |  |  0
trace: |  (_ #<procedure values _> (0))
trace: |  (_ 0)
trace: |  0
scheme@(guile-user)> 

It seems to me that the early exit doesn't kick in and the whole stack of multiplications gets applied

What am I doing wrong ?


Solution

  • Based on the comments, it's unclear if you still have a question here. (shift k 0) does indeed clear the current continuation and discards it.

    I don't have Guile on this machine but I wrote a simplified times example below with racket using cond -

    (require racket/control)
    
    (define/traced (times numbers)
      (cond ((null? numbers) 1)
            ((zero? (car numbers)) (shift k 0)) ;; <- shift
            (else (* (car numbers) (times (cdr numbers))))))
    

    @ignisvolens provides define/traced in this Q&A. reset wraps the expression but you could move it to an inner auxiliary function like you did in your code -

    (reset                           ;; <- reset
     (times '(1 2 3 4 5 6 7 8 9)))
    
    (times (1 2 3 4 5 6 7 8 9)) ...
     (times (2 3 4 5 6 7 8 9)) ...
      (times (3 4 5 6 7 8 9)) ...
       (times (4 5 6 7 8 9)) ...
        (times (5 6 7 8 9)) ...
         (times (6 7 8 9)) ...
          (times (7 8 9)) ...
           (times (8 9)) ...
            (times (9)) ...
             (times ()) ...
             -> (1)
            -> (9)
           -> (72)
          -> (504)
         -> (3024)
        -> (15120)
       -> (60480)
      -> (181440)
     -> (362880)
    -> (362880)
    362880
    

    We can see the immediate exit when the 0 is encountered -

    (reset (times '(1 2 0 4 5 6 7 8 9)))
    
    (times (1 2 0 4 5 6 7 8 9)) ...
     (times (2 0 4 5 6 7 8 9)) ...
      (times (0 4 5 6 7 8 9)) ...
    0
    

    Notice in the first example, define/traced shows -> ... when times returns a value. In the second example, the entire continuation is discarded and times never fully evaluates.