ラベル DSL の投稿を表示しています。 すべての投稿を表示
ラベル DSL の投稿を表示しています。 すべての投稿を表示

2009年11月8日日曜日

【make】2 ルール(その1)

やってみると、やっぱりmakeはルールベースプログラミングでありDSLなんだなぁ、ということをあらためて感じる。


* 2 ルール
- ルールにはいくつかの種類がある。
- 'GNU make'は'make'と互換性がある。
- ルールの書き方について、'GNUM make'は'make'を進
化させて、使いやすくした部分がある。

** 2.1 明示的ルール

ターゲットは複数行にわけたり、単一行にまとめたりできる。

hoge.o piyo.o: puyo.h ponyo.h moge.h

これは、

hoge.o: puyo.h ponyo.h moge.h
piyo.o: puyo.h ponyo.h moge.h

これと等価。

hoge.o: puyo.h ponyo.h moge.h

これは、

hoge.o: puyo.h ponyo.h
hoge.o: moge.h

これと等価。

*** 2.1.1 ワイルドカード
- makeのワイルドカードは、Bournese Shellと同じ記
法。
- ワイルドカードは、makeのどの項にも使える。
- ワイルドカードの展開は、ターゲットと前提条件に
ついてはmakeが実施し、コマンドについてはシェル
が実行する。

例。
------
hoge: *.c
gcc -o $@ $^
------

- ワイルドカードは、シェルと同じように展開されて
から解釈される。なので、

*.o : piyo.h

というルールは、まだobject fileがひとつも存在し
ないディレクトリにおいては、

------
: piyo.h
------

となってしまう。

*** 2.1.2 疑似ターゲット

- 疑似ターゲット(phony target)なるものあり。
- これは、ターゲットで指定した名前のファイルは存
在しない。すなわち、そのターゲットのコマンドは
ターゲット名のファイルを生成しないようなもので
あること。

例。
------
clean:
rm -f *.o
------

- これだけだと、cleanってファイルが間違って存在し
てしまったら、'make clean'してもこの掃除処理は
実行されなくなってしまう。
- なのでこうする。

------
.PHONY: clean
clean:
rm -f *.o
------

- 応用。疑似ターゲットはmakefile内でのプロシージャ
呼び出しみたいに使える。

------
.PHONY: clean
clean: hoge
rm -f *.o

hoge:
ls -l *.o
------

- 疑似ターゲットは、エイリアス的にもつかえる。使
い勝手が向上する。

------
.PHONY: task-a
task-a: jugemujugemugokounosurikirekaijarisuigyo

jugemujugemugokounosurikirekaijarisuigyo: hoge.h piyo.h
gcc -o $@ $^
------

- よくある疑似ターゲット

| ターゲット | 意味 |
|------------+--------------------------------------------------|
| all | アプリケーションを構築するすべての作業を行う |
| install | 構築したアプリケーションをシステムに配置する |
| clean | 構築したアプリケーションを削除する |
| distclean | 配布状態に含まれていないものをすべて削除する |
| TAGS | TAGSを作成する |
| info | Texinfoのソースからinfoファイルを作成する |
| check | アプリケーションに関するすべてのテストを実施する |


*** 2.1.3 空のターゲット

- 疑似ターゲットは常に「最新ではない」と判断され
る。そのため、指定されれば常に実行される。
- なので、指定したときは常に実行される処理にはよ
い。
- 指定とは別に実行するかしないかを制御するにはどう
するか。それを制御するために、touchで時刻を更新
するファイルを利用すればよい。

- 例えば、次のようにするとhoge.cが更新されたときだ
け、piyoが実行される。

------
hoge: piyo hoge.c
gcc hoge.c -ohoge

piyo: hoge.c
size $^
touch size
------

** 2.2 変数

- 変数の基本的なかきぶりは次のとおり。

$(variable-name)

- bashでは、これはcommand substitutionだな。bash
での変数参照は、${PATH}などのcurly bracket。
bashとmake、揃えてくれればいいのに、ややこし
い。。。

*** 2.2.1 自動変数

- 自動変数は、実行ルールが決定した後に、makeが自
動的にその値を設定する。

- 自動変数の一覧

