部分継続による Python 風ジェネレータ

Scheme

ここ数日 HTML パーサーの開発に取り組んでいたんですが、その過程で次のような問題にぶつかりました。

HTML を構文解析して木構造を作る際に、トークン (字句) を一つずつ返してくれるジェネレータが欲しい、と思ったんです。

一般に、言語の解析は字句解析と構文解析の2段階から成りますが (参照: Wikipedia:構文解析) 字句を一つ取り出してその都度構文解析に回したい、と考えたわけです。

例えば、

<body>
  <p>text with <a href="foo.htm">anchor</a> in between</p>
</body>

のような HTML 片があった時に、次のようにして一つずつのトークンを得たい、ということなんです:

(body)
(p)
"text with "
(a (@ (href "foo.htm")))
"anchor"
(/ a)
" in between"
(/ p)
(/ body)

ここで重要なのは、"<" と ">" で囲まれた要素を読み込んだ後は "<" ">" を含まない要素を (もしあれば) 読む、という風に、読み込みたい順序が決まっていることです。

したがって、指定の順序で読み込みながらループを回し、トークンのリストを得ることは比較的容易でした:

(define (tokenize in)
  (let loop ((acc '()))
    (cond ((read-tag in)
           => (lambda (tag)
                (loop
                 (append acc
                         (cons tag
                               (as-list (read-content in)))))))
          (else acc))))

(define (as-list x)
  (if x (list x) '()))

問題は、このように一気に字句解析して (長々とした) リスト・データを作ってしまうのではなく、ポートからトークンを読み出すごとに構文解析の側に提供したい、ということなんです。

「次に読み込むべきものは何か」を記憶しながら制御を呼び出し元に戻す方法、ということで考えた結果、部分継続を使う方法を思い付きました:

(define (generate-token in)
  (define next #f)
  (define (loop)
    (cond ((read-tag in)
           => (lambda (tag)
                (shift k
                  (set! next k)
                  tag)
                (let ((body (read-content in)))
                  (when body
                    (shift k2
                      (set! next k2)
                      body))
                  (loop))))
          (else #f)))
  (lambda ()
    (if next
        (next #f)
        (reset (loop)))))

さらに、shift の部分を括り出すとスッキリします:

(define (generate-token in)
  (define next #f)
  (define (yield x)
    (shift k
      (set! next k)
      x))
  (define (loop)
    (cond ((read-tag in)
           => (lambda (tag)
                (yield tag)
                (cond ((read-content in) => yield))
                (loop)))
          (else #f)))  ; StopIteration
  (lambda ()
    (if next
        (next #f)
        (reset (loop)))))

yield を評価した時点で制御がジェネレータの呼び出し元に戻り、値が返されます。再びジェネレータに入った時は、前の yield の続きから処理が再開されます。

利用例:

(call/input-port url
  get-pure-port
  (lambda (in)
    (let ((next (generate-token in)))
      (let loop ((tok (next)))
        (when tok
          (display tok)
          (newline)
          (loop (next)))))))

ついでなのでマクロを書いてみると:

(define-syntax (defgen stx)
  (syntax-case stx ()
    ((defgen (?fun ?args ...) ?body ...)
     (with-syntax ((yield (datum->syntax stx 'yield)))
       #'(define (?fun ?args ...)
           (define next #f)
           (define (yield x)
             (shift k
               (set! next k)
               x))
           (lambda ()
             (if next
                 (next #f)
                 (reset ?body ...))))))))

(defgen (generate-token in)
  (let loop ()
    (and-let* ((tag (read-tag in)))
      (yield tag)
      (cond ((read-content in) => yield))
      (loop))))

と書けます。

datum->syntax により yield というキーワードが定義の中で参照可能になっていますが、構文ではなく通常の関数として呼び出せる点が Python とは違うところでしょう。


普通に call/cc を使ってジェネレータを作ることもできるんですが (参照: Scheme:generatorとdoとwhile)、部分継続の方がフルな継続よりも軽量ですし、呼び出し元に戻るための継続を捉える必要が無い (shift を評価した時点で脱出が起こる) のでプログラミングも楽です。