［今日のPiet］順序判定関数 - 趣味プログラミングの部屋

今日のPietです。

拙作「GridPietGenerator」を使って、

テキストベースで書かれた「処理フローファイル」から、

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

今回のテーマは「順序判定」です。

順序判定をするPietソースコード

概要

スタックに積まれた値の大小関係を判定します。

仕様

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

例によって、スタックには数列 $a_1,\cdots,a_{N}$ と、その個数Nが積まれた状態から始めます。

処理後にスタックに残る値はRです。

Rは0または1で、以下のように値が決まります。

$a_1>a_2$ 、かつ、 $a_2>a_3$ 、かつ、・・・、かつ、 $a_{N-1}>a_N$ のとき、R=1
それ以外のとき、R=0

つまり、スタックボトム側から、スタックトップ側に数列 $\{a_n\}$ を辿っていったときに、

値が単調に減少する時だけ、R=1となります。

たとえば、

$\{a_n\}=\{5,4,3,2,1\}$ ならR=1
$\{a_n\}=\{74,54\}$ ならR=1
$\{a_n\}=\{4,5,3,1\}$ ならR=0 （4→5で増加している）
$\{a_n\}=\{10,9,6,5,4,3,3,1\}$ ならR=0 （3→3で「減少していない」）

となります。

処理フローファイル

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

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

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
########################################
## inorder
##  [...|a_1,...,a_N,N
##  ==> [...|(a_1>a_2 && ...,a_{N-1}>a_N)
########################################
:inorder            #[...|a_1,...,a_N,N
push1               #[...|a_1,...,a_N(=>a_n),N(=>n),R(=1)
push2 push1 roll    #[...|a_1,...,a_n,R,n
dup if::inorder_err #[...|a_1,...,a_n,R,n
:inorder_loop       #[...|a_1,...,a_n,R,n
dup push1 sub       #[...|a_1,...,a_n,R,n,n-1
if::inorder_end     #[...|a_1,...,a_{n-1},a_n,R,n
push4 push3 roll    #[...|a_1,...,a_n,R,n,a_{n-1}
dup                 #[...|a_1,...,a_n,R,n,a_{n-1},a_{n-1}
push5 push4 roll    #[...|a_1,...,R,n,a_{n-1},a_{n-1},a_n
gt                  #[...|a_1,...,R,n,a_{n-1},a_{n-1}>a_n(=>J)
push4 push3 roll    #[...|a_1,...,n,a_{n-1},J,R
mul                 #[...|a_1,...,n,a_{n-1},J*R(=>R)
push3 push2 roll    #[...|a_1,...,a_{n-1},R,n
push1 sub           #[...|a_1,...,a_{n-1}(=>a_n),R,n-1(=>n)
goto:inorder_loop   #[...|a_1,...,a_n,R,n
:inorder_err        #[...|R,n(==0)
pop pop             #[...|
push1 dup sub       #[...|a_1(=0)
dup dup             #[...|a_1,R(=0),n(=0)
:inorder_end        #[...|a_1,R,n(==0)
push3 push2 roll    #[...|R,n,a_1
pop pop             #[...|R
########################################
## inorder
########################################
outn end            #[...| ==>R

今回は比較的単純です。

まず、入力については、sum関数やmax関数のものを、そのまま使い回しました。

ymos-hobby-programing.hatenablog.com

出力については、得られたRの値をoutnで出力するようにしています。

次に処理の中身です。

roll命令で数列の末尾2つの値をスタックトップに移動させます。

gt命令で比較を行い、その結果をR（1で初期化）に掛け算していきます。

（数列の末尾の値はgt比較のときに消えてしまうため、数列の長さは1短くなります。

　また、数列の末尾から2番目の値は、次のループでも使うため、あらかじめ忘れずに複製しておきます。）

以上の処理を、スタックに積まれている要素がなくなるまで繰り返します。

この繰り返しの過程で、gt命令が1回でも0を返せば、結果Rは0になるため、

$a_1>a_2$ 、かつ、 $a_2>a_3$ 、かつ、・・・、かつ、 $a_{N-1}>a_N$ のとき、R=1
それ以外のとき、R=0

の判定が可能となります。

なお、今回は空数列が入力されたときのエラー処理も対応しています。

この前やらかしましたし・・・。

ymos-hobby-programing.hatenablog.com

生成されたPietソースコード

次のようなPietソースコードが生成されます。

順序判定関数のPietソースコード

npiet実行結果

まずはR=1を返す例。

./npiet -tpic -tpf 10 inorder.ppm
? 5
? 4
? 3
? 2
? 1
? -1
1

正しくR=1を返してます。

npietによるトレース画像

トレース画像の彷徨い具合はいつも通りです。

次にR=0を返す例。

./npiet -tpic -tpf 10 inorder.ppm
? 10
? 9
? 6
? 5
? 4
? 3
? 3
? 1
? -1
0

正しくR=0を返してます。

npietのトレース画像は省略します。（先ほどのものとあまり変わらないため。）

そうそう、空の配列を渡したときの結果も。

./npiet -tpic -tpf 10 inorder.ppm
? -1
0

空の配列を渡した時は、無条件で0を返すようにしました。

このときのnpietトレース画像はこちら。

空の配列を渡したときのnpietトレース画像

先ほどのトレース画像と比較してみます。

ループがない分、スッキリしているのは間違い無いのですが、

注目すべきは下辺右側のColor Blockです。

先ほどPietインタプリタは、下辺右側にあったColor Blockを無視していました。

その部分のみ拡大した画像がこちら。

空でない配列入力時のnpietトレース画像（下拡大）

今回のトレース画像では、そのColor Blockを通っています。

その部分のみ拡大した画像がこちら。

空の配列入力時のnpietトレース画像（下拡大）

おそらく、これが空の配列を渡したときのエラー処理に該当する処理なのでしょう。

（処理フローファイルでいうと、32-35行目、:inorder_errの部分。）

最後に

本日2つ目の記事投稿。

暇かよ！

いえす。暇です。

前回投稿したsum関数、今回投稿した順序判定関数は

いずれもあるPiet処理のために作っているものですが、

そちらはかなり複雑な処理になり、現在鋭意製作中です。

ある程度出来上がってきたらこのブログで紹介します。