| 形式 | 意味 |
|------+------------------------------------------------------------------|
| $@ | ターゲット文字列 |
| $% | ターゲット文字列の一部。"hoge(piyo)"ならpiyo。 |
| $< | 最初の前提条件 |
| $? | 前提条件のうち、ターゲットよりも新しいもの達をスペース区切りで |
| $^ | 前提条件すべてをスペース区切りで。重複しないようにダブリを削除。 |
| $+ | 前提条件すべてをスペース区切りで。重複しないようにダブリあり。 |
| $* | ターゲット文字列の一部。通常は、suffixを削除したもの。 |

- 自動変数のテストmakefile

これでひととおりの挙動の確認ができる。

------
# 行頭に'#'を置くとその行はmakeのコメント行。行頭以外の置き方もあるがそれは後述。

### このプログラムの動かし方
#
# ファイルの一括削除
# make distclean
#
# 必要ファイルの作成
# make all
#
# すべてのテストを実行
# make check

### ルールの構文 (簡略版2)
# target1 target2 ... targetN : prerequiste1 prerequiste2 ... prerequisteM
# command1
# command2
# ...
# commandK

### コメントについて
# commandを書くゾーンは、行頭の'#'はmakeのコメント
# であり、それ以外はshellに渡される。それがコメント
# かどうかはshellが判断する。それ以外のゾーンでは、
# 行頭ではなくても'#'があればそれ以降はmakeのコメン
# ト。

.PHONY: all # この行はallが疑似ターゲットであることを指定している。
all: update-file1 update-file2 update-file3 hoge.c piyo.c foolib(hoge.c) foolib(piyo.c)

# phonyはまとめて指定できる。
.PHONY: check distclean update-file1 update-file2 update-file3 \
update-hoge update-piyo \
test-\# test-@ test-percent test-< test-? test-? test-^ test-+ test-*.c
# '\'でmakeの継続行になる。commandゾーンであれば
# shellにわたり、shellの継続行となる。

check: test-\# test-@ update-hoge test-percent test-< test-? test-? test-^ test-+ test-*.c

distclean:
rm -f file1 file2 file3 \
hoge.c piyo.c foolib

update-file1:
touch file1

update-file2:
touch file2

update-file3:
touch file3

update-hoge:
touch hoge.c

update-piyo:
touch piyo.c

hoge.c:
echo '#include ' > hoge.c

piyo.c:
echo '#include ' > piyo.c

# ar なarchiveについてはその構成ファイルを指定する
# ことができる。これは実戦的には.a形式のためのもの。
foolib(hoge.c): hoge.c
# $%
ar cr foolib hoge.c
## foolib(hoge.c) end
## next test maybe start

foolib(piyo.c): piyo.c
# $%
ar cr foolib piyo.c
## foolib(piyo.c) end
## next test maybe start

test-\#:
# これはmakeのコメント。commandゾーンだがshellに渡されない。
# これはmakeとしてはcommand。shellはコメントと解釈する。
## test-# end
## next test maybe start

test-@:
# ターゲット文字列(すなわちファイル名)
# $@
## test-@ end
## next test maybe start

test-percent: foolib(hoge.c) foolib(piyo.c)
## test-percent end
## next test maybe start

test-<: file1 file2 file3
# 最初の前提条件
# $<
## test-< end
## next test maybe start

test-?: update-file3 file1 file2 file3
# 前提条件のうち、ターゲットよりも新しいもの達をスペース区切りで。
# $?
touch test-\?
## test-? end
## next test maybe start

test-^: file1 file2 file3 file1
# 前提条件すべてをスペース区切りで。重複しないようにダブリを削除。
# $^
## test-^ end
## next test maybe start

test-+: file1 file2 file3 file1
# 前提条件すべてをスペース区切りで。重複しないようにダブリあり。
# $+
## test-+ end
## next test maybe start

test-*.c:
# ターゲット文字列の一部。通常は、suffixを削除したもの。
# $*
## test-*.c end
## next test maybe start
------

- 自動変数の修飾子

