プログラミングを上達させたい

プログラミングの勉強を始めた、情報学専攻の大学院生です。モチベーション維持のため、ブログに勉強したことを書いていきます。→就職。IT全然関係ない仕事をしています

Prolog 第3回

さあ、いよいよプログラムプログラムしたものを作っていきます。
ワクワクする反面、つまずいたらいやだなー、という感じです。
僕のプログラミングの経験は、授業でschemeを少しやったのみ、という状態なので、どちらかというと不安の方が大きいです。

 


ついに、こういうプログラムを書くわけです。

gist7035444



そして質問をすると、こう返ってくるわけです。

---------------------------------------------
| ?- consult('wa.pl').
compiling /home/ecsfs2/ecs/a0075/a0075995/wa.pl for byte code...
/home/ecsfs2/ecs/a0075/a0075995/wa.pl compiled, 2 lines read - 783 bytes written, 23 ms

yes
| ?- wa(2,S).

Sum = 3 ?

yes

---------------------------------------------

では、この動作を追ってみましょう。

wa(2,S)という質問に対し、コード中のwa(N,Sum)がマッチします。マッチの仕方は、

N=2,Sum=Sですね。そしてwa(N,Sum)の右辺を見て、前から順に見ていきます。

M is N-1 より、M=1,そしてwa(M,Sum2)を満たせるか確認するため、またコードに戻り、またwa(N,Sum)とマッチします。ここで変数の名前がかぶっていますが、マッチした段階でwa(N,Sum)をwa(X1,Y1)という感じで、被んないようにしてからやってる(らしい)です。内部では。

んで、X1=0,とし、wa(0,Sum2')へ。同じように、Sum2だとかぶっちゃうのでこう表記しました。

そしたらSum2'=0とすることでwa(0,0)とマッチします!

そしたらSum2 is 1 +0でSum2=1となり、そしてSum is 2 + 1となって、S=Sumとなっているため、S=3となって答えが出てくる!となっているわけです。


ううん、面倒くさい。仕方ないのか・・・
他のプログラミング言語だと sum(3) と聞いたら 6 と返ってくる、みたいな感じなのに、Prologだと答え入れる用の変数を自分で用意しなきゃいけないんですね。
んもう。

で、上では適当だった動作の仕組みの話をもう少し丁寧に。だいたいで。だいたいで!細かいことはなし!
まず、質問が与えられたら、先頭から順に処理していきます。
先頭の節について、コードの中上から順に見て行って、適合するものを探して、マッチさせ、変数を束縛する。
そしてマッチしなかったらコードの中の他のところでマッチするものを探し・・・
なかったらその時点でno、あったならそれで変数を束縛して、次の節の質問へ、という流れだそうです。
なんか字で説明してもわかりにくい。とりあえずいろいろ試してみましょう。

まず、コードを上から順に見ていくということ。
これは普通そうですよね。
つまり、さっきの和を求めるプログラムを以下のように書いちゃうと、

gist7035686




-------------------------------------------------
| ?- consult('wamiss.pl').
compiling /home/ecsfs2/ecs/a0075/a0075995/wa.pl for byte code...
/home/ecsfs2/ecs/a0075/a0075995/wa.pl compiled, 2 lines read - 784 bytes written, 17 ms

yes
| ?- wa(3,Sum).

Fatal Error: local stack overflow (size: 8192 Kb, environment variable used: LOCALSZ)
-------------------------------------------------

こうなっちゃいます。
wa(3,Sum)->wa(2,Sum')->.....->wa(-20,Sum''''''.....')-.>.......となっていってしまったわけですね。
気をつけねば。


そして、質問とコードの実行され方について、めちゃくちゃ分かりやすい(と僕は思いました)例が本に載っていたので、これだけ掲載してみます。

gist7035587




"tab(1)"は、空白を一文字分出力する命令です。
そして、go2.と尋ねると、以下のようになります。

-------------------------------------------
| ?- go2.
a x y b x y

yes

-------------------------------------------

動作を追ってみましょう。
まず、go2という質問に対し、コードを上から見ていって、マッチするものを探すと、
go2 :- rf,rg,fail.
を見つけます。
そして、rfを満たそうとして探していくと、
rf :- f(X),write(X),tab(1).
を見つけます。そしてf(X)を満たそうとして、
f(a).
を見つけ、Xをaとマッチングさせます。で、f(X)がX=aで満たされたので、rf内のXは一旦すべてaにし、rfの次の節、write(a)に移り、aを出力します。そしてtab(1).も実行。
次にrfが満たされ終わったので、go2 :- rf,rg,fail.に戻って、rgを満たそうとします。
そして満たし終わったあと、failと書いてあるので、このマッチングのさせ方はミスだと判断し、frでの束縛はそのままで、rgの別解を探します。
そしてその結果yが出力され・・・・と続いていくわけです。最終的に
go2 :- rf,rg,fail.
が満たせないとわかると、それより下のgo2を探して、一番下の行にあるgo2.を見つけ、yesと返した。という動作ですかね。
厳密にはヴァリアントとかインスタンスとかそういうので決まってる、という考え方らしいのですが、その辺はまぁいいでしょう。
あとあと響いてこないことを祈るばかりです。

これで一応基礎の基礎はできた、という感じですかね。
さて、練習問題解いていくぞー
今日はここまで。

広告を非表示にする