実用Common Lisp　読書メモ

ウェブ技術 デジタルトランスフォーメーション技術 人工知能技術 機械学習 自然言語処理技術 推論技術 セマンティックウェブ技術 深層学習技術 オンライン学習 強化学習技術 チャットボットと質疑応答技術 ユーザーインターフェース技術 知識情報処理技術 推論技術 プログラミング スパースモデリング 確率的生成モデル サポートベクトルマシン LISP Prolog 本ブログのナビ

LISPについて

LISP（リスプ）は、人工知能や人工言語処理などの分野で広く使用されるプログラミング言語の一種であり、その名前は「LISt Processing」に由来する。LISPは、関数型プログラミング言語あり、かつプログラムをデータとして扱い、データをプログラムとして評価する、リフレクティブ（反射的）なプログラミング言語としても知られている。LISPの主な特徴は以下のようになる。

• リスト（リンクドリスト）が基本的なデータ構造である：LISPのデータはリストとして表現され、それ自体がLISPのプログラムとして評価される。この特徴を活用して、LISPは高度に柔軟なデータ構造を扱うことができる。
• 関数型プログラミングをサポートしている：LISPは関数型プログラミング言語であり、関数を一等の値として扱うことができる。関数を引数や戻り値として他の関数に渡したり、変数に代入したりするメタ的な「高階関数」としての使い方もできる。
• 自己言及（セルフリファレンス）をサポートしている：LISPのプログラムは自己言及をすることができ、自身の構造を参照することができる。これにより、LISPは高い柔軟性を持ち、自己変更可能なプログラムを書くことができる。
• シンプルな構文：LISPの構文は非常にシンプルであり、プログラムの記述が簡潔である。
• 多くの派生言語が存在する：LISPには多くの派生言語が存在し、それぞれに独自の特徴や用途がある。代表的な派生言語には、Common Lisp（コモンリスプ）、Scheme（スキーム）、Clojure（クロージャー）などがある。

今回は、世界的に著名なAI研究者であり、Googleの研究本部長(Director of Research)でもあるピーター・ノーヴィグによるLISPの代表的な参考図書「実用Common LISP」(原題”Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp”)の読書メモを記載する。

実用Common Lisp　読書メモ

本書が扱っているトピックは、人口知能（AI）、コンピュータプログラミング技術、プログラミング言語Common Lispの3つつなる。丁寧に読めばAIに対する多くの疑問が解けると同時に、重要なAIの技法も理解できるようになる。また、Common Lispのプログラムを読み、修正し、作成する能力の向上も期待できる。

本書のプログラム例は、良質のプログラミングスタイルで書かれているもので、実例はAIの研究で使用されるパラダイムを使っている。

第1部 Common Lisp 入門

第1章 Lisp 入門

概要
コンピューターのユーザーとプログラマの違い
ユーザー:新たな入力またはデータ(単語や数 )を供給する
プログラマ:新しい操作またはプログラムとデータの型を定義する
多くの言語は文(statement)と式(expression)に差異がある
文は作用を及ぼすが値は返さない
Lispの場合は全てが式なので値を返す
LISP:LISt Processing

1.1 記号計算
1.2 変数
1.3 特殊形式
1.4 リスト
1.5 新しい関数の定義
1.6 関数の使用
1.7 高階関数
1.8 その他のデータ型
1.9 要約：Lisp 評価規則
1.10 Lisp は何が違うのか？

組み込みのリスト処理機能
自動的な記憶域管理
動的な型付け
第1級関数
一様な構文
対話的環境
拡張性

1.11 演習
1.12 解答

第2章 簡単なLisp プログラム
2.1 英語のサブセット用文法
2.2 成功法による解法
2.3 ルールベースによる解法
2.4 進むべき2つの道
2.5 プログラムの変更を伴わない文法の変更
2.6 同じデータを使用した複数のプログラム開発
2.7 演習
2.8 解答

第3章 Lisp 概要
3.1 Lisp スタイルガイド

あらゆるプログラマが従うべき6つの原則
明確に規定すること(specificであること)
抽象化すること
簡素であること
与えられたツールを使うこと
明瞭であること
一貫性があること

3.2 特殊形式

定義のための特殊形式
条件分岐のための特殊形式
変数と場所を扱うための特殊形式
繰り返しのための関数と特殊形式
再帰による繰り返し
その他の特殊形式
マクロ
逆引用符表記法

3.3 リストを扱う関数
3.4 等値性と内部表現
3.5 シーケンスを扱う関数
3.6 表を管理するための関数
3.7 木構造を扱う関数
3.8 数を扱う関数
3.9 集合を扱う関数
3.10 破壊的な関数
3.11 データ型の概要
3.12 入力／出力
3.13 デバックツール
3.14 バグ予防ツール

概要
計時ツール

3.15 評価

funcall
関数を個々の引数に適用する
apply
関数を引数のリストに適用する
eval
単一の引数が渡される

3.16 クロージャ
3.17 スペシャル変数
3.18 多値
3.19 パラメータに関する補足
3.20 その他
3.21 演習
3.22 解答

第2部 初期のAIプログラム

第4章 GPS：一般問題解決機

AIプログラミングの5つの局面
1 問題記述: 文章の形式で漠然と問題を記述する
2 仕様記述: アルゴリズム的に問題の仕様を記述する
3 実装:プログラミング言語を使って問題を実装する
4 テスト: 代表的な例を使ってプログラムをテストする
5 デバッグと分析: プログラムをデバッグ/分析し、そしてプロセスを繰り返す

4.1 局面1：問題記述

GPSの中心的な手法群が連携して 手段目的分析(mean-ends analysys)のヒューリスティックを具現化する
(例)息子を保育園に連れて行きたい
アリストテレス
我々は目標についてではなく手段について熟議する
私が所有しているものと、私が必要としているものの違いを解消する方法を発見できれば、問題を解決できる
手段目標分析
現在状態と目標状態があるとき、両者の「差」を縮小する行動を選択
その行動は現在状態に対して実行され、新たな状態を生む
このプロセスが繰り返し行われ、目標状態が現在状態になるまで続けられる
機能要因
検出可能な差異に従ってその差異を縮小する適切な行動を関連づける方法を持つ
行動が失敗して代替案を実行するため、進捗状況(実際の状態と目標状態の差異)を把握する手段を持つ

4.2 局面2：仕様記述

この世界における現在の状態や目標の状態を条件の集合として表現
許されるオペレーターのリスト
オベレータは、行為、前提条件のリスト、効果のリストから構成される構造体
全ての前提条件を満たした場合にオペレータを適用できる

4.3 局面3：実装