- ここまでのところ、makefileもソースファイルも
バイナリファイルも同一のディレクトリの同一階
層にあることを前提としている。
- しかし、makeは同一ディレクトリの中のサブディ
レクトリにあるファイルも扱える。(後で出てくる
はず)
- するとターゲットはパスを含むものもOK。
(hoge/piyo/puyo.c)など。

- この形式のターゲットのために、自動変数の修飾
子'D'と'F'がある。

例。

-------
all: dist/src/hoge.c

dist/src/hoge.c:
# target : $@
# target (directory part) : $(@D)
# target (file part) : $(@F)
-------


こつこつ。

2009年9月20日日曜日

【LPL】5章 ブール論理の証明方法

5章完了。

私が今までに読んだ本とは違っていて、興味深い点がいくつか。

  • 例えばQuineでは、論じているドメインの知識は捨ててしまって、それでも残るのが論理という言語や思考の性質、という感じであり、他にもそういう本がけっこうあり、それは確かに論理の本質なのだが、日常の議論においては、ドメインの制約も論証の一部として利用しているということから、どうもすわりが悪かったのが本当のところ。この本は、その点を明確にし、ドメインと論理の兼ね合いも分析的帰結(Analytic Consequences)として、TW-帰結(TWにおけるドメイン知識活用)、TT-帰結、FO-帰結、論理的帰結などと分類しつつ適切に導入している。これはありがたい。
  • 非形式的証明という名のもとに、自然言語での証明についてもページを割いているのだが、これが前項と相俟って内容豊かになっている。すなわち、論理の推論規則だけだと、骨組みだけの荒涼とした証明となるが、ドメイン知識による推論もカバーしているので、日頃、コンピュータ科学や数学で使われている証明に近い内容になる。しかも、どの推論が(ある意味)pure論理で、どの推論がドメイン知識かという関係も明確にしてそれをやってくれる。

これだけでもこの本を読んだ価値はあった。

こつこつ。

2009年7月23日木曜日

【DBiD】3 タプルと関係


* 3 タプルと関係

** 私の雑感
この本はDateのアジというか、ノイズが多い。
このアジは、SQLをリレーショナルモデルと思い込んで
いる人に対する気付け薬的なものだろう。

そういう思い込みが無い人にとっては、アジはいいから、
もうちょっとすっきり整理して言いたいことを言って欲
しいなぁ、と感じさせるものではないか。実際私はそう
だ。しかしそれはこの本を読んでいる私の選択の問題だ
ろう。C.J.Dateは著書が豊富なので、その中にはすっき
り整理してある本もあるのだろう。

また、この本の訳書のタイトルはまずいかもしれない。
「データベース実践講義」というタイトルで期待するこ
とは、本書の内容とは違うことが多いのではないか。原
書の「Database in Depth」はそういう意味ではアリであ
る。訳書のタイトルのアンマッチが、読者の誤解や不評
に繋らなければよいのだが。私自身は原題の認識が先行
していたので、アジ以外は期待通り。

閑話休題。

という事情も加味しつつ、この章も自分なりのまとめを
書く。読書メモとはちょっと違うものです。


** タプルの定義
定義なので、原文まま引用。

---
T1,T2,...Tn (n>=0)が型名であり、それらが必ずしも異
なるとは限らないとする各Tiに識別可能な属性名Aiを関
連付ける。これによって生じるn個の属性名と型名の組
みは、それぞれ属性である。各属性をTi型の値viに関連
付ける。それによって生じるn個の属性と値の組みは、
それぞれコンポーネントである。そのように定義された
n個のコンポーネントからなる集合(t)は、属性
A1,A2,...,Anのタプル値(または略してタプル)である。
値nはtの次数であり、次数1のタプルは単項、次数2のタ
プルは2項、次数3のタプルは3項である。一般に、次数n
のタプルはn項である。n個の属性からなる集合は、tの
見出しである。
---

** タプルをCommon Lispのオブジェクトで表現してみる

- 型名
- これはatom。

T1 T2 T3

- 属性名
- これもatom。

A1 A2 A3

- 属性
- これはdotted pairにしてみる。

(T1 . A1)
(T2 . A2)
(T3 . A3)

- 値
- これもatomにしてみる。

v1 v2 v3

- コンポーネント
- dotted pair。

