第326回 シーズン33 エピソード6

スタックとキュー（後編）

スタックを実装しよう

スタックを作ろう

僕「あっ、これは、もしかして……テトラちゃんが好きな《知らないふりゲーム》になってる？」

テトラ「そうなんですよ！　スタックを使う側では、スタックがどう実装されているか知らなくていい。 スタックを作る側では、スタックをどう使うかを知らなくていい。 両者が知るべきなのは、NEW-STACKとPUSHとPOPとIS-EMPTY-STACKの入力と出力だけです。これらのインタフェースを守っていれば……守っているものを……スタックと呼ぶんですっ！」

僕「おもしろい！　これはすごくおもしろい話だねえ！」

テトラ「おもしろいですよねえ！」

僕「ということは、具体的にはPUSHやPOPという手続きを作る……プログラミングしていくことになるのかな、テトラ先生！」

テトラ「先輩、『テトラ先生』はやめてください……ちょっと恥ずかしくなってきました」

僕「わかったけど、でもテトラちゃんの《講義》はとてもわかりやすいよ。教え方がうまいんだ」

テトラ「あ、ありがとうございます。教えるといっても、あたしは習ったことをお伝えしているだけなんです……あ、でも、 あたし、先輩に教えていて思ったんですが、 いろいろ話してもらった方が教えやすいんですね」

僕「話すというのは、教えてもらう側が？」

テトラ「そうです。あたしが先輩に少し何かを伝えますと、 先輩はいろいろ質問を返してきます。その質問があると、あたしはとても話しやすくなります。 それから、先輩はご自身が考えたことを語ってくださいます。あたしの話はそこに導かれることもよくあります」

僕「なるほど。その感覚は僕もよくわかるよ。 ほら、以前ノナちゃんの話をしたことがあるよね（『数学ガールの秘密ノート／学ぶための対話』）。 あのときは、数学を教えるのがすごく難しかった。 話しても反応があまり帰ってこないから、わかったのかどうかがわからないし、 どこまでわかったかもわからない。ノナちゃんが悪いわけじゃないんだけどね」

テトラ「はいはい。たとえばあたしが先輩に《スタック》や《ステップワイズ・リファインメント》のことをお話ししたときに、 もしも先輩が無表情で無言だったら……あたしはたぶん何も話せなくなると思います。 もっと詳しくお話しした方がいいのか、どんどん次に進んでいいのかがわからないからです」

僕「無表情、試してみる？」

テトラ「や、やめてくださいよう……ああ、でも、あたし、 授業中に先生に対して同じことをやってるかもしれません。 先生が『わかりましたか』と尋ねたときに、きちんと反応を返していなかったかも。 それって先生にとっては教えるのが難しい生徒ってことですよね……」

僕「いやあ、テトラちゃん。 テトラちゃんが授業中に反応を返してないなんてことは絶対にないと思うよ……」

テトラ「そうでしょうか……だといいのですが」

僕「うん。自信を持って言えるよ！」

新たなスタックを作る

テトラ「では、双方向リストでスタックを実装するというお話に入ります。 最初はNEW-STACKです。この手続きを呼び出すと、要素が一個も含まれていない双方向リストを作って返します。 それだけです」

僕「List 29ではNEW-NODEを呼び出している。 prevフィールドもnextフィールドも自分自身を指しているリストヘッドだけが作られて、 そのアドレスを返したということだよね（第324回参照）」

テトラ「はい、その通りです。要素が一つもない双方向リストを作ったことになります」

僕「実際には、 $$ S \leftarrow \textrm{NEW-STACK}() $$ のようにして、スタックSを使うことになるんだよね？」

テトラ「そうです」

僕「でもね、NEW-STACKって、単にNEW-NODEを呼び出しているだけだから、 わざわざNEW-STACKを作らなくてもいいんじゃないの？」

テトラ「ええ、そうですね。ただ、このようにすると実装が隠蔽されて都合がいいんです」

僕「いんぺい？　隠蔽されて都合がいい？」

テトラ「あ、い、いえ。隠蔽というと不穏な雰囲気が漂いますけれど、よからぬお話ではありません。 先ほどの《知らないふりゲーム》のお話と同じです。どんなふうにスタックを実装するかを見せないようにするというだけのことです」

