計算機とその周辺: What I Talk About When I Talk About Computers: 7月 2009

2009年7月31日金曜日

【JT】1 はじめてのJava


* 1 はじめてのJava
** Javaテクノロジ現象
 - Javaはテクノロジであるとともにプラットフォーム
   である。
** はじめてのJavaプログラミング
 - NetBeans IDEの紹介。NetBeans IDEは使わないので
   スキップ。
** はじめの一歩 (Microsoft Windows)
 - スキップ。
** はじめの一歩 (Solaris OS, Linux)
 - バージョンチェック。問題なさげ。
the-java-tutorial $ java -version
java version "1.6.0_10"
Java(TM) SE Runtime Environment (build 1.6.0_10-b33)
Java HotSpot(TM) 64-Bit Server VM (build 11.0-b15, mixed mode)
the-java-tutorial $
 - HelloWorldApp、問題なし。

** Hello Worldプログラムを解剖する
 - 特になし。

** エラーの説明
 - 特になし。

** 設問と演習
*** 設問
 - 1. バイトコード.
 - 2. c.
 - 3. HelloWorldApp.classが存在するかどうか。
*** 演習
 - 1.
---

class HolaMundoApp {
    public static void main(String[] args) {
        System.out.println("Hola Mundo!");
    }
}

---

 - 2. "が漏れている。

既視感が激しいと思ったらProcessingがJavaだった。この前やったばかり。
こつこつ。

Javaを学ぶ

意図あって、Javaをちょこっと学んでみようと思う。

本は、

Javaチュートリアル

にする。この本がものすごいよさそう、というわけではないのだが（悪そうというわけでもない）、公式チュートリアルがあるなら、まあそれをやるべし、という選定。

あまり根を詰めずにゆるくやりたい。

2009年7月30日木曜日

本日の基礎トレ

微積分　：Calculus
(15/596)
※問題のうち、*と**はやらない。

線形代数：線型代数
(30/333)

位相空間：はじめよう位相空間
(10/182)

計算練習：コンピュータの数学
(4問)
※これはページ数による進捗管理が適さないことがわかった。問題にどんどん取り組んで、それに解答できるように本文を理解していく、という問題駆動がよいようだから。なので、問題数で進捗管理することにする。進捗管理表を時間があるときに作成する。

凡例　赤：やらなかった。黄：やったけど有意に進まず。青：やって進んだ。

のろのろ。

2009年7月29日水曜日

本日の基礎トレ

微積分　：Calculus
(15/596)
※問題のうち、*と**はやらない。

線形代数：線型代数
(28/333)

位相空間：はじめよう位相空間
(9/182)

計算練習：コンピュータの数学
(2問)
※これはページ数による進捗管理が適さないことがわかった。問題にどんどん取り組んで、それに解答できるように本文を理解していく、という問題駆動がよいようだから。なので、問題数で進捗管理することにする。進捗管理表を時間があるときに作成する。

凡例　赤：やらなかった。黄：やったけど有意に進まず。青：やって進んだ。

のろのろ。

2009年7月28日火曜日

2009年7月27日月曜日

本日の基礎トレ

微積分　：Calculus (15/596)
※問題のうち、*と**はやらない。
線形代数：線型代数 (27/333)
位相空間：はじめよう位相空間 (9/182)
計算練習：コンピュータの数学 (29/461)
※これはページ数による進捗管理が適さないことがわかった。問題にどんどん取り組んで、それに解答できるように本文を理解していく、という問題駆動がよいようだから。なので、問題数で進捗管理することにする。進捗管理表を時間があるときに作成する。

凡例　赤：やらなかった。黄：やったけど有意に進まず。青：やって進んだ。

のろのろ。

【基礎トレ】基礎トレもエントリに

基礎トレがどうしてもなおざりになってしまう。
そこで、基礎トレもエントリとして上げることにして発奮材料にしよう。

微積分　：Calculus (14/596)
線形代数：線型代数 (26/333)
位相空間：はじめよう位相空間 (9/182)
計算練習：コンピュータの数学 (29/461)

括弧の中は、ページ数での進捗状況。

この4つをやることはとても重要。知識として身に付けるのが目標ではなく、体で覚えることが目標。ゆっくりやる。これらが身体化できれば、いろいろ自由自在になれるはず。これらを終えれば、現在のレベルを、高校三年生をすっとばして大学一年生としてもよいはずだ！

のろのろ。

【雑】ブログのラベル(タグ)整理

ラベル(タグ)のメンテをちょこちょこやってます。
モチベーションは次のとおり。

話題がクロスオーバーしてきたので、タグを整備すると自分にとっても便利。
一過性の興味などにより、エントリが1つしかないタグがある。これは他のにマージしていく。タグ数を減らした方が見易いから。
同義語なタグについて考える。そのまま残すことに語彙として価値があるか、それともマージするか。

こつこつ。

2009年7月26日日曜日

2009年7月25日土曜日

2009年7月24日金曜日

2009年7月23日木曜日

2009年7月22日水曜日

2009年7月21日火曜日

2009年7月20日月曜日

2009年7月19日日曜日

データベース実践講義(Database in depth)を読む

Prologと論理のことが多少わかってきたところで、じゃあRDBって何なのさ、ということを探ってみたい。ぼやぼやーとした感じでよいので。

そこで、次の本を読むことにした。

C.J.Dateのデータベース実践講義

根を詰めると倒れるので、ぼやぼやーといきたい。

【検証論】3 形式的理論

3章が終わった。
大変勉強になった。この章は今までの形ではブログには載せられない。理由をいくつか。

取ったメモは、本文のほぼ丸写し。自分の言葉では無い。これは載せられない。
途中から紙と鉛筆になった。論理記号を端末でうまく入力できない。

そこで、トピックをいくつか。

前のエントリで書いたように、形式理論または一階述語論理にたいする大変よい解説である。
ただし最後の方は著者の息切れ感があり、多少表現が雑なところや、誤字・脱字があるので要注意。
項の代入性のところがモヤモヤしている。というのはそもそも代入の定義のところが曖昧に記述されているからだ。

プログラム検証論は私にとってそれなりにごついので時間がかかりそうだ。
そこで、刻んでいくことにする。その代わり並行して別の本にも取り組もうと思う。

こつこつ。

2009年7月17日金曜日

端末で論理記号がずれる

SKKの▽とかもそうなので、悩みは深いのですが、
端末で論理記号がずれる、というか、論理記号の後続が
めりこんじゃうんだよね。見ずらくて、萎える。

これ、端末の問題なのかフォントの問題なのかその両方
の組み合わせなのか、なんだけど、gtkアプリはずれない。

困ったなぁ。

2009年7月16日木曜日

【検証論】3 形式的理論

プログラム検証論、すごい。。。
この3章形式的理論ほど、慈愛に満ちて、簡にして要を得た
形式的理論の導入をみたことがない。

昔の自分はそれがわからなかった。今はわかる。

2009年7月15日水曜日

2009年7月14日火曜日

プログラム検証論を読む

AIMAをかじったところ、論理について少し見通しがでてきた。

そこでこれを機会にプログラム検証論の基本も見ておこうと思う。

本はこれ。

プログラム検証論

仕事の中でも、書籍の中でもユニットテストとか検証とかでてくるのですが、一度数学的見地がどうなっているのかみてみたいなぁと思ってました。

というわけで、こつこつ、再開します。

【AIMAメモ】Agentアプローチ <=> Domain指向の間違い

------
Agent in Environment.

なんですがこれは、

Domain in World.

と同型であり、ここでDomain指向との対応がとれる、と。
------

違う！これは同型ではない。同型なのは、

------
an Agent in an Environment in the World
an IT system in a Domain in the World
------

だ。

こんなんじゃ、駄目だ。。。

2009年7月13日月曜日

【AIMAメモ】PrologとLisp

