无可变单元类Scheme语言中，不用set!消费call/cc迭代器的可行性

我正在使用一种完全不支持任何可变单元（如Scheme的set!或OCaml的ref）的类Scheme语言。我希望实现生成器，让生成器的结果作为其正常返回值，生成器与迭代器的类型定义如下（伪代码）：

Generator (receive : Type) (yield : Type) (return : Type) = Fix(fun (nextStep : Type) =>
  (receive, (yield, nextStep) -> ⊥) -> return
)

Iterator (yield : Type) = Generator ⊤ yield ⊤

在Scheme中，我可以实现生成0到9的迭代器（注：原代码中< i 10会生成0到9）：

(define (seqTo10 y)
  (define (go i yl)
    (if (< i 10)
        (go (+ i 1) (call/cc (lambda (cont) (yl (list i cont)))))))
  (go 0 y))

但在不使用set!消费迭代器结果时遇到了问题。我尝试了如下实现：

(define (seqSum seq)
  (call/cc (lambda (return)
             (define (sum t n)
               (apply
                (lambda (i x) (sum (+ t i) x))
                (call/cc (lambda (k)
                           (n k)
                           (return t)))))
             (sum 0 seq))))

此时n代表迭代器下一步的延续，当go正常退出时，会回到call/cc外的首个帧（即t为0的帧），导致(seqSum seqTo10)返回0而非预期的45。

我的问题是：能否保留生成器/迭代器的该行为（即正常终止时指定终端值），同时不用set!来消费并累加其结果？

可以做到。问题出在当前的seqSum实现中：当迭代器正常退出时，n k执行完毕后会回到该call/cc的调用点，直接触发(return t)，但此时的t是初始的0——因为这个call/cc的上下文绑定到第一次调用sum的环境。

要解决这个问题，我们需要让迭代器的正常返回路径能传递当前的累加值，而非直接跳回最外层的return。通过调整延续的使用，让sum函数在迭代器结束时自然返回当前累加值即可。

修改后的实现 #

迭代器（添加终止标记）

(define (seqTo10 y)
  (define (go i yl)
    (if (< i 10)
        (go (+ i 1) (call/cc (lambda (cont) (yl (list i cont)))))
        (yl #f))) ; 迭代结束时传递终止标记
  (go 0 y))

累加函数（适配终止逻辑）

(define (seqSum seq)
  (define (sum t n)
    (call/cc
     (lambda (k)
       (n (lambda (val)
            (if (pair? val)
                (apply (lambda (i next) (sum (+ t i) next)) val)
                (k t)))))))
  (sum 0 seq))

原理说明 #

1. 迭代器终止标记：seqTo10在完成所有元素生成后，会调用yl #f，用非配对值#f作为迭代终止的信号，替代原实现中直接退出的行为。
2. 累加逻辑适配：sum函数中，每次调用迭代器延续n时，传入的匿名函数会判断收到的值：
   • 如果是配对值（元素+下一个延续），则递归调用sum累加当前元素，并传入下一个延续继续迭代；
   • 如果是终止标记#f，则通过延续k返回当前的累加值t——这个延续对应call/cc的调用点，会让sum函数正常返回该值，最终传递到seqSum的顶层。

这样既不需要使用任何可变单元，又保留了生成器正常终止的行为，(seqSum seqTo10)会正确返回45。

内容的提问来源于stack exchange，提问作者Aly