1

我刚刚开始研究 Racket/Scheme 延续，并找到了一个有用的资源 - Matt Mights 页面。在非确定性 Amb 示例之前，我理解了一切。谁能解释我在这个例子中延续是如何工作的？目前对我来说看起来像是黑魔法。

; current-continuation : -> continuation
(define (current-continuation) 
  (call-with-current-continuation 
   (lambda (cc)
     (cc cc))))

; fail-stack : list[continuation]
(define fail-stack '())

; fail : -> ...
(define (fail)
  (if (not (pair? fail-stack))
      (error "back-tracking stack exhausted!")
      (begin
        (let ((back-track-point (car fail-stack)))
          (set! fail-stack (cdr fail-stack))
          (back-track-point back-track-point)))))

; amb : list[a] -> a
(define (amb choices)
  (let ((cc (current-continuation)))
    (cond
      ((null? choices) (fail))
      ((pair? choices)
       (let ((choice (car choices)))
         (set! choices (cdr choices))
         (set! fail-stack (cons cc fail-stack))
         choice)))))

; (assert condition) will cause
; condition to be true, and if there
; is no way to make it true, then
; it signals and error in the program.
(define (assert condition)
  (if (not condition)
      (fail)
      #t))

; The following prints (4 3 5)
(let ((a (amb (list 1 2 3 4 5 6 7)))
      (b (amb (list 1 2 3 4 5 6 7)))
      (c (amb (list 1 2 3 4 5 6 7))))

  ; We're looking for dimensions of a legal right
  ; triangle using the Pythagorean theorem:
  (assert (= (* c c) (+ (* a a) (* b b))))

  (display (list a b c))
  (newline)

  ; And, we want the second side to be the shorter one:
  (assert (< b a))

  ; Print out the answer:
  (display (list a b c))
  (newline))
4

1 回答 1

2

哦，男孩……这段代码看起来像是在尝试使用延续来进行正确的错误处理。这是......技术上......可能。但老实说，既然你说你是在 Racket 中执行此操作而不仅仅是在方案中执行此操作，那么直接使用 Racket 的异常处理机制会好得多。

但我会分解程序的各个部分。

首先，一般算法是：

  • 假设a、b和c是它们各自列表中的第一项。

  • 如果在运行代码时遇到一个assert失败的问题，请及时返回并假设这c实际上是列表中的下一件事。

  • 如果你的时间已经足够回到你已经没有任何可能性的地步，请c尝试第二个项目b。重复直到你用尽了 的可能性b，然后对 做同样的事情a。

基本上，它只是一种回溯搜索算法，它使用延续来试图看起来很花哨。

功能

(define (current-continuation) 
  (call-with-current-continuation 
   (lambda (cc)
     (cc cc))))

只是抓住当前的延续。基本上你可以把它想象成一个时间快照，你可以通过调用它作为一个函数来访问它。所以你可以这样做：

(let ([cc (current-continuation)])
  ...)

现在，在该块调用中，cc将计算回退到该点，替换cc为您传递给它的内容。因此，如果您要cc进入它，例如：

(let ([cc (current-continuation)])
  (cc cc))

你的程序会循环。

(define fail-stack '())

; fail : -> ...
(define (fail)
  (if (not (pair? fail-stack))
      (error "back-tracking stack exhausted!")
      (begin
        (let ((back-track-point (car fail-stack)))
          (set! fail-stack (cdr fail-stack))
          (back-track-point back-track-point)))))

; (assert condition) will cause
; condition to be true, and if there
; is no way to make it true, then
; it signals and error in the program.
(define (assert condition)
  (if (not condition)
      (fail)
      #t))

assert这只是在失败时保留一堆继续调用。

; amb : list[a] -> a
(define (amb choices)
  (let ((cc (current-continuation)))
    (cond
      ((null? choices) (fail))
      ((pair? choices)
       (let ((choice (car choices)))
         (set! choices (cdr choices))
         (set! fail-stack (cons cc fail-stack))
         choice)))))

这设置了可以探索的空间。

; The following prints (4 3 5)
(let ((a (amb (list 1 2 3 4 5 6 7)))
      (b (amb (list 1 2 3 4 5 6 7)))
      (c (amb (list 1 2 3 4 5 6 7))))

  ; We're looking for dimensions of a legal right
  ; triangle using the Pythagorean theorem:
  (assert (= (* c c) (+ (* a a) (* b b))))

  (display (list a b c))
  (newline)

  ; And, we want the second side to be the shorter one:
  (assert (< b a))

  ; Print out the answer:
  (display (list a b c))
  (newline))

这会进行实际搜索，并打印出结果。

于 2018-03-20T22:13:29.290 回答