論理プログラミングをやろうと思ったら、Prologはひとつの選択肢だろう。

Prologの処理系を使うというのもあるが、別の言語をメインで使っていて、一部論理プログラミングを使いたいとする。

そうするとそのホスト言語でProlog的なものを実装するわけだが、そのとき、

実装が楽であり、
実装したものを使う際にホスト言語と似ていて使いやすい

ということが大事だろう。すると例えばCとCommon LispをくらべるとCommon Lispの方が適していると思う。

ではRubyだとどうだろう?
結構いけそうな気がする。しかし、記号(Symbol)の取扱いがCommon Lispの方が統一的かつ簡易なので、Common Lispの方が楽だろう。(Rubyはあまりくわしくないので間違いかも)

PrologとLispのつながりというのはこの程度じゃないかなぁ。

もしかしたら、もっとあるのかもしれないが、今のイメージはこんな感じ。

とりあえず、これにて、今回の「AIMAかじり」は終了しよう。
AIMAは別の機会にがっつりやりたい。

次は、今回習得したPrologとAIMAの知識を利用して、PAIPのProlog実装とその利用をちゃんと理解するステップに入ろう。

【AIMAメモ】Algorithm = Logic + Control の周辺

Algorithm = Logic + Control.

なわけですが、一方で、より有名なので、

Programs = Data structures + Algorithms.

があるわけです。

ちなみにAIMAがエージェントアプローチと呼ばれるのは、AIMAで取扱うものは、機械だろうが生物だろうが、ソフトウエアだろうがハードウエアだろうが、Common Lispが採用言語だろうがJavaがそうだろうが、エージェントという統一的な観点で整理しているからです。

そこで、Logicが知識表現である、というのが私にとっては大きな気づきでした。AIMAの中では他の知識表現として統計的なものを含めてLogic以外のものも取り上げられています。ベイズとか隠れマルコフとか。それらがどちらかというと現代的なAIのお話になっている。

さて、日頃プログラムを書くときにデータというのはよく使うわけですが、これもエージェント的な観点でみると何かしらの知識表現とも見做せてきます。そうすると、

Algorithm = Logic + Control.

ではなく、

Algorithm = Knowledge Base + Control.

の方がいいように思えてきます。Knowledge Baseの構築方法の一つとして知識表現にLogicを使うこともあるよ、ということで。Knowledge Baseを拡大解釈すれば、あながち間違いではないかと。

するとデータベースってなんじゃないな、ということが気になるわけです。

これはこれで、Prologと、SQL(というか関係代数)との関係含めて先々確認しなければいけないのですが、ある種のデータベースはKnowledge Baseとみなすのがよいと思うし、ある種のデータベースは、外界としてしまってデータベースとのやりとりは、エージェントのセンサを介して情報を得るという、外部入出力とみなすのがよいように思います。直感ですが。

まとめると、Environmentの中で、

Agent = Sensor + Actuator + Intelligence.

なんですが、Intelligence というのはいろいろありえてSoftwareの場合もあり、
Sensor,Actuator,Intelligenceの全部がSoftwareの場合がよくあるプログラミングでやっていることで、
だからそれをProgramと呼んで、
その場合は全部Softwareなので、どこでインターフェイスを切りますかということが整理の入口になりそれがアーキテクチャであり、
同じ対象領域でも何がSensorで何がActuatorでとかは違うわけで、
SensorとActuatorは外部インターフェイスというか入出力と考える部分にあたり、
するとIntelligenceの部分が入出力以外ということになり、いわゆるProgramの本体部分なので、

Intelligence = Data structures + Algorithm

なんですが、Data structuresを知識表現とみれば、

Algorithm = Knowledge Base + Control

のKBに吸収されてしまうので、

Intelligence = Knowledge Base + Control

となるなか、

データベースはEnvironmentに属すのかIntelligenceに属するのかという判断があるので、
その判断によって、EnvironmentにいったりKBにいったりするという。

さて、大本にもどると、

Agent in Environment.

なんですがこれは、

Domain in World.

と同型であり、ここでDomain指向との対応がとれる、と。
そちらの言葉で言えば、DomainとWorldの境界線がSystem Boundaryにてシステム思考が出てくる、と。

また、Common Lispのhomoiconicというのは、

Algorithm = Knowledge Base + Control.

ここのKBとControlの境目を柔軟にして探検的にプログラミングできますよ、ということで、それだけじゃなくて、リストまたはS式というのは知識表現言語として柔軟ですよ、というつながり。

つながった?

【AIMAメモ】FOPLの確定節(definite clauses)

まず、訳語の揺れについて。
第七章の命題論理では、definite clausesを確定節としているが、一階述語論理の第九章では限定詞節としている。よくわかんなくなっちゃったので、原書を確認した。ま、このくらいはしょうがないのかな。

で、一階述語論理(FOPL:FOPLはFOLとほぼ同義)にもホーン節的なものは存在しているのだ(AIMAではFOPLの方はホーン節と呼ばない)。
ここではホーン節と呼んじゃおう。

ホーン節は正リテラルをゼロ個または一つ含む。一つ含む方をdefinite clausesと呼ぶ。またFOPLの場合の違いは、全称限量子が略記されていると見做す。これがPrologの文だ。

hoge(X) :- piyo(X),poyo(X).

というわけで、PrologのKBはホーン節の選言文となる。すなわちFOPLよりは記述力が弱い。そのかわりに、推論のスピードを確保している。ホーン節も記述力はナカナカなので、落としどころ、という感じか。

詳細はまだつかめていないが、FOPL(FOL)とPrologの関係はイメージできるようになった。

【AIMAメモ】融合規則からホーン節へ

で、融合規則(resolution rule)なる推論規則が注目される。これは、命題論理においては、この推論規則たったひとつで完全である。すなわち、KBから伴意される任意の文を導出できる。モーダスポーネンスもなんもかんもいらないのだ。

ここで、命題論理における任意の文がk-CNFの形で書けることが重要な役割をもっていることになる。するとKBも、任意の文αもk-CNFだから、融合法を適用できる。

この文脈でホーン節、登場。

融合法(= 融合規則+探索)は強力だが、そのままで使うのではなく、文に含まれる節の形を多少制限するといろいろメリットがある。それがホーン節。

ホーン節は正リテラルを高々ひとつ含む選言節である。

(¬A∨¬B∨C)はホーン節だが、(¬A∨B∨C)はホーン節ではない。ホーン節は含意に変形できる。例えば、

(¬A∨¬B∨C) は (A∧B)⇒C、

とか。ここで(A∧B)の部分を体部(body)と呼び、Cの部分を頭部(head)と呼ぶ。

ここでPrologと繼がった！　Prologの記法だと、

C := A,B.

であり、左右が逆だが意味は同じ。

head := body.

なので用語も同じ。

ただしここでの話は命題論理なので、FOLとの関係はどうなっているのというのはわからない。まだ関連が見えただけ。

【AIMAメモ】推論規則(推論パターン)

命題論理のお話。

統語論を決める。
意味論にて、モデルの考え方を決める。ここでは、命題記号に直接真偽を割り当てるのがモデルとし、結合子の意味論は真理値表にて定義することにし、定義する。

すると、伴意の考え、および論理的同値の考えから、命題論理の複合文についての論理的同値関係がいろいろでてくる。ドモルガンの法則と呼ばれるものだとか、なんやかんや。

ここまでは命題論理の定義(= 統語論 + 意味論)からストレートな感じである。

で、推論規則(推論パターン)。

ここ、AIMAではヒューリスティックな流れだ。モーダスポーネンスとかAnd除去とかをどうやって導出するのか、もしくは何を推論規則と認定するかは曖昧である。例えば、And除去は論理的同値だが、モーダスポーネンスは違う。

ただ、何を推論規則とするかには何か法則性があるんだろうな、と感じる。

