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を使用してプログラムの現在の状態を保存する必要があります。エスケープとcall/ccをどこに置くべきか正確にはわかりません。私の答えが正しいか間違っているかを教えてくれるアクセプターがいないので、今すぐベースケースを追加する必要があると思いますが...

誰かが私に行うべき主な変更についてのいくつかの指針を教えてくれれば、私はおそらくそれを理解できると思います。私はその時点で、WHATの個々の部分を理解していますが、それを実装する方法の全体像を正確に理解することはできません。

4

1 に答える 1

0

スキーム的に考えてみましょう。

必要なのは、すべての一致を 1 つずつ返すストリームだけです。そして、次のように、一致を順次返す関数を既に取得しています。

(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 に答える