4

所以我认为我了解延续在 Scheme 中的基本工作原理,但我无法弄清楚如何使用它而不是递归。

我们得到了 make-matcher 的工作代码(只是基本的模式匹配),它已经完成了我们想要的一切。您给它一个模式,它会为您创建一个匹配器,您可以使用它在片段中搜索该模式。匹配器接受一个接受器,将它的结果提供给它,如果结果不被接受,它会递归地下降到片段的下一部分并继续前进。

现在,我们要做的基本上就是修改它以使用延续而不是接受器。它返回后缀(从不匹配的模式中留下的东西)和一个延续,所以像

(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 为例。目前,如果它找到匹配项,它会将结果提供给接受者,如果接受者不喜欢这个结果,它会继续寻找下一个可能的答案。如果我想使用延续,我将不得不在它找到结果后强制它退出并使用 call/cc 来存储程序的当前状态。我只是……不完全确定我应该把逃生和呼叫/抄送放在哪里。我想我现在需要添加一个基本案例,因为我没有接受者告诉我我的答案是对还是错,但是......

我想如果有人只是给我一些关于要进行的主要更改的指示,我可能会弄清楚。我当时了解 WHAT 的各个部分,但无法完全了解如何实现它。

4

1 回答 1

0

让我们考虑一下方案方式。

您只需要一个流,它会一一返回所有匹配项。并且您已经获得了一个返回匹配顺序的函数,如下所示:

(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)
于 2013-02-04T11:20:32.833 回答