推論規則は証明に使えてナンボだと思うので、おそらくその観点での判断になるのかな。

また、推論規則を定めるまでは統語論と意味論が混ざっているが、推論規則を定めると、それは文の変形(書換え)のみになり、統語論だけで処理が進む。

伴意による推論アルゴリズムはモデルチェックであり、意味論ごりごりなわけだが、推論規則による証明という推論アルゴリズムは、統語論ごりごりであるという対比があるように思う。

【AIMAメモ】論理(logic)の誤解の誤解

http://aka-cs-blog.blogspot.com/2009/07/aimalogic.html
で書いた、
---
これでは計算機科学的には間違っていて、

知識(論理による表現) <-(推論規則)- アプリケーション(探索実装)

なのだ。
---
というのはちょっとどうかと思えてきました。融合法(resolution)のみを考えているわけではないので。

---
知識(論理による表現) <-(推論アルゴリズム)- アプリケーション(実装)
---

の方がいいかも。

これも気づき。

2009年7月12日日曜日

【AIMAメモ】数理論理学の三階層 (または論理という言葉の曖昧さについて)

論理(logic)という言葉が、一般的にも、論理学においてもかなり曖昧に運用されていることが理解できてきた。

これから書くことはAIMAに書かれていることではなく、AIMAに書かれていることを起点にして自分なりに考えたことだ。

まず数理論理学とはどんなものなのか多少探ってみよう。

論理学と数理論理学との関係はどうなのだろう。
考えてみると、そしていくつか調べてみると、大体次のようなイメージでよいのではないか。
論理学の方が広い概念である。
数理論理学は論理学の一分野である。
数理論理学では、記号を用いる。別名、記号論理学とも呼ばれる。
記号は、音、物理形状、文字などいろいろな形を取りえるが、記号論理学で扱うのは文字と考えてよいだろう。
これは、計算理論における情報の定義に関わるが、あらゆる情報は文字で表現できる、もしくは文字で表現できることが情報の定義である、ということを背景としている。

さて、次にもともと論理学とは何だったのだろう。

もともとでいうと自然言語と知性に関する知的探求である。
自然言語をつかってわれわれは情報を伝達したり、考えたり、意見を戦わせたりするのだが、どうやらそこには何か法則性というか何か構造があるようだ。
自然言語の文について、その何か構造がありそうに思える部分に着目しよう。逆に言うと、それ以外の部分を除去して考えていこう。
その何か構造と思えるものを論理(logic)と呼ぼう。
論理と名前つけたものは、どうやら人間における事実の言明や仮定や推論などの知的活動や知的能力の重要な部分ではあるまいか。
言葉という「外部表現」から、人間の思考という「内部表現+推論」を探っていこう。

というようなものが論理学の原始的モチベーションなのではないか。もちろん学問分野の定義は曖昧なので、進めば進む程、定義や対象領域も変化していくのですが。

で、数理論理学というのは、次のとおり。

別に自然言語に限らなくてもいいじゃん。
ひとつには自然言語って難しいよ。論理としておぼろげながら捉えられた構造の研究に集中したい。
自然言語じゃなくて、論理研究用のミニ言語みたいなのをつくっちゃうのがいいじゃん。(形式言語)
その言語は文法(=統語論)もきっちり決めちゃおう。

ここまでは前置きです。で、数理論理学というのは、ある意味、どうやら概念として次の三階層をとっているように思えてきたというお話です。

1. 数理論理学自体の枠組み
2の数理論理フレームワークを俯瞰してみたときに共通していると考えられる概念。逆にいうと2のフレームワークを新しく考えるときに満たさなければいけない条件や、使わないければいけない語彙。
2. 数理論理フレームワーク
3の具体的な論理を作る際のフレームワーク。いろいろなものがあり、問題領域に対してどれを使って論理をつくろうか選択したりする。
3. 具体的な問題解決のための数理論理
例えば、算数(小学校で習う形態は数理論理フレームワークを使っていないが)であったりWumpus Worldのエージェントを構成する論理(命題論理という数理論理フレームワークを使用)だったり。

そして、数理論理学の諸概念は、この3つの階層に分かれている。代表的なものを列記しよう。

1. 数理論理学自体の枠組み
数理論理学で扱う「論理」は必ずこれらの概念下で構築されている。
- 数理論理学は形式言語を対象とする。
- 形式言語では統語論と意味論が定義されている。
- 統語論はconstantsとvariablesを含む。
- モデル：ある文について、それが含むvariablesがそれぞれconstantsに特定化されたものをモデル(別名、可能世界)と呼ぶ。
- 真理値：文は、個々のモデルについて真または偽となる値をもつ。その値を真理値と呼ぶ(ファジ論理はここでは除外する)。文αがモデルmで真となることを、mはαを充足する、とも言う。
- 伴意：2つの文αとβについて、αの真理値が真であるあらゆるモデルにおいてβの真理値が真となるとき、文αから文βが伴意される、という。α |= β と書く。
- 知識ベース：文の集まりを知識ベースと呼ぶ。KBと略記する。
- 推論：あるKBと伴意関係にある文αは存在するかもしれないし存在しないかもしれない。そんなαを推論アルゴリズムiがKBをもとに見付けることができる場合、「αはiによってKBから導出された」と言い、KB |-i αと書く。
- 推論規則：個々の数理論理フレームワークにおいて、その統語論と意味論とから発生する文から文への変換ルールを推論規則という。
- 証明：ある導出をするための推論規則の適用系列を証明と呼ぶ。
- 融合法：完全な探索アルゴリズムと単一の推論規則とによって完全な推論アルゴリズムを生み出す方法。
- 健全性：ある推論アルゴリズムが、それが導き出す文はKBと必ず伴意関係があることが保証されている場合、その推論アルゴリズムは健全である、という。また、真理値を保存する、という言い方もある。
- 完全性：ある推論アルゴリズムが、KBと伴意関係があるαを全て導出可能なことが保証されている場合、その推論アルゴリズムは完全である、と言う。
- 論理的同値性：二つの文αとβについて、各々が真となるモデルの集合が一致するとき、αとβは論理的に同値であるという。α <=> βと書く。(伴意を用いた別の定義もある点に注意)
- 妥当性：ある文がすべてのモデルに対して真となるとき、その文は妥当であると言う。妥当な文のことをトートロジと呼ぶ。
- 充足可能性：文αが真となるモデルmが存在するとき、文αは充足可能であると言う。
- 単調性：非形式的に言うと、センサにあやまりがないことが保証されている場合で新しい知識たる文βが得られたとしても、KB |= αならばKB^β |= αである。すなわち、βを知る前に導出されていた文αがβの出現によってくつがえされることはない、ということ。
などなど。
2. 数理論理フレームワーク
1の各種概念を用いているが具体的な問題領域には適用してはいないフレームワーク。例えば、命題論理、一階述語論理、高階述語論理などがこれにあたる。基本的には、それぞれの「論理」にて統語論や意味論やそれらを表現する語彙は異なる。もちろんそれぞれ発展していったものなので、その関連性から同じような用語が現れることもあるが、それは上の1の意味で共通な用語ではないことが要注意である。以下は命題論理の場合の語彙を示す。
- 統語論の語彙：原子文、命題記号、複合文、論理結合子、リテラル、選言、連言、含意文、前提、結論、双条件文、ホーン節
- 意味論の語彙：真理値表
- 推論の語彙：モーダスポーネンス(三段論法)、And除去、演繹定理、背理法、連言標準形、前向き推論、後ろ向き推論、Davis-Patnumアルゴリズム
などなど。
もちろん1の概念や性質や観点は、どの数理論理フレームワークでも有効であり、それに基づいて個々の数理論理フレームワークも研究されるし、相互の特性の比較も為される。
3. 具体的な問題解決のための数理論理
これは例えばwumbus worldのエージェントを「論理」によって判断させる場合にあたる。
- どの数理論理フレームワークを採用するかをきめる。
- その数理論理フレームワークにおいて、環境や知識をどのように表現するかをきめる。
- あとは数理論理フレームワークにて研究済みであるツールを用いて実行する。すなわちKBを構築し、推論し、行動し、あたらしい情報を知覚し、KBにそれを投入し、また推論し、と繰り返す。
wumbus world以外の例としては、例えば、自然言語で考えられ構築されてきた数学の集合論の知識を一階述語論理という数理論理フレームワークを用いて表現し推論するというものがある。