((T1 . A1) . v1)
((T2 . A2) . v2)
((T3 . A3) . v3)

- タプル値 (タプル)
- listで表現する。しかしタプル値としては集合な
ので、そこは表現しきれていない。

(((T1 . A1) . v1)
((T2 . A2) . v2)
((T3 . A3) . v3))

- 見出し

タプル値、

(((T1 . A1) . v1)
((T2 . A2) . v2)
((T3 . A3) . v3))

の見出しとは、

((T1 . A1)
(T2 . A2)
(T3 . A3))

である。listだが、集合として使うことを想定して
いる。

- タプル値というのは、super-boxedなデータみたいな
ものかな。型のみならず、現在の(DSLの意味での)
ドメインの名前(属性名)までもデータに入っている。
そうか、Common Lispとかの構造体と同じなのか。
例えば、HyperSpecから例をとると、構造体の定義は、

---
(defstruct ship
(x-position 0.0 :type short-float)
(y-position 0.0 :type short-float)
(x-velocity 0.0 :type short-float)
(y-velocity 0.0 :type short-float)
(mass *default-ship-mass* :type short-float :read-only t))
---

であり、一応生成された構造体のスロットも、自分
自身のスロット名やスロットの型を知っている。な
るほどなるほど。

** タプルに関するトピック

- nullを含むタプルは存在しない。
- そう決めるのは自由なのだが、Common Lispには
nilがあり、構造体の値にも使えたりする。

- タプルの部分集合はタプルである。
- 見出しの部分集合は見出しである。

- 次数がゼロのタプルを0タプルと呼ぶ。
Common Lisp的に表現すると、

()

かな。
- タプルの等価性は、Common Lispのequalp的に定義さ
れている。

** 関係の定義
定義なので原文まま引用。

---
{H}をタプルの見出しとし、t1,t2,...,tm (m >= 0)を見
出し{H}を持つ個々のタプルであるとする。{H}とタプル
の集合{t1,t2,...,tm}との組み合わせrは、属性
A1,A2,...,Anにおける関係値(または単に関係)である。
ここで、A1,A2,...,Anは{H}の属性である。rの見出しは
{H}である。rは見出しと同じ属性(よって、同じ属性名
と型)と、見出しと同じ次数を持つ。rの本体はタプルの
集合{t1,t2,...,tm}である。値mはrの濃度である。
---

- タプルの流れで、Common Lispで関係を表現すると、

まず、これが見出しで、

((T1 . A1)
(T2 . A2)
(T3 . A3))

タプル値が例えば、3つあるとするとそれらは、

(((T1 . A1) . v11)
((T2 . A2) . v12)
((T3 . A3) . v1))

(((T1 . A1) . v21)
((T2 . A2) . v22)
((T3 . A3) . v23))

(((T1 . A1) . v21)
((T2 . A2) . v22)
((T3 . A3) . v23))

なんぞであり、タプル値の集合が関係の本体なので、

((((T1 . A1) . v11)
((T2 . A2) . v12)
((T3 . A3) . v1))
(((T1 . A1) . v21)
((T2 . A2) . v22)
((T3 . A3) . v23))
(((T1 . A1) . v21)
((T2 . A2) . v22)
((T3 . A3) . v23)))

リストで集合を表現するとこれが本体。

この本体と見出しを組み合わせたのが関係だから、
それをリストであらわすと、

(((T1 . A1)
(T2 . A2)
(T3 . A3))

((((T1 . A1) . v11)
((T2 . A2) . v12)
((T3 . A3) . v1))
(((T1 . A1) . v21)
((T2 . A2) . v22)
((T3 . A3) . v23))
(((T1 . A1) . v21)
((T2 . A2) . v22)
((T3 . A3) . v23))))

これが関係。

** 関係に関するトピック
- 本体の部分集合はすべて本体である。
- 関係の中でのタプルの重複はリレーショナルモデル
では禁止されるべきである。Tutorial Dでは禁止さ
れている。SQLでは禁止されていない。

