逆転を狙う工大生の日々

絶賛留年中の落ちこぼれがなんとか頑張ろうとしている日記です

Prologのお勉強1~スタックを実装~

演習でPrologという論理型言語を学んでおります。ちなみに去年軽く落単しましたので再履修です。今より遥かにプログラミング出来なかったので(今も出来ているとはいいがたいですが)、CやJavaと全く異なるPrologなんて出来っこなかったわけで。

 

というわけで、SWI-Prologを導入して教科書の演習問題を細々と解いていました。少し慣れてきたので、昨日やったスタックをPrologで実装することに挑戦してみました。

 

使用している教科書は、

Prologへの入門/I.Bratko 著,安部憲広 訳」

です。今後のPrologはすべてこれです。

  http://www.geocities.jp/m_hiroi/prolog/prolog01.html

たまにこのサイトを使うかもしれません。とても細かくまとめられてます。

実装したい機能

・スタック(リスト)を与えると、そのスタックポインタを返す(機能1)

・ポップ(機能2)

・プッシュ(機能3)

 

これらの機能を実現するためにまずいくつかの関数を別に定義します。しなくてもいいのでしょうが、別に定義しておくことで、見栄えとあとから追加する場合などに便利だと思ったからです。今回は、

・「二つのリストをくっつけたリストを返すconc/3」

・「リストの要素数を求めるlist_elem_num/2」

を定義します。

-conc/3-

conc([],L,L).
conc([X|L1],L2,[X|L3]) :- conc(L1,L2,L3).

conc([a,b,c],[d,e],L3)のとき、L3=[a,b,c,d,e]となります。この関数は今後も度々でると思います。教授が興奮してこの関数の発明は革命的ですとか言ってました。確かに最初に考えた人は凄いですね。

 -list_elem_num/2-


list_elem_num([],0).
list_elem_num([X|Tail],Num) :-
    list_elem_num(Tail,Num1),
    Num is Num1 + 1.

「リストが空の時は要素数が0」を終了条件として、再帰処理でリストの要素数Numを求めてます。

さて、これで準備がととのったので、一気にまとめて貼ります。



% スタック(Spはスタックポインタ)
stack([],0).
stack(List,Sp) :- list_elem_num(List,Sp).

% ポップ(先頭から要素を取り出す)
% 第二項は取り出した要素、第三項はポップ後のスタック
pop([],X,[],0) :- false.
pop([X|Tail],X,Tail,Sp) :-
     stack(Tail,Sp).

% プッシュ(先頭に要素を追加する)
% 第一項は追加したい要素、第三項はプッシュ後のスタック
push(X,[],[X],1).
push(X,List,Newlist,Sp) :-
     conc(X,List,Newlist),
     stack(Newlist,Sp).

まずstackを定義したstack/2についてですが、現在の要素の先頭のインデックスをn-1とすると、そこから一つ足したnをスタックポインタのインデックスとしていました。配列のインデックスは0から始まるので、リストの要素数がそのままスタックポインタのインデックス数と一致します。それ故にシンプルな構造です。

続いてpop/4についてです。

pop(_対象リスト,_ポップした要素,_ポップ後のリスト,ポップ後のスタックポインタ)

を入力します。ポップはスタックの一番上の要素を取り出すので、先頭を取り出したあとのTailをstack/2に渡せばポップ後のスタックポインタが求められます。またTailはポップ後のリストそのものであるため、こちらもシンプルな構造となります。

最後にpush/4

push(_プッシュする要素,_対象リスト,_プッシュ後のリスト,プッシュ後のスタックポインタ)

を入力すると、まずプッシュする要素と対象リストを結合した、プッシュ後のリストを生成し、その生成したリストのスタックポインタを求めるという手順です。

 

実行結果は

f:id:ikuth:20140507233701p:plain

ひたすら見にくいですね。申し訳ないです。

List = [0,1,2,3,4,5]

を2回ポップした後、10をプッシュするという問い合わせです。それぞれの操作後のスタックポインタ値も出しています。List4の下にSp4=5と出力されるのではなく、Sp2 = Sp4, Sp4 = 5とされる理由はよくわかんないです。一応プッシュとポップ操作はできていることがわかります。よかったよかった。

 

自由課題のテーマ考えないとなあ。それでは。