限定継続でパーサを書く

限定継続って何？という話については浅井先生の大変わかりやすいチュートリアルを参照。

このチュートリアルに、状態モナドの機能をshift&resetで再現する話が出てくる。

これを使ってパーサ（四則演算の式を読んで、Lispの前置記法に直すやつ）を書いてみた。

言語はSchemeが元になったRacketを使う（勉強中だから）。

tokenize

とりあえずは文字列からトークンのリストを得るところを普通に書く。

文字列のうち数の部分はnumberに、それ以外の記号は文字列にする。例えば、"32 + 2 * 3"を(32 "+" 2 "*" 3)にする。

(define (digit? x)
  (string-contains? "0123456789" x))

(define (tokenize str)
  (define l (map string (string->list str)))
  (define (tokenize-rec rest)
    (match rest
      [(list-rest " " rest) (tokenize-rec rest)]
      [(list-rest (? digit? d) ..1 rest)
       (define numstr (apply string-append d))
       (define num (string->number numstr))
       (cons num (tokenize-rec rest))]
      [(list-rest x rest)
       (cons x (tokenize-rec rest))]
      ['() '()]))
  (tokenize-rec l))

継続の仕込み

• まだ読んでいないトークンのリストを状態として管理する
• パースが失敗した時に計算を中断する

以上の二つの機能があると便利。モナドであれば、MaybeとStateにあたる機能だ。これをshift&resetで次のように書く。

(require racket/control)

(struct result (value state) #:transparent)

(define (get)
  (shift k
         (λ (x)
           ((k x) x))))

(define (set x)
  (shift k
         (λ (_)
           ((k (void)) x))))

(define (fail)
  (shift k
         (λ (_) #f)))

(define (run thunk state)
  ((reset
    (let ([value (thunk)])
      (λ (s) (result value s))))
   state))

まず計算の結果を表現する構造体としてresultを用意する。

get、set、runがなぜこうなるかは前述のチュートリアルを読んでください。

getとsetがわかればfailが何をしているかもわかるはず。計算が失敗したらこいつを呼ぶと、現在の状態(ラムダで取得する引数）も残った計算（継続k）も無視して問答無用で結果が#fになる。

簡単なパーサ

これだけで書ける簡単なパーサをいくつか。

パーサ（呼び出すとトークン列を消費し、結果を返す関数）と、パーサを生成する関数を区別するよう注意。

; トークン化してパースする
(define (parse thunk str)
  (define tokens (tokenize str))
  (run thunk tokens))

; 無条件で冒頭のトークンを取得するパーサ
(define (item)
  (match (get)
    [(list-rest x rest)
     (set rest)
     x]
    [_ (fail)]))

; 条件を満たせば冒頭のトークンを取得するパーサを生成
(define (satisfy pred?)
  (λ ()
    (define x (item))
    (if (pred? x) x (fail))))

; numberを取得するパーサ
(define number (satisfy number?))

; xとequal?なら取得するパーサを生成
(define (equal x) (satisfy (λ (y) (equal? y x))))

; 文字列xをシンボルとして取得するパーサを生成
(define (assymbol x) (λ () (string->symbol ((equal x)))))

選択

複数のパーサを試して、成功したものの結果を取得するようなパーサが欲しい。

(run (alt p0 p1) tokens)と書いた場合、tokensにp0を当てはめてうまくいけばそれでOK、ダメならtokensにp1を当てはめる、といった具合。

指定されたパーサ列を現在の状態に順番に当てはめていき、#fでない（失敗しなかった）結果が出たら、その状態と値を引き継ぐようにすればいい。

ormapを使うと、#fではない結果が出るまで計算を続ける、という処理が簡単に書ける。

; resultの状態と値を引き継ぐ
(define (continue maybe-result)
  (when (false? maybe-result) (fail))
  (set (result-state maybe-result))
  (result-value maybe-result))

(define (alt . thunks)
  (λ ()
    (define state (get))
    (continue (ormap
               (λ (f) (run f state))
               thunks))))

四則演算のパーサを書く

これで四則演算のパーサが書ける。

(define factor
  (alt
   number
   (λ () ((equal "(")) (define ret (addsub)) ((equal ")")) ret)))

(define signed
  (alt
   factor
   (λ () ((equal "-")) (define f (factor)) `(- ,f))))

(define (chain elem-thunk op-thunk)
  (λ ()
    (define first (elem-thunk))
    (let loop ([prev first])
      ((alt
        (λ () (define op (op-thunk)) (define next (elem-thunk))
          (loop `(,op ,prev ,next)))
        (λ () prev))))))

(define muldiv (chain signed (alt (assymbol "*") (assymbol "/"))))

(define addsub (chain muldiv (alt (assymbol "+") (assymbol "-"))))

こんな感じで動きます。

> (parse addsub "3 + -(32 + 5) * 2")
(result '(+ 3 (* (- (+ 32 5)) 2)) '())

マクロで簡略化

即席のパーサを定義するところで(λ () ((equal "(")) (define ret (addsub)) ((equal ")")) ret)))みたいなのが、カッコが連続したりラムダが出たりでやや気持ち悪い。

せっかくSchemeなのでマクロで簡略化しよう。

(λ () ((equal "(")) (define ret (addsub)) ((equal ")")) ret)))を、
(seq (equal "(") [ret <- addsub] (equal ")") ret)と書けるようにする。……まあdo記法だ。

(define-syntax expand-pattern
  (syntax-rules ()
    [(_ (x <- thunk))
     (define x (thunk))]
    [(_ x)
     (x)]))

(define-syntax-rule (seq pattern ... ret)
  (λ () (expand-pattern pattern) ... ret))

(define factor
  (alt
   number
   (seq (equal "(") [ret <- addsub] (equal ")") ret)))

(define signed
  (alt
   factor
   (seq (equal "-") [f <- factor] `(- ,f))))

(define (chain elem-thunk op-thunk)
  (λ ()
    (define first (elem-thunk))
    (let loop ([prev first])
      ((alt
        (seq [op <- op-thunk] [next <- elem-thunk]
             (loop `(,op ,prev ,next)))
        (λ () prev))))))

(define muldiv (chain signed (alt (assymbol "*") (assymbol "/"))))

(define addsub (chain muldiv (alt (assymbol "+") (assymbol "-"))))

感想

モナドに比べた時の限定継続の良さは、do記法のような特別なシンタクスに従わなくても、普通に計算効果を隠蔽したコードを書けることだと思っていた。

実際、マクロを使う前のコードは普通のラムダ、関数適用、defineだけで処理を淡々と繋げることができている。

のだが、結局ラムダとか関数適用とかを書くのがめんどくさくなってdo記法と同じマクロを導入することになったのがなんか悔しい。

もっと柔軟に処理を書かなきゃいけなくなった時は限定継続の方がスッキリする気はするのだが……

shift&resetやマクロの使い方の勉強になってよかった。