** nullを禁止すべき理由
- リレーショナルモデルは、2値論理(2VL)に基づくべ
きである。(その方が有用だから) そして実際に、リ
レーショナルモデルの中の各部は2値論理に基づいて
組みたてられている。
- nullを含むということは、述語の値が
true,false,unknownの3値になり3値論理(3VL)という
ことになる。
- 2値論理の機構と3値論理の機構が混在すると、期待
する正しい結果が得られないというか、保証されな
い場合がでてくる。実際、SQLではそういった例があ
る。
- よってnullはリレーショナルモデルに含まない方が
よい。
- nullが入っている状態はリレーショナルモデル以外
の何かであると認識した方がよい。

** TABLE_DUM と TABLE_DEE
- TABLE_DUMは、空の関係である。
Common Lispの表現の流れでは、

(() ())

である。次数ゼロなので、見出しは空集合である。ま
た、本体も何も含まないので、空集合である。

- TABLE_DEEは、次数ゼロで空のタプルを壱つ含む関係
である。
Common Lispの流れの表現では、

(() (()))

である。本体に空のタプルを壱つ含んでいるが、空
のタプルは空集合なので、このようになる。

- これらはリレーショナル代数において役割をもつ。
TABLE_DEEはゼロの役割を果す。
- 真理値の観点で言うと、TABLE_DUMはNO/FALSEの役割
を果たし、TABLE_DEEはYES/TRUEの役割を果たす。


こつこつ。

2009年7月10日金曜日

【AIMAメモ】知識工学とDSL

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

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

前半戦に類似がある。

2009年7月7日火曜日

【LPN】7 Definite Clause Grammars


* 7 Definite Clause Grammars
** 1 Context Free Grammars
- Prologは多様な目的に利用できるが、発明時の目的と
してcomputational linguistics (計算言語学?、計
算機言語学?)があった。
- Prologにはcomputational linguisticsに有効なツー
ルがたくさんある。
- その筆頭がDCGである。
- DCGは文法を記述するための記法である。
- そもそも文法って何だ。CFGをもってそれを考える。
- CFGの説明。
- CFGはシプサでやったので、用語だけ確認しておく。
- non-terminal symbols
- terminal symbols
- context free rules
- -> : can consist of, can be built out of.
- parse tree : parseは品詞を記述する、構成要素に
分析するという意味らしい。websterだと、Analyze
syntactically by assingning a constituent
structure to (a sentence).
- licensed : "every part of the tree is licesed
by one of our rules", 認可された
- strings : ここではstring of wordsというように
wordの並びをstringという。
- structure : parse treeのもつ構造のこと。
- grammatical : the stringが(given grammarにおい
て)grammaticalであるとは、その文法規則によって
parse treeを構成できることを言う。
- language generated by a grammar : その文法要素
によって生成可能な全てのstringsの総体をこのよ
うに呼ぶ。
- recogniser : stringsがgiven grammarにて生成可
能かどうか判定するプログラム。
- parser : recogniserの機能に加えて、the
structureを示すもの。具体的にはparse treeを示
すもの。
- context free language : context free grammarで
文法を記述可能な言語達のこと。英語はCFGと考え
られている。ドイツ語はCFGでは無いことが証明さ
れている。

- まず、CFGのrecognizerをPrologでどう作るか。
- stringsはlistsとする。
- 対象CFG。

s -> np vp
np -> det n
vp -> v np
vp -> v
det -> 'a
det -> 'the
n -> 'woman
n -> 'man
v -> 'shoots

(注)italic表示のかわりに'を頭につけている。
terminalたちです。

- appendを使う素朴なやり方。
- その1。

s(Z) :- np(X), vp(Y), append(X,Y,Z).
np(Z) :- det(X), n(Y), append(X,Y,Z).
vp(Z) :- v(X), np(Y), append(X,Y,Z).
vp(Z) :- v(Z).
det([the]).
det([a]).
n([woman]).
n([man]).
v([shoots]).

- 動く。しかし、入力情報を探索のガイドにつかって
いないので非効率的。

- その2。
- goalsの順番を変えてみる。

s(Z) :- append(X,Y,Z), np(X), vp(Y).
np(Z) :- append(X,Y,Z), det(X), n(Y).
vp(Z) :- append(X,Y,Z), v(X), np(Y).
vp(Z) :- v(Z).
det([the]).
det([a]).
n([woman]).
n([man]).
v([shoots]).

