🔩

LISPでパターンマッチング

2020/11/10に公開

初心者

なんかZennではLISPの記事が少ないので（泣），初心者アウトプット風記事を呼び水的に投稿．LISP（Scheme）の実行方法や基本構文は既に把握していることを想定しています．

Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp by Peter Norvig (1992)

この書籍のChapter 5にて，元祖chatbotの"ELIZA"がCommon Lispで書かれており，その実装の解説の中で登場したパターンマッチング処理（5.2 Pattern Matching）がいかにも最初の記号処理プログラミング応用例っぽいので（偏見），これをSchemeで書き直しながら解説．

実行例

GNU Guile 3.0.4およびGauche 0.9.6にて確認．処理系固有の表示等は省略．

> (load "./pattern-matching.scm")
> (pat-match '(i need a ?X) '(i need a vacation))
((?X . vacation))
> (sublis (pat-match '(i need a ?X) '(i need a vacation))
          '(what would it mean to you if you got a ?X ?))
(what would it mean to you if you got a vacation ?)
> (pat-match '(i need a ?X) '(i really need a vacation))
#f
> (pat-match '(this is easy) '(this is easy))
((#t . #t))
> (pat-match '(?X is ?X) '((2 + 2) is 4))
#f
> (pat-match '(?X is ?X) '((2 + 2) is (2 + 2)))
((?X 2 + 2))
> (pat-match '(?P need . ?X) '(i need a long vacation))
((?X a long vacation) (?P . i))

構成関数の定義

変数チェック

ここでは，頭に?が付く記号（シンボル）を変数とみなしているので，記号が変数か否かをチェックする関数をまず定義．

(define (variable? x)
  (and (symbol? x)
       (equal? (string-ref (symbol->string x) 0) #\?)))

symbol->stringは記号を文字列に変換する関数，string-refは文字列の中の1文字を位置情報（冒頭0）で取得する関数，#\?は文字?を示す表現です．

定数の定義

failをマッチング失敗の時の戻り値の定数，((#t . #t))をマッチングに成功した変数と値のセット（変数束縛）を格納する連想リストの初期値として定義．

(define fail #f)
(define no-bindings '((#t . #t)))

なお，連想リストは他のプログラミング言語でいうところの辞書型や連想配列に相当し，通常は，ドット対（内部的にはコンスセル構造）によるキーと値のセットをリストにしたものを指します．

変数束縛に関するユーティリティ関数

get-bindingが連想リストから変数束縛のセットを取り出す関数，binding-valが変数束縛のセットから値を取り出す関数，extend-bindingsが変数束縛のセットを連想リストに追加する関数．

(define (get-binding var bindings) (assq var bindings))

(define (binding-val binding) (cdr binding))

(define (extend-bindings var val bindings)
  (cons (cons var val)
        (if (equal? bindings no-bindings) '() bindings)))

変数束縛のチェック

変数が現れた時の処理．束縛済みの値がなければ，新しく変数束縛のセットを連想リストに追加．束縛済みの値があれば現在対応している値と比較し，同じであれば連想リストをそのまま返し，異なれば『マッチング失敗』としてfailを返す．

(define (match-variable var input bindings)
  (let ((binding (get-binding var bindings)))
    (cond ((not binding) (extend-bindings var input bindings))
          ((equal? input (binding-val binding)) bindings)
          (else fail))))

パターンマッチング処理本体

第一引数でパターンを示し，第二引数にマッチング処理を行う対象，第三引数に変数束縛のセットを格納する連想リストを指定．

(define (pat-match pattern input . r)
  (let ((bindings (if (null? r) no-bindings (car r))))
    (cond ((eq? bindings fail) fail)
          ((variable? pattern)
           (match-variable pattern input bindings))
          ((equal? pattern input) bindings)
          ((and (pair? pattern) (pair? input))
           (pat-match (cdr pattern) (cdr input)
                      (pat-match (car pattern) (car input)
                                 bindings)))
          (else fail))))

処理本体としては，第一引数と第二引数が最初の呼び出し時と同じく共にリストの場合(and (pair? pattern) (pair? input))と，第一引数と第二引数が各リストの同じ位置にある要素であることを想定したマッチング処理の，二種類の処理を兼ねています．前者については，第一引数と第二引数のそれぞれ先頭要素を取り出して自分自身を呼び出すことで後者のマッチング処理を行い，その結果の変数束縛を連想リストして受け取ると同時に，各リストの残りのパターンマッチング処理を行うため，更に自分自身を呼び出しています．

プログラムコード一式

※Common Lispのsublisに相当するものが（なぜか）見つからなかったため，実行例では適当に自作したものを使用しています．

pattern-matching.scm

;;;;
;;;; Pattern Matching example
;;;; ported from Section 5.2 at https://github.com/norvig/paip-lisp
;;;;

(define (variable? x)
  (and (symbol? x)
       (equal? (string-ref (symbol->string x) 0) #\?)))

(define (sublis al L)
  (if (null? L) '()
      (cons (let ((r (assq (car L) al)))
              (if r (cdr r) (car L)))
            (sublis al (cdr L)))))

(define fail #f)
(define no-bindings '((#t . #t)))

(define (get-binding var bindings) (assq var bindings))

(define (binding-val binding) (cdr binding))

(define (extend-bindings var val bindings)
  (cons (cons var val)
        (if (equal? bindings no-bindings) '() bindings)))

(define (match-variable var input bindings)
  (let ((binding (get-binding var bindings)))
    (cond ((not binding) (extend-bindings var input bindings))
          ((equal? input (binding-val binding)) bindings)
          (else fail))))

(define (pat-match pattern input . r)
  (let ((bindings (if (null? r) no-bindings (car r))))
    (cond ((eq? bindings fail) fail)
          ((variable? pattern)
           (match-variable pattern input bindings))
          ((equal? pattern input) bindings)
          ((and (pair? pattern) (pair? input))
           (pat-match (cdr pattern) (cdr input)
                      (pat-match (car pattern) (car input)
                                 bindings)))
          (else fail))))

まとめ

変数束縛やリスト要素の逐次処理を扱うことから，今回の例は本質的に『言語処理』の一種と言えます．書籍では更に発展させた処理を用いてchatbot（疑似対話プログラム）を組み上げています．

備考

記事に関する補足

解説をコメント文にしていないのはわざとです(^^;)．コードの見通しの良さを優先したためですが，ボトムアップ＆インクリメンタル的な発想としてはどうなんだろう…．
書籍ではChapter 11で更に発展させてPrologインタプリタを実装しているのだよな．前の記事と同じノリで，他のプログラミング言語でもPrologインタプリタを実装できないものかな．マクロ使ってるところが厳しいか？

更新履歴

2020-11-10：初版公開

実行例