［今日のPiet］［デバッグ］合計値を求める関数「sum」

今日のPietです。

拙作「GridPietGenerator」を使って、テキストベースで書かれた「処理フローファイル」から、

所望の処理をするPietソースコード画像を生成します。

今日のテーマについて

さて、前回スタックに積まれた数の合計値を求める関数「sum」を作りました。

ymos-hobby-programing.hatenablog.com

しかし、この関数には重大なバグがあったため、

今回は訂正版を作りました。

関数sumのバグ

関数sumの振る舞いは以前説明した通りです。

$[\cdots|a_1,\cdots,a_{N},N\Longrightarrow[\cdots|a_1,\cdots,a_{N},N,\sum_n{a_n}$

スタックに積まれた数列 $a_1,\cdots,a_{N}$ 、および、それらの個数Nから、

合計値 $\sum_n{a_n}$ を求めるのでした。

前回紹介した「sum関数」では、確かに合計値を求めることができるのですが、

あるケースで挙動がおかしくなります。

それは空の数列を入力に入れた時です。

スタックの状態で言えば、次の状態のとき。

$[\cdots|0,\Longrightarrow$ ？？？

つまり、数列 $a_1,\cdots,a_{N}$ に該当するものが何もなく、

いきなり数列の個数0がスタックに積まれる場合です。

挙動確認

前回紹介したプログラムでこの状態を再現するには

いきなり-1を入力してやればOKです。

拙作の「GridPietInterpreter」（GridPietGeneratorに添付）で先日の処理フローファイルをデバッグしてみます。

「GridPietInterpreter」は、処理フローファイルの挙動を確認するためのプログラムで、

命令を実行している場所やスタックの状況、出力状況を随時表示するプログラムです。

さて、先日のプログラムを動かすと次のようになります。

./GridPietInterpreter sum.txt

まず、入力を求められます。

===PietInterpreter [0x16b50f448]
cnt :4
pc  :4
cur : :ci_input @ l.6-1
next: inn @ l.7-1
stack: [00000 :     0] 
output:

スタックの状態は「stack」の部分に表示されます。

スタックにはまだ値がひとつだけ積まれていて、その値はゼロであることがわかります。

（コロン「:」の左側がスタックボトムからの距離、右側がスタックの中の値です。）

通常ならここで適当な正数を入れるのですが、 -1を入れてみます。

まず、sum関数の開始時点では、

===PietInterpreter [0x16fb5b448]
cnt :14
pc  :20
cur : :sum @ l.23-1
next: dup @ l.24-1
stack: [00000 :     0] 
output:

期待通りスタックに、

「空の行列」（空なので何もプッシュされていない）と

その個数「0」だけがプッシュされています。

詰まるところ、「0」しかプッシュされていません。

で、この後の処理なのですが。

・・・

・・・止まらない・・・。

とりあえずプログラムを強制終了してみて、スタックの状態を確認すると、

===PietInterpreter [0x16fb5b448]
cnt :24341
pc  :47
cur : roll @ l.36-3
next: dup @ l.37-1
stack: [00000 :     0] [00001 : 16684816] [00002 :  -676] [00003 : -1962061414] [00004 :     0] 
output:

よくわかりませんが、期待した動作でないことだけはわかります。

まずプログラムのステップ数「cnt」の値が2万を突破していますが、そんなはずはなく。

スタックボトムから2番目の値「 [00001 : 16684816] 」や、

４番目の値「[00003 : -1962061414]」も明らかにおかしな値を取っています。

設計上、スタック内部の値がこんな大きくなるはずはありません。

原因と対策

sum関数内にループがあるので、その先頭にあるラベル「:sum_loop」を通過したときの状態を調べます。

ここで想定しているスタック状態は次の通りです。

[...|a_1,...,a_N,S,N,n

まず「[」がスタックボトムを表します。逆に右端の要素がスタックトップの要素です。

「|」より右側の部分、つまり、「...|」の部分については、

「そこに要素があっても、この関数内ではタッチしません」ということなので無視します。

次の「a_1,...,a_N」の部分は数列（がrollされたもの）です。

その後ろに、「S（合計値）」、「N（数列個数）」、「n（カウンタ）」が順に積まれています。

今回の条件では、数列が空のため、

[S,N,n

のように3つの要素が積まれているのが正しい状態です。

1回目通過時

まず、1回目にここを通ったときの出力です。

===PietInterpreter [0x16fb5b448]
cnt :22
pc  :28
cur : :sum_loop @ l.27-1
next: push4 @ l.28-1
stack: [00000 :     0] [00001 :     0] [00002 :     0] 
output:

問題なさそうです。

2回目通過時

続いて、2回目にここを通ったときの出力です。

===PietInterpreter [0x16fb5b448]
cnt :58
pc  :28
cur : :sum_loop @ l.27-1
next: push4 @ l.28-1
stack: [00000 :     0] [00001 :     6] [00002 :     4] [00003 :     0] [00004 :    -1] 
output:

わーお。スタックの状態が全然違います。

というか、そもそも、数列に何も積まれてないのに、

ループの2回目に突入すること自体、違和感があります。

原因

ソースコードを見返すと、数列の個数Nがいくつであっても、

カウンタnの値をチェックして終了判定する前に、

とにかく合計値を出そうと処理をしてしまうことがわかります。

具体的に言えば、ループの開始点「:sum_loop」が20行目にあるのに対し、

ループ脱出判定が36行目（if:sum_loop:sum_end）にあり、

その間にも何らかの処理をすることになります。

エラーの内容からして、おそらくこの処理が空の数列を想定していないために、

スタックアンダーフロー¹を起こしていると思われます。

Pietインタプリタは、スタックアンダーフローが生じる場合は

命令を無視して継続する仕様であるため、

この手のミスがあっても止まることはありません。

実際探してみたら、ありました。

===PietInterpreter [0x16fb5b448]
cnt :22
pc  :28
cur : :sum_loop @ l.27-1
next: push4 @ l.28-1
stack: [00000 :     0] [00001 :     0] [00002 :     0] 
output: 


===PietInterpreter [0x16fb5b448]
cnt :23
pc  :29
cur : push4 @ l.28-1
next: push2 @ l.28-2
stack: [00000 :     0] [00001 :     0] [00002 :     0] [00003 :     4] 
output: 


===PietInterpreter [0x16fb5b448]
cnt :24
pc  :30
cur : push2 @ l.28-2
next: roll @ l.28-3
stack: [00000 :     0] [00001 :     0] [00002 :     0] [00003 :     4] [00004 :     2] 
output: 


===PietInterpreter [0x16fb5b448]
cnt :25
pc  :31
cur : roll @ l.28-3
next: push2 @ l.29-1
stack: [00000 :     0] [00001 :     0] [00002 :     0] [00003 :     4] [00004 :     2] 
output:

まさに１回目のループに入った直後です。

最後の2つ、cnt :24とcnt :25の間でroll命令が無視されています。

（実際、スタックの値に変化がありません。）

細かくみていきます。

３つ目（cnt:24のとき）で、次の命令がrollとなっています。（next: roll @ l.28-3）

ここで、スタックトップには、「 [00003 : 4] [00004 : 2] 」と並んでおり、

これらはroll命令の引数として扱われます。

この場合は、「スタックトップから4つの要素に着目し、2個分ずらす」という処理になりますが、

スタックには「[00000 : 0] [00001 : 0] [00002 : 0]」のように

要素が3つしかありません。

これは、配列があることを前提に設計されたプログラムを、

無理矢理、空の配列に適用したために起こったミスと考えられます。

結局、roll命令を実行しようにも実行できず、無視したまま進めます。

ここで、本来は消えるはずのroll命令の引数「4, 2」が残ったままになり、

スタックの状態が壊れます。

これが動作がおかしくなる全ての原因です。

対策

この場合は対策は簡単です。

ループ開始直後にループ終了判定をすればOKです。

幸い、元々の処理フローファイルでは、

終了判定直後にループ先頭に飛ぶという構成になっていました。

...
:sum_loop                    #[...|a_{n+1},...,a_n,S,N,n
...
roll                         #[...|a_{n+1},...,a_n,S,N,n
dup if:sum_loop:sum_end      #[...|a_{n+1},...,a_n,S,N,n
...

つまり、判定処理をしている「if:sum_loop:sum_end」の直後と、

ループ先頭「:sum_loop」とでは、スタックの状態は同一です。

ですので、心置きなく、次のように順序を入れ替えればOKです。

...
:sum_loop                    #[...|a_{n+1},...,a_n,S,N,n
dup if::sum_end              #[...|a_{n+1},...,a_n,S,N,n
...
roll                         #[...|a_{n+1},...,a_n,S,N,n
goto:sum_loop                #[...|a_{n+1},...,a_n,S,N,n
...

本来の処理終了判定は、

「ループ先頭に戻るか、ループから脱出するか」の2択でしたが、

処理判定終了をループ先頭直後に移動したため、

「そのまま進むか、ループから脱出するか」の２択となるように変更しました。

また、ループ末尾からループ先頭へは無条件でジャンプして良くなるため、

goto命令に変更しています。

処理フローファイル

改善した処理フローファイルは次のようになります。

処理フローファイルを見る

push1 dup sub     #[N(=0)
:ci_input         #[...|N
inn               #[...|N,p
dup push1 dup sub #[...|N,p,p,0
gt if::ci_input_end  #[...|N,p
push2 push1 roll  #[...|p:N
push1 add         #[...:p(=>a_N)|N+1(=>N)
goto:ci_input     #[...|N
:ci_input_end     #[...|N,p
pop               #[...|a_1,...,a_N,N
########################################
## sum
##  [...|a_1,...,a_N,N
##  ==> [...|a_1,...,a_N,N,a_1+...+a_N
########################################
:sum              #[...|a_1,...,a_N,N
dup               #[...|a_1(=>a_{n+1}),...,a_N(=>a_n),N,N(=>n)
push1 dup sub     #[...|a_{n+1},...,a_n,N,n,S(=0)
push3 push1 roll  #[...|a_{n+1},...,a_n,S,N,n
:sum_loop         #[...|a_{n+1},...,a_n,S,N,n
dup if::sum_end   #[...|a_{n+1},...,a_n,S,N,n
push4 push2 roll  #[...|a_{n+1},...,N,n,a_n,S
push2 push1 roll  #[...|a_{n+1},...,N,n,S,a_n
dup               #[...|a_{n+1},...,N,n,S,a_n,a_n
push5 push1 roll  #[...|a_{n+1},...,a_n,N,n,S,a_n
add               #[...|a_{n+1},...,a_n,N,n,S+a_n(=>S)
push3 push1 roll  #[...|a_{n+1},...,a_n,S,N,n
push1 sub
      #[...|a_{n+1}(=>a_{n+2}),...,a_n(=>a_{n+1}),S,N,n-1(=>n)
push3 push1 roll  #[...|a_{n+2},...,a_{n+1},n,S,N
dup               #[...|a_{n+2},...,a_n,a_{n+1},n,S,N,N
push4 push3 roll  #[...|a_{n+2},...,a_n,a_{n+1},S,N,N,n
push5 push4 roll  #[...|a_{n+2},...,a_n,S,N,N,n,a_{n+1}
push3 push2 roll  #[...|a_{n+2},...,a_n,S,N,n,a_{n+1},N
push3 add push1   #[...|a_{n+2},...,a_n,S,N,n,a_{n+1},N+3,1
roll              #[...|a_{n+1},...,a_n,S,N,n
goto:sum_loop     #[...|a_{n+1},...,a_n,S,N,n

:sum_end          #[...|a_1,...,a_N,S,N,n
pop               #[...|a_1,...,a_N,S,N
push2 push1 roll  #[...|a_1,...,a_N,N,S
########################################
## /sum
########################################
outn             #[...|a_1,...,a_N,N ==>S
end              #[...|a_1,...,a_N,N

これをGridPietInterpreterにかけます。

===PietInterpreter [0x16f6ab438]
cnt :4
pc  :4
cur : :ci_input @ l.1-1
next: inn @ l.2-1
stack: [00000 :     0] 
output:

入力を求められるので、いきなり「-1」を入力します。

まず、念のためsum関数の開始直後の状態を見ておきます。

===PietInterpreter [0x16f6ab438]
cnt :14
pc  :20
cur : :sum @ l.15-1
next: dup @ l.16-1
stack: [00000 :     0] 
output:

こちらは（先ほどと同じく）正常です。

次に、sum関数内のループ開始直後の挙動を示します。

===PietInterpreter [0x16f6ab438]
cnt :22
pc  :28
cur : :sum_loop @ l.19-1
next: dup @ l.20-1
stack: [00000 :     0] [00001 :     0] [00002 :     0] 
output: 


===PietInterpreter [0x16f6ab438]
cnt :23
pc  :29
cur : dup @ l.20-1
next: if::sum_end @ l.20-2
stack: [00000 :     0] [00001 :     0] [00002 :     0] [00003 :     0] 
output: 


===PietInterpreter [0x16f6ab438]
cnt :24
pc  :64
cur : if::sum_end @ l.20-2
next: :sum_end @ l.37-1
stack: [00000 :     0] [00001 :     0] [00002 :     0] 
output: 


===PietInterpreter [0x16f6ab438]
cnt :25
pc  :65
cur : :sum_end @ l.37-1
next: pop @ l.38-1
stack: [00000 :     0] [00001 :     0] [00002 :     0] 
output:

今度はすぐに終了判定を実施し（cnt :24）、

終了処理「:sum_end」にジャンプしていることがわかります。

最終的な出力は次の通りです。

===PietInterpreter [0x16f07f438]
cnt :30
pc  :70
cur : outn @ l.43-1
next: end @ l.44-1
stack: [00000 :     0] 
output: 
0

今度は正しく0が出力されています。

スタックには空の配列（実際には何もない）と

その個数0がプッシュされたままの状態となっており、

想定通りの動きをしていることがわかります。

最後に

この「sum」関数ですが、実はある目的のために作りました。

その目的では、空の配列を渡す可能性があったため、

「あれ？そういえば・・・」と思い見返してみたら、やはりバグがいました。

このようにプログラムにはバグがつきものです。

バグを出さないのもプログラムを作る上で重要ですが、

バグが出る前提でバグを潰しやすいコーディングをしておくことや、

バグの原因を特定できることも、同じくらい重要なスキルとなると思います。

Pietに限らず。

（Pietでバグ取りをする人はあまりいない、というツッコミは無視の方向で・・・。）

ではまた。

スタックに何も積まれていないにもかかわらず、スタックから値をポップしようとするエラーのこと。↩