この3つの階層に概念がわかれており、数理論理学で何かを語るときに、この階層を縦横無尽に行き来するということを理解していなかったから、今まで数理論理学がもやもやしていたのだ。

また「論理」という言葉の定義がかなり曖昧であり、文脈によって特定される機会がかなり多いこともその原因だったと思う。

「論理」が何を指しているかを理解するには、文脈がどうであるかを理解する必要があり、個別の文章の文脈を理解するには、数理論理学が概念や対象の階層構造を成していることを理解する必要があったということ。

これも大きな気づきだ。

2009年7月11日土曜日

【AIMAメモ】論理言語の意味論(Semantics)

意味論という言葉も厄介じゃないかなぁ。

まず、意味論として国語辞典、Semanticsとして英和辞書、英英辞書をみてももやもやしてわからない。これは例えば数学(Math)を国語辞典や英英辞典で見てもそれを理解できないのと同じことなのかな、と理解しておけばいいのだろうか。

でも、言葉としてのスケールが違うような?とも思う。

* この文のセマンティクスはどう決まっていますか?

というのが意味がありそうだと思えても、

* この文の数学はどう決まっていますか?

というのは無意味な質問に思える。数学と比してセマンティクスという言葉がスケールが小さいものにも適用できる言葉であるならば、辞書や辞典にもっと分かりやすい説明があってよいと思うのだが。。。

と考えていた。で、AIMAを読むとわかるのかわからないのか。

これが、わかるのだ。

x + y = 4 という文でAIMAは論理言語の意味論を説明している。それを私なりに咀嚼して書いてみよう。

まず、x + y = 4という文をみて我々はこの文を頭の中に入れることができる。ただしそれは+ x y 4 =であっても同じである。それらに比してx + y = 4というのは特別である。何故特別かというとそれはこの文に対する統語論を我々は学校で「算数」という名のもとに教えてもらっているからである。逆に言うと、+ x y 4 =は、「算数」という統語論では規則違反である。
「算数」という統語論の中には、+ = 1 2 3 4などのconstantsとx yなどのvariablesが定義されており、文の構成素材として使用することができることも教えてもらっている。
xとyはvariablesなので、このx + y = 4という文に対してモデル(別名で可能世界)を考えることができる。例えば、「xが1、yが2であるようなモデル(世界)」「xが2、yが2であるようなモデル(世界)」などなど。これは「算数」ではconstansが無限にあることによって、モデルの数も無限になる。ここで大事なのは、ここでモデル云々の考え方は、「算数」の中で定義されているのではなく、論理言語一般の考え方ということだ。別の言葉でいうと、「算数」というものを論理言語の考え方で捉えて語っているのがこの文章であるということ。
さて、我々は x + y = 4という文において、「xが1、yが2であるモデル」ではこれが偽であり、「xが2、yが2であるモデル」ではこれが真であると言われると、それは合点がいくような気持になる。それはひとつの観点では、+ = 1 2 3 4などのconstansの意味を知っているからそれと照し合わせてそういう気持になるとも言えるが、そうすると意味って何よ?ということになってここが曖昧である。
そこを考えると我々がここで「意味」と認識しているものは、結局、
x + y = 4 という文は、
「xが1、yが1であるモデル」にて偽、
「xが1、yが2であるモデル」にて偽、
「xが1、yが3であるモデル」にて真、
「xが2、yが1であるモデル」にて偽、
「xが2、yが2であるモデル」にて真、
...
ということ自体が展開された形での「意味」そのものではないか、ということになる。
すなわち、我々が「算数」という名称で教わったものは、「算数」としての文の書き方と、「算数」としてそれら文がどのようなモデルにて真偽値を取るかという対応であるということになる。この前者が「算数」の統語論(Syntax)であり、「後者」が意味論(Semantics)である。

スタートレックは異文化に対するイマジネーションに満ちているのでスタートレックのアナロジーを再度やってみよう。

Mr.スポック曰く、バルカン星では子供のころに「バルカニーナ」を教わる。
バルカニーナの統語論は、constansとして+ = 1 2 3 4であり、variablesとしてxとyがある。もちろん文の構造を決める他の文法規則もある。それら規則によると、x + y = 4は文とみなせるが、+ x y 4 = は違反であり文とみなせない。
バルカン星人は、 x + y = 4という文において、「xが2、yが2であるモデル」ではこれが偽であり、「xが1、yが1であるモデル」ではこれが真であると言われると、それは合点がいくような気持になる。それはひとつの観点では、+ = 1 2 3 4などのconstansの意味を知っているからそれと照し合わせてそういう気持になるとも言えるが、そうすると意味って何よ?ということになってここが曖昧である。
そこを考えるとバルカン星人がここで「意味」と認識しているものは、結局、
x + y = 4 という文は、
「xが1、yが1であるモデル」にて真、
「xが1、yが2であるモデル」にて偽、
「xが1、yが3であるモデル」にて偽、
「xが2、yが1であるモデル」にて真、
「xが2、yが2であるモデル」にて偽、
...
ということ自体が展開された形での「意味」そのものではないか、ということになる。
すなわち、バルカン星人が「バルカニーナ」という名称で教わったものは、「バルカニーナ」としての文の書き方と、「バルカニーナ」としてそれら文がどのようなモデルにて真偽値を取るかという対応であるということになる。この前者が「バルカニーナ」の統語論(Syntax)であり、「後者」が意味論(Semantics)である。

これで明確になったと思うけど駄目おしを。

Dr.マッコイ：「x + y = 4」という暗号通信をクリンゴンの偵察挺が送信していたらしい。これはどういう意味だろう。

Mr.スポック：それは意味論により異なりますね。地球人はそれを算数の意味論に従っていると盲目的に解釈しがちですが、それは理性的ではありません。

Dr.マッコイ：「x + y = 4」に理性もへったくれもあるか！

Mr.スポック：感情的にならないでください。実際にバルカン星人にとっては、その文が適格である統語論でもっとも最初に習うのは「バルカニーナ」であり、「バルカニーナ」の意味論は地球人の「算数」の意味論とは違います。さらにバルカン星人の知識の中にある別の12の統語論においても「x + y = 4」を適格と見做すことができますがね。統語論と意味論をごちゃごちゃにして初等教育を行う地球人とは、バルカン星人は大きく異なるのです。バルカン星人は常に統語論と意味論を分けて学習します。

Dr.マッコイ：君だって地球人の血が半分流れてるじゃないか！

閑話休題。

x + y = 4 の意味論を算数とする

という表現がAIMAでもあるのですが、これはちょっとリスキーなんですね。私は今までこれがわからなかった。より混乱が少いのは、

x + y = 4 の意味論を、算数という名称で君や私が習った意味論にする。(統語論が算数と一致しているということは前提としている)

という表現である。

ああ、すっきりした。

【AIMAメモ】論理と物理

AIMAを読んでいて合点がいく部分が多いのは、物理との接続に言及しているところが大きいと思う。

たとえば、知識ベース(Knowledge Base,KB)のことを、物理的な構造にすぎないとズバリ言っている。ここでの物理的な構造は、電気的であったり有機化学的であったりするわけですが、この視座に立つとき、人間の知能というものと、計算機による知能(人工知能)というものを統一的に考えることができるようになる。これは気づき。

