［今日のPiet］合計を求める関数sum - 趣味プログラミングの部屋

今日のPietです。

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

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

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

合計を求めるPietソースコード

概要

スタックに積まれている数値の合計値を返します。

仕様

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

シグマ記号とかあるとカコイイですね。まあ使ってみたかっただけです。

例の通り、N個の値、及び、それらの個数Nがスタックに積まれた状態から、

それらの数の合計値を算出しスタックトップに積む関数「sum」を作ります。

以前、最大値を求める関数を作った時は、

スタックに積まれていた数は全てポップし、

最終的には最大値のみがスタックに残るようにしました。

今回は逆に積まれていた値を保持したままとし、

スタックトップに合計値を積んだだけの形になるように設計しました。

処理フローファイル

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

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

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
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
dup if:sum_loop:sum_end
      #[...|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

まず、冒頭の1-10行目は、一番初めに製作したmax関数から

ほぼ使い回しています。

負の数が入りませんが、あまりこだわっても仕方ないので。

ymos-hobby-programing.hatenablog.com

次に、11-43行目が、sum関数の本体になります。

基本的な考え方としては、 $a_1$ 、…、 $a_N$ の要素を1つずつシフトさせながら、

結果用に用意した変数に足し込んでいきます。

具体的には、

カウンタとなる値nを用意する（スタックに積まれた要素数Nで初期化する）
合計値となる値Sを用意する（0で初期化する）
カウンタnが0になるまで以下を繰り返す
- はじめに入力したN個の値たち $a_1$ 、…、 $a_N$ の部分のみをrollする
- $a_1$ 、…、 $a_N$ のうち、もっともスタックトップ側に来た要素をSに足し、カウンタnをデクリメント

となります。

途中、「 $a_1$ 、…、 $a_N$ の部分のみをroll」とか、しれっと書いてますが、

Pietの基本命令だけではそんなことできるわけがないので、

うまいこと、こちょこちょとして、そのように見えるような処理に仕上げています。

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

こんなソースが出てきます。

合計を求める関数「sum」

久しぶりに粗めのPietソースコードです。人の目には優しい。

npiet実行結果

./npiet sum.ppm -tpic -tpf 10  
? 1
? 2
? 3
? 4
? 5
? 6
? 7
? 8
? 9
? 10
? -1
55

有名（？）な1から10までの足し算です。55で正解です。

縦横サイズが小さめなので、久しぶりに詳細なトレース画像を掲載できます。

f:id:y-mos:20210721233604p:plain — 合計を求める関数「sum」のトレース画像

右下の処理が長めで、全体も縦長の長方形になってますね。

実はこれ、ラベルをわざと無駄に追加すれば、正方形に近づけることもできます。

たとえば、次のように。

ラベルを適当に加えた処理フローファイルを見る

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
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)
:sum_loop_mid1
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
:sum_loop_mid2
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}
:sum_loop_mid3
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
dup if:sum_loop:sum_end
      #[...|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

26、32、35の各行に意味もなくラベルを入れました。

GridPietGeneratorはラベルの位置で強制的にブロック分けするので、

この無駄なラベルのおかげで、Pietブロックを細切れにできます。

その結果・・・