5章 ELIZA 5.2とEx5.1

Common Lisp PAIP

Ex4.5〜Ex4.7は[d] ratingなのでさすがに難しいです。Ex4.6で5,6章でパターンマッチングについて勉強してこいと言われたので取りあえず先に進みます。

5.1 ELIZAの記述と明確化

ELIZAは入力されたシンボルのリストとあらかじめ用意しておいたルールセットに対しパターンマッチングを行い、一致したルールによって応答を書き換えるプログラムです。

以下のステップで実現します。

  1. 入力を読み込む
  2. 入力にマッチするルールを選択する
  3. 選択したルールで入力を加工して応答をつくる
  4. 応答を出力する

入力と出力はlispの場合、シンボルとして入出力してしまえば良いのでまずは置いておけます。
面倒なのは2と3です。

まずはパターンマッチの作成から。ということで5.2へ

5.2 パターンマッチ

最初に定義するパターンマッチャは単純マッチだけのもの。

(defun pat-match (pattern input)
   "Does pattern match input? Any variable can match anyting."
   (if (variable-p pattern)
       t
       (if (or (atom pattern) (atom input))
	   (eql pattern input)
	   (and (pat-match (first pattern) (first input))
		(pat-match (rest pattern) (rest input))))))

variable-pはまだ定義されていません。
ここでEx5.1

;; Exercise 5.1 [s] Would it be a good idea to replace the complex and
;; form in pat-match with the simpler (every #'pat-match
;; pattern input)?

A. everyは長さが異なるリストを渡した場合、一番短いリストに合わせて比較を止めてしまいます。その為、(a b c)と(a b c d)がマッチしてしまうのでNGです。

続き

パターンマッチの関数は定義しましたが、variable-pは定義していませんでした。これをどのように実装するかの話です。

変数の表現として考えられるお手軽な方法は、以下の３つです。

  1. いくつかのシンボルを変数として扱う。使えるのは最初に決めた変数だけ。
  2. シンボルを変数であると宣言する。変数が必要になったら登録する。
  3. 命名規則で変数を示す。変数を特別な表記にする。Prologは変数は大文字から始まる。

Common Lispはシンボル表記として大文字小文字を通常は区別しないのでProlog的な手法は使えません。ここでは名前が#\?で始まるシンボルを変数として扱うことにする様です。

(defun variable-p (x)
  "Is x a varibale (a symbol begging with '?')?"
  (and (symbolp x) (equal (char (symbol-name x) 0) #\?)))

置き換え

選択したルールによる入力を加工するのに、Common Lispには便利な関数があります。

CL-USER> (sublis '((?x . vacation))
		 '(what would it mean to you if got a ?x ?))
(WHAT WOULD IT MEAN TO YOU IF GOT A VACATION ?)

sublisを使ってテンプレートを書き換えるのに楽なように、pat-matchの戻り値を変更します。
今のpat-matchは戻り値がtかnilなので、マッチした変数と値のリストを返す様に修正します。

変数と値の束縛を返す

変数と値のalistを返す様にpat-matchを変更すると、変数無しのパターンにマッチした場合に何を返すかが問題になります。空リスト'()を返すとすると、空リストはCommon Lispではnilであるため問題となります。

ここでは、マッチしなかった場合にnil、変数なしのパターンにマッチした場合には、*1を返す様にします。

(pat-match '(a) '(b))
;; => nil ; マッチしなかった
(pat-match '(a) '(a))
;; => ((T . T)) ; マッチした
(pat-match '(?x ?y ?z) '(a b c))
;; => ((?z . c) (?y . b) (?x . a)) ; マッチした

実装は以下のようになりました。

;;;; 
;;;; patten matcher の拡張
;;;; 
(defun variable-p (x)
  "Is x a varibale (a symbol begging with '?')?"
  (and (symbolp x) (equal (char (symbol-name x) 0) #\?)))

(defconstant fail nil "パターンマッチ失敗を表す値")
(defconstant no-bindings '((t . t)) "マッチの結果、何も変数束縛が無かった場合を示す値。")

(defun binding-value (binding)
  "束縛されている変数の値を返す。- 変数がnilに束縛されていた場合は見分けがつかない…"
  (cdr binding))

(defun get-binding (variable bindings)
  "束縛リストから変数に対応する束縛を返す"
  (assoc variable bindings))
  
(defun extend-bindings (variable value bindings)
  "変数の束縛リストを拡張して返す"
  (acons variable value (if (equal bindings no-bindings)
			    '()
			    bindings)))

(defun check-and-extend-bindings (variable value bindings)
  "束縛リストを拡張する。変数が既に束縛されている場合はequalで比較し異なっている場合failとする。"
  (let ((binding (get-binding variable bindings)))
    (cond ((null binding) (extend-bindings variable value bindings))
	  ((equal (binding-value binding) value) bindings)
	  (t fail))))

(defun pat-match (pattern input &optional (bindings no-bindings))
  "入力がパターンとマッチすることを確認する。マッチした場合、マッチした変数と値のリストを返す"
  (cond ((eq bindings fail) fail)
	((variable-p pattern) (check-and-extend-bindings pattern input bindings))
	((eql pattern input) bindings)
	((and (consp pattern) (consp input))
	 (pat-match (rest pattern) (rest input)
		    (pat-match (first pattern) (first input) bindings)))
	(t fail)))

*1:T . T