すなわち、(+ x 2)のようなものはこれが計算機のメモリ(電気的信号の状態)なのか、私の頭の中のこれを記憶している何らかの状態(電気的信号の状態 or 有機化学的な結合状態)なのか、いずれにしても物理的な状態を指している。

統語論(Syntax)が何かということも、それも物理的な構造としての文の形を規程するものとしている。

以下、以上の文脈にて。

KBは文の集まりである。文の統語論を命題論理としたとき、KB全体を単一の文(別の言い方をすると言明)とみなすことができる。これは、KBに含まれる文(論理)がS1,...,Snだったとすると、KB = S1^...^Sn (ここで^は連言)にすぎない、ということだ。言われてみれば当然なのだが、言われるとはっとする。

そしてそもそもこの単一の言明であるKBがそもそも現実世界において真であるかということをどうやって知るかということをグラウンディング(grounding)と言う。グラウンディングは哲学的論争になっているが、ひとつの立場は、センサという機器にて解釈する、ということだ。そもそも文の生成(すなわちKBの構築)にもセンサによる知覚が用いられる。そのことにより現実世界とKBはつながりをもちつづける。

実は、このような物理との接続がない状態で今まで人工知能の書籍を読んできたのですが(例えばPAIP)、どうも、どこがどういう観点で「知能」なのかということの座りがわるかった。例えば、macsymaが人の代わりに代数演算をするということも、確かに計算機という機械が人がやっていたことをやってくれるという観点では何かしらの人の知能的な側面を実現しているということでは人工知能だよねと自分を納得させていたのだが、腑に落ちないところもあった。

そういう意味では、このエントリは大きな気づき。

# センサと知るということになると量子論との接続はどうなのよ、と思ってしまうが、今は考えない。
# 日常的なオーダーの中での知覚と知能と行動については、まずはそのオーダーで良好な物理法則をベースに考えてもよいとは思う。
# それによって人間のKBも構築されてきたのだと思うから。

【AIMAメモ】論理のモデルと設計のモデル

これは、気づきではなくて、改めて確認したこと。

論理におけるモデルと設計におけるモデルとは随分違う。

文章にしてみて、より理解を堅牢にしてみたい。

まず、論理におけるモデルは、より具体的には、論理言語のモデルのことを指す。
次に、設計におけるモデルは、対象領域の記述のためのモデルのことを指す。

順番は逆になるが、それぞれさらに詳しくいうと。

対象領域の記述のためのモデルとは、例えばMVCにおけるモデルであり、それはドメインを分析した結果、そのドメインにおいてエクステントが比較的に長い概念や語彙のことである。

論理言語におけるモデルとは、今、ある論理言語にて書かれた文αがあるとして、そのαの真偽を考えるにあたって想像しうる(存在しうる)可能世界(possible world)のことである。

ということ。

ここでまず違うのが、

設計におけるモデルは現実に対する「何らかの抽象」と位置付けられているのに対して、
論理におけるモデルは論理文αに対する「何らかの(想像しうる)具象」と位置付けられている、

ということである。ただし、これら2つのモデルという言葉の用法がunification可能かどうか考えてみると、これはできそうだ。

設計におけるモデルというのは抽象ではあるが、それはいろいろ考えうる抽象のうちの一つであり、その中から設計の選択として実装に使用するモデルを選択しているということである。これって可能世界としてありうるものの一つという感覚と似てなくもない。

こう書いてみると、抽象と具象というのはN:Mな関係であることに気づいた。ある抽象を決めれば、それを満たす具象がいろいろあると考えられる(具象群)。OOにおけるクラスとオブジェクトの関係。具象群からある抽象をつくるとは、その具象群の抽象の形というのはいろいろありえるわけで(抽象群)、その中から選択をする行為とも考えられる。まあ、実際に設計をするということは、この双方をいったりきたりして、フィードバックをかけてチェックしつつうまい抽象化というのを探索している行為と考えられるのですが。

ちなみにSPINなどのModel checkerのモデルとは、論理の方のモデルのことですね。

【AIMAメモ】論理(logic)の誤解

誤解していた。これは大きな気づきだ。

論理(logic)というのを、日常の「あの人、論理的だよねー」とかそういう言い回しが三段論法的な話し方を指したりすることに引っ張られて、何か手法であったり知識を使うために運用するものだと今まで暗黙に思っていた。違うのだ。論理は知識の表現そのものなのだ。それを運用するのは推論規則なのだ。

Mr.スポック的にいうと、

知識 <-(論理的思考法)- Mr.スポック

なんだけど、これでは計算機科学的には間違っていて、

知識(論理による表現) <-(推論規則)- アプリケーション(探索実装)

なのだ。だから、

logic <- control

によって計算機から具体的な結果が得られ、これが

Algorithm = logic + control.

そしてこのlogicの部分が宣言的プログラミング、
このcontrolの部分が手続き的プログラミング。

2009年7月10日金曜日

【AIMAメモ】知識工学とDSL

そうか、知識工学って今でいうDSLとかなりクロスオーバーしているものなんだ！

DSL : システム分析 -> ドメイン分析 -> ドメインモデル -> 手続き/永続化実装 -> 基本的なデータの投入 -> DSLとして利用
知識工学 : システム分析 -> ドメイン分析 -> 語彙と知識表現の決定 -> 知識を表現 -> 推論エンジンを介して利用

前半戦に類似がある。

【AIMAメモ】ブログエントリの考え方

さて、途中から読んでみると、頭から読むのとやり方が違うのがすぐにわかった。ゲリラ的というかなんというか。のっけから自分なりの理解を組み立てるしかないので、読み方も縦横無尽になる。わかっているところから切り崩していく感じ。これはこれでおもしろい。もしかしたら、この方がよい読書方法なのかもしれないなぁ。でも著者と膝を突き合わせる感じでじっくり最初から読んでいくのが好きなんだけどね。

さて、そんなこんなで、今回のAIMAアタックにおいては、気づきがあったところなどを散発的にメモとしてエントリに上げようと思う。なので小さなエントリがちょこちょこ出ると思う。

AIMAをかじる

せっかく得たPrologの理解（イロハのイだが）もたぶんすぐに消えてしまう。今はまだ、日々ごりごりプログラムを書く状態じゃないから。

そうするとこれが消えないうちに、PrologとFOLとLispとをもうすこし繋いでおきたい。どうしたもんかなぁ、FOLを数理論理学の本できっちりやるのは、それはそれで時間がかかるしなぁ、と思案してたんだけど、これAIMA(Artificial Inteligence a Modern Approach)をやればいいじゃん！ということに気付いた。AIMAにはFOLについて簡潔にまとめた部分があるのです。PAIPやってて、Prologやったところだから、Norvigつながりもあって結構よい組み合わせではないか。

AIMAのFOLは8章と9章なんで、頭から読んでいるとPrologを忘れちゃう。そこで、思い切って7章からやろうと思う。7章から論理エージェントが初まる。

本を途中から読むということに慣れていないので、うまくいかないかもしれない。うまくいくかもしれない。チャレンジしてみよう。

こつこつ。

2009年7月9日木曜日

Allegro Prolog

以前はまったくわからんかったが、今はわかる！！

Allegro Prolog

LispとPrologとを多少連携して使えるみたい。

PAIPやりながらAllegro Prologもいじってみることにする。これは楽しみ。


CL-USER(2): (require :prolog)
; Fast loading /opt/acl81.64/code/prolog.002
;;; Installing prolog patch, version 2.
T
CL-USER(3): (use-package :prolog)
T
CL-USER(4): (?- (append ?x ?y (1 2 3)))
?X = ()
?Y = (1 2 3)
?X = (1)
?Y = (2 3)
?X = (1 2)
?Y = (3)
?X = (1 2 3)
?Y = ()
No.
CL-USER(5): (<-- (likes Kim Robin))
LIKES
CL-USER(6): (<- (likes Sandy Lee))
LIKES
CL-USER(7): (<- (likes Sandy Kim))
LIKES
CL-USER(8): (<- (likes Robin cats))
LIKES
CL-USER(9): (?- (likes Sandy ?x))
?X = LEE
?X = KIM
No.
CL-USER(10):