トップレベル関数
GPS
オペレータのリストを使ってある状態から目標へと問題解決する
(defn GPS (*state* goal *ops*) "General Problem Solver: achieve all goal using *ops*." (If (every #'achieve goals) 'solved))
スペシャル変数
*state*
現在の状態:条件のリスト
(defvar *state* nil "The current state a list of conditions.")
*ops*
利用可能なオペレータのリスト
(defvar *ops* nil "A list of available operations.")
データ型
op
前提条件、追加条件、削減状態を備えたオペレータ
(destruct op "An operation" (action nil) (preconditions nil) (add-list nil) (del-list nil))
関数
achieve
個々の目標に到達する
(defund achieve (goal) "A goal is achieved if it already holds, or if there is an appropriate op for it that is applicable." (or (member goal *state*) (some #'apply-op (find-all goal *ops* :test #'appropriate-p))))
appropriate-p
オペレータが目標に適合するかどうかを判定する
(defun appropriate-p (goal op) "An op is appropriate to a goal if it is in its add list." (member gaol (op-add-list op)))
apply-op
オペレータを現在の状態に適用する
(defund apply-op (op) "Print a message and update "state" if op is applicable." (when (every #'achieve (op-preconds op)) (setf *state* (set-difference *state* (op-del-list op))) (setf *state* (union *state* (op-add-list op)))
選択されたCommon Lisp関数
member
ある要素がメンバーかどうかをテストする
set-difference
片方の集合には存在して他方の集合には存在しない全ての要素
union
2つの集合に存在する全ての要素
every
リストのあらゆる要素が述語を満足するかどうかをテストする
some
リストのある要素が述語を満足するかどうかをテストする
定義済みの関数
find-all
マッチした要素全てのリスト

4.4 局面4：テスト

「車で保育園に連れて行く」

4.5 局面5：分析、もしくは「GPSの一般性について嘘をついていた」

AIプログラミングは、明確に定義された仕様に合致させるというよりも、 問題領域についてより理解を深めることを目的とすることが頻繁にある

4.6 「ブロックの周りを走り回る」問題

運動している状態の記述??

4.7 「シブリング目標を打ち消す」問題

シブリング:兄弟
全ての目標を満足させるのではなく、順番に解いていくと前の目標を打ち消す場合がある
シブリング目標を打ち消す問題
前提条件がシブリング目標を打ち消す問題を人息できるようにすれば良い
(defun achieve-all (goals) "Try to achieve each goal, make sure they still hold." (And (every #'achieve goals) ( subsets goals *state*)))
4.8「調べることなく跳躍する」問題
「前提条件がシブリング目標を打ち消す」問題に対処する時には、 目標リストの中の目標の順番についてもっと慎重に考える必要がある
(Jump-off-cliff land-safety)
崖を都護越えようとしたが、安全な着地を考えていなかった
あるオペレータの行為が結果的に行き止まりにな流可能性があったとしてもその行為が実行されて*state*が決定的に変更される
局所的な状態変数を導入することが一つの解

4.8 「調べることなく跳躍する」問題
4.9 「再帰的な副目標」問題

再帰的になっていると無限ループが生じる可能性がある
ループを検出したら断念する仕組みを入れる

4.10 「中間情報の不足」問題

解決方法を提示できないとnilを返すだけでは、失敗の原因を何も知らせない
debugとundebug、traceとuntrace

4.11 GPSバージョン2：もう少し一般性のある一般問題解決機

トップレベル関数
GPS
オペレータのリストを使ってある状態から目標へと問題解決する
(defn GPS (*state* goal *ops*) "General Problem Solver: achieve all goal using *ops*." (If (every #'achieve goals) 'solved))
スペシャル変数
*ops*
利用可能なオペレータのリスト
(defvar *ops* nil "A list of available operations.")
データ型
op
前提条件、追加条件、削減状態を備えたオペレータ
(destruct op "An operation" (action nil) (preconditions nil) (add-list nil) (del-list nil))
主要関数
achieve-all
目標のリストに到達する
Achieve
個々の目標に到達する
(defund achieve (goal) "A goal is achieved if it already holds, or if there is an appropriate op for it that is applicable." (or (member goal *state*) (some #'apply-op (find-all goal *ops* :test #'appropriate-p))))
appropriate-p
オペレータが目標に適合するかどうかを判定する
(defun appropriate-p (goal op) "An op is appropriate to a goal if it is in its add list." (member gaol (op-add-list op)))
apply-op
オペレータを現在の状態に適用する
(defund apply-op (op) "Print a message and update "state" if op is applicable." (when (every #'achieve (op-preconds op)) (setf *state* (set-difference *state* (op-del-list op))) (setf *state* (union *state* (op-add-list op)))
補助関数
executing-p
状態はexecutingか?
(defun executing-p (p) "Is x of the form: (executing ...) ?" (starts-with x 'executing))
starts-with
引数が指定されたアトムで始まるリストか?
(defun starts-with (list x) "Is this a list whose first element is x?" (And (conspired list) (eel (first list) x)))
convert-op
Executing規則を使用するためにオペレターを変換する
(defun convert-op (op) "Make op conform to the (EXECUTING op) convention. " (unless (some #'executing-p (op-add-list op)) (Push (list 'executing (op-action op)) (op-add-list op))) op)
op
オペレータを作成する
(defun op (action &key preconds add-list del-list) "Make a new operator that obey the (EXECUTING op) convention." (convert-op (make-op :action action :preconds preconds :add-list add-list :del-list del-list)))
use
オペレータのリストを使用する
member-equal
要素がリストのメンバーに等しいかどうかをテストする
選択されたCommon Lisp関数
member
ある要素がメンバーかどうかをテストする
set-difference
片方の集合には存在して他方の集合には存在しない全ての要素
subsrtq
ある集合が別の集合に含有されているかどうかをテストする
union
2つの集合に存在する全ての要素
every
リストのあらゆる要素が述語を満足するかどうかをテストする
some
リストのある要素が述語を満足するかどうかをテストする
remove-if
テストを満足する全ての項目を取り除く
定義済みの関数
find-all
マッチした要素全てのリスト
find-all-if
述語を満足する全ての要素のリスト

4.12 モンキーとバナナ（新しい領域の問題）

新しい課題への適用
異なるオペレータを導入するだけでGPSで動作

4.13 迷路探索

異なるオペレータを導入するだけでGPSで動作

4.14 積み木の世界

Sussmanのアノマリー

4.15 局面5（再び）：バージョン2の分析
4.16 「跳躍もしなければ調べもしない」問題

可能性のあるすべての解決方法を調べる
保護すべき目標のリストを管理する

4.17 「記述力不足」問題

conjunction(連言)だけではなく、disjunction(選言)や否定(negation)が必要
時間を扱う問題の取り扱い
部分解で満足できるかどうか

4.18 「完全な情報」問題

曖昧さの表現が必要
GPSはオペレータず実行しようとしていることを、常にかつ正確に知っている
予期していない困難を表現する方法も持たない

4.19 「相互作用する目標」問題

すべての目標を満足させるという概念もない
目標の多くは眠ったまま
部分的にしか目標に達せない
目標を延期したり捨てたりの絶え間のないプロセスがある
人間は自分で避けようとする望ましくない状況も知っている
Heb Simonのアプローチ
程よい数の目標を程よい程度に満足させる一方で、目標を捨てたり延期したりする戦略を記述するために、「必要最低限の条件を満たすこと(satisficting)」という用語を作る
GPSは成功と失敗の識別しかできないので、部分的な成功を最大限に生かす術を持たない

4.20 GPSの限界

解決できない問題
実行時間が長すぎる
問題自体に解決方法がない
GPSの本質は「Local Feature -Guided Network Searcher」
GPSにより塾考すること(deliberation)の本質」を探求するための手段となる
塾考するためのツールにできないのか
手段目的分析のより完全な理解のためのツールとなる
AIの魅力は、手段と目標の分割
AIプロジェクトの目標は、有益と思われる仕事を、以前よりも有効、高速、安価に達成できること

4.21 歴史と参考資料

Earl ScaerdotiのABSTRIPSプログラム
STRIPSの修正バージョン
David WarrenのWARPLANプランナー
Austin TateのNONLINシステム
David ChapmanのTWEAK
概観論文
Allen Hender, Tate

4.22 演習
4.23 解答

第5章 ELIZA：機械との対話

概要
1960年代に作られた3つの有名なプログラム
ELIZA
精神分析医をシミュレート
STUDENT
中学程度の代数を解く
MACSYMA
微積分を含む記号代数のための数式処理プログラム
3つのプログラムともパターンマッチングがベースに動作
説明するということは、説明して疑問を解くこと
プログラムは、入力の要素を注意深く認識、変換、真似ることで、理解するという仕事をやっている
手続きは、入力の中でキーとなる単語や句に基づいて、特定のパターンを探すこと

5.1 ELIZAの問題記述と仕様記述

アルゴリズム
入力を読み込む
入力にマッチするパターンを発見する
入力を応答に変換する
応答を出力する

5.2 パターンマッチング

パターンマッチング変数の実装
[X, Y, Z]のようなシンボルの集合だけを変換
Variable型の構造体を定義する方法
シンボルを使用し、シンボルの名前によって変数と定数を区別する
シンボルは構成要素を持つアトム

5.3 セグメントパターンマッチング
5.4 ELIZAのプログラム：ルールベーストランスレータ

用語解説
トップレベル関数
eliza
パターンマッチングルールを使用してユーザー入力に応答する
スペシャル変数
*eliza-rules*
変換ルールのリスト
データ型
rule
パターンと応答のリストの関連付け
関数
eliza
パターンマッチングルールを使用してユーザー入力に応答する
use-eliza-rules
入力を変換するルールを探し出す
switch-viewpoint
「I」を「you」に変更する、また逆に変更する
flatten
リストの要素を付け加えて一緒にする
選択されたCommon Lisp関数
sublis
要素を木に代入する
定義済みの関数
random-elt
リストから無作為に要素を取り出す
pat-match
パターンを入力に対してマッチさせる
mappend
mapcarの結果を付け加えて一緒にする
別名(エイリアス)方式
複数の単語を同じパターンと関連づける
例:motherとfatherをfamilyパターンに関連づけ
同義語機能(シノニム)
「don't」と「do not」、「everyone」と「everybody」
カンマで区切られた句を持つ入力の場合は、各句は別々に処理され、最も優先度の高い応答が選ばれる
「記憶(メモリ)」機能を持ち、パターンが入力とマッチしない時に「Tell me more aboit X」のような応答をする
重要なのは、プログラムではなく技法

5.5 歴史と参考資料

オリジナル文献
Weizenbaum(1966)
類似のパターンマッチング技法を使用した対話システム
Kenneth ColtyのPARTY
Colbyによる提言
信念をモデル化した対話システムに関する研究
Alan Collins(1978)
Jamie Carbonell(1981)

5.6 演習
5.7 解答

第6章 ソフトウェアツールの構築
6.1 対話的インタープリタツール

REPL(read-eval-print)ループ
(defun lisp() (loop (print '>) (print (eval (read)))))
(loop (print (eval (read))))
一番シンプルな構成
readは構文解析パーサー
入力を読み込み、 入力されたものをある方法で評価または変換し、 出力し、 それからさらなるの入力を読み込むために戻る
繰り返し出現するパターンの利用方法
非公式な利用方法
パターンをクリシェやイデオムとして扱う
頻繁に出現するが、使われ方は少しづつ違う
コピーして修正
公式な利用方法
関数と、おそらくデータ構造の形で抽象化し、新しいアプリケーションからは、抽象化したものを明示的に参照する
インタープリタパターンの抽象化
(defun interactive-interpreter (prompt transformer) "Read an expression, transform it, and print the result." (loop (print prompt) (print (funcall transformer (read)))))
(defun lisp ( ) (Interactive-interpreter '> #'eval))
(defun eliza ( ) (Interactive-interpreter 'Eliza> #'(lambda (x) (flatten (use-eliza-rules x)))))
compose関数の利用
(defun compose (f g) "Return the function that computes (f (g x))." #'(lambda (x) (fungal f (fungal g x))))
(defun Eliza ( ) (Interactive-interpreter 'Eliza> (Compose #'flatten #'use-eliza-rules)))

6.2 パターンマッチングツール

一つの入力を一つのパターにマッチさせる
「一般性のある」ツールとは
そのツールでどんな機能を提供するかを決定することが課題
機構
0個以上の要素にマッチするセグメント変数を提供
その述語を満足しなければマッチしないような、任意の述語を指定できるようにする
(Pat-match '(x = (?is ?n numbers)) '(x = 34)) -> ((?N . 34))
(Pat-match '(x = (?is ?n numbers)) '(x = x)) -> NIL
?and, ?or, ?notの組み合わせ
(Pat-match '(?x (?or < = >) ?y) '(3 < 4)) -> ((?Y . 4) (?X . 3))
(Pat-match '(x = (?and (?is ?n numbers) (?is ?n odd))) '(X = 3)) -> ((?N . 3))
(Pat-match '(?x /= (?not ?x)) '(3 /= 4)) -> ((?x . 3))
パターンの文法
pat => var 任意の一つの式とマッチする 　　　 constant このアトムとマッチする 　　　 segment-pat シーケンスに対して何かとマッチする 　　　 single-pat 1つの式に対して何かとマッチする 　　　 (apt . pat) 最初と残りとマッチする Single-pat => (?is var predicticate) 1つの域に対して銃後をテストする 　　　　　　　 (?or pat...) 1つの式に対して任意のパターンとマッチする 　　　　　　 　(?and pat...) 1つの式に関してあらゆるパターンとマッチする 　　　　　　 　(?not pat..) パターンがマッチしない時に成功する Segment-pat => ((?* var) ...) 0以上の式とマッチする 　　　　　　　　　 ((?+ var) ...) 1つ以上の式とマッチする 　　　　　　　　　 ((?? Var) ..) 0または1つ以上の式とマッチする 　　　　　　　　　 ((?if exp) ..) 変数を含む式が真かどうかテストする 　　　　 var => ?cahrs ?で始まるシンボル 　 constant => atom 変数ではない任意のアトム
データ駆動型プログラミング
パターン/アクションを表に格納する
デスパッチ関数
データ駆動の関数を呼び出す関数
ディスパッチメカニズム:言語が振る舞いを動的に選択する様々な仕組み
セグメント
何かの塊
シーケンス
連続しているもの

6.3 ルールベーストランスレータツール

入力をいくつかのパターンに対してマッチさせる
マッチしたパターンの中から何かを選ぶルールを作る
(defun use-eliza-rules (input) "Find some rule with to transform the input." (some #'(lambda (rule) (let (( result (pat-match (rule-pattern rule) input))) (If (not (eq result fail)) (sublis (switch-viewpoint result) (Random-Let (rule-response rule)))))) *Eliza-rules* ))
ルールのリストを探索し、マッチしたルールに基づいてアクションを取る
汎用的なルールベーストランスレータ
(defun rule-based-translator (input rules &key (matcher #'pat-match) (Rule-if #'first) (rule-then #'rest) (action #'sublist)) "Find the first rule in rules that match input, and apply the action to that rule." (Some #'(lambda (rule) (Let ((result (fungal matcher (fungal rule-if rule) Input))) (If (not (qe result fail)) (Fungal action result (fungal rule-then rule))))) Rules))

6.4 探索ツール一式

概要
GPSプログラムはある状態から探索しはじめて、隣の状態を調べながら書いへ到達する探索問題
状態とは問題の状況や状態を記述したもの
状態は隣接した状態を保つ
探索問題は、次へ進むべき最良の選択を決定する方法がない:非決定的
探索問題の特徴
開始状態
目標状態(1つ以上)
サクセッサ、もしくは、ある状態から次に到達できる状態
探索する順番を決定する戦略
手段目的分析
定義が必要なのは、状態空間もしくは可能性のあるすべての状態
状態はノード、サクセッサとの関連はグラフにおけるリンク
木構造の探索
探索の誘導
探索経路
「良い解を推定すること」対「良い解を保証すること」
グラフ探索

6.5 探索問題としてのGPS
6.6 歴史と参考資料
6.7 演習
6.8 解答

第7章 STUDENT：代数の文章題を解く
7.1 英文を方程式に変換する
7.2 代数方程式を解く
7.3 例題
7.4 歴史と参考資料
7.5 演習
7.6 解答

第8章 記号計算：簡単化プログラム
8.1 中置記法を前置記法に変換する
8.2 簡単化ルール
8.3 結合性と可換性
8.4 対数関数、三角関数、微分
8.5 ルールベースの限界
8.6 積分
8.7 歴史と参考資料
8.8 演習

第3部 ツールと技法

第9章 効率性の問題

概要
Lispの効用
ラピッドプロトタイピング
大量のデータと巨大な探索空間を扱う場合には、効率化が重要になる
効率の良いプログラム
プログラムを変更する必要が生じた時に、容易に変更できる
適切な抽象化
プログラムを動かす際に時間がかかっている場所を特定できる
効率の悪い部品を拘束のバージョンに置き換えれる

9.1 キャッシュ技法：メモ化（Memoization）

計算結果の再利用

9.2 コンパイル技法

実行時に行うことを少なくする
コンパイルはインタープリタの2倍?

9.3 遅延計算技法

計算が部分的に不要かもしれない場合、その計算を遅延させる
クロージャ(closure)
関数閉包
プログラミング言語における関数オブジェクトの1種
ラムダ式や無名関数にて利用可能な機能・概念
引数以外の変数を実行時の環境ではなく、自身が定義された環境(静的スコープ)において解決する
関数とそれを評価する環境のペア
クロージャの仕事
集合のコンストラクタを関数として指定し、後でその関数を呼び出す

9.4 索引付け技法

データ構造に索引をつけて素早く情報を取り出す
長さがnのリストの要素を見つけるには、平均n/2ステップが必要

9.5 インスツルメンテーション：最適化すべきものを決定する

使用頻度の高い備品を特定して最適化する
選択された関数の呼び出し回数を測る
関数のプロファイリング(profiling)
trace関数

9.6 効率に関するケーススタディ：SIMPLIFY プログラム

メモ化、コンパイル、索引付けを組み合わせて130倍の高速化
メモ化
サブルーチン呼び出しの結果を後で利用可能なように保持する
構文解析等でも使われる
バックトラッキング式の再帰下降構文解析
アーリー法
キャッシュの限定的な形態
索引付け
単一ルールコンパイラ
ルールセットコンパイラ

9.7 歴史と参考資料
9.8 演習
9.9 解答

第10章 低レベルの効率性の問題

概要
アルゴリズムを大幅に変えずに効率化する方法
プログラムの中でも頻繁に使われる部分を特定して、その部分を局所的に最適化(micro-optimizing)する

10.1 宣言の使用

汎用コンピューターでlispを走らせる場合には、型検査に多くの時間が費やされる
頑健性を犠牲にして、特定の変数が常に指定された方であることを選言する(declare)もしくは約束する(promise)

10.2 総称関数の回避

Common Lispは高い一般性を持つ関数を備えている
引数がリストかベクターかを気にせずに使う

10.3 複雑な引数リストの回避

キーワード引数を持つ関数は大きなオーバーヘッドを伴う

10.4 不必要なcons の回避

関数consは隠れたコストがかかっている

10.5 適切なデータ構造の使用

キーポイントになるデータ型を、最も効率の良い実装で使用することが重要
適切なデータ構造 : 変数
適切なデータ構造 : キュー(queue)
キュー(queue)
後ろに要素を追加して前から削除できるデータ構造
スタックはリストで扱いやすいがキューは処理に時間がかかる
スタックは出入り口が１つ
適切なデータ構造 : 表(table)
表(table)
キーと値を関連付けて格納し、後でキーを使用して値を取り出す
表の持つ操作の可能性
キー数をカウントする
全てのキーをクリアする
表のキー/値のついにマッピング関数を適用する
非循環有効グラフ (DAG: directed acyclic graph)
スペル修正プログラム

10.6 演習
10.7 解答

第11章 論理プログラミング
11.1 アイディア1：一様なデータベース
11.2 アイディア2：論理変数のユニフィケーション
11.3 アイディア3：自動後戻り制御
11.4 ゼブラ問題
11.5 後戻りとユニフィケーションの相乗効果
11.6 破壊的ユニフィケーション
11.7 Prolog によるProlog
11.8 Prolog とLisp の比較
11.9 歴史と参考資料
11.10 演習
11.11 解答

第12章 論理プログラムのコンパイル
12.1 Prologコンパイラ
12.2 コンパイラのエラー修復
12.3 コンパイラの改良
12.4 ユニフィケーションのコンパイルの改良
12.5 ユニフィケーションのさらなる改良
12.6 コンパイラのユーザインタフェース
12.7 コンパイラのベンチマークテスト
12.8 プリミティブの追加
12.9 カット
12.10 「実際の」Prolog
12.11 歴史と参考資料
12.12 演習
12.13 解答

第13章 オブジェクト指向プログラミング
13.1 オブジェクト指向プログラミング
13.2 オブジェクト
13.3 総称関数
13.4 クラス
13.5 委譲
13.6 継承
13.7 CLOS：Common Lisp Object System
13.8 CLOS による実装例：探索ツール

最良優先探索

13.9 CLOS はオブジェクト指向システムか？
13.10 オブジェクト指向プログラミングの利点

正当性
頑健性
拡張性
再利用性
適合性

13.11 歴史と参考資料
13.12 演習

第14章 知識表現と推論

概要
1960-年代のAI研究は探索問題に全力を注いでいた
正しい探索法が発見できれば問題は全て解かれ、 定理も全て証明される
1970年代
どんなに賢い推論アルゴリズムが考案できても、 NP困難な問題は解けない
一般的な推論機構はトイプロブレムには有効だが、 問題のサイズが大きくなると対応できない
代替案
エキスパートシステム
困難な問題を解く鍵は、 問題をより簡単な問題に分けるための特例のルールを獲得すること
MYCIN
どのような推論機構を選択するかは、 正しい知識を持つほど重要ではない
確信度、確率、ファジー集合論を仕様しているかどうかは重要ではない
重要なことは知識の獲得
システムで使用された知識が 明確に定義できていなかったことに大きな認識を持つ
(Color apple red)は、特定のりんごが赤いことを意味するのか、全てのりんごが赤いことを意味するのか
知識表見の分野の技術
知識を操作するためのアルゴリズム
知識表現のための明確なセマンティクスの提供
表現力と効率のトレードオフ
1980年代終わり
合理的な表現力を持つ良い言語を見つける願望に対する疑念
簡単な質問に応答するための計算量はワーストケースで指数オーダー
1990年代
知識表現と推論へ関心が移る
言語の表現力と効率の両方を含有
平均的なケースがワーストケースよりも重要
知識量はワーストケースでは、 解決困難な問題を解くには役立たないが、 実際には稀にしか起こらない

14.1 知識表現言語の分類

論理式(prolog)
ネットワーク(意味ネットワーク、概念グラフ)
論理型言語の構文上の変形
論理型との相違点は「リンク」を重要に扱うところ
推論はリンクをたどることで実行される
AとBの間にリンクを置くことは L(A,B)が真であることを表現するだけでなく、 知識ベースがどのようにして探索されるかについて、何かを表現することができる
オブジェクト(スクリプト、フレーム)
述語論理の構文上の変形
例(a person (name =Jan) (age = 32))
∃p: person(p) ∧ name(p, Jan) ∧ age(p,32)
述語論理の方が表現力が大きい
フレーム言語
手続き(Lisp, プロダクションシステム)
知識の明示的な表現がなくても答えを計算する
表現が難しい値を計算するのに手続きを使う

14.2 述語論理とその問題

述語論理は、AIの中で特別の地位にある表現方法
他の表現方法の定義や評価を行う普遍性の高い標準
言語で表現されたものの意味を理解するためり定義ができる
知識表現
関係や関数が適用された個体
論理結合子and,or,notにより関係を結合して形成された文を使用する
哲学者や心理学者は、人間の思考モデルを記述
述語論理はビットの世界に翻訳が容易
コンピューターのある状態を表現できれば、 ある状態を別の状態にマップする公理群として 任意のコンピュータープログラムを実悟論理で表現できる
述語論理の課題
決定可能性(decidability)
身売りの集合と目標が与えられた場合に、目標とその否定のどちらも、公理から導出できないかもしれない
扱いやすさ(tractability)
目標が証明可能であったとしても、利用可能な推論機構を使用してその証明を発見するのに時間がかかりすぎる
不確実性(uncertainty)
ある程度証明されているが、真または偽であるか各施設にわからない関係を扱うことは不都合かもしれない
単調性(monotonicity)
純粋な述語論理では、一旦定理が証明されると永久に真である
しかし、仮説に基づいて仮の定理を導出し、仮説が偽であることが証明された時に、仮説を撤回する方法を用いた
無矛盾性(consistency)
純粋な述語論理では矛盾は許されない
矛盾が少しでもあれば、データベース全体が汚染される
全知性(omniscience)
証明可能なものと、証明される必要があることを区別することが難しい
エージェントがわかっている事実から全ての帰結を信じるという根拠のない仮説につながる
表現力(expressiveness)
一階述語論理は、関係や命題のようなものについて語ると、ぎこちないものになる

14.3 論理型言語：Prolog

概要
論理でプログラミングする問題に対する答えとして提案される
Kowalskiの等式
アルゴリズム=論理+制御
論理
計算で使われる公理
制御
公理に演繹が適用される方法
制御された演繹
演繹
一般的・普遍的な前提から、より個別・特殊な結論を得る論理的推論の方法
論理=アルゴリズム- 制御
?無限の探索空間を持つ場合に、探索方ほうに関する助言を得なければ合理的な時間で答えを得られない
prologの問題
言語の効率を良くするために、その表現力が制限されている
例:人の名前がJanまたはJohnであることを表明できない
ある事実が偽であることを表明できない
Prologは偽と未知を区別できない
推論機構が正しくもないし、完全でもない
循環ユニフィケーションの検査をしないので誤った答えを出すかもしれない
深さ優先探索を行うので、正しい答えを見つけられないかもしれない
基本となる論理に制御情報を追加するよう方法を持たない
制御情報を追加すると、特定の問題に関しては効率を悪くする可能性もある

14.4 Prolog の表現力に関する問題

prologは完全な述語論理ではない
ある種の不明確な事実を表現できない
例
code1
(<- (not (capital LA CA)))
(<- (or (capital Albany NY) (capital NYC NY)))
New York州の州都はNew York CityかAlbanyのどちらかである
code2
NYCがNY州の州都でなければ、AlbanyがNY州の州都である
(<- (capital Albany NY) (not (capital NYC NY)))
AlbanyがNY州の州都でなければ、NYCがNY州の州都である
(<- (capital NYC NY) (not (capital Albay NY)))
Prologのnotは論理のnotとは異なる
Prologが質問に「no」と答えた時には、 その質問が基地の事実からは証明できないことを意味している
未知の事実があると、実際には真かもしれない
「証明されていない」ことと、「偽」を同等とみなす
閉世界仮説 (closed world assumption)
真であるもの全てが既知である
一般的な知識表現が持つ要素
「yes」
「No」
「unknown」
prologにはない
Prologは照明が全く不必要な時に、同じ証明を2回行う
一度に単一の説しか考慮しないのでは不十分
正しい答えを出すために、 複数の節を一緒に考慮する必要がある
選言的推論
3つの色分けブロック
ブロックを国とする
ある東欧の国Eが、共産主義国家を維持するか、 民主主義国家になるかどうかを決定したが結果はわからない
Eの国土は民主主義国家Dと共産主義国家Cに囲まれている
問題
ある共産主義国家が、ある民主主義国家に隣接しているか?
yes
Prologは選言(or)と否定(not)が得意ではない
表現の変換がうまくいく例
Jan likes everyone.
∀x person(x) ⇒ likes(Jan, x)
( <- (likes Jan ?x) (person ?x))
表現の変換がうまくいかない例
Jan likes someone.
∃x person(x) ⇒ likes(Jan,x)
(<- (likes Jan p1)) (<- (person p1))
p1:Janが好む道の人を示すシンボル
p1は、変数ではなく定数
特定されているが道の存在を示す定数
スコーレム定数 (skolem constant)
名前の唯一性仮説 (unique name assumption)
異なるアトムが異なる個体を表す
上記の例でアサーションp1=Adrin(Janが好む人がAdrin)を 入れてもprologはうまく働かない
スコーレム関数 (Skolem function)
例
Everyone likes someone.
∀y∃x person(x) ⇒ likes(y,x)
(<- (likes ?y (p2 ?y))) (<- (person (p2 ?y)))
p2が変数?yによって決まるスコーレム関数
誰もが、必ずしも同じ人ではないある人を好む

14.5 述語論理の表現力に関する問題

述語論理における表現力の限界
例
(<- (animal ?x) (lion ?x)) (<- (animal ?x) (tiger ?x)) (<- (animal ?x) (bear ?x))
任意の基地のライオン、トラ、クマが 動物であることを証明できる
「そこにはどのような種類の動物がいるのか?」に答えられない
(?- (<- (animal ?x) ?proposition))
高階文(higher-order sentence)
関係や文を項として利用する述語論理の文
高階表現のパラドクス
他の文の真偽に関することを 述べる文を許すとパラドクスに陥る
「この文は偽である」という文は真か、偽か?
述語論理は、固体で構成される世界において、 固体の特性や個体間の関係を利用して定義される
個体を見つけ出し分類するモデルに適している
連続的な実態の世界は(例えば水)定義しづらい
Patrick Hayseのアプローチで表現可能
カテゴリを定義する場合
数学的に明確なカテゴリに対しては述語論理は
xが3片を持つ多角形の時、かつその時に限り、xは3角形である

14.6 完全性に関する問題

Prologは深さ優先に探索するので、 探索空間の１つの枝だけにとらわれて他の枝を調べない
(<- (sibling lee kim)) (<- (sibling ?x ?y) (sibling ?y ?x)) Leeはkimのシブリング 「XがYの兄弟姉妹である」を表す述語sibling(X,Y) 14.7 効率に関する問題：索引付け Prologコンパイラは「プログラムのような」述語を 効率的に処理するように設計されている 「プログラムのような」述語 複雑な本体を持っているが、ルール数は少ない述語 上記のコンパイラは「表のような」述語 に対しては効率が悪い 「表のような」述語 多数の単純な事実を持つ述語 14.8 索引付け問題の解決法 「表のような」述語に対する解決 項目の追加、削除、検索を容易にするため「索引付け」を行う 「トライ」や「弁別木データ構造」の拡張 行動と反応の心理学の視点 般化と弁別 般化 ある刺激に対して特定の反応が条件付けられた場合、 類似の刺激(似た刺激)に対しても同様の反応が生起すること 似ている度合いが低いほど 反応が引き起こされる頻度(=反応の生成頻度)が低くなる 汎化勾配 弁別 よく似た刺激の場合般化によってどちらの刺激にも条件反射を生じるが それを繰り返していくと片方の刺激にしか反応しなくなる Prologの事実に対して弁別木を作成することは、事実と質問の両方に変数が存在するために複雑になる キーと質問が、ワイルドカードを持った述語構造である弁別木の問題 ワイルドカードは変数 変数束縛はない 例 例2 14.9 安全性の問題の解決法 14.10 表現力の問題の解決法 高階述語 「どんな種類の動物がいるのか?」 新しい言語を用いることで制約して「高階述語」で無くする 新しい言語の許す3つのオブジェクト カテゴリ(category) 1項述語 関係(relation) 2項述語 個体(individual) ゼロ項述語 プリミティブオペレータ sub (sub サブカテゴリ スーパーカテゴリ) 例:(sub dog animal) 犬は動物の一種である rel (rel 関係 領域カテゴリ 値域カテゴリ) 例: (rel birthday animal date) 誕生日という関係は、各動物と、ある日付の関係を保持する ind (ind 個体 カテゴリ) 例:(ind fido dog) 個体Fidoは犬に分類される val (val 関係 個体値) 例: (val birthday fido July-1) Fidoの誕生日はJuly-1である and (and アサーション...) 例: (and A B) AとBの両方が真である 改良 フレーム言語 読み書きを容易にする代替の構文を提供する フレームはスロットを備えたオブジェクト 可能世界 : 心理、否定、選言 4つの問題に着目 未知と偽を区別する 否定を表現する 選言を表現する 複数の可能性がある状況を表現する 解決する手段 可能世界 否定された述語 Truth maintenance system(TMS)の追加 ユニフィケーション、等値性、型、スコーレム定数 14.11 歴史と参考資料 14.12 演習 14.13 解答 第4部 高度なAIプログラム 第15章 標準形による記号計算 概要 prologの課題 不確実性を備えた推論 明らかに真か偽であるような白黒のはっきり区別できる世界しか扱えない 偽についてもうまく扱えない 説明 会がどのようにして導出されたかに関して説明できない 柔軟な制御フロー 目標から後ろ向きに連鎖によって機能する 医療診断では、医師によって出された支持に従って、患者に関する特定の情報を獲得する これらの課題に対するアプローチがエキスパートシステム MYCIN 医療診断のシステム 細菌性の血液感染症に関する抗生物質による治療の指示を出すように設計 (defrule 52 If (site culture is blood) (Gram organism is neg) (Morphology organism is rod) (Burn patient is serious) Then .4 (Identity organism is pseudomonas)) EMYCIN Prologと多くの共通部分を持つ後ろ向き連鎖ルールのインタープリタ 相違点 不確実性を扱うことができる 各叙述に確信度(CF:crertainty factor)を関連づける 計算を重複して繰り返す必要がないようにキャッシュする システムがユーザーに情報を求めるための容易な方法を多提供 振る舞いの説明を提供 要約 EMYCINプログラムの用語解説 クライアント用トップレベル関数 emycin 問題を表現するコンテキストのリストによりシェルを走らせる mycin 細菌感染ドメインでシェルを走らせる 専門家用トップレベル関数 defcontext コンテキストを定義する defparm パラメータを定義する defrule ルールを定義する 定数 true +1の確信度 false -1の確信度 unknown 0の確信度 cf-cut-off このCFより低い時は探索を打ち切る データ型 context 特定の問題に関係するサブドメイン parm パラメータ rule 確信度を備えた後ろ向き連鎖のルール yes/no Yesとnoをメンバーにもつ型 Emycinの主要関数 get-context-data データを集めて結論を出す find-out データベース、ユーザーに要求、ルールの使用により値を決定する get-db データベースから事実を取得する use-rules パラメータに関連した全てのルールを適用する use-rule 一つのルールを適用する new-instance コンテキストの新しいインスタンスを作成する report-findings 結果を出力する 補助関数 cf-or 確信度をorで結合する cf-and 確信度をandで結合する true-p このCFは真か? false-p このCFは偽か? cf-p これは確信度か? put-p 事実をデータベースに置く clear-db 全ての事実をデータベースからクリアする get-vals パラメータ/インスタンスに対する値とCFを取得する get-cf パラメータ/インスタンスに対する値とCFを修得する update-cf パラメータ/インスタンスに対する値とCFを変更する ash-vals ユーザーにパラメータ/インスタンスに対する値/CFを要求する prompt-and-read-vals プロンプトを出力し返答を読み込む inst-name インスタンスの名前 parse-reply 返答を値/CFのリストに変換する parm-type このパラメータの値はこの型でなければならない get-parm この名前を持つパラメータの構造体を取得するか作成する put-rule 結論の各パラメータの下で索引付けした新しいルールを追加する get-rule このパラメータを決定するのに役立つルールを取得する clear-rule 全てのルールを取り除く satisfy-premises 前提の結合されたCFを計算する eval-condition 条件のCFを決定する reject-premise 前提が明らかなに偽ならば排除する conclude パラメータ/インスタンス/値／CFをデータベースに追加する is equalの別名 check-conditions ルールが正当であることを確かめる print-rule ルールを出力する print-conditions 条件のリストを出力する print-condition 単一の条件を出力する cf->english
CFを英語表現に変換する

15.1 多項式のための標準形
15.2 多項式の微分
15.3 中置形式と前置形式間の変換
15.4 多項式簡単化プログラムのベンチマークテスト
15.5 有理式のための標準形
15.6 有理式の拡張
15.7 歴史と参考資料
15.8 演習
15.9 解答

第16章 エキスパートシステム

概要
prologの3つの課題
不確実性を備えた推論
Prologではおそらくとかは扱えない
説明
会がどのようにして導出されたか説明できない
柔軟な制御フロー
Prologは、目標からの後ろ向き連鎖で機能する
後ろ向き連鎖以外の戦略が必要
医療では医師の指示に従って患者に対する特定の情報が獲得される
EMYCINとprologの違い
EMYCINは不確実性を扱える
各叙述に確信度を与える
計算を重複しなくて済むようにキャッシュする
システムがユーザーに情報を求めるための容易な方法を提供する
振る舞いの説明を提供する

16.1 不確実性への対応

確信度の結合手法
例:combine(.60,.40)=.76
AとBが独立の場合の確率とやなじ
確信度は確率とは違う
信念や疑念は扱うが、依存や独立は扱わない
EMYCINの仮設
単一のルールの中にある条件はお互いに依存
異なるルールの中にある条件は独立
EMYCINの確信度関数
革新度は真と偽の世界では成り立たない
分数の世界のみ
確信度は探索を打ち切る時に使う

16.2 導出された事実のキャッシュ

Emycinは同種したすべての事実をデータベースに格納する
Put-db
Get-db
Clear-db

16.3 質問

ルールから答えが同定できない時に、ユーザーに質問できる
Ask-vlaはインスタンスのパラメータに関する質問を出力し、ユーザーが確信度をふよした値もしくはあたいのリストを読み込む
以前に同じ質問がされていないか確認する
その後値と確信度をけんさして正しい方かどうかを調べる
ユーザーから?を受けるとシステムが想定する答えの方を出す
Ruleを返すとシステムが現在扱っているルールを変え
Whyはシステムがわかっていることと発見症としていることを詳細に説明する
Helpはそれぞれのタームを説明する
Ask-vals
Prompt-ans -read-vals
実際にしつもんして返答を読み込む
Formatをよびだしてぷろんぷとを出力し
Readを呼び出して返答を取得する
Get-param
シンボルに関連づけられた構造体を取得する
Params-prompt
パラメータのためのプロンプトを取得
Param-reader
リーダー関数を取得する
Check-reply
Parse-replyを使用して、ユーザーの返答を標準形に変換する
各値が正しい型かどうか、確信度が正当かどうかを検査する
検査が合格するとデータベースが更新されて新しい確信度が反映される
パラメータは6つのスロットを持つこうぞうたいとして実装される
名前(シンボル)
コンテキスト
ユーザーに値を質問するためのプロンプト
ユーザーへの質問がルール適用の前か後かほ指定するブール値
型の制約
値を読むために適用される関数
パラメータはその名前の属性リストに属性paramで格納される

16.4 変数の代わりをするコンテキスト

EMYCINはprologのような論理変数の代わりにコンテキストを利用する
EMYCINの知識ベース設計者は、推論が行われる状況をコンテキストして定義できる
コンテキストはデータ型
プログラムに与えるコンテキストとは、との型のオブジェクトが推論対象となるのかを決定する
プログラムは各型から最もあたらしく作られたインスタンスを管理する
ルールからインスタンスを参照するには型の名前を使用する(EMYCINだとpatient,culture,organism)
Initial-dataパラメータは、各インスタンスが生成された時に、ユーザーに質問される
Goalパラメータはユーザーはわかっていない
後ろ向き連鎖のプロセスで決定される

16.5 後ろ向き連鎖再考

EMYCINはprologと同様に、目標が与えられるとその目標に適合するルールを適用する
ルールを適用するという意味は、ルールの前提部をもくひょうとみなし、適合するルールを再帰的にてきようすること
Prologのばあいは、適合したルールが成功すると、その目標が真になる
EMYCINの場合は、目標に適合するルールを全て調べる必要がある
EMYCINはパラメータ/インスタンスの対に関するすべての証拠を集め、すべての証拠が集まった後で目標を評価する
例
目標が(temp patient > 98.6)とする
患者の体温についてのけつろんをすべて評価する
その後体温と98.6を比較する
Prologは深さ優先(任意のルールが真であればそれが真)
EMYCINは幅優先探索を行う
.99の確信度を持ったルールは、より多くの証拠を集めると結果的に偽となるかもしれない
Find-out
3つの方法でパラメータのあたいを解明する
値がデータベースにすでにあるかどうか
ユーザーに質問する
ルールを使用する
Eval-condition
単一の条件を評価し確信度を返す
Reject-premise
conclude
ルールの前提が真の場合は結論をデータベースに格納する
条件はすべてパラメータインスタンスオペレータ値の型式を持つ
例
(Morphology organism is rod)
Parse-condition
この形式のリストを4つの値に変える
Get-context-data
各コンテキストが順番に扱われるように保証する

16.6 専門家との対話

Check-condition
Conditionかせ正しいかどうかをチェック

16.7 クライアントとの対話

知識の出力
問題に対する解
そのこたえがなぜ合理的なのかを示す
Repport-findings
インスタンスのあらゆるパラメータを出力
説明機構としては
現在のルールを見る
Rule
Print-ruleでこれを翻訳して出力する
ユーザーがwhyとするとルールのより詳細な説明が出る

16.8 医療診断エキスパートシステムMYCIN
16.9 確信度に代わるもの
16.10 歴史と参考資料
16.11 演習
16.12 解答

第17章 制約充足による線画のラベル付け

概要
線画
ラベル付けされた図形
ルール
可能性のある頂点とラベル付け

17.1 線画ラベル付け問題
17.2 制約と探索の組み合わせ
17.3 線画のラベル付け

立方体の4つの解釈
平面上のラベル付けされた立方体

17.4 線画のエラー検査
17.5 歴史と参考資料

Guzmanが最初に描画を解釈する問題を考えた

17.6 演習

第18章 探索とオセロゲーム
18.1 ゲームのルール
18.2 表現に関する選択
18.3 局面の評価
18.4 先読み探索：ミニマックス探索
18.5 賢い探索：アルファ・ベータ探索
18.6 ゲームの分析
18.7 競技版オセロ
18.8 一連のゲームによる戦略の評価
18.9 効率の良い探索
18.10 プレサイクル（Precycle）
18.11 キラー手
18.12 選手権試合のプログラム：Iago とBill

機動性
端の安定性
評価ファクタの結合

18.13 その他の技法

反復深化法
フォワードプルーニング
ノンスペキュレイティブフォワードプルーニング
アスピレイション探索
前もって考える(Think-Ahead)
ハッシュ法と定石
終盤
メタ推論
学習

18.14 歴史と参考資料
18.15 演習
18.16 解答

第19章 自然言語入門

概要
シンタックス(文法)
形式/準形式的手法
セマンティクス(意味)

19.1 句構造文法によるパース

文を構成する構造を再生する
文を認識するために、どのような順序で生成規則を適用するかを発見する

19.2 文法の拡張とあいまいさの認識
19.3 効率の良いパース
19.4 未知の単語
19.5 意味表現へ踏み込んだパース

文はアイデアを伝達するためのもので、文法を伝達するものではない

19.6 選好を使用するパース
19.7 文脈自由な句構造規則の問題点

ユニフィケーション文法

19.8 歴史と参考資料

chart parser
:部分的なパースをキャッシュし、より大きなパースを構築する時に再利用する
チャート
パースの部分列を格納するデータ構造
Top-down-parser

19.9 演習
19.10 解答

第20章 ユニフィケーション文法

概要
PrologはAlain Colmerauerによって フランス語の文法を記述するための形式論として考案された
ホーン節(Horn Clauses)とユニフィケーションの組み合わせによって、 自然言語の中に現れるような制約を表現する強力な言語を構成できる
文法を論理プログラミングの節の集合として扱う方法
節は、パースや生成のプロセスを明示的に参照することなく、 何が正当な文で、何が正当でないかを定義する
説を使用すると、極めて効率的なパーサーを定義できる

20.1 推論としてのパース

「文は名詞句とそれに続く動詞句によって構成できる」のprologによる表現
(<- (S ?s) (NP ?np) (VP ?vp) (concat ?np ?vp ?s))
?s :単語列
名詞句の単語列があり、 動詞句の単語列があり、 かつそれが連結されて?sが形成されるならば、 文である
変数は単語の列を表現
シンボルのリスト
(<- (S ?s) (concat ?np ?vp ?s) (NP ?np) (VP ?vp))
(<- (S ?s0 ?s2) (NP ?s0 ?s1) (VP ?s1 ?s2)) S0からb1までの単語列が名詞句で、 s1からs2までの単語列が動詞句ならば。 s0からs2までは文である example The boy ate the apple ?s0=(The boy ate the apple) ?s1=(ate the apple) ?s2=() アキュームレータ(accumulator) 入力パラメータと出力パラメータの組み合わせ 差分リスト(difference list) 20.2 確定節文法 EdinburghPrologは、 確定節文法(definite clause grammer:DCG)規則 と呼ばれるアサーションを認識する DCGは論理文法とも呼ばれる (Rule (S) --> (NP) (VP))
Memo:qiita dcg
DCG入門 - Qiita
#はじめにO-PrologにDCGを追加実装しました。このテストでわかったこと、調べたことなどを投稿します。#動機DCGとはdefinite clause grammarの略であり日本語では限…
qiita.com
A dog bites a postman
その構造は一定の文法規則に従っています
文 -> 名詞句、動詞句 名詞句　->冠詞、名詞 冠詞　->a 名詞　->dog 名詞　->postman 動詞句　->動詞、名詞句 動詞　->bites
上記の規則をほぼそのままの形で記述することが可能
s --> np,vp. np --> det,n. det -->[a]. n -->[dog]. n -->[postman]. vp --> v,np. v -->[bites].
文　sentence　s 名詞　noun　n 名詞句　noun　phrase　np 動詞　verb　v 限定詞　determiner　det 動詞句　verb　phrase
Phraseという述語で文が正しいかどうかを確認することができます
文法規則にかなった文を生成させることもできます
| ?- phrase(s,X). X = v_1; X = [a,dog,bites,a,dog]; X = [a,dog,bites,a,postman]; X = [a,postman,bites,a,dog]; X = [a,postman,bites,a,postman]; no

20.3 DCG形式の単純な文法
20.4 限定作用素（Quantifier)を持つDCG 文法
20.5 限定作用素の有効範囲に関するあいまいさの保持
20.6 長距離依存性
20.7 DCG 規則の拡張
20.8 歴史と参考資料
20.9 演習
20.10 解答

第21章 英語の文法
21.1 名詞句
21.2 修飾語
21.3 名詞修飾語
21.4 限定詞
21.5 動詞句
21.6 副詞
21.7 節
21.8 文
21.9 XP
21.10 単語
21.11 辞書（Lexicon)

動詞
助動詞
名詞
代名詞
固有名詞
形容詞
副詞
冠詞
基数詞と序数詞
前置詞

21.12 辞書の支援
21.13 その他のプリミティブ
21.14 例題
21.15 歴史と参考資料
21.16 演習

第5部 Lisp の続き

第22章 Scheme：Uncommon Lisp
22.1 Scheme インタープリタ
22.2 マクロによる構文の拡張
22.3 真正な末尾再帰インタープリタ
22.4 Throw、Catch、Call/cc
22.5 Call/ccをサポートするインタープリタ
22.6 歴史と参考資料
22.7 演習
22.8 解答

第23章 Lisp のコンパイル
23.1 真正な末尾再帰Lisp コンパイラ
23.2 Call/cc の導入
23.3 抽象マシン
23.4 のぞき穴最適化（Peephole Optimizer)
23.5 異なる語彙規約を持つ言語
23.6 歴史と参考資料
23.7 演習
23.8 解答

第24章 ANSI Common Lisp
24.1 パッケージ

7つの名前空間

24.2 状態とエラー処理

エラーの伝達
エラーの処理

24.3 プリティプリンティング
24.4 シリーズ（Series)
24.5 Loop マクロ

ループの解剖
繰り返し制御
終了条件テスト制御
値の蓄積
変数の初期化
条件付き実行
無条件実行
その他の機能

24.6 シーケンス関数（Sequence Function)

Once-only : マクロ論のレッスン
マクロ乱用の回避
MAP-INTO
:key キーワードを持つREDUCE

24.7 演習
24.8 解答

第25章 トラブルシューティング
25.1 何も起こらない
25.2 変数を変更してもその効果がない
25.3 関数を変更してもその効果がない
25.4 値がひとりでに変わる
25.5 組み込み関数が要素を発見できない
25.6 多値が欠落する
25.7 宣言が無視される
25.8 Lisp 処理系に問題がある？
25.9 必要な関数の見つけ方
25.10 Loop 構文
25.11 COND 構文
25.12 CASE 構文
25.13 LET 構文とLET* 構文
25.14 マクロに関する問題
25.15 Lisp のスタイルガイド

関数を定義すべき時
変数を定義すべき時
レキシカル変数を定義すべき時
名前の選択方法
パラメータの順番に関する決定

25.16 ファイル、パッケージ、システムの処理
25.17 可搬性の問題
25.18 演習
25.19 解答

付録 この本に載っているコードを取得する方法
A.1 FTP：ファイル転送プロトコル
A.2 利用可能なソフトウェア

参考文献
索引
訳者あとがき