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 ?
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.