- 動く。しかしappendとinstansiationsの組み合わせ
は非効率的。traceをみる。

[trace] ?- np([a,woman]).
Call: (7) np([a, woman]) ?
Call: (8) append(_L179, _L180, [a, woman]) ?
Exit: (8) append([], [a, woman], [a, woman]) ?
Call: (8) det([]) ?
Fail: (8) det([]) ?
Redo: (8) append(_L179, _L180, [a, woman]) ?
Call: (9) append(_G366, _L180, [woman]) ?
Exit: (9) append([], [woman], [woman]) ?
Exit: (8) append([a], [woman], [a, woman]) ?
Call: (8) det([a]) ?
Exit: (8) det([a]) ?
Call: (8) n([woman]) ?
Exit: (8) n([woman]) ?
Exit: (7) np([a, woman]) ?
true

- もっとうまい方法はないか。
- ある。
- difference listsという方法。(差分リストとでも言
うのかなぁ)

- difference listsは、2つのリストの差によって対象
となるリストを表現する。

- difference lists版。

s(X,Z) :- np(X,Y), vp(Y,Z).
np(X,Z) :- det(X,Y), n(Y,Z).
vp(X,Z) :- v(X,Y), np(Y,Z).
vp(X,Z) :- v(X,Z).

det([the|W],W).
det([a|W],W).

n([woman|W],W).
n([man|W],W).

v([shoots|W],W).

- これ、昨日flatten書くときに使った手法だ。
- この手法にdifferencial listsという名前をつけて、
汎用化するところが頭いいな。

[trace] ?- s([a,woman,shoots,a,man],[]).
Call: (7) s([a, woman, shoots, a, man], []) ?
Call: (8) np([a, woman, shoots, a, man], _L180) ?
Call: (9) det([a, woman, shoots, a, man], _L198) ?
Exit: (9) det([a, woman, shoots, a, man], [woman, shoots, a, man]) ?
Call: (9) n([woman, shoots, a, man], _L180) ?
Exit: (9) n([woman, shoots, a, man], [shoots, a, man]) ?
Exit: (8) np([a, woman, shoots, a, man], [shoots, a, man]) ?
Call: (8) vp([shoots, a, man], []) ?
Call: (9) v([shoots, a, man], _L234) ?
Exit: (9) v([shoots, a, man], [a, man]) ?
Call: (9) np([a, man], []) ?
Call: (10) det([a, man], _L252) ?
Exit: (10) det([a, man], [man]) ?
Call: (10) n([man], []) ?
Exit: (10) n([man], []) ?
Exit: (9) np([a, man], []) ?
Exit: (8) vp([shoots, a, man], []) ?
Exit: (7) s([a, woman, shoots, a, man], []) ?
true

- うーん。きれい。
- さて、differece listsを使ったrecogniserはかきぶ
りがちょっと汚い。
- そこでDCGの出番。

** 2 Definite Clause Grammars

- DCGは、difference listsを隠蔽してくれるa nice
notation。
- 例。

s --> np,vp.
np --> det,n.
vp --> v,np.
vp --> v.
det --> [the].
det --> [a].

n --> [woman].
n --> [man].

v --> [shoots].

- うむ。構文糖衣というかDSLというか。
- Prologがこれをdifferece listsを使った先の書きぶ
りに変換するとのこと。試す。

?- listing(s).
s(A, C) :-
np(A, B),
vp(B, C).

true.

?-

- ルール追加。

s --> s,conj,s.
conj --> [and].
conj --> [or].
conj --> [but].

- このs,conj,sのsが左再帰問題。
- 語彙を変える。

s --> simple_s.
s --> simple_s,conj,s.
simple_s --> np,vp.
np --> det,n.
vp --> v,np.
vp --> v.
det --> [the].
det --> [a].

n --> [woman].
n --> [man].

v --> [shoots].

conj --> [and].
conj --> [or].
conj --> [but].

- そっか。CFGでnon-terminalについて名前を工夫し
ているときってこういう理由だったんだな。PAIPも
そうやってた。

