どもです。
GridPietGeneratorの 入門編、第６弾です。
今回で命令全て説明するぞー！
「ohce」を実装する
今回のテーマは「ohce」です。
「ohce」を知ってますか？ 多分ご存知ないのではと思います。
いま私が命名しましたゆえ。
「echo」を逆から書くと「ohce」
入力した内容をそのまま出力するプログラムは「echo」なので、
入力した内容を逆順に出力するプログラムを「ohce」と呼ぶことにします。
今回はこの「ohce」を実装します。なんという無理矢理感。
プログラムの方針
今回のプログラムの方針です。
- 文字入力を繰り返し、入力ごとに文字をスタックにプッシュする。
- ただし、半角スペース
が入力されたら繰り返しを終了する。 - スタックにプッシュされた文字を全て出力する。
これだけです。
たとえば、「echo 」と入力すると、「ohce」と出力を返します。
シンプルですが、少々考えなければならない点があります。
ループの作り方
今回は繰り返し処理を含むので、ループが必要です。
入力時・出力時それぞれでループするので、２つループを作ります。
注意しなければならないのは、
ループ中のスタックの状態変化と、 出力ループの止め方です。
ループ中のスタックの状態変化
今回は入力した値を一旦スタックにとどめ置く必要があります。
したがって、ループ１回ごとにスタック中の値の数は増えていきます。
たとえば、't'、'e'、's'、't'という文字を順次入力すると、
他にスタックに何もいなければ、スタックの状態はつぎのように変化していきます。
→ 
→ 
→ 
これまで、ループで同じ位置を通過する際には、スタックの状態が同じになることが必要でした。
しかし、今回はスタックに値を保存する必要があるので、上図のように変化させざるを得ません。
これを前提としてスタックを扱う必要があります。
出力ループの止め方
さて、問題はこちらです。
出力ループでは、outc命令を繰り返してスタック内の値を出力するのですが、
そのループはどのように止めましょうか。
実は現状では、このループを止める手立てはありません。
Pietの命令にも、処理フローファイル用の命令にも、
スタックが空かどうかを判別する手段はないからです。
そこで、文字の終端を示す値を一つプッシュしておきます。
C言語の文字列でいう「ヌル文字 \0」です。
入力を開始する前に、ヌル文字の役割をする値0をスタックに入れておきます。
ヌル文字の考え方そのまんまですね。
→ 
→ 
→ 
→ 
こうしておけば、出力ループでは
これから出力しようとしている値が、0かそうでないかで終了判定ができます。
→ → → →
これで良さそうです。
ちょっとだけお断り
さて、今回半角スペース（文字コード32）が入力されたら終了としましたが、
諸事情により、文字コード32以下になったら入力ループ終了とします。
諸事情の内容については、前回同様、お察しください。
プログラム
さて、以上を踏まえると、プログラムはつぎのようになります。
push1 not :input_loop inc dup push2 dup dup mul dup mul mul gt if:input_loop:output :output pop :output_loop dup if::end outc goto:output_loop :end pop end
今回もPiet化したコードを先に示します。
npietによるトレース画像はつぎのようになります。
出力はつぎのようになります。
./npiet ohec.ppm -tpic -tpf 16 ? test ? ? ? ? tset
自分でやってみて気づいたのですが、１文字ずつ入力しようとして、
一文字入力→エンターとすると、
./npiet ohce.ppm -tpic -tpf 16 ? t ? t
その一文字で処理を終了してしまうようです。
おそらく、改行文字の文字コードが、32以下だからだと思うのですが。
一気に"test"と入力してからエンターを押すと、
１つ目の例のように出力されるようです。
とにもかくにも、逆順に出力はされているようです。
解説
では解説にいきます。
ヌル文字の準備
まず1行目で「ヌル文字」である0をプッシュしています。
が、不思議な命令の並びですね。
ここでnot命令について解説します。
not命令は、スタックの最上部の１つの値をポップし、
ポップした値に応じて値を1つスタックにプッシュします。
具体的にどのような値をプッシュするかというと、
- ポップした値が0ならば、1をプッシュする。
- ポップした値が0でないならば、0をプッシュする。
not命令は、１つ値をポップして、１つ値をプッシュするので、
結果的にはスタック内の値の数を変化させません。
not命令の本来の使い方は、
演算対象の値をtrue/falseと同じ真理値と見なして、
その論理否定を行うことです。
ですが、ちょっと捻った方法としては、今回のように、
0をプッシュする手っ取り早い方法として利用する事もできます。
Pietは0を直接プッシュすることができないので、
知っておくと重宝するテクニックかもしれません。
プログラムに戻ります。
超シンプルで書く必要があるかわかりませんが、
１行目でのスタックの変化は、つぎのようになります。
→
入力ループ
入力ループ部分です。
2行目の:input_loopと、5行目の「if:input_loop:output」の間で、
ループを形成しています。
5行目がif命令であることから、ループ継続の条件は、
if命令が実行される直前に、スタックの最上部の値が0でないことです。
（仮にif命令が実行される直前に、スタックの最上部の値が0であったとすると、
ラベル:outputに飛び、ループから外れてしまうからです。）
さて、3行目の先頭で、inc命令を実行しています。
inc命令は、標準入力から文字を１つ読み取り、入力された値（文字コード）をスタックにプッシュします。
たとえば、初回ループのinc命令では、入力された文字列の１文字目の't'を読み込みます。
また、3行目の最後ではdup命令で、入力された文字't'を複製します。
お察しいただけるかと思いますが、複製する理由は、
入力された文字't'の文字コードが、32以下かどうかを判定するためです。
3行目ではスタックはつぎのように変化します。
ここでは、１文字目't'を入力した時を想定したスタックの状態を示します。
→ → 
文字コードの判定
次に、dup命令で複製した値が32以下かどうかを判定します。
比較対象である32を4行目で作っています。
ここでは、と分割しました。
→ 
→ 
→ 
そして、判定部分にはgt命令を使っています。
この流れで、「諸事情」もお察しいただけたかと思います。
gt命令
gt命令は「greater than」の略で、「大なり」”＞”を表す命令です。
gt命令は、スタック最上部の2つの値をポップして、それらの比較結果を1つスタックにプッシュします。
具体的には、ポップした２つの値について、
- スタック最上部にあった値よりも、その下にあった値の方が大きい場合、1をプッシュする。
- 上記以外の場合は、0をプッシュする。
言葉だとややこしいので、図示します。
たとえば、スタックの最上部から、１、２の順で値が積まれていれば、
gt命令によって１がプッシュされます。
上から２番目の値の方が、最上部の値より大きいからです。
→ 
逆に、スタックの最上部から、２、１の順で値が積まれていれば、
gt命令によって０がプッシュされます。
→ 
では、スタックの最上部から、１、１の順で値が積まれていた場合はどうでしょうか。
この場合はgt命令によって０がプッシュされます。
「上から２番目の値の方が、最上部の値より大きい」という条件が成立していないからです。
→
（解説の続き）文字コードの判定
ではプログラムに戻ります。
5行目の初めでgt命令を使っているため、
スタックトップの't'（文字コード116）と32を比較します。
この場合は、't'の文字コート116が32より大きいので、スタックには1が積まれます。
その結果、つぎのif命令で、ラベル:input_loopに飛ぶように判定されるということです。
→ 
→
もう１周追ってみる
if命令から2行目に戻ると、3行目でふたたびinc命令が実行されます。
ここで、2文字目'e'が入力された場合のことを考えます。
このとき、スタックはつぎのように変化していきます。
→ 
→ 
→ 
→ 
→ 
→ 
→ 
ここからわかることは、スタックのうち、3行目のinc命令で追加した値より
下の部分はループ内で変化しないということです。
つまり、図のオレンジ色部分、前回のループで追加した値't'は、
ループ内処理によって、変更を受けていないのです。
このことが確認できれば、この後いくつ文字を足して行っても、
同様にしてスタックに値を積んでいくことがわかります。
半角スペースを入力した場合
では、半角スペースを入力したときはどのような挙動になるでしょうか。
3-4行目の部分では、スタックに半角スペースを積み、
それを複製して、続いて数値32をスタックに積みます。
ここまでは一緒です。
異なるのは5行目の部分です。その部分だけ図示してみます。
（半角スペースを入力するまでに、"test"の4文字が入力されていたとします。）
→ 
→ 
今回は、半角スペースの文字コード32と、値32の比較をしていますが、
「」が成立しないので、スタックには0が積まれます。
こうして、続くif命令では、ラベル:outputにジャンプするのです。
出力ループ
さて、入力でだいぶパワーを割いてしまったので、
出力はさらっといきたいです。。。
まず、8行目のpop命令で、最後に入力された半角スペースを取り除きます。
→ 
次に、9行目のラベル:output_loopに入りますが、
この9行目のラベル:output_loopと、12行目の「goto:output_loop」の間で
ループが構成されています。
出力ループの方は、ループの基本形に近い形をしています。
10行目では、現在のスタック最上部の値が0かどうかを判定しています。
たとえば、今の場合は、スタックはつぎのように変化します。
→ 
→
ここではスタック最上部が0でないため、ifのひとつ目のラベルにジャンプします。
ですが、ifのひとつ目のラベルは省略されているため、
つぎの命令、すなわち11行目の命令にジャンプします。
そして11行目では、具体的な処理をしています。
ここではoutc命令による出力命令です。
→ 
ここでは、スタック最上部の's'が出力されます。
この後ループの最初9行目に戻っていきます。
お分かりのように、スタックに積まれた値が１つ減った状態で、
つぎのループに突入します。
ここまでの処理は、全てスタックの最上部のみに対して
処理をしていたことに注意してください。
つまり、つぎのループでも最上部の値しか操作対象にはなりません。
→ 
→
→ 
このループでは's'が出力されます。
このように、ループごとに一文字ずつ判定と出力の処理を実施します。
そしてその都度、スタックの値は減っていきます。
文字列を全て出力すると、スタックトップが0となります。
この状態で10行目を通ると、
→ 
→ :endにジャンプするよう判定されます。
最後に、スタックに残った0をpopして、完了です。
おわりに
お疲れ様でした。やっぱりそれなりの文字数になりましたね。
数え間違えてなければ、今回でPiet命令は全て解説しきったことになります。
次回は残りの命令のチートシートをあげます。
じゃ、今回はこの辺で。
では。
