［今日のPiet］GridPietGenerator入門編６（ユーザー入力２）

どもです。

GridPietGeneratorの入門編、第６弾です。

今回で命令全て説明するぞー！

「ohce」を実装する

今回のテーマは「ohce」です。

「ohce」を知ってますか？　多分ご存知ないのではと思います。

いま私が命名しましたゆえ。

「echo」を逆から書くと「ohce」

入力した内容をそのまま出力するプログラムは「echo」なので、

入力した内容を逆順に出力するプログラムを「ohce」と呼ぶことにします。

今回はこの「ohce」を実装します。なんという無理矢理感。

プログラムの方針

今回のプログラムの方針です。

文字入力を繰り返し、入力ごとに文字をスタックにプッシュする。
ただし、半角スペースが入力されたら繰り返しを終了する。
スタックにプッシュされた文字を全て出力する。

これだけです。

たとえば、「echo 」と入力すると、「ohce」と出力を返します。

シンプルですが、少々考えなければならない点があります。

ループの作り方

今回は繰り返し処理を含むので、ループが必要です。

入力時・出力時それぞれでループするので、２つループを作ります。

注意しなければならないのは、

ループ中のスタックの状態変化と、 出力ループの止め方です。

ループ中のスタックの状態変化

今回は入力した値を一旦スタックにとどめ置く必要があります。

したがって、ループ１回ごとにスタック中の値の数は増えていきます。

たとえば、't'、'e'、's'、't'という文字を順次入力すると、

他にスタックに何もいなければ、スタックの状態はつぎのように変化していきます。

f:id:y-mos:20210825201128p:plain — 't'を入力→'e'を入力→'s'を入力→'t'を入力

f:id:y-mos:20210825201136p:plain — 't'を入力→'e'を入力→'s'を入力→'t'を入力

これまで、ループで同じ位置を通過する際には、スタックの状態が同じになることが必要でした。

しかし、今回はスタックに値を保存する必要があるので、上図のように変化させざるを得ません。

これを前提としてスタックを扱う必要があります。

出力ループの止め方

さて、問題はこちらです。

出力ループでは、outc命令を繰り返してスタック内の値を出力するのですが、

そのループはどのように止めましょうか。

実は現状では、このループを止める手立てはありません。

Pietの命令にも、処理フローファイル用の命令にも、

スタックが空かどうかを判別する手段はないからです。

そこで、文字の終端を示す値を一つプッシュしておきます。

C言語の文字列でいう「ヌル文字　\0」です。

入力を開始する前に、ヌル文字の役割をする値0をスタックに入れておきます。

ヌル文字の考え方そのまんまですね。

f:id:y-mos:20210825202216p:plain — ヌル文字→'t'を入力→'e'を入力→'s'を入力→'t'を入力

f:id:y-mos:20210825202221p:plain — ヌル文字→'t'を入力→'e'を入力→'s'を入力→'t'を入力

こうしておけば、出力ループでは

これから出力しようとしている値が、0かそうでないかで終了判定ができます。

f:id:y-mos:20210825202238p:plain — 't'を出力→'s'を出力→'e'を出力→'t'を出力→0なので出力終了

f:id:y-mos:20210825202232p:plain — 't'を出力→'s'を出力→'e'を出力→'t'を出力→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によるトレース画像はつぎのようになります。

f:id:y-mos:20210825203403p:plain — npietによるトレース画像（"test "と入力）

出力はつぎのようになります。

./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を直接プッシュすることができないので、

知っておくと重宝するテクニックかもしれません。

プログラムに戻ります。

超シンプルで書く必要があるかわかりませんが、

１行目でのスタックの変化は、つぎのようになります。

f:id:y-mos:20210825204723p:plain — push1→not

入力ループ

入力ループ部分です。

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行目で作っています。

ここでは、 $32=2\times(2\times{2})\times(2\times{2})$ と分割しました。

f:id:y-mos:20210825205817p:plain — 4行目開始時点→push2→dup→dup

f:id:y-mos:20210825211721p:plain — 4行目開始時点→push2→dup→dup

f:id:y-mos:20210825211742p:plain — mul→dup→mul→mul

f:id:y-mos:20210825211750p:plain — mul→dup→mul→mul

そして、判定部分にはgt命令を使っています。

この流れで、「諸事情」もお察しいただけたかと思います。

gt命令

gt命令は「greater than」の略で、「大なり」”＞”を表す命令です。

gt命令は、スタック最上部の2つの値をポップして、それらの比較結果を1つスタックにプッシュします。

具体的には、ポップした２つの値について、

スタック最上部にあった値よりも、その下にあった値の方が大きい場合、1をプッシュする。
上記以外の場合は、0をプッシュする。

言葉だとややこしいので、図示します。

たとえば、スタックの最上部から、１、２の順で値が積まれていれば、

gt命令によって１がプッシュされます。

上から２番目の値の方が、最上部の値より大きいからです。

f:id:y-mos:20210825212856p:plain — gt命令の実行結果（１）

f:id:y-mos:20210825212901p:plain — gt命令の実行結果（１）

逆に、スタックの最上部から、２、１の順で値が積まれていれば、

gt命令によって０がプッシュされます。

f:id:y-mos:20210825212906p:plain — gt命令の実行結果（２）

f:id:y-mos:20210825212910p:plain — gt命令の実行結果（２）