12 Working With Files


* 12 Working With Files
** 1 Splitting Programs over Files
 - consult
  - [FileName]. (at top-level)
  - 実体はconsultという述語らしい。
  - ファイルの中で使うときは頭に:-をつけるようだ。
 - ensure_loaded
  - ensure_loaded([FileName]).は、読み込み済みで無
   変更なものは再読み込みしないようだ。
 - module
  - そのファイルをmoduleにする。
  - :- module(ModuleName,
              List_of_Predicates_to_be_Exported).
 - use_module
  - moduleを使う。
  - :- use_module(ModuleName).
  - importする述語の指定(制限)もできる。
  - :- use_module(ModuleName,
                  List_of_Predicates_to_be_imported).
 - library
  - 処理系にてライブラリとして定義されているもの
    を指定する。use_moduleとあわせて使う。
  - 例:
    :- use_module(library(lists)).

** 2 Writing to Files
 - streamがある。使い方はこんな感じ。

open('hoge.txt',wrie,Stream),
write(Stream,'This is hoge.',nl(Stream),
close(Stream).

** 3 Reading from Files
 - read/2
  - streamからPrologのtermsを読み込む。
  - streamが読むものがないとエラーになる。
 - at_end_of_stream/1
  - streamの終端の検知。
 - get_code/2
  - streamからcharacterをひとつ読む。

** 4 Exercise
 - Exercise 12.1.

main :-
    open('hogwarts.houses',write,Stream),
    tab(Stream,10),write(Stream,'glyffindor'),nl(Stream),
    tab(Stream,3),write(Stream,'hufflepuff'),tab(Stream,4),write(Stream,'ravenclaw'),nl(Stream),
    tab(Stream,10),write(Stream,'slytherin'),nl(Stream),
    close(Stream).

 - Exercise 12.2.

:- dynamic word/2.

main :-
        open('swipl-man.txt',read,S),
        doWords(S),
        close(S).

readWord(InStream,W) :-
        get_code(InStream,Char),
        checkCharAndReadRest(Char,Chars,InStream),
        atom_codes(W,Chars).

checkCharAndReadRest(10,[],_) :- !.
checkCharAndReadRest(32,[],_) :- !.
checkCharAndReadRest(-1,[],_) :- !.
checkCharAndReadRest(end_of_file,[],_) :- !.
checkCharAndReadRest(Char,[Char|Chars],InStream) :-
        get_code(InStream,NextChar),
        checkCharAndReadRest(NextChar,Chars,InStream).

doWords(InStream) :-
        \+ at_end_of_stream(InStream),
        readWord(InStream,W),
        writeWord(W),
        doWords(InStream).

writeWord(Word) :-
        Word \== '', memoize(Word).
writeWord('').

memoize(W) :-
        word(W,N),M is N+1,asserta(word(W,M)),retract(word(W,N)),!.
memoize(W) :- asserta(word(W,1)).
   
** 5 Practical Session
 - 今まで作ってきたものをモジュール化して統合。
 - モジュール名と、ファイル名の拡張子より前は、同
   じでないといけないみたい。
 - Step 2までにしておき、後は入出力の練習なので、
   割愛する。

読了！！！！
頭がくたくただ！

【LPN】10 Cuts and Negation [落葉拾い]

いずれも寝た後なら簡単だった。疲れたときにも頑張ることは、意味がないのかなぁ。


 - Exercise 10.4.

   うーん。むずかしい。cutは宣言的かつ手続き的なの
   で、慣れれば強力かもしれないが、慣れないと中途
   半端で考えにくい。特にunificationがどう効いてく
   るかが問題になると、自分で束縛管理した方が楽じゃ
   んと思えてしまう。
   
   ここは後日、再チャレンジ。

   一晩寝たら5分でできた。。。

directTrain(saarbruecken,dudweiler).
directTrain(dudweiler,saarbruecken).
directTrain(forbach,saarbruecken).
directTrain(saarbruecken,forbach).
directTrain(freyming,forbach).
directTrain(forbach,freyming).
directTrain(stAvold,freyming).
directTrain(freyming,stAvold).
directTrain(fahlquemont,stAvold).
directTrain(stAvold,fahlquemont).
directTrain(metz,fahlquemont).
directTrain(fahlquemont,metz).
directTrain(nancy,metz).
directTrain(metz,nancy).


route(From,To,Route) :- rt(From,To,[To],Route).
rt(From,From,A,A) :- !.
rt(From,To,A,Route) :-
        directTrain(From,To),
        rt(From,From,[From|A],Route).
rt(From,To,A,Route) :-
        directTrain(ViaSt,To),
        rt(From,ViaSt,[ViaSt|A],Route).


** 5 Practical Session   
 - 1.

   \+ version.

nu(A,B) :- \+ A = B.

   \+ cut-free version

nu(A,B) :-
        A = B, fail;
        A \= B.

   cut-fail combination version

nu(A,B) :- A = B, !, fail.
nu(_,_).
   
 - 2.

  頭がまわらないので、これも後日。

  これも一晩寝たら30分くらいでできた。

unifiableUni(Term1,Term2) :-
        atomic(Term1),atomic(Term2),
        Term1 = Term2.
unifiableUni(Term1,Term2) :-
        var(Term1);
        var(Term2).
unifiableUni(Term1,Term2) :-
        complexterm(Term1),
        complexterm(Term2),
        Term1 =.. [F1|Args1],
        Term2 =.. [F2|Args2],
        F1 = F2,
        unifiableLists(Args1,Args2).  
unifiableLists([],[]).
unifiableLists([H1|T1],[H2|T2]) :-
        unifiableUni(H1,H2),
        unifiableLists(T1,T2).

unifiableAcc([],Term,A,A).
unifiableAcc([H|T],Term,A,R) :-
        unifiableUni(H,Term),
        unifiableAcc(T,Term,[H|A],R),!;
        unifiableAcc(T,Term,A,R).

unifiable(List1,Term,List2) :-
        unifiableAcc(List1,Term,[],List2).

こつこつ。

【LPN】11 Database Manipulation and Collecting Solutions


* 11 Database Manipulation and Collecting Solutions
** 1 Database Manipulation
 - assert/1。む、swi-prologはちょっと変なことを言う。

?- listing.
true.

?- assert(happy(mia)).
true.

?- listing.

:- dynamic happy/1.

happy(mia).
true.

?- 

 - ファイルから読み込んだものはstatic predicates、
   REPL?で定義したものはdynamic predicates。
 - retract : 撤回する
 - swi-prologではretractの対象がDBに複数あるとき、
   バックトラック的な操作で全て消せる。

?- retract(happy(vincent)).
true ;
true.

?- listing.

:- dynamic happy/1.

happy(butch).

:- dynamic naive/1.

naive(A) :-
 happy(A).
true.

?- 

 - assertはmemoisaitonに使える。
 - database manipulationの迂闊な利用はnightmareだか
   ら注意して。

** 2 Collecting Solutions
 - findall/3はちょっとmap的。
 - bagof/3、便利。
 - setof/3、便利。

** 3 Exercise
 - Exercise 11.1.
   - 第一段階

q(foo,blug).
q(a,b).
q(1,2).

   - 第二段階

q(foo,blug).
q(a,b).
p(X) :- h(X).

   - 第三段階

p(X) :- h(X).

 - Exercise 11.2.
   - findall(X,q(blob,X),List).
     List = [blug,blag,blig].
   - findall(X,q(X,blug),List).
     List = [blob,dang].
   - findall(X,q(X,Y),List).
     List = [blob,blob,blob,,blaf,dang,dang,flab].
   - bagof(X,q(X,Y),List).
     Y = blug,
     List = [blob,dang].
     Y = blag,
     List = [blob,blaf].
     Y = blig,
     List = [blob].
     Y = dong,
     List = [dang].
     Y = blob,
     List = [flab].
   - setof(X,Y^q(X,Y),List).
     List = [blaf,blob,dang,flab].

 - Exercise 11.3.
   - まずこう書いた。
sigma(0,0).
sigma(N,S) :-
        M is N - 1, M >= 0,
        T is S - N, T >= 0,
        sigma(M,T),!,
        asserta((:- sigma(N,S))).

   - これはpredicateとしては使えるが、構築には使え
     ない。

?- sigma(5,15).
true.

?- sigma(10,X).
ERROR: is/2: Arguments are not sufficiently instantiated
^  Exception: (9) _L143 is _G174-10 ? 

    - traceで調べる。

?- trace.
Unknown message: query(yes)
[trace]  ?- sigma(2,X).
   Call: (7) sigma(2, _G303) ? 
^  Call: (8) _L180 is 2-1 ? 
^  Exit: (8) 1 is 2-1 ? 
^  Call: (8) 1>=0 ? 
^  Exit: (8) 1>=0 ? 
^  Call: (8) _L181 is _G303-2 ? 
ERROR: is/2: Arguments are not sufficiently instantiated
^  Exception: (8) _L181 is _G303-2 ? 
   Exception: (7) sigma(2, _G303) ? 
?- 

    - なるほど。Unificationのinstantiationがいまい
      ちつかめていないのだな。accumulatorを使おう。

sigma(N,S) :- sigmaAcc(N,0,S),!,asserta((sigma(N,S))).
sigmaAcc(0,A,A) :- !.
sigmaAcc(N,A,S) :-
        M is N - 1,
        NewA is A + N,
        sigmaAcc(M,NewA,S).

      assertaが

ERROR: asserta/1: No permission to modify static_procedure `sigma/2'

      を吐く。これはまた別の問題なので割愛する。

** 4 Practical Session
 - 1.

subset([],_).
subset([H|T],[H|ST]) :-
        subset(T,ST).
subset([H|T],[SH|[H|ST]]) :-
        subset(T,[SH|ST]).

   backtrackで出力する集合に重複があるけどそれは勘
   弁。

 - 2.

powerset(L,P) :-
        findall(X,subset(X,L),P).

   先の重複の問題があるので、同じ集合だけど並びが
   違うものも含んでしまっている。

?- powerset([a,b,c],P).
P = [[], [a], [a, b], [a, b, c], [a, c], [a, c, b], [b], [b|...], [...|...]|...].

   これらの手落ちは後日時間があったらやろう。

よろよろ。

2009年7月8日水曜日

【LPN】10 Cuts and Negation


* 10 Cuts and Negation
** 1 The Cut
 - ! : predicate called cut.
 - cutは常に成功する。副作用する。副作用が大事。
 - fat-freeじゃなくてcut-free。
 - commit A to do,doing : Aに...することを義務づけ
   る。
 - cutを踏んだ時点で2つのことが義務となる。1つめは、
   現在のproof searchにおいて、そのclauseのみを探
   索の対象とすること(他のclauseは除外するというこ
   と)。次に、cutを踏む前にunify済みの変数について
   は、これ以降unificationは実施しないこと。
** 2 Using Cut
 - green cuts : cutsを入れても入れなくてもプログラ
   ムの意味(入出力の対応)に変化はないもの。green
   cutsに意味があるのは、効率があがるときである。
 - red cuts : cutsの有り無しでプログラムの意味が変
   わるcuts。
 - red cutsがある、ということはそのプログラムがあ
   まり宣言的ではない証左。なるほど。
** 3 Negation as Failure
 - fail/0 : バックトラックを強制する述語。
 - cut-fail combination : failによるバックトラック
   を抑制するイディオム。このイディオムがくると、
   そこでproof search自体がfailする(バックトラック
   しない)。
 - この章に入って、Prologの手続き的側面がどんどん
   導入されていく。。
 - negation : Monadic Boolean operations whose
   result have the Boolean value opposite to that
   of the operand.
 - cut-failじゃなくてnegation as failureを使うほう
   が安全。

neg(Goal) :- Goal,!,fail.
neg(Goal).

 - \+ : built-in negation as failure predicate.

 - cutsとnegation as failureの使い方についての完全
   なルールは存在しないケースバイケースの判断が必
   要。

 - まあ、プログラミングは、科学であるのと同じくら
   い芸術(技芸)でもあるので、自身が選択した言語と
   問題領域について理解を常に深めなければならない。
   だから面白いんだよ、プログラミングは。など。
** 4 Exercises
 - Exercise 10.1.
   p(X).
   X = 1.
   X = 2.

   p(X),p(Y).
   X = 1, Y = 1.
   X = 1, Y = 2.

   これ、間違えた。正解は、


?- p(X),p(Y).
X = 1,
Y = 1 ;
X = 1,
Y = 2 ;
X = 2,
Y = 1 ;
X = 2,
Y = 2.

?- 

   ということ。p(Y)でのcutはp(X)の探索には影響を及
   ぼさないことに注意。
   
   p(X),!,p(Y).
   X = 1, Y = 1.
   X = 1, Y = 2.
   
 - Exercise 10.2.

class(Number,positive) :- Number > 0.
class(0,zero).
class(Number,negative) :- Number < 0.

   これは数字のクラスに関する述語。正か負かゼロか
   でクラス分けしている。

   green cutsによる効率化。

class(Number,positive) :- Number > 0,!.
class(0,zero) :- !.
class(Number,negative) :- Number < 0.
   
 - Exercise 10.3.

   まず、cut-free。
   
split([],[],[]).
split([LH|LT],[LH|PT],N) :-
        LH >= 0, split(LT,PT,N).
split([LH|LT],P,[LH|NT]) :-
        LH < 0, split(LT,P,NT).

   続いてgreen cuts。

split([],[],[]) :- !.
split([LH|LT],[LH|PT],N) :-
        LH >= 0, !, split(LT,PT,N).
split([LH|LT],P,[LH|NT]) :-
        LH < 0, !, split(LT,P,NT).

 - Exercise 10.4.

   うーん。むずかしい。cutは宣言的かつ手続き的なの
   で、慣れれば強力かもしれないが、慣れないと中途
   半端で考えにくい。特にunificationがどう効いてく
   るかが問題になると、自分で束縛管理した方が楽じゃ
   んと思えてしまう。
   
   ここは後日、再チャレンジ。



** 5 Practical Session   
 - 1.

   \+ version.

nu(A,B) :- \+ A = B.

   \+ cut-free version

nu(A,B) :-
        A = B, fail;
        A \= B.

   cut-fail combination version

nu(A,B) :- A = B, !, fail.
nu(_,_).
   
 - 2.

  頭がまわらないので、これも後日。

よろよろ。

【LPN】9 A Closer Look at Terms


* 9 A Closer Look at Terms
** 1 Comparing Terms
 - ==/2はCommon Lispのeqみたいなニュアンスかな。
 
?- a == a.
true.

?- a == b.
fail.

?- a == 'a'.
true.

?- X == Y.
fail.

?- X=Y.
X = Y.

?- a = X, a == X.
X = a.

?- 

 - ふむ、eval、、、ではなくunifyされたobjectsを
   eq、、、じゃなく==は等価性チェックする。
 - ただ、==はtrue/failだけでなく、unifyされている
   ときは、unification(binding)を返しているな。な
   んか気になる。
 - \==/2の導入。

** 2 Terms with a Special Notation
 - Arithmetic terms

?- (2 =:= 3) == =:=(2,3).
true.

?- 2 =:= 3 == =:=(2,3).
ERROR: Syntax error: Operator priority clash
ERROR: 2 =:=
ERROR: ** here **
ERROR:  3 == =:=(2,3) . 
?- 

 - なるほど。

 - List as terms
   
?- .(a,[]) == [a].
true.

?- .(a,.(b,[])) == [a,b].
true.

?- 
 - おお、consだ！会いたかったよ、cons。こんなに小
   さくなっちゃって。。。

** 3 Examining Terms
 - Types of Terms
 - termsの型を調べる述語たち。
 
 - The structure of Terms

?- functor(f(a,b),F,A).
F = f,
A = 2.

?- 
 - おお、functorとarityも取れるのね。

?- functor(T,hoge,1).
T = hoge(_G240).

 - 構成もしてくれる、と。

 - complex termに対する型判定述語は自分で作る。

complexterm(X) :-
        nonvar(X),
        functor(X,_,A),
        A > 0.

 - arg : 引数に対するアクセス。
 - =.. : complex termsのfunctorとargsをリストで返
   す。univと呼ばれる。
 - atom_codes/2にてatomとstringの相互変換ができる。

** 4 Operators
 - ?-というのはprefix operatorだったのか。
 - precedenceが大きいものが主たる(:外側の)functor
   になる。+と*でいうと+の方が優先度が大きいので

   2 + 3 * 4.

   は、

   +(2,*(3,4)).

   になる。優先度が高い = 結合度が低い、かな。

 - operatorsとpredicatesが同義語なのかそうでないの
   かがわからない。先々わかるかな。
 - precedenceが同じoperatorsが存在する場合どうなる
   か。それはoperatorsのassociativityという概念/機
   構によって振る舞いがきまる。
 - 例えば、+は左結合性をもっている(left
   associative)。
 - 左結合性をは何か？
 - まずexpressionsのprecedenceの概念がある。それは
   そのexpressionの主functorのprecedenceである。さ
   て、左結合性とは、infix operatorsなのでそもそも
   引数は左右の2つなのだが、左にいれるexpressionは
   自身と同じprecedenceでもよいが、右にいれる
   expressionは自身より低くないといけない。これに
   よって、

   2 + 3 + 4.
   
   は、

   +(+(2,3),4).

   というように曖昧さなく解釈される。ためす。

?- 2 + 3 + 4 = +(+(2,3),4).
true.

?- 2 + 3 + 4 = +(2,+(3,4)).
fail.

   なお、これは内側のoperatorが+でなくても(同じで
   なくても)適用される。

 - ==, =:= は同じprecedenceを持ち、かつ
   non-associtiveである。すなわち、左右引数双方と
   も自身よりもprecedenceが低い必要がある。そのた
   め、

   2 =:= 3 == =:=(2,3).

   が、

   ==((2 =:= 3),=:=(2,3)).

   なのか、

   =:=(2,==(3,=:=(2,3))).

   なのかをPrologは自動判定できない。

 - Defining operators
 - operatorsというのは、operatorとして構文定義され
   たpredicatesのことのようだな。逆に言うと、op
   operatorが定義するのは構文だけで、それの意味と
   いうかその演算の結果がどうなるかは通常のqueryと
   同じであるということ。

?- assert(kill(marcellus,zed)).
true.

?- kill(X,zed).
X = marcellus.

?- assert((is_dead(X) :- kill(_,X))).
true.

?- is_dead(zed).
true.

?- op(500,xf,is_dead).
true.

?- zed is_dead.
true.

?- is_dead zed.
ERROR: Syntax error: Operator expected
ERROR: is_dead 
ERROR: ** here **
ERROR: zed . 

?- 

** 5 Exercise
 - Exercise 9.1.
  - 12 is 2*6.
    true.
  - 14 =\= 2*6.
    true.
  - 14 = 2*7.
    true. /* 正しくはfail。unifyは計算しない。term
    の種類が違う。*/
  - 14 == 2*7.
    fail.
  - 14 \== 2*7.
    true.
  - 14 =:= 2*7.
    true.
  - [1,2,3|[d,e]] == [1,2,3,d,e].
    true.
  - 2+3 == 3+2.
    fail.
  - 2+3 =:= 3+2.
    true.
  - 7-2 =\= 9-2.
    true.
  - p == 'p'.
    true.
  - p =\= 'p'.
    fail. /* 正しくはERROR.数字じゃないので計算で
    きない */
  - vicent == VAR.
    fail
  - vincent=VAR,VAR==vincent.
    true.

 - Exercise 9.2.
  - .(a,.(b,.(c,[]))) = [a,b,c].
    true.
  - .(a,.(b,.(c,[]))) = [a,b|c].
    fail
  - .(.(a,[]),.(b,[]),.(.(c,[]),[])) = X.
    ERROR. /* 最外の.の引数が3つ。*/
    お、ERRORにならない。そうか'.'/3が定義されるの
    か!
  - .(a,.(b,.(.(c,[]),[]))) = [a,b|[c]].
    fail. /* [a,b,[c]] */
 - Exercise 9.3.

complexterm(X) :-
        nonvar(X),
        functor(X,_,A),
        A > 0.

termtype(Term,atom) :-
        atom(Term).
termtype(Term,number) :-
        number(Term).
termtype(Term,constant) :-
        atomic(Term).
termtype(Term,variable) :-
        var(Term).
termtype(Term,simple_term) :-
        atomic(Term);
        var(Term).
termtype(Term,comprex_term) :-
        complexterm(Term).
termtype(_,term).

 - Exercise 9.4.

groundterm(X) :-
        atomic(X), nonvar(X).
groundterm(X) :-
        nonvar(X),
        X = [H|T],
        groundterm(H),
        groundterm(T).
groundterm(X) :-
        complexterm(X),
        '=..'(X,[functor|Args]),
        groundterm(Args).

 - Exercise 9.5.
 
  - うー。operatorの結合めんどくさい。S式でいいじゃん。

X is_a witch
is_a(X,witch).

harry and ron and hermione are friends
are(and(harry,and(ron,haermione)),friends)

harry is_a wizard and likes quidditch
illegal.

dubledore is_a famous wizard
is_a(dubledore,famous(wizard)).

** 6 Practical Session   
 - pretty printer

pptree(T) :- ppt(T,0).
ppt(T,I) :-
        atomic(T),tab(I),write(T).
ppt(T,I) :-
        complexterm(T),
        '=..'(T,[Functor,Single]),
        tab(I),write(Functor),write('('),write(Single),write(')').
ppt(T,I) :-
        complexterm(T),
        '=..'(T,[Functor,Left,Right]),
        tab(I),write(Functor),write('('),nl,
        NewI is I + 2,
        ppt(Left,NewI),nl,
        ppt(Right,NewI),write(')').

 - propositional logic formulas

:- op(200,fx,not).
:- op(300,xfy,implies).

さすがに体調が悪くなってきた。
仕事との両立が難しいのか、体が弱いのか。

こつこつ。

登録: 投稿 (Atom)

2009年7月31日金曜日

2009年7月30日木曜日

2009年7月29日水曜日

2009年7月28日火曜日

2009年7月27日月曜日

2009年7月26日日曜日

2009年7月25日土曜日

2009年7月24日金曜日

2009年7月23日木曜日

2009年7月22日水曜日

2009年7月21日火曜日

2009年7月20日月曜日

2009年7月19日日曜日

2009年7月17日金曜日

2009年7月16日木曜日

2009年7月15日水曜日

2009年7月14日火曜日

2009年7月13日月曜日

2009年7月12日日曜日

2009年7月11日土曜日

2009年7月10日金曜日

2009年7月9日木曜日

2009年7月8日水曜日

ラベル

自己紹介

ブログ アーカイブ

ブログアーカイブ