我认为我基本上理解了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 告诉我答案是真还是假,但是......。
我认为如果有人给我一些关于主要更改的指针,我可能能够弄清楚。我现在明白了每个部分的具体含义,但无法准确看到如何实施大局。