- formal languageってnatural languageと対を成す
単語なんだ。
- 形式言語(a^n)(b^n)。シプサの世界だ。

s --> [].
s --> l,s,r.

l --> [a].
r --> [b].

** 3 Exercises
- Exercise 7.1.
s(A,D) :-
foo(A,B),bar(B,C),wiggle(C,D).
foo([choo|W],W).
foo(X,Z) :-
foo(X,Y),foo(Y,Z).
bar(X,Z) :-
mar(X,Y),zar(Y,Z).
mar(X,Z) :-
me(X,Y),my(Y,Z).
me([i|W],W).
my([am|W],W).
zar(X,Z) :-
blar(X,Y),car(Y,Z).
blar([a|W],W).
car([train|W],W).
wiggle([toot|W],W).
wiggle(X,Z) :-
wiggle(X,Y),wiggle(Y,Z).

- Exercise 7.2.
s --> l,r.
s --> l,s,r.

l --> [a].
r --> [b].

- Exercise 7.3.
s --> [].
s --> l,s,r,r.

l --> [a].
r --> [b].

** 4 Practical Session
- 1.
s --> [].
s --> w,s,w.
w --> [a].

- 2.
s --> core.
s --> a,s,d.
core --> [].
core --> b,b,core,c,c.
a --> [a].
b --> [b].
c --> [c].
d --> [d].

- 3.
- propositional logic : 命題論理

prop --> [p].
prop --> [q].
prop --> [r].
prop --> not, prop.
prop --> lparen, prop, or, prop, rparen.
prop --> lparen, prop, and, prop, rparen.
prop --> lparen, prop, imp, prop, rparen.

not --> [not].
or --> [or].
and --> [and].
lparen --> ['('].
rparen --> [')'].
imp --> [implies].


この章おもしろかった。
こつこつ。

2009年1月3日土曜日

【実践CL】7 マクロ:標準的な制御構文の構築


  • 前説

    • 要旨:プログラミングの大部分は言語の拡張である。CLのマクロは、関数、オブジェクトに並ぶ第三の拡張方法である。

  • 7.1 WHENとUNLESS

    • 要旨:マクロ機構が言語に組込まれているので、DSLを手軽に書ける。

  • 7.2 COND

    • 要旨:CONDの紹介。

  • 7.3 ANDとORとNOT

    • 要旨:ANDとORとNOTの紹介。(NOTは関数)

  • 7.4 繰り返し

    • 要旨:CLにおける繰り返し機構は階層をなしている。下から言うと、tagbodyとgo -> do -> dolist,dotimes,.. という系列と、loopがある。loopは英語のように繰り返しを書く機構。

  • 7.5 DOLISTとDOTIMES

    • 要旨:DOLISTとDOTIMESの紹介。

  • 7.6 DO

    • 要旨:DOの紹介。

  • 7.7 強力なLOOP

    • 感想:「LOOPを悪く言う人たちは、そのシンタックスがちっともLispっぽくない(つまり、括弧が足りない)と主張している」これは少なくともPGとNorvigについてはあてはまらない。彼らはどちらかというとLOOP否定派だが、その理由は、「拡張LOOPはANSI仕様において、またそれ以外のところにおいても、十分な構文定義が存在しない。そして実際、解釈が不定な表現も書けてしまう」ということがひとつ。あとは、「拡張loop構文は複数節の組み合わせという構造をもっているが、それをなす各節を拡張LOOP構文以外のところで再利用できないつくりはよろしくない」ということだったような。
    • 感想:私個人としては、プロトタイピングとかに有効につかって、固くするときにdoとかに書き換えればいいんじゃない、と考えている。
    • 要旨:賛否は別にして、こんなものもできちゃうのがマクロのパワーだ。


こつこつ。

2008年12月24日水曜日

学びのエクササイズ 認知言語学

昨日は街中をぶらぶらしつつ本を読んだ。

学びのエクササイズ 認知言語学

を一気読み。面白かった!
OOの抽象ドメインモデル、DSLなどとの関連が浮き出ている。
また認知言語学の背後にあるのは圏論。圏論の雰囲気もつかめた。

気分転換にお勧めの一冊。

2008年11月9日日曜日