僕「そうか……スタックを《使う》側に対して隠すということ？　『双方向リストによって実装している』ことを隠蔽しているのかな？」

テトラ「はい、そういうことになります」

僕「スタックを《作る》側には隠蔽しているわけじゃないよね。まあ、それは当然か」

テトラ「はい。いまのあたしたちはスタックを《作る》側にいて、もちろん、双方向リストでスタックを実装することを知っています。 先輩のおっしゃる通りです。隠蔽してはいません」

僕「うん、ここまでは理解したと思うよ」

スタックにPUSHする

テトラ「NEW-STACKの次に実装する手続きはPUSHです。スタックSと、スタックに積む値vが入力になって、 これまで練習してきたようなリンクの付け替えを行います。 やっていることは……」

僕「……うん、List 30は読めるよ。2行目では、スタックに積むvの値をvalueフィールドに入れたノードを一つ確保している。 そして3行目から6行目までで、そのノードを双方向リストの先頭に入れている。たとえばPUSH(S, 123)を呼び出したら、こんなふうになるよね」

テトラ「はい、その通りです！　ここでも、PUSHという手続きの中では、双方向リストであることを利用しているわけですが、 PUSHを呼び出す側では、スタックが双方向リストで実装されていることは知りません。 入力として与えているのがスタックSと値のvだけだからです」

僕「確かに、この二行だけを見た場合、Sが双方向リストで実装されているかどうかはわからないね。 《使う》側には知らされていない。隠蔽されている。知らされているのは、Sに対してPUSHやPOPができるということだけ……？」

テトラ「そうです！　講師の先生は《インタフェースを設計する》とおっしゃっていました。 どのような手続きのセットを用意するか、それぞれの手続きは何を入力とし、何を出力とするか……それがインタフェースの設計です。 もちろん、インタフェースがどうなっていても、つじつまがあえばプログラムは動きます。 でも、実装をどこのレベルまで見せるか、そしてどこのレベルまで隠蔽するかによって、プログラムが修正しやすくなったり、しにくくなったりするそうです」

僕「……そうか。プログラムを考えるときには、そういう工学的な観点が出てくるってことなのかな。プログラムを修正しやすいとか、どこまでを隠蔽するかとか……」

テトラ「工学的な観点……」

僕「数学の場合には修正しやすいかどうかなんて考えないし、どこまで隠蔽するかなんて考えない……いやいや、待てよ。 《知らないふりゲーム》だと考えてみると、そうでもないかな」

テトラ「先輩は何を考えていらっしゃるんですか？」

僕「うん、あのね。インタフェースの設計って、《群》や《環》と似ているよね」

テトラ「えっ？」

僕「群では、積という演算が定義されていて、単位元があって、結合法則などの法則を満たしていた。 そして、そのようなものを《群》と呼んだ。 それが実際には足し算だろうがビット演算だろうが、あみだくじだろうが《群》だった。《群》と見なせた。 環では、積と和という演算が定義されていて、分配法則などを満たすべき法則が決まっていた。 そして、そのようなものを《環》と呼んだ。 それが整数環だろうが、多項式環だろうが、《環》だった……似てない？」

テトラ「ああ、そうですね！　《スタック》も似ています。PUSHとPOPというものがあれば、 それが何で実装されていようともスタックと呼べます。そういう意味ですね？」

僕「うんうん。インタフェースの設計をまちがえるというのは、 一般的な群に関する証明でビット演算であることを仮定したり、 一般的な環に関する証明で整数環であることを仮定しちゃうのに似ているかも……って思ったんだよ」

テトラ「似てると思います！」

スタックが空かどうかを調べる

僕「じゃあ、次はPOPを双方向リストで実装する？」

テトラ「その前に、スタックが空かどうかを調べるIS-EMPTY-STACKを実装します。List 31になります。 これは双方向リストのときと同じです（第324回参照）」

僕「ああ、そうだね。List 31では、要素数が0であることを使うんじゃなくて、 もっと直接的にリストヘッドが自分自身を指しているかどうかで空かどうかを判断している」

スタックからPOPする

テトラ「次にPOPですが……」

僕「これはPUSHの逆だね。リストヘッドから先頭の値を得ればいい」

テトラ「だいたいはそうなんですが、注意が必要になります。エラー処理が必要になるからです」