Scheme-使用continuations

4

我认为我基本上理解了Scheme中continuations的工作原理,但是我在尝试用它代替递归时遇到了困难。

我们已经有了make-matcher的可用代码(仅基本模式匹配),它已经做了我们想要的一切。您给它一个模式,它为您创建一个匹配器,您可以使用该匹配器搜索该模式的片段。匹配器接受一个接收器,并且如果结果不被接受,它会递归地进入片段的下一个部分并继续进行。

现在,我们需要做的基本上是修改它以使用continuations而不是acceptors。它返回剩余部分(未匹配的模式)和一个continuation,因此类似于:

(let ((suffix (car match-result))
          (backtrack (cdr match-result)))

如果您能提供后缀和回溯函数,我们可以调用该函数以继续进行。

因此,为了参考,以下是原始代码:

(define match-junk
  (lambda (k frag accept)
    (or (accept frag)
        (and (< 0 k)
             (pair? frag)
             (match-junk (- k 1) (cdr frag) accept)))))

(define match-*
  (lambda (matcher frag accept)
    (or (accept frag)
        (matcher frag
                (lambda (frag1)
                  (and (not (eq? frag frag1))
                       (match-* matcher frag1 accept)))))))

(define make-matcher
  (lambda (pat)
    (cond    
     ((symbol? pat)
      (lambda (frag accept)
        (and (pair? frag)
             (eq? pat (car frag))
             (accept (cdr frag)))))

     ((eq? 'or (car pat))
      (let make-or-matcher ((pats (cdr pat)))
        (if (null? pats)
            (lambda (frag accept) #f)
            (let ((head-matcher (make-matcher (car pats)))
                  (tail-matcher (make-or-matcher (cdr pats))))
              (lambda (frag accept)
                (or (head-matcher frag accept)
                    (tail-matcher frag accept)))))))

     ((eq? 'list (car pat))
      (let make-list-matcher ((pats (cdr pat)))
        (if (null? pats)
            (lambda (frag accept) (accept frag))
            (let ((head-matcher (make-matcher (car pats)))
                  (tail-matcher (make-list-matcher (cdr pats))))
              (lambda (frag accept)
               (head-matcher frag
                             (lambda (frag1)
                               (tail-matcher frag1 accept))))))))

     ((eq? 'junk (car pat))
      (let ((k (cadr pat)))
    (lambda (frag accept)
      (match-junk k frag accept))))

     ((eq? '* (car pat))
      (let ((matcher (make-matcher (cadr pat))))
    (lambda (frag accept)
      (match-* matcher frag accept)))))))

那么让我们以or-matcher为例。目前,如果它找到匹配项,就会将结果提供给接受者,如果接受者不喜欢结果,它会继续寻找下一个可能的答案。如果我想使用 continuation,我需要在找到结果后强制它退出并使用 call/cc 存储程序的当前状态。但我不确定应该把 escape 和 call/cc 放在哪里。我认为现在需要添加一个基本情况,因为没有 acceptor 告诉我答案是真还是假,但是......。
我认为如果有人给我一些关于主要更改的指针,我可能能够弄清楚。我现在明白了每个部分的具体含义,但无法准确看到如何实施大局。
1个回答

0

让我们考虑一下Scheme的方式。

你所需要的就是一个流,它会逐个返回所有匹配项。而你已经有了一个函数,可以按顺序返回匹配项,就像这样:

(define matcher
  (lambda (yield)
    ; the following is your matcher implementation
    (loop ... (yield one-result) ...)))

yield 是一个函数,它捕获了当前的状态并将控制权返回给调用者。我们可以通过使用 call/cc 来实现它,并创建一个流。

(define make-match-stream
  (stream-unfold
    car                     ; map
    identify                ; pred
    (lambda (x) ((cdr x)))  ; gen
    (begin                  ; base
      (matcher (lambda (one-result)
        (call/cc (lambda (continuation)
          (cons one-result continuation)))))
      #f)))

stream-unfold 来自于 srfi-41,它返回一个类似于 unfold 的流。

使用 stream-filter 过滤掉你不需要的结果:

(stream-filter accept result)

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接