状態機械を書く


Tags: R6RS, 手続き

末尾呼び出しの最適化を利用し、手続きそのものを状態とし、手続き呼び出しを状態遷移として状態機械を記述すると簡潔に記述できることがある。

例えば CSV の各行内のフィールドを分割する手続きを書くとき、クォート外とクォート内というふたつの状態を手続きで表し、その間の遷移を手続き呼び出しで表すと次のようになる(Cf. wikipedia-ja:CSV)。

(import (rnrs))

(define (csv-split-line str)
  (define (normal cs rfcs rfs)
    (if (null? cs)
        (reverse (cons (list->string (reverse rfcs)) rfs))
        (case (car cs)
          ((#\,)
           (normal (cdr cs) '() (cons (list->string (reverse rfcs)) rfs)))
          ((#\")
           (in-quote (cdr cs) rfcs rfs))
          (else
           (normal (cdr cs) (cons (car cs) rfcs) rfs)))))
  (define (in-quote cs rfcs rfs)
    (if (null? cs)                      ; for robustness
        (reverse (cons (list->string (reverse rfcs)) rfs))
        (case (car cs)
          ((#\")
           (if (and (not (null? (cdr cs)))
                    (char=? (cadr cs) #\"))
               (in-quote (cddr cs) (cons #\" rfcs) rfs)
               (normal (cdr cs) rfcs rfs)))
          (else
           (in-quote (cdr cs) (cons (car cs) rfcs) rfs)))))
  (normal (string->list str) '() '()))

(csv-split-line "a,ab,abc") ; => ("a" "ab" "abc")
(csv-split-line "a,ab,a\"\"bc") ; => ("a" "ab" "abc")
(csv-split-line "a,ab,a\"b\"c") ; => ("a" "ab" "abc")
(csv-split-line "a,ab,\"ab\"\"c\"") ; ("a" "ab" "ab\"c")

また、文章やフローチャートで書かれたアルゴリズムをそのまま記述する場合にも便利なことがある。例えば『The Art of Computer Programming (2) 日本語版 Seminumerical algorithms』(ISBN 4756145434)では選択サンプリング法のアルゴリズムを次のように説明している。

アルゴリズム S(選択サンプリング法 (Selection sampling technique))。 0 < n ≦ N とし、 N 個の中からランダムに n 個のレコードを選択する方法。

これを素朴に書き下すと次のようになる。

(import (rnrs) (srfi :27))

(define (algorithm-S n N)
  (define (s1 t m U rs)
    (s2 0 0 U rs))
  (define (s2 t m U rs)
    (s3 t m (random-real) rs))
  (define (s3 t m U rs)
    (if (>= (* (- N t) U) (- n m))
        (s5 t m U rs)
        (s4 t m U rs)))
  (define (s4 t m U rs)
    (let ((t* (+ t 1))
          (m* (+ m 1))
          (rs* (cons t rs)))
      (if (< m* n)
          (s2 t* m* U rs*)
          (reverse rs*))))
  (define (s5 t m U rs)
    (s2 (+ t 1) m U rs))
  (s1 #f #f #f '()))

(algorithm-S 5 20) ; => (5 6 7 11 18) for example

これはあまりスマートなプログラムではないが、アルゴリズムの説明とこのプログラムが正しく対応していることを確認するのは難しくない。効率も悪いわけではない。逆に、「より Scheme らしい」次のプログラムが上のアルゴリズムと等価であることを判断するのはそれほど容易ではないだろう。

(import (rnrs) (srfi :27))

(define (algorithm-S n N)
  (let loop ((t 0) (m 0) (rs '()))
    (cond ((= m n)
           (reverse rs))
          ((< (- n m) (* (- N t) (random-real)))
           (loop (+ t 1) m rs))
          (else
           (loop (+ t 1) (+ m 1) (cons t rs))))))

手続きをひとつの状態やステップと見做すことでプログラムの見通しがよくなることは多い。