［今日のPiet］GridPietGenerator入門編４（ループの応用２）
どもです。
今回もGridPietGeneratorの 入門編をお送りします。
今回は、ループ処理の応用２回めです。
おさらい
ループ処理の基本は以下の３点です。
- ループのプログラムテンプレを書く
- コメント「#1」の行で、スタックを初期化する
- コメント「#2」の行で、ループ内の処理をする
まず、ループのテンプレです。
push3 dup mul #1 :loop dup if::end dup outn #2 push1 sub goto:loop :end pop end
次に、コメント「#1」の行でスタックを初期化します。
ここでは、イテレータをループ回数9で初期化しています。
最後に、コメント「#2」の行でループ内処理を記述します。
ここでは、イテレータの値をそのまま出力しています。
基本的には、上記の考え方でループ処理が作れます。
もちろんこれが唯一の方法ではありませんが、はじめはこの方法でループ処理を作ってみて、
慣れてきたら独自の方法にシフトしていくのがいいと思います。
もっといい方法があればぜひ教えてください。
ループの初期化
今回はループの初期化について説明します。
いままでコメント「#1」の行では、ループ回数の初期化のみ行なっていました。
もし「#1」の行で複数の値をプッシュしたらどうなるでしょうか。
初期化時にプッシュする値を増やす
たとえば、プログラムをつぎのように改変します。
元のプログラムに、コメント「#1-1」の行を追記します。
push1 #1-1 push3 dup mul #1 :loop dup if::end dup outn #2 push1 sub goto:loop :end pop end
いままでは「#1」の行の完了時点で、
スタックにはループ回数9のみがプッシュされた状態でした。
一方で、今回のプログラムでは、「#1」の行の完了時点で、
スタックには、数値1と9がプッシュされた状態になります。
この状態からループに突入するとどうなるのでしょうか？
先に答えを言ってしまうと、
数値9はこれまで通り、ループ回数として機能します。
一方で、数値1は、ループ内で全く変更されず、最後まで残ります。
スタック状態変化のトレース
実際にスタックの状態を追って確認してみましょう。
スタック変化の詳細は以前説明したので、割愛します。
なお、詳細な説明はこちら：
ymos-hobby-programing.hatenablog.com
→ 
→ 
→
まず、上記の図はイテレータiが0ではなく、
:loopからgoto:loopまで処理が進んだときのトレース結果です。
ここからわかるように、スタックの下から2番めがイテレータiとして機能しており、
スタック最下部の値には何の操作もされていません。
→ 
→
→ 
→
次に、上記の図は、イテレータiの値が0になり、
ループを抜けるときのトレース結果です。
ここでもやはりスタック最下部の値には何の操作もされていません。
このことから、つぎの予想ができます。
「ループの処理中は、ある深さより深いスタックの値は変更を受けない」
これは冷静に考えると当たり前です。
前回はイテレータiの直下がスタックの底でしたので、
イテレータiより下の値を使わない前提の処理になっているのです。
ですから、イテレータiの下に値があっても、ループ処理を継続できますし、
イテレータiより下の値は、ループ処理によって変更を受けないのです。
ループ内で変数を使う
さて、実はこの話、ループ内で値を保持するのに応用することができます。
前回までに実装してきたループ処理では、
たとえば「ループごとにイテレータiの値を加算していった合計値」
（つまり、１、２、・・・、９の合計値）の算出はできませんでした。
それまでに計算した合計値を、次のループまで保持する手段がなかったからです。
しかし、イテレータiより下にある値は、ループ処理で変更されないため、
合計値をイテレータiの下に置いておけば、次のループまで合計値を保持できます。
合計値を算出するプログラム
では実際にプログラムを見ながら考えていきます。
お題は「1から9までの整数の合計値を算出するプログラム」です。
push1 dup sub #1-1 push3 dup mul #1 :loop dup if::end dup #2-1 push3 push2 roll #2-2 add #2-3 dup outn #2 push2 dup dup add #2-4 dup mul mul outc #2-5 push2 push1 roll #2-6 push1 sub #3 goto:loop :end pop outn end
今回のプログラムも、ベースはループプログラムのテンプレですが、
コメント「#1」の行、「#2」の行、両方に変更を加えています。
コメント「#1」、つまり、初期化の部分では、
複数の値（イテレータと合計値）をプッシュし、初期化しています。
コメント「#2」、つまり、ループ処理の部分も、何行か追記しています。
「#2-1」、「#2-2」、「#2-3」、「#2-6」は新たに追加した部分です。
「#2」はテンプレプログラムそのままです。
「#2-4」、「#2-5」は半角スペースを出力する部分で、前回の使い回しです。
なお、「#3」はテンプレプログラムそのままです。（説明の都合上マークしました。）
Piet化
今回も長くなってしまったので、先にPiet画像だけ載せておきます。
まずPiet画像：
ちょっと縦長ですね。
インタプリタの動き方は今までとあまり変わりないですね。
処理結果はつぎのようになります。
9 17 24 30 35 39 42 44 45 45
ループごとに、その時点での合計値Sの値が出力されます。
イテレータは9から1までデクリメントしていくため、
先頭から順に
9
9+8=17
9+8+7=24
・・・
9+8+7+・・・+1=45
と表示されています。計算結果もあっています。
最後に45が2回表示されているのは、ループを抜けた後に
合計値Sの最終結果を再度表示しているからです。
解説
では、解説です。
初期化
まず、コメント「#1-1」の解説をします。
初期化時に合計値を保持する値を作っておきます。合計値は0で初期化します。
ここでは、push、dup、subを組み合わせてスタックに0をプッシュしています。
→ 
→ 
続けて繰り返し回数である9をプッシュします。
ラベル:loop直前ではスタックは次の状態になっています。
ループ内での役割を示すため、文字式で表しておきます。
iは前回同様イテレータ、Sは求める合計値です。
ループ内処理
次にループ内処理の部分を解説します。
「#2-1」の直前では、スタックはつぎの状態になっています。
「#2-1」の行で、dup命令を実行し、イテレータiを複製します。
そして、次がポイント、roll命令です。
いったん逸れてこの命令を説明します。
roll命令
roll命令は、Pietの命令の中で、おそらく最も複雑で、かつ、重要な命令です。
この命令は、スタックの中身を入れ替えます。
ただし、自由に入れ替えられるわけではなく、
スタック最上部のまとまった領域の中で、順番をずらす操作しかできません。
この命令がなぜ重要なのでしょうか？
それは、Pietではスタックの最上部しか、演算の対象にならないからです。
たとえば、スタックの最深部の値と、最上部の値を足し算したくても、
その2つの値の間に別の値が挟まっていたら、足し算はできません。
add命令は、スタック最上部と、そのすぐ下の値との足し算をするからです。
こんなときに使うのがroll命令です。
roll命令でスタックの中の値を何回かずらせば、
足し算したい2つの値をスタック最上部に移動させることができます。
このように演算のため、スタック最上部に値を集めたいとき、roll命令が活躍します。
具体的な挙動
まず前提として、スタックの状態がつぎのようになっているとします。
roll命令で操作できるのは、スタック最上部を含む連続した領域です。
たとえば、上の図だと、薄黄色部分のa[1]、a[2]、・・・、a[n-1]、a[n]のn個の値などです。
途中の値を飛ばして（たとえばa[1]とa[n]だけを）操作することはできません。
その間のa[2]、・・・、a[n-1]もroll命令の影響を受けます。
ただし操作範囲の深さnは自由に決めることができます。 1
roll命令は、このn個の値の順番をずらします。
順番を自由に入れ替えることはできません。ずらすだけです。
たとえば、つぎのようにスタックをずらしていきます。
→ 
→ 
→ 
→ → ・・・
1つずらすと、スタックの最上部の値が深さnのところに移動し、
その他の値は一つずつ位置が持ち上げられているのがわかります。
roll命令を行う前には、深さnに続けて、ずらす回数cをプッシュする必要があります。
→ 
→ 
この上でroll命令を実行すると、まず、最上部の2つの値がポップされ、
深さnとずらす回数cが読み取られます。
そして、スタックに残った値のうち、上からn個めまでを対象に、ずらす操作をc回実行します。
ー(roll実行)→ 
1回ずらすと最上部の値がn番めの位置に移動するので、この例では、
1回ずらすと、スタックの最上部はa[2]になる。
2回ずらすと、スタックの最上部はa[3]になる。
・・・
c回ずらすと、スタックの最上部はa[c+1]になる。
となることがわかります。
まとめると、つぎのようになります。
- 深さnと、ずらす回数cをプッシュする
- roll命令を実行する
ややこしいですが、今後Pietを扱っていくとなると、
嫌というほど使うことになるので、慣れておくと楽です。
（解説の続き）合計値のroll
では、話をサンプルプログラムに戻します。現在地はコメント「#2-2」の行の先頭でした。
それでは「#2-2」の行のスタックの動きをトレースしてみます。
→ 
→ 
→ 
ここでは操作範囲の長さnが3、ずらす回数cが2なので、
roll命令の動きを追っていくと、つぎのようにスタックが操作されたことになります。
→ 
→
「スタック最上部の値を、上から3番めの位置に移す操作」が、2回実行されています。
これで合計値Sがスタックトップに来ました。
これによって、Sに対して足し算を行うことができるようになります。
（解説の続き）合計値への加算
合計値Sにはイテレータの値iを足し込んでいくので、
S+iを計算し、それをそのままつぎのSとして使えばいいことがわかります。
幸運なことに、現時点でのスタックの最上部の2つはSとiです。
したがって、すぐにadd命令を実行することができます。（「#2-3」の行）
→ 
続く「#2」の行では、スタック最上部の値Sを出力し、
「#2-4」と「#2-5」では、半角スペースを出力しています。
この部分は以前説明した通りなので説明は割愛します。
ymos-hobby-programing.hatenablog.com
なお、「#2-5」の行の終了時点のスタックの状態は、先ほどの図の最後の状態と変わりません。
（解説の続き）スタックの原状復帰
さて、この後はループのテンプレ処理に戻るのですが、
「#2-5」が終了した後、そのままテンプレ処理に戻ってはいけません。
テンプレ処理の「#3」の行の実行時には、
スタック最上部の値はイテレータiだと想定されているからです。
現在スタック最上部の値は合計値Sなので、このままだとおかしなことが起こります。
それを防ぐため、再度roll処理を実行し、スタックの状態を戻してやることが必要です。
それを行なっているのが「#2-6」の行です。
「#2-6」の行のスタック変化をトレースします。
→ 
→ 
→ 
先ほどとは深さnの値が変わっていることに注意してください。
この結果、ループのテンプレ処理の想定通り
「イテレータiがスタック最上部にある状態」になったので、
心置きなくループのテンプレプログラムに処理を譲ることができます。
（解説の続き）ループ脱出後
さて、以上の説明で、ループが回るごとに
イテレータiが合計値Sに足し込まれていくことがわかりました。
それでは、イテレータiが0になったときの挙動を考えてみましょう。
まず、ループ脱出した直後のラベル:endにおいて、スタックはつぎの状態になっています。
せっかくですから、最終的な合計値Sの値は表示させておきたいものです。
一方で、イテレータiの値は0のはずなので、わざわざ表示は不要です。
そこで、表示不要のiはpop命令で、表示が必要なSはoutn命令で、
それぞれスタックから捨ててしまいます。
→ 
→ （空のスタック）
これでスタックに忘れ物もなく、end命令でプログラムをしめくくることができます。
おわりに
またしても長い記事を書いてしまった。。。
とはいえ、roll命令は本当に頻繁に使うのと、
しょっちゅう、わけわからなくなるので、
このぐらい字数かけてでも説明していいものだと思います。
とりあえず一番説明が大変なroll命令が終わったので、
命令の説明のヤマは超えました。
残りの命令は、できれば次回に一気に説明して、
処理の流れに専念した説明ができるようにしたいと思います。
じゃ、今回はこの辺で。
では。
-
当然、スタックにある値の個数よりも小さいことが前提です。↩
