所以我想我明白延續基本上是如何在Scheme中工作的,但是我很難找出如何使用它而不是遞歸。計劃 - 使用延續
我們給出了make-matcher的工作代碼(只是基本模式匹配),它已經完成了我們想要的任何事情。你給它一個模式,它爲你創建一個匹配器,你可以用它來搜索這個模式的片段。匹配器需要一個接受者,它將結果提供給它,如果結果不被接受,它會遞歸地下降到片段的下一部分並繼續前進。
現在,我們要做的事情基本上就是將其修改爲使用continuations而不是acceptors。它返回後綴(遺留下來,這不是匹配的模式的東西)和延續,所以像
(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)))))))
因此,讓我們使用或匹配器的一個例子。目前,如果找到匹配項,它會將結果提供給接受者,如果接受者不喜歡結果,它會繼續,尋找下一個可能的答案。如果我想使用continuation,那麼在找到結果後,我必須強制它退出並使用call/cc來存儲程序的當前狀態。我只是...不完全確定我應該在哪裏放置逃生和呼叫/ cc。我想我現在需要添加一個基本案例,因爲我沒有一個接受者告訴我,如果我的回答是真的或假的,但...
我想如果有人只是給我一些關於主要變化的指針,我可以弄明白。我在那個時候理解WHAT的各個部分,但不能完全看到如何實現它的大局。