抢先 - 经验丰富的阴谋家

Question

请查看第 19 章中的 two-in-a-row*? 函数。

我的问题是关于 get-first 辅助函数中的 (leave '())。请注意，(waddle l) 将是 return '() 或一个原子，这表明列表已用完或从列表中检索了一个原子。

没有(leave '())它仍然会return这两种值，只是不使用continuation leave。但是书上说没有(leave '())是不好的，我就是不明白为什么。

(define two-in-a-row*
  (letrec ([leave id] ; the identity function 
           [fill id]
           [waddle (lambda (l)
                     (cond [(null? l) '()]
                           [(atom? (car l))
                            (begin 
                              (letcc rest
                                     (set! fill rest)
                                     (leave (car l)))
                              (waddle (cdr l)))]
                           [else
                            (begin
                              (waddle (car l))
                              (waddle (cdr l)))]))]
           [get-first (lambda (l)
                        (letcc here
                               (set! leave here)
                               (waddle l)
                               (leave '()) ; why is this part needed???
                               ))]
           [get-next (lambda (l)
                       (letcc here
                              (set! leave here)
                              (fill 'go)))]
           [T? (lambda (a)
                 (let ([n (get-next 'dummy)])
                   (if (atom? n)
                       (or (eq? a n)
                           (T? n))
                       #f)))])
    (lambda (l)
      (let ([fst (get-first l)])
        (if (atom? fst)
            (T? fst)
            #f)))))

非常感谢。

另一个有趣的 tread 关于这个问题。

Answer 1

命名看起来不对劲。我用 "yield" 代替 "leave"，用 "next" 代替 "fill"。我还必须将 atom? 和 re-write letcc 定义为 call/cc，以使其在 Racket 中工作。这是完整的代码：

(define two-in-a-row*
  (letrec ([yield '()] 
           [next '()]
           [atom? (lambda (x) (and (not (null? x))
                                   (not (pair? x))))]
           [waddle (lambda (l)
                     (cond [(null? l) '()]
                           [(atom? (car l))
                            (begin 
                              (call/cc (lambda ( here2 )
                                          (set! next here2)
                                          (yield (car l))))
                              (waddle (cdr l)))]
                           [else
                            (begin (waddle (car l))
                                   (waddle (cdr l)))]))]
           [get-first (lambda (l)
                        (call/cc (lambda ( here1 )
                                    (set! yield here1)
                                    (waddle l)
                                    (yield '()) ; why is this part needed???
                                    )))]
           [get-next (lambda ()
                       (call/cc (lambda ( here3 )
                                   (set! yield here3)
                                   (next 'dummy))))]
           [T? (lambda (a)
                 (let ([n (get-next)])  (display (list "next:" n))
                   (and (atom? n)
                        (or (eq? a n)
                            (T? n)))))])
    (lambda (l)
      (let ([a (get-first l)])
        (and (begin                     (display (list "first:" a))
                    (atom? a))
             (T? a))))))

我们可以看到这里的区别：

(two-in-a-row* '(((7) (b)) c (d)))
  ; w/out yield () : (first: 7)(next: b)(next: c)(next: d)(first: ())#f
  ; w/    yield () : (first: 7)(next: b)(next: c)(next: d)(next: ())#f
  ; w/    yield #f : (first: 7)(next: b)(next: c)(next: d)(next: #f)(next: #f)#t

(two-in-a-row* '(((7) (b)) c ()))
  ; w/out yield () : (first: 7)(next: b)(next: c)(first: ())#f
  ; w/    yield () : (first: 7)(next: b)(next: c)(next: ())#f
  ; w/    yield #f : (first: 7)(next: b)(next: c)(next: #f)(next: #f)#t

(two-in-a-row* '(((7) (b)) b ()))
  ; w/out yield () : (first: 7)(next: b)(next: b)#t
  ; w/    yield () : (first: 7)(next: b)(next: b)#t
  ; w/    yield #f : (first: 7)(next: b)(next: b)#t

Answer 2

非常感谢 Will Ness 的示例。我检查了一些更简单的。所以 "what is it so bad about that?" -- 在 get-first.

中没有 (leave '())

简答：
请注意，从我的代码
i) 每次调用 get-first 或 get-next 时，总是会重新创建 leave。它将 return 变为 get-first 或 get-next。
ii) fill 将根据之前的 fill 成为一个链，它总是 return 到 get-first。

示例
输入：'(1)

所以我们首先在 '(1) 上评估 get-first。
i) 设置 leave
ii) 开始 (waddle '(1)
iii) 由于 1 是一个原子，因此将 fill 设置为当前延续。注意如果我们使用fill，那么它会去(waddle (cdr l))，然后它会return到get-first。 iv) return 到 get-first 通过使用 leave 和 return 值 1.

然后我们进入 eval (T? 1)，这将依次进入运行 get-next.
i) 设置 leave
ii) 运行 fill
iii) 开始 (waddle '())
iv) return () 从 waddle，然后 return 到 get-first。

备注
1）如果我们没有(leave '()，那么get-first就会return'()，然后two-in-a-row*return#f。所以我们可以得到相同的答案，但是行为不是我们想要的。
2) 如果我们有它，请注意 leave 现在是由 get-next 创建的 leave，因此它将把 '() 转移到 get-next。
3) 当我们创建 fill 时，列表中的输入超过 1 个，它将基于之前的 fill 创建，因此结果是一个依赖于之前的 fill.

的链

Answer 3

这很棘手。书中的线索是 wow! 回复。学生说 wow! 是因为他们已经意识到 () 是 return 来自不同函数的。

无论是在书中还是通过使用 drracket，这都不清楚，我花了一段时间才理解，但理解这一点的关键是：

get-first 调用了 waddle 来使 fill 继续。
waddle（不使用延续时）returns 到 get-first.

但是

get-next 呼叫 fill.
fill 继续 waddle
waddle 使用 leave 到 return 到 get-next 而不是 get-first.

但是在(waddle '())的情况下，waddle不使用leave到return到get-next。它 return 正常。这意味着 return 到 get-first。

这意味着 get-next 实际上不会获得 () return 值。它不会获得此值，因为 waddle 正在 returning 到 get-first。

现在到了有趣的部分。

我们知道，对于值()，waddlereturns到get-first当我们想要它return到get-next.
我们知道get-next设置leave到return到get-next。
因此，get-first可以用leave到return到get-next。

这很棘手的真正原因是因为看看在 get-first 中不使用 (leave '()) 的情况。

fill 用 () 调用 waddle。
waddle return秒到 get-first.
get-first 然后 returns ().

这相当于：

  (let ([fst '()])     ;; was (let ([fst (get-first l)])
    (if (atom? fst)
        (T? fst)
        #f)))))

哪个 return 与 return 进入 get-next 的版本的值相同：

       [T? (lambda (a)
             (let ([n '()])      ;; was (let ([n (get-next 'dummy)])
               (if (atom? n)
                   (or (eq? a n)
                       (T? n))
                   #f)))])

两者都是#f，只是不小心！没有人说这本书不会让你思考 ;)

抢先 - 经验丰富的阴谋家

get-first - the-seasoned-schemer

scheme

continuations

callcc

seasoned-schemer