では、スタックの最上部から、１、１の順で値が積まれていた場合はどうでしょうか。

この場合はgt命令によって０がプッシュされます。

「上から２番目の値の方が、最上部の値より大きい」という条件が成立していないからです。

f:id:y-mos:20210825213255p:plain — gt命令の実行結果（３）

（解説の続き）文字コードの判定

ではプログラムに戻ります。

5行目の初めでgt命令を使っているため、

スタックトップの't'（文字コード116）と32を比較します。

この場合は、't'の文字コート116が32より大きいので、スタックには1が積まれます。

その結果、つぎのif命令で、ラベル:input_loopに飛ぶように判定されるということです。

f:id:y-mos:20210825211802p:plain — 5行目の開始時点→gt→if:input_loop:output

f:id:y-mos:20210825213926p:plain — 5行目の開始時点→gt→if:input_loop:output

もう１周追ってみる

if命令から2行目に戻ると、3行目でふたたびinc命令が実行されます。

ここで、2文字目'e'が入力された場合のことを考えます。

このとき、スタックはつぎのように変化していきます。

f:id:y-mos:20210825214912p:plain — 3行目開始時点→inc→dup

f:id:y-mos:20210825215045p:plain — 3行目開始時点→inc→dup

f:id:y-mos:20210825215039p:plain — 4行目開始時点→push2→dup→dup

f:id:y-mos:20210825215009p:plain — 4行目開始時点→push2→dup→dup

f:id:y-mos:20210825215112p:plain — mul→dup→mul→mul

f:id:y-mos:20210825215118p:plain — mul→dup→mul→mul

f:id:y-mos:20210825215134p:plain — 5行目の開始時点→gt→if:input_loop:output

f:id:y-mos:20210825215149p:plain — 5行目の開始時点→gt→if:input_loop:output

ここからわかることは、スタックのうち、3行目のinc命令で追加した値より

下の部分はループ内で変化しないということです。

つまり、図のオレンジ色部分、前回のループで追加した値't'は、

ループ内処理によって、変更を受けていないのです。

このことが確認できれば、この後いくつ文字を足して行っても、

同様にしてスタックに値を積んでいくことがわかります。

半角スペースを入力した場合

では、半角スペースを入力したときはどのような挙動になるでしょうか。

3-4行目の部分では、スタックに半角スペースを積み、

それを複製して、続いて数値32をスタックに積みます。

ここまでは一緒です。

異なるのは5行目の部分です。その部分だけ図示してみます。

（半角スペースを入力するまでに、"test"の4文字が入力されていたとします。）

f:id:y-mos:20210825220308p:plain — 5行目の開始時点→gt→if:input_loop:output

f:id:y-mos:20210825220318p:plain — 5行目の開始時点→gt→if:input_loop:output

今回は、半角スペースの文字コード32と、値32の比較をしていますが、

「 $32\gt32$ 」が成立しないので、スタックには0が積まれます。

こうして、続くif命令では、ラベル:outputにジャンプするのです。

出力ループ

さて、入力でだいぶパワーを割いてしまったので、

出力はさらっといきたいです。。。

まず、8行目のpop命令で、最後に入力された半角スペースを取り除きます。

f:id:y-mos:20210825220326p:plain — 8行目最初のスタックの状態→pop

f:id:y-mos:20210825221821p:plain — 8行目最初のスタックの状態→pop

次に、9行目のラベル:output_loopに入りますが、

この9行目のラベル:output_loopと、12行目の「goto:output_loop」の間で

ループが構成されています。

出力ループの方は、ループの基本形に近い形をしています。

10行目では、現在のスタック最上部の値が0かどうかを判定しています。

たとえば、今の場合は、スタックはつぎのように変化します。

f:id:y-mos:20210825222319p:plain — 10行目最初の状態→dup→if::end

ここではスタック最上部が0でないため、ifのひとつ目のラベルにジャンプします。

ですが、ifのひとつ目のラベルは省略されているため、

つぎの命令、すなわち11行目の命令にジャンプします。

そして11行目では、具体的な処理をしています。

ここではoutc命令による出力命令です。

f:id:y-mos:20210825222537p:plain — 11行目最初の状態→outc

ここでは、スタック最上部の's'が出力されます。

この後ループの最初9行目に戻っていきます。

お分かりのように、スタックに積まれた値が１つ減った状態で、

つぎのループに突入します。

ここまでの処理は、全てスタックの最上部のみに対して

処理をしていたことに注意してください。

つまり、つぎのループでも最上部の値しか操作対象にはなりません。

f:id:y-mos:20210825223039p:plain — 10行目最初の状態→dup→if::end

f:id:y-mos:20210825223049p:plain — 11行目最初の状態→outc

このループでは's'が出力されます。

このように、ループごとに一文字ずつ判定と出力の処理を実施します。

そしてその都度、スタックの値は減っていきます。

文字列を全て出力すると、スタックトップが0となります。

この状態で10行目を通ると、

f:id:y-mos:20210825223509p:plain — 10行目最初の状態→dup→if::end

　最後のif命令でラベル:endにジャンプするよう判定されます。

最後に、スタックに残った0をpopして、完了です。

おわりに

お疲れ様でした。やっぱりそれなりの文字数になりましたね。

数え間違えてなければ、今回でPiet命令は全て解説しきったことになります。

次回は残りの命令のチートシートをあげます。

じゃ、今回はこの辺で。

では。