You...というわけで、『Glaeja』が持っている「ワケがわからない」ものの1つである「スタック」の解説エントリです。文字列解析エンジンと続いた「ワケがわからない」解説エントリも(多分)最後となります。LIFO)の構造で保持するものです(wikipedia参照)。イメージがわきやすいようにすると、こんな感じでしょうかw(この画像はココの商品ですね)要するに、箱1つに何らかのデータが1つ入っていて、それらを積み重ねることで多数のデータの集合体を表す。データを追加するには積み重なった箱の一番上にデータ入りの箱を新たに置くしかない、データを取り出すのも一番上の箱からしか取り出せない、という感じです。説明にいちいち写真使ってられませんので、イラストで描くことにしましょう。図にあるように、追加したり取り出したりできる一番上の部分を「最上段」とか「トップ」「スタックトップ」といい、重なっている一番下の部分を「底」「スタックの底」といいます。データを格納している箱のことを「段」といったりします。箱の中にどんなデータを入れることができるか、は実行環境依存で、『Glaeja』の場合は「実数のみ」となっています。スタックが「箱が積み重なる」イメージだとすると、イラストでも上図のように箱を上に重ねていくべきなんでしょうが、それでは高くなりすぎて図示しにくいので、今後は下図のように横倒しにしたイメージで考えていきましょう。横倒しに表記した場合、向かって左端が「底」、右端が「トップ」になります。ちなみに、スタックに1つもデータがない(図でいうと1つも箱がない)状態のことを「スタックが空である」とか「空のスタック」といいます。~プッシュとポップ~では、このスタックにデータを追加したり取り出したりしてみましょう。空のスタックに、最初に「2」を追加し、次に「7」を追加、最後に「0」を追加する様子を図に示すと、以下のようになります。このようにスタックにデータを追加することを「プッシュする」とか「積む」とかいいます。プッシュは必ずスタック最上段におこなわれます。上図スタックからデータを取り出してみましょう。データの取り出しはかならずスタック最上段からおこなわれます。このようにデータをスタック最上段から取り出すことを「ポップする」といいます。このとき、プッシュしたのとは逆の「0」→「7」→「2」の順にデータがポップされていることに注目してください。LIFO)』ということです。LIFO)』により、『スタックにプッシュしたデータは、ポップされるまで記憶される』という「スタック」の持つ重要な特徴がもたらされるわけです。2.スタックを使った演算と後置記法これで、プッシュとポップというスタックの基本操作が理解できたかと思います。「スタック」というデータ構造を使うのでしょうか。他のデータ構造ではダメなんでしょうか?それは、スタックには他のデータ構造にはないいくつかの利点データ構造の実装が簡単スタックを使った「演算」ができるデータを「後回し」にできるがあるからです。1.はともかく、2.3.はどういう意味なんでしょうか。3.の「後回し」にできる、というのは「データを記憶しておける」ということです。この性質を利用することで、2.の「演算」をおこなうことができる、ということになります。「演算」とは、まぁぶっちゃけ「計算」と同じような意味で、「ある法則に従って計算する」というものです。この演算の従う法則とか手順のことを「アルゴリズム」といいます。コンピュータ内部でおこなわれる処理のほとんどは「演算である」ということができます。数値の加減乗除も「演算」ですし、数値同士の大小を比較するのも「演算」、ある物事が正しいか間違ってるか真偽を判断するのも「演算」です。この「演算(ある法則に従って計算する)」がコンピュータ内部ではどのようなやり方(アルゴリズム)でおこなわれているのでしょうか。「12+34」という演算をおこなう場合、兎にも角にも「12」と「34」という2つの数値をどこかに記憶しておかないといけません。演算結果である「46」という数値も同様に記憶する必要があるでしょう。このようなものを記憶するのに「スタック」を利用しよう、というわけです。やり方としては、「12」と「34」という2つの数値をスタックにプッシュして記憶しておいて、足すという演算をおこなうときには2つをポップして足し算してやり、その結果を代わりにスタックにプッシュして演算は終了です。上の例でいう「12」や「34」のような『演算されるもの』のことを「項」、「+」のような『どのような演算をおこなうか』を表す記号のことを「演算子」、「12+34」のように項と演算子で記述された演算全体のことを「式」といいます。データの記憶装置として「スタック」が利用できるとわかったので、実際に「12+34」という演算をおこなってみたいところなんですが、ここでちょっと面倒なことがあります。それは、「演算の前に『12+34』という文字列を解析して『「12」と「34」を足す』という意味を把握する」という文字列解析処理が必要なんですが、それが実に面倒くさいんですよね。面倒くさいかというと、下図のような感じです。『12+34』という文字列を解析すると、『「12」と「34」を足す』という意味を把握するのに、カーソル位置のマークして先読み、といった面倒くさい処理が必要になるわけです。...なんとかならんのでしょうか。+』と書き換えてもらいましょう。途中の空白文字は2つの数値がくっついて「1234」という1つの数値と見間違えないための区切りです。これの文字列解析は、上のものよりはるかに簡単になります。+』と書き換えてあれば、区切りが現れるたびに数値をスタックにプッシュし、演算子が現れたら演算をおこなう、という非常に簡単な手順(アルゴリズム)で処理をおこなうことができるようになります。Notation)」といいます。Notation)」といいます。上図でもわかるように、この後置記法は非常にスタックと相性が良いので、スタックを使う演算はしばしばこの後置記法で記述されます。この後置記法とスタックによる演算には、相性が良い以外に「カッコが不要」という便利さがあります。+』と後置記法で書かれた式は、以下のような順で演算されます。これはよく見ると「3+4」を先におこなっているので、『2+(3+4)』というカッコ付きの式を演算したのと同じ順序になっていることがわかります。*』と書かれた式はどうでしょう(乗算記号の「×」は英文字の"x"と見間違えないようアスタリスク"*"で表されます)。この記述は『2*(3+4)』というカッコ付きの式を演算したのと同じ順序になるわかるかと思います。カッコのない『2*3+4』(2*3を先に乗算し、それに4を加算する)は、どう記述すればいいのでしょうか。+』と記述すればいいのです。このように後置記法を用いることでカッコを用いることなく、カッコ付きと同じように演算順序を制御することが可能となるわけです。...その分、演算順序をコンピュータに指示するために、記述順序を(人間が)調整してやらないといけませんので、一部の方々が力説するほど便利な記法だとは私個人は思いませんが...3.スタックと関数これで、加減乗除という四則演算をスタックによっておこなうやり方(後置記法に書きなおしてスタックを操作する)がわかったかと思います。毛色の異なった演算について見てみましょう。「関数」というものがあります。これは、平たくいうと「ある数を渡すと、ゴニョゴニョと処理をして、ある数を返してくれる」というものです。この関数も演算になります。関数に渡す数のことを「引数」、関数から返される数のことを「返り値」といいます。Bという2つの引数を受け取る)。引数がゼロ個の場合もあります(例えば、「現在のバッテリー残量」を返す関数には引数は不要)。B]という数の集合を返す)。返り値がゼロ個の関数もあります(例えば、スピーカー音量を50%にする関数は返り値を持つ必要がない)。この関数というものをコンピュータ内に実現するにおいて、複数個の引数や返り値を記憶しておくためにもスタックが用いられます。「ある数AのB乗を返す関数pow」というものを考えてみましょう。pow」と記述します。pow」という記述が、スタックを使ってどのように演算されるのか見てみましょう。...こんな感じですかね。呼び出し元が引数をスタックに積んで関数を呼び出し、呼び出された関数がそのスタックから引数を取り出して演算し、返り値をスタックに積んで呼び出し元へ返る、という一連の流れが理解できたでしょうか。してみると、スタックを用いて演算するにおいて、この「関数」と上で記した「(+や*等の)演算子」には本質的な違いがないことがわかります。以降では、面倒くさいので全てまとめて「演算子」と表記することにしましょうw4.多様な演算子さて、演算は、上で見てきたような「(いくつかの)数から、ある数を求める」というもの(数値演算)だけではありません。他にもいろんな種類の演算がありますので、ここではそのいくつかを見てみましょう。B]という2つの状態のどちらに属するか分類する」という操作も演算にあたります。この2つの状態を「正しい(真)か」「正しくない(偽)か」と定めた場合、その結果(演算の返り値)のことを「真偽値(論理値、ブール値ともいう)」といいます。このような「真偽値」を返す演算子というものを考える場合、スタックは真偽値を格納できるようになっていなければなりません。『Glaeja』を含む一部の環境におけるスタックでは数値しか格納できませんので、真偽値を数値で表現しなければなりません。そこで以降では、「偽」を「0」、真を「1(もしくはゼロ以外の数)」と定めておきます。B]について、AがBより小さい」という事柄について、それが正しい(真)か正しくないか(偽)かを返す関数(演算子)について考えてみましょう。このような「2つの項について大小等の関係性を比較する」演算子のことを「2項比較演算子」といいます。これをスタックで演算すると以下のようになります。「真偽値を引数として渡されて、それらを演算した結果を真偽値として返す」演算子というものもあります(論理演算子)。偽]について、"and"を演算」するときのスタックの様子は以下のようになります。5.スタックによる演算の組み合わせ上で見てきたように、スタックを用いた演算では、演算子による返り値も同じスタックに積まれ、記憶されます。+』)や、2つの演算結果を記憶しておいて後で別の演算の引数にすることも可能です。5に等しい場合も含む)なら偽」を返す演算を考えてみましょう。<』で「2がAより小さいなら真」という演算をおこないます。Aを「3」とすると、以下のような様子でしょうか。<』で「Aが5より小さいなら真」という演算をおこないます。<』の結果が積まれていることになります。この2つを『and』で演算することで、「2と5の間にあるなら真、間にないなら偽」という演算がおこなわれました。このように、スタックの持つ「データを記憶しておける」「データの演算ができる」という2つの性質を利用することで、複雑な演算をおこなうことが可能になっているわけです。6.『Glaeja』におけるスタック演算の記述方法さて、これで「スタックを用いた演算」を「後置記法」で記述する、ということが理解できたと思います。『Glaeja』の文字列解析エンジンには「後置記法」を解釈してスタックを操作する機能がありませんからねwですので、『Glaeja』でスタックを用いた演算をおこなわせるには、上図で棒人間がおこなっている「スタックを操作する」ってのを、明示的に指示してやらなければなりません。+』と後置記法に書き換えた上で、それをさらに『2@0/1/\p@3@0/1/\p@+@0/1/\x@』("2"をプッシュ、"3"をプッシュ、"+"を演算子とみなしてスタック演算)とスタック操作用の前方文字置換エスケープキャラクタに書き換えてやらなければなりません(「@0/-1/\p@」は「@p@」、「@0/-1/\x@」は「@x@」と糖衣構文を使って短縮できます)。この後置記法からスタック操作用の前方文字置換エスケープキャラクタへの書き換えは、面倒ではありますが、数値なら「@p@」、演算子なら「@x@」を機械的に書き加えていくだけですので、特に難しいことはないでしょう。and』は、"A"が"3"なら『2@p@3@p@<@x@3@p@5@p@<@x@and@x@』と書き換えられます。結局のところ、難しいのは『やりたい演算を後置記法に書き換える』というところで、これはもう「慣れるしかない」としか言えませんw7.スタック自体を操作する演算子これまでに見てきた演算子は、全て「スタックからいくつか値をポップし、それらを演算して、結果をスタックにプッシュする」という共通の動作をおこなっています。「+」ですと「スタックから2つ値をポップし、それらを加算して、結果をスタックにプッシュ」しています。このように「演算子とはスタックをプッシュしたりポップしたりするものである」と考えると、「プッシュ」や「ポップ」自体も演算子の一種である、と見なせます。ここでは、『Glaeja』に実装されている「プッシュ」「ポップ」以外のスタック自体を操作する演算子を見てみましょう。・dup「dup」は「duplicate(複製)」の略で、演算子の機能は「スタック最上段の値を複製してプッシュ」です。・drop「drop」の機能は「スタック最上段の値を破棄」です。「ポップ」でも破棄はされるのですが、「drop」は表示がおこなわれません。・rot「rot」は「rotation(回転)」の略で、演算子の機能は「スタック底の値をポップして最上段へプッシュ」です。・-rot「-rot」は「rot」の逆の機能を持ち、「スタック最上段の値をポップして底へプッシュ」します。番目の値をスタック最上段へ移動」です。文章ではわかりにくいですが、下図のような操作をおこなうものです。・dump「dump」は、「現在のスタック全段の値を、底を先頭とするコンマ区切りの文字列として出力」します。出力は文字列解析エンジンの結果文字列に出力されます。これで「スタック」の解説はとりあえず終了です。Adsense社による広告配信のために、Cookieやウェブビーコンを使用したデータ収集をおこなっています。ブラウザのCookie機能をオフにすることで、第三者へのデータ送信をおこなわせないことが可能です。詳しくは、Adsense広告の公式プライバシーポリシーをご覧ください。http://www.google.com/intl/ja/privacy.html本ブログで紹介したプログラム等による不利益等は一切関知いたしません。