【ANSI-CL】17 例:オブジェクト指向言語 (その2)


  • 完全には習得していないが、写経しつつ、イメージはわかった。自分なりに少しまとめてみる。

  • ある特定の問題を解くプログラムではなく、言語内言語のようなものを作る作業である。Fowler風に言えば内部DSL。
  • 同じものをC言語でつくることを想像してみる。

    • ちょっとうまく想像できない。。。
    • まずLisp的マクロはないので、関数が書きぶりのメインになるのだろう。
    • データ構造的な部分は、基本型、配列、構造体などの基本的なものとポインタで大抵いけるだろう。
    • methodcall (&obj &method &method_params) 的な呼び出し構造があふれそうな。
    • これ、先々やってみると面白いかも。


これにて最終章完了。付録は「付録A デバッグ」のみやることにする。

2008年9月17日水曜日

【シプサ】6 計算可能性の理論における先進的な話題 (その2)

上半期末に向けて、業務が膨大に、、、
されど、こつこつ。
「6.2 Decidability of logical theories」から。

  • ある数学的言明(statement)が真かどうかを判定するアルゴリズムがあるかどうか、ということは、もちろんその言明が属している数学のドメインによる。判定するアルゴリズムがあるドメインもあるし、それが存在しないドメインもある。
  • このことをTMで扱うために、言語をつくる。
  • その言語に含まれる要素は、真である(ある特定された対象ドメインに属する)数学的言明の表現である。
  • 数学的言明というオブジェクトの表現方法を決める。文字列で表現するルールをきっちり定める、ということ。
  • ここで定めているのは、一階述語論理っぽい。

  • R(x1, ..., xj)のかたちのもの = atomic formula
  • 構成ルールにしたがって、atomic formulaからつくったもの = well-formed formula (単にformulaと言うときはこれ)
  • formulaで、コンティフィアが冒頭にしかないもの = prenex normal form
  • formulaで、no free variableなもの = sentence or statement

  • さて、これでformulaを整備できた。違う言葉でいうと、数学的言明を表現する方式を確立した。

  • あと、やらねばならぬことが2つ。

  • ひとつは、variableってなんじゃないな、ということ。
  • それはvariableの値になりうるのはこれこれですよということを明確にする集合があるとする。
  • その集合をUniverseと呼ぶ。
  • これを具体的に割当てる必要がある。(これが意味論?)
  • つぎに、Relationsというのは第一章で確認済みな真偽値を値とする写像なんだが、
  • この言語におけるRelationsシンボルが、どういう具体的Relationを表現しているのよということの特定。(これが意味論?)

  • で、この具体的に特定された(universe, relation assignments)の組のことを、modelと呼ぶ。
  • 逆に、あるmodelに対応したstatementの集りのことを、language of a modelと呼ぶ。
  • ここで「対応した」とは、そのmodelに適合した形(relationシンボルとrelationのarityがポイント)であるということ。
  • で、ここ、ややこしいというか用語が混乱しているように思うのだが、

    • model Mがあるとする。
    • statement Φ が 、Mに対するlanguage of a modelに属しているとする。
    • すると、Φは、Mによって、trueとなったりfalseとなったりするでしょう。(ここまではよい。)
    • あるMでΦがtrueになったとする。
    • そのとき、MはΦの a modelであるという。(ここ、ちょっと混乱している)

  • まあ、これが定義なのだからしかたなし。

  • EXAMPLE 6.10 そうか、「∀x∀y(R1(x,y)∨R1(y,x)をモデル(N,<=)で考える」というのが言語とモデルの正式な関係で、これを「∀x∀y(x<=y)∨(y<=x)を考える」といってしまうのはこのモデルを念頭においた略記にすぎないのだな。

  • で、Th(M): theory of M の定義

    • a model たる Mがあるとする。
    • すると、Mに対する複数のlanguage of a modelがあるだろう。
    • そのなかで、すべてのsentenceがtrueとなるものがあったとする。
    • それをtheory of Mと呼ぶ。


TMもずいぶん長くやっているし、「論理学をつくる」で一階述語論理まではかじっているので、すんなり。
とりあえず、ここまで。
次回は、これらについて判定可能性を調べていく。