scheme - 提前退出递归过程

Question

观看this视频 (11:56)

它显示了一个将列表中包含的数字相乘的递归过程

这个想法是，如果列表包含零，则可以丢弃整个递归调用堆栈并返回 0

这样可以节省一些乘法

它通过提前退出带有分隔延续的过程来实现这一点

我想在 Guile Scheme 中重现这一点，并且我编写了这段代码

(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))
    )

它正确地相乘，但是如果我向它传递一个包含零的列表并跟踪这样的调用，我得到

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)> 

在我看来，提前退出并没有生效，并且整个乘法堆栈都被应用

我做错了什么？

Answer 1

根据评论，目前尚不清楚您是否还有疑问。 (shift k 0) 确实清除了当前的延续并丢弃它。

我在这台机器上没有 Guile，但我使用 cond 编写了一个简化的 times 示例，其中包含 Racket -

(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 在this Q&A 中提供define/traced 。 reset 包装表达式，但您可以将其移动到内部辅助函数，就像您在代码中所做的那样 -

(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

我们可以看到遇到0时立即退出 -

(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

请注意，在第一个示例中，当 times 返回值时，define/traced 显示 -> ...。在第二个示例中，整个延续被丢弃，并且 times 永远不会完全计算。