［今日のPiet］atoi関数 - 趣味プログラミングの部屋

今日のPietです。

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

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

今日のテーマについて

昨日（というか今日か）Pietで「最大値」を算出するコードを作りましたが、

「負数が入力できない問題」がありました。

原因は、負数をフラグとして使っていることです。

そこで、数値入力のときに一旦文字列として読み込むことを考えます。

数値の区切り文字（たとえばカンマ「,」）や、

入力終了を表す文字（たとえばセミコロン「;」）を決めておけば、

「21,54,-25,-3,0,5;」

のように入力すればOK。あとから「,」や「;」でパースして、

数字を表す文字列を整数に変換してスタックにプッシュしなおせば、

数値をフラグとして扱う必要はなくなります。

これを行う上で必要なのが、「Piet版atoi関数」です。

今回はこれを題材にします。

ところがどっこい、これがなかなか難しかった。

とりあえずできてはいるので公開します。

Piet版atoi関数

概要

スタックに積まれた文字列を整数値に変換してスタックに積む関数を作ります。

仕様

関数適用前後のスタックの状態を図示するとこんな感じ。

$[\cdots|s_1,\cdots,s_{N},N~~\Longrightarrow~~[\cdots|i$

$\{s_1,\cdots,s_{N}\}$ は整数を表す文字列、 $i$ はこの文字列が表す整数です。

たとえば、スタックボトムから順に文字「'-'、'2'、'7'、'3'」が積まれているとします。

つまり、 $s_1=\texttt{'-'}$ 、 $s_2=\texttt{'2'}$ 、 $s_3=\texttt{'7'}$ 、 $s_4=\texttt{'3'}$ です。

積まれている文字数は4なので、さらに数値の「4」をスタックに積みます。

この時点でのスタックの状態はこうなっています。

[00000 : 45] [00001 : 50] [00002 : 55] [00003 : 51] [00004 :  4]

左から4つはそれぞれ、「'-'、'2'、'7'、'3'」の文字コードに対応する数値です。

この状態でatoi関数に処理を引き継いで、スタックを次の状態にするのが今回の目標です。

[00000 : -273]

スタックに積まれていた文字列と長さの値を全て取り出し、

代わりに文字列を整数に変換した値がプッシュされています。

処理フローファイル

では処理フローファイルを。今回は長いし複雑です。

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

push1 dup sub     #[N(=0)
:input            #[...|N
inc dup           #[...|N,p,p
push4 push1 push2 push5 mul add mul sub
                  #[...|N,p,p-','
if::input_end     #[...|N,p
push2 push1 roll  #[...|p:N
push1 add         #[...:p(=>a_N)|N+1(=>N)
goto:input        #[...|N
:input_end        #[...|N,p
pop               #[...:a_1,...,a_N|N
########################################
## atoi
##  [...|i_1,...,i_N,N
##  ==> [...|i
## *a_n=[-+0-9]
########################################
:atoi            #[...|i_1,...,i_N,N
########################################
## reverse
##  [...|i_1,...,i_N,N
##  ==> [...|i_N,...,i_1,N
########################################
:reverse         #[...|i_1,...,i_N,N
dup              #[...|i_1,...,i_N(=>i_n),N,N(=>n)
:reverse_loop    #[...|i_1,...,i_n,N,n
dup              #[...|i_1,...,i_n,N,n,n
push3 push1 roll #[...|i_1,...,i_n,n,N,n
push1 sub        #[...|i_1,...,i_n,n,N,n-1
push4 push2 roll #[...|i_1,...,N,n-1,i_n,n
push2 add push1  #[...|i_1,...,N,n-1,i_n,n+2,1
roll             #[...|i_n:i_1,...,i_{n-1},N,n-1
dup              #[...:i_n|i_1,...,i_{n-1},N,n-1,n-1
if:reverse_loop:reverse_end
                 #[...|i_1,...,i_{n-1}(=>i_n),N,n-1(=>n)
:reverse_end     #[...|i_N,...,i_1,N,n
pop              #[...|i_N,...,i_1,N
########################################
## /reverse
########################################
:atoi_issign     #[...|i_N(=>i_1),...,i_1(=>i_N),N
push2 push1 roll #[...|i_1,...,N,i_N
dup              #[...|i_1,...,N,i_N,i_n
push3 push1 roll #[...|i_1,...,i_N,N,i_n(=>es)
:atoi_isplus     #[...|i_1,...,i_N,N,es
dup              #[...|i_1,...,i_N,N,es,es
push6 dup push1 add mul push1 add
                 #[...|i_1,...,i_N,N,es,es'+'
sub if:atoi_isminus:
                 #[...|i_1,...,i_N,N,es
pop              #[...|i_1,...,i_N,N
push1            #[...|i_1,...,i_N,N,s(=1)
goto:atoi_ignore_1st
                 #[...|i_1,...,i_N,N,s
:atoi_isminus    #[...|i_1,...,i_N,N,es
dup              #[...|i_1,...,i_N,N,es,es
push3 dup push5 mul mul
                 #[...|i_1,...,i_N,N,es,es'-'
sub if:atoi_nosign:
                 #[...|i_1,...,i_N,N,es
pop              #[...|i_1,...,i_N,N
push1 push2 sub  #[...|i_1,...,i_N,N,s(=-1)
goto:atoi_ignore_1st
                 #[...|i_1,...,i_N,N,s

:atoi_nosign     #[...|i_1,...,i_N,N,es
pop dup push1    #[...|i_1,...,i_N,N,N,s(=1)
goto:atoi_push_s #[...|i_1,...,i_N,N,N,s
:atoi_ignore_1st #[...|i_1,...,i_N,N,s
push3 push1 roll #[...|i_1,...,i_{N-1},s,i_N,N
push1 sub        #[...|i_1,...,i_{N-1}(=>i_N),s,i_N(=>G),N-1(=>N)
dup              #[...|i_1,...,i_N,s,G,N,N
push4 push2 roll #[...|i_1,...,i_N,N,N,s,G
pop              #[...|i_1,...,i_N,N,N,s
goto:atoi_push_s #[...|i_1,...,i_N,N,N,s
:atoi_push_s     #[...|i_1,...,i_N,N,N,s
push2 push1 roll #[...|i_1,...,i_N,N,s,N
push2 add push1  #[...|i_1,...,i_N,N,s,N+2,1
roll             #[...|s,i_1,...,i_N,N
goto:atoi_pre    #[...|s,i_1,...,i_N(=>i_n),N(=>n)

:atoi_pre        #[...|s,i_1,...,i_n,n
push1 dup sub    #[...|s:i_1,...,i_n,n,r(=0)
push2 push1 roll #[...:s|i_1,...,i_n,r,n
:atoi_loop       #[...|i_1,...,i_n,r,n
dup if::atoi_end #[...|i_1,...,i_n,r,n
push3 push2 roll #[...|i_1,...,r,n,i_n
push3 push4 dup mul mul sub
                 #[...|i_1,...,r,n,i_n-'0'(=>v)
dup dup if::atoi_calc
                 #[...|i_1,...,r,n,v,v(=>v')  #v==0?
push1 sub dup if::atoi_calc
                 #[...|i_1,...,r,n,v,v'-1(=>v')  #v==1?
push1 sub dup if::atoi_calc
                 #[...|i_1,...,r,n,v,v'-1(=>v')  #v==2?
push1 sub dup if::atoi_calc
                 #[...|i_1,...,r,n,v,v'-1(=>v')  #v==3?
push1 sub dup if::atoi_calc
                 #[...|i_1,...,r,n,v,v'-1(=>v')  #v==4?
push1 sub dup if::atoi_calc
                 #[...|i_1,...,r,n,v,v'-1(=>v')  #v==5?
push1 sub dup if::atoi_calc
                 #[...|i_1,...,r,n,v,v'-1(=>v')  #v==6?
push1 sub dup if::atoi_calc
                 #[...|i_1,...,r,n,v,v'-1(=>v')  #v==7?
push1 sub dup if::atoi_calc
                 #[...|i_1,...,r,n,v,v'-1(=>v')  #v==8?
push1 sub dup if::atoi_calc
                 #[...|i_1,...,r,n,v,v'-1(=>v')  #v==9?
goto:atoi_value_error
                 #[...|i_1,...,i_{n-1},r,n,v,v'
:atoi_calc       #[...|i_1,...,r,n,v,v'
pop              #[...|i_1,...,r,n,v
push3 push2 roll #[...|i_1,...,n,v,r
push2 push5 mul  #[...|i_1,...,n,v,r,10
mul add          #[...|i_1,...,n,10*r+v(=>r)
push2 push1 roll #[...|i_1,...,i_{n-1},r,n
push1 sub        #[...|i_1,...,i_{n-1}(=>i_n),r,n-1(=>n)
goto:atoi_loop   #[...|i_1,...,i_n,r,n

:atoi_value_error
                 #[...|i_1,...,i_{n-1},r,n,v,v'
pop pop          #[...|i_1,...,i_{n-1},r,n
push2 push1 roll #[...|i_1,...,i_{n-1},n,r
pop push1 sub    #[...|i_1,...,i_{n-1}(=>i_n),n-1(=>n)
:atoi_value_error_loop
                 #[...|i_1,...,i_n,n
dup if::atoi_value_error_end
                 #[...|i_1,...,i_{n-1},i_n,n
push2 push1 roll #[...|i_1,...,i_{n-1},n,i_n
pop push1 sub    #[...|i_1,...,i_{n-1}(=>i_n),n-1(=>n)
goto:atoi_value_error_loop
:atoi_value_error_end
                 #[...|n(=>r)(==0)
dup goto:atoi_end
                 #[...|r(==0),n(=0)

:atoi_end        #[...|r,n(=0)
pop              #[...:s|r
mul              #[...|s*r(=>r)
########################################
## /atoi
########################################
:output          #[...|r
outn             #[...|   ==>r
end

atoi関数の前処理として、スタックに数値を表す文字列を入力する処理を入れてます。

数値入力は0〜9の数字、または、符号（「+」または「-」）のみを使用でき、

カンマ「,」を入力すると数値入力が終了します。

（今回の時点では、入力できる数値は1つだけです。

初めて「,」が入力されたところまでを整数に変換します。）

その後、atoi関数で入力した文字列を数値に変換します。

最後に、変換された数値をoutn命令で出力します。

以上が今回作ったPietソースコードの挙動の全貌です。

なお、途中でスタックの中身を反転させる「reverse関数」を入れてあります。

これについては別の機会に解説します。

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

さて、先ほどの処理フローファイルから、

Pietソースコードを生成すると、次のようになります。

atoi関数Pietバージョン

画像サイズ335x284という超巨大プログラムの完成です。

プログラムが複雑になればなるほど、画像サイズが大きくなっていく、

画像サイズが大きくなるほど、より鮮明な画像にPietコードを埋め込める。

これが拙作の「GridPietGenerator」、及び、「GridPietEmbedder」の醍醐味です。

ちなみに、以前使った富士山の画像

富士山画像

こちらにatoi関数のPietコードを埋め込んでみました。

atoi富士山

以前つくった「hello,world富士山」よりも、富士山であることがよくわかりますね。

npiet実行結果

せっかくなので、「atoi富士山」をnpietで実行してみます。

./npiet 210718_atoi/atoi_mt_fuji.png -tpic -tpf 3 -tps
? -273,
? ? ? ? -273

正しく数値「-273」が出力されます。¹

npietのトレース画像

ついでにトレース画像も示します。

atoi富士山のトレース画像

今回はトレースした軌跡のみを示しています。

いい感じにあちこち動いてくれてますね。

解説

分量が多く大変ですが解説します。興味なければスルーしてください。

解説を見る

入力

1-11行めが入力部分です。

ユーザーからの文字入力（数値ではなく）を待ち受けて、

1文字入力するたびにスタックに積んでいきます。（同時に入力文字数もカウントします。）

カンマ「,」を入力すれば終了です。

「reverse」処理

スタックに積まれている値を反転します。

今度詳細に解説します（覚えていれば←）。

動作としては、次のような感じ。

$[\cdots|s_1,\cdots,s_{N},N~~\Longrightarrow~~[\cdots|s_N,\cdots,s_1,N$

スタックには数列そのものが格納されており、

さらに、スタックトップに数列の要素数Nが格納されています。

この状態から初めて、数列部分のみ順序を入れ替えるのが、reverse関数の処理です。

24-37行目でこの処理を行います。

なお、わざわざ順序を入れ替えたのは、符号チェックや処理のアルゴリズムを考えたときに、

最初に入力した文字から順にスキャンしたかったからです。²

符号チェック

数値への変換に入る前に、符号をチェックします。

あり得るのは以下の3つのケース：

一番初めに入力された文字が「+」である。
一番初めに入力された文字が「-」である。
一番初めに入力された文字が数字である。

1つめと3つめのケースでは符号はプラス、 2つめのケースでは符号はマイナスです。

最初に入力された文字を調べて、

上記3つのうち、どのケースに当たるかを判定して符号sを決めます。

符号sはプラスなら1、マイナスなら-1として、

文字列の最深部にroll命令で移動させておきます。

その上で、後述する「数値への変換」を、符号を無視したまま実行し、

変換完了後、結果にsを乗算して、符号をつけます。

符号チェックは41-80行目で行っています。

文字列から数値への変換

今回の処理の根幹部分です。

まず答えを格納する変数rを0で初期化した上で、以下の操作を繰り返します。

これまでの変換結果rを10倍する。
現時点の文字列の中で、一番初めに入力された文字sを数字に変換し、rに足す。
文字sを文字列から除去する。
文字列に要素が残っていれば最初に戻る。残っていなければ終了。

つまり、文字列は入力された順に（つまり、高い位から低い位へ）１文字ずつ読み込まれます。

結果の値を10倍して位を揃え、今の位の値を足す、その後つぎの位へ移動する、を繰り返して、数値に変換します。

たとえば、'273'という文字列に対しては、もっとも高い桁の'2'（百の位）から始めて、

「変換結果rを10倍（0→0）」

　→「今の桁を結果に足す（0+2=2）」

　→「ひとつ低い位へ（次は十の位の「7」）」

→「変換結果rを10倍（2→20）」

　→「今の桁を結果に足す（20+7=27）」

　→「ひとつ低い位へ（次は一の位の「3」）」

→「変換結果rを10倍（27→270）」

　→「今の桁を結果に足す（270+3=273）」

　→「ひとつ低い位へ（ここで一の位を通り過ぎる）」

→終了

となります。

直接この処理をしているのは、85-86行め、及び、112-119行めとなります。

エラーチェック

さて、上記説明で飛ばされた87-110行目では何をしているでしょうか。

ここではエラーチェックをしています。

つまり、「数字を表さない文字」が出てこないかを確認しています。

たとえば入力した文字列が「12s24」とかだった場合です。

この文字列は途中に「s」が含まれるため、数値として解釈することができません。

今回作ったatoi関数は、このようなエラー時は、一律「0」を返すようにしました。

チェック方法ですが、今着目している文字が、

'0'に等しいか、'1'に等しいか、・・・、'9'に等しいか、を全て調べ、

どの値にも一致しないならエラーとします。

エラー処理は121-135行めで行っており、スタックを一旦カラにして

結果が0になるようにスタックに値を積み直しています。

出力

上記処理が終わったら、結果に符号sをかけて終了です。

この「atoi富士山」は、出力された結果をoutn命令で表示します。

〜〜〜解説ここまで〜〜〜

最後に

やっぱりブログ書くのに時間がかかってしまった。今日の内容もヘビーでしたね。

まぁ処理が複雑なほど富士山が明瞭になっていくので、嬉しい限りではあるんですが。

ではまた。

自分の環境ではなぜか1文字ずつ入力しようとすると正しく解釈してくれませんでした。改行が悪さしてるのか・・・？↩
では入力の時点で反転させればよかったのでは？・・・と、ブログを書いているときに気づきました。↩