early exiting a recursive procedure

Question

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 ?

Answer 1

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.