［お知らせ］GridPietGeneratorアップデート

GridPietGeneratorを更新しました。

バグフィックス

  • 一部処理系でビルド時にエラーとなるのを修正（返り値の指定忘れ）

引数の変更

  • 入力ファイル名（処理手順を書いたテキストファイル）は、オプションなしで指定
  • 出力ファイル名は下表のように指定
オプション 説明
-o, --output 出力ppmファイル名を指定（Pietソースコード画像）
-a, --ascii 出力アスキーファイル名を指定（GridPietEmbedderの入力ファイル）
-c, --csv デバッグ用csvファイルを指定
-l, --log ログファイル名を指定

例

  1. githubからGridPietGeneratorをダウンロードまたはクローン
  2. ビルド
  3. sampleフォルダに実行ファイルをコピー
  4. 使ってみる
    1. ppm形式のPietソースコードfact.ppmを出力するだけなら次のコマンドを実行 ./GridPietGenerator fact.txt -o fact.ppm
    2. GridPietEmbedderへの入力ファイルfact.ascii1も出力したいなら次のコマンドを実行
      ./GridPietGenerator fact.txt -o fact.ppm -a fact.ascii
    3. csvやログを出力したいなら次のコマンドを実行2
      ./GridPietGenerator fact.txt -o fact.ppm -c fact.csv -l fact.log

終わりに

とりあえず報告だけアップします。 私の環境のVisual Studioではバグが発生しました。（普段Mac使いなもので気づいてませんでした。） ビルドに失敗していた方はもう一度やってみてください。

ではまた。

  1. "ascii"という拡張子は勝手につけました。実態はただのテキストファイルです。↩
  2. ここで出てくるcsvやログファイルの中身は一切解説していません。現時点では完全に自分用です。↩

［Piet］10の階乗

Piet

今回のテーマは「10の階乗」です。 プログラミングでは定番の「再帰関数」をPietで実装します。

階乗

数学ででてくる「10!」というもので、 10から1までの整数全ての積のことです。 具体的に計算すると、

10!=10×9×8×...×2×1=3628800

となります。

再帰関数

プログラミングで使われる「再帰関数」とは、 内部で自分自身を呼び出すような関数です。

繰り返し処理の中には、「再帰関数」を利用すると、 プログラムの記述が非常に簡単になるものがあります。

先ほどの「階乗」は、

10!=10×9×8×...×2×1=10×(9×8×...×2×1)=10×9! 9!=9×8×7×...×2×1=9×(8×7×...×2×1)=9×8!

のように、

x!=x・(x-1)!

と書け、ある数の階乗計算には 元の数から1引いた数の階乗計算の結果を使えます。

こういう計算は再帰関数と相性がよいです。 例えばC++では次のように実装されます。

#include <iostream>

int f(int x)
{
  if(x==0){ return 1; }
  else { return x*f(x-1); }
}

int main()
{
  std::cout << f(10) << std::endl;
  return 0;
}

関数fの中で、

  • 引数xが0なら1を返す
  • 引数xが0でないならx*f(x-1)を返す

というように、返り値にこの関数自身fが含まれています。

ちなみに再帰関数を使わないと、for文で次のように書くことになります。

#include <iostream>

int main()
{
  int x=1;
  for(int i=10;i>0;i--)
  {
    x*=i;
  }
  std::cout << ｘ << std::endl;
  return 0;
}

まあ、このくらいなら正直どちらでも変わらない気もします。

しかし、処理内容によっては普通にループを書くより 再帰関数にした方が圧倒的に簡潔なので、 使いこなせることが好ましいテクニックです。

Pietで再帰関数

この程度なら難しくはありません。1

まずは方針を決めます。

  1. フラグ0と階乗を計算する値をプッシュしておく
  2. 〜ループ開始1〜
  3. 直前にプッシュした値から1を引いた値をプッシュする
  4. フラグ1をプッシュし、先ほどの値と順番を入れ替える
  5. 先ほどプッシュした値が0でないなら「〜ループ開始1〜」に戻る
  6. 最後にプッシュしたフラグと値を削除
  7. 〜ループ開始2〜
  8. フラグをチェックして0ならループをぬけ「〜終了処理〜」へ
  9. スタックの最上部にある2つの数値を掛け算する
  10. 「〜ループ開始2〜」へ
  11. 〜終了処理〜
  12. 計算結果を表示し、終了

Pietソースコード

では実際に書いてみます。 まずは処理順から。 今回は短いのでそのまま載せます。

命令の詳細はこちら。

ymos-hobby-programing.hatenablog.com

ymos-hobby-programing.hatenablog.com

push1 dup sub push2 push5 mul
goto:fact

:factR
outn pop end

:fact
dup push1 sub push1 push2 push1 roll
dup dup dup sub gt
if:factN:factMulP

:factN
goto:fact

:factMulP
pop pop

:factMul
push2 push1 roll
if:factMulN:factR

:factMulN
mul goto:factMul

これをGridPietGeneratorで処理した結果がこちら。

GridPietGeneratorについてはこちらの記事を参照。

ymos-hobby-programing.hatenablog.com

ymos-hobby-programing.hatenablog.com

10の階乗計算ソースコード（10倍に拡大）

コーデル数は51x53と小さめです。

ちゃんとnpietでも動きます。

./npiet -cs 10 factorialx10.png 
3628800

処理解説

では処理の解説です。例によって処理順はコロン「：」で始まる行で区切られており、 それぞれが処理のひとかたまりになっています。

ちなみに生成されたソースコードに対応させるとこんな感じです。 このように、GridPietGeneratorで生成されたコードは、処理ブロックのカタマリが 画像のフチに配置されます。

処理ブロックの配置
 

これらの処理順を図示すると次のようになります。極めてシンプルです。

処理順

処理順を解説していきます。

スタックの初期化

まずは「:1」ブロックでスタックを初期化します。

初期化時のスタックの変化は下図の通りです。

  • 灰色部分がスタック（＝データを入れる容器）
  • 文字のついた白い長方形がデータ
  • スタックのデータ出入り口は上がわ

と考えてください。

初期化時のスタック変化

最終的にスタックには0と10が積まれます。

  • 下の0はフラグです（後で説明します）
  • 上の10は階乗計算の対象となる数値10です

10, 9, 8, ... と数値をスタックに積んでいく処理

次に:factと:factNの部分です。

数値をスタックに積む処理

この部分では数値1ずつ減らしながらスタックにプッシュしていきます。

具体的なスタックの変化は次のようになります。

`:fact`ブロックの処理前半（フラグと数値のプッシュ）

スタックには既にフラグfと数値xの組（f、x）がいくつか入っていて、そのうちの最上部の1組だけを表示したのが上の図だと考えてください。

まずは今スタックに入っている値xをコピーして、x-1をスタックにプッシュします。 さらに新たにフラグ1をプッシュして順番を入れ替え、初期化の時と同じ順番、つまり、

  • 下がフラグ
  • 上が値

となるようにします。

`:fact`ブロックの処理後半（ループ判定）

続いてこの部分で、現在の値x-1が0より大きいか判定します。 比較に使う0を作るために、x-1をdup命令で3回も複製し、 うち2つを引き算して0をつくっています。

最後の部分は次の判定をif命令で実行しています。

  • x-1が0より大　→　:factに戻って繰り返す 2
  • x-1が0　→　次の処理である:factMulPに進む

この部分を繰り返すことで、スタックには、下から、

フラグf(=0)、10、フラグf(=1)、9、...、フラグf(=1)、1、フラグf(=1)、0

と値がプッシュされていきます。 フラグを挟んで階乗計算に必要な数列{10, 9, ..., 1}が用意できました。

階乗計算

いよいよ階乗計算です。

まず準備として、:factMulPブロックでは、スタックの最上部の2つの値をポップします。 この2つの値は使わないからです。

階乗計算準備

階乗計算準備（スタック変化）

続いて終了判定と掛け算を繰り返す部分です。:factMulブロックと:factMulNブロックで その処理をしています。

終了判定と掛け算

`:factMul`ブロックのスタック変化（終了処理）

:factMulブロックでは、終了判定を行なっています。 まず上2つだけに注目して、roll命令で順番を入れ替えます。 フラグがスタックの最上部に来たところで、if命令を使い、

  • フラグfが1なら継続　→　:factMulNブロックに進む
  • フラグfが0なら終了　→　:factRブロックに進む （＝ループ脱出）

とします。 初期化時や:factブロックでプッシュしていたフラグは、 ここで処理順を決めるために使われます。

継続の場合は、:factMulNブロックで、スタック最上部の2数を掛け算します（mul命令）。

`factMulN`ブロックのスタック変化

上図のスタック変化には、フラグf'のさらに下にあった、 フラグf''と数値データx'も表示しています。 掛け算の結果、スタック最上部は、

...、フラグf''、数値x'、フラグf'、数値x X

となり、フラグと数値が交互に現れます。 このまま:factMulに戻れば、スタックにプッシュされている数値が順々に 掛け算されていくという算段です。

ループ終了

掛け算のループは初期化時にプッシュしたフラグ0 に到達すると終了します。 このときの:factMulブロックでの処理を見てみましょう。

`:factMul`ブロックでのスタック変化（ループ脱出直前）

このときはif命令で、初期化時にプッシュしたフラグfが読み込まれますが、 このfの値は0なので:factRブロックに進みます。

ループ脱出時

ここまででスタックには、計算結果、つまり、10、9、...、1までの 全ての数値の積Xのみが格納されています。 その結果を:factRブロック内のoutn命令で出力して終わり、となります。3

以上が10の階乗プログラムの説明です。

最後に

「再帰関数」と銘打ちながら、あまり再帰関数らしさが感じられませんでした。 正直、階乗の計算ならループでいけますし。。。

さて、前回お話ししていたように、今回はスタックの変化がわかるように図にしてみました。 正確にいうと、この図を半自動で作るツールを作り、今回初めて使ってみました。 説明の手間も省けますし、見るほうも図があると多少わかりやすいと思うので、 自分としてはよかったと思っています。

次回もまた適当にネタを探してPietで実装したいと思います。

ではまた。

  1. とか言ってデバッグに結構時間かかりましたが・・・。↩
  2. 厳密には:factNに進みますが、:factNブロックには命令がなく、すぐに:factにジャンプしますので、実質的には:factに進むことになります。↩
  3. ちなみに:factRブロック内にはpop命令もありますが、これは不要でした。すみません。これでも動きはします（スタックに値がないのにポップしようとするので命令が実行されず無視されます。）↩

［Piet］ASCIIコード表

Pietでプログラミングしていると文字出力のためにASCIIコード表が欲しくなります。表を作ること自体は難しくありません。でもめんどくさい。

そういう面倒なことはプログラムにお任せするのが良いと思います。というわけでPietで書いてみました（なぜ）

概要

調べてみるとASCIIコードの印字可能文字は、16進数で 0x20-0x7Fの範囲にあるそうで、とりあえずこの 範囲の表ができれば問題ありません。

出力されるASCIIコード表は次のようなものにします。

|' ' (32)|'!' (33)|'"' (34)|'#' (35)|'$' (36)|'%' (37)|'&' (38)|''' (39)|'(' (40)|')' (41)|'*' (42)|'+' (43)|',' (44)|'-' (45)|'.' (46)|'/' (47)|
|'0' (48)|'1' (49)|'2' (50)|'3' (51)|'4' (52)|'5' (53)|'6' (54)|'7' (55)|'8' (56)|'9' (57)|':' (58)|';' (59)|'<' (60)|'=' (61)|'>' (62)|'?' (63)|
|'@' (64)|'A' (65)|'B' (66)|'C' (67)|'D' (68)|'E' (69)|'F' (70)|'G' (71)|'H' (72)|'I' (73)|'J' (74)|'K' (75)|'L' (76)|'M' (77)|'N' (78)|'O' (79)|
|'P' (80)|'Q' (81)|'R' (82)|'S' (83)|'T' (84)|'U' (85)|'V' (86)|'W' (87)|'X' (88)|'Y' (89)|'Z' (90)|'[' (91)|'\' (92)|']' (93)|'^' (94)|'_' (95)|
|'`' (96)|'a' (97)|'b' (98)|'c' (99)|'d'(100)|'e'(101)|'f'(102)|'g'(103)|'h'(104)|'i'(105)|'j'(106)|'k'(107)|'l'(108)|'m'(109)|'n'(110)|'o'(111)|
|'p'(112)|'q'(113)|'r'(114)|'s'(115)|'t'(116)|'u'(117)|'v'(118)|'w'(119)|'x'(120)|'y'(121)|'z'(122)|'{'(123)|'|'(124)|'}'(125)|'~'(126)|''(127)|

文字をシングルクォーテーション'でくくり、カッコでASCIIコードの数値を10進数で示します。

表全体は垂直バー|で区切って表現します。Pietでシンプルに表を出力するならこんなもんでしょう。

1行は16文字とします。 1行めが文字コード0x20-0x2Fに対応、2行めが文字コード0x30-0x3Fに対応、・・・とします。

プログラムのフロー

  1. 表の縦方向のループカウンタyを用意する
  2. 縦方向ループ開始
  3. 表の横方向のループカウンタxを用意する
  4. 横方向ループ開始
  5. 表示する文字コードを計算（x+16*y）
  6. 垂直バーを表示（|）
  7. 文字を表示（'文字'）
  8. 文字コードを表示（(文字コード)）
  9. xを更新（x<-x+1）
  10. x<16なら「横方向ループ開始」に戻る
  11. 垂直バーと改行文字を出力する（次の行へ）
  12. yを更新（y<-y+1）
  13. y<8なら「縦方向ループ開始」に戻る
  14. 終了

プログラム

まずは作ったプログラムと自動生成したPietソースコードを示します。プログラムは長いので、見たい方は下の文字をクリックして開いてください。

クリックしてプログラムをみる

push2
:loopY
push1 dup sub

:loopX
dup push3 push2 roll
dup push4 push1 roll
push2 dup mul dup mul mul add push1
goto:out_bar
:out_bar_return1
pop goto:out_char
:out_char_return
goto:out_num
:out_num_return
pop push1 add dup push3 push5 mul gt
if::loopX
push2 goto:out_bar
:out_bar_return2
pop
goto:out_NL
:out_NL_return
push2 push1 roll push1 add dup
push3 push2 dup add add gt
if:end:
push2 push1 roll
pop
goto:loopY

:out_char
dup
push2 dup dup dup dup push1 add add mul mul mul push1 sub dup
push3 push1 roll outc outc outc
goto:out_char_return

:out_bar
push2 dup dup dup mul mul dup mul mul push2 dup mul sub outc
:out_bar_return
dup push1 sub if::out_bar_return1
dup push2 sub if::out_bar_return2
end

:out_num
dup
push2 dup dup push1 add add mul dup mul push1 sub gt
if:out_num_out:
push1 goto:out_space
:out_space_return1
pop
:out_num_out
dup
push2 dup dup mul mul push2 push3 add mul
dup push1 add push3 push1 roll
outc outn outc
goto:out_num_return

:out_space
push2 dup dup mul dup mul mul outc
:out_space_return
dup push1 sub if::out_space_return1
end

:out_NL
push2 push5 mul outc
goto:out_NL_return

:end
end

ASCII表を出力するPietコード（6倍拡大）

これをnpietで実行すると次のようになります

> ./npiet -cs 6 asciix6.png 
|' ' (32)|'!' (33)|'"' (34)|'#' (35)|'$' (36)|'%' (37)|'&' (38)|''' (39)|'(' (40)|')' (41)|'*' (42)|'+' (43)|',' (44)|'-' (45)|'.' (46)|'/' (47)|
|'0' (48)|'1' (49)|'2' (50)|'3' (51)|'4' (52)|'5' (53)|'6' (54)|'7' (55)|'8' (56)|'9' (57)|':' (58)|';' (59)|'<' (60)|'=' (61)|'>' (62)|'?' (63)|
|'@' (64)|'A' (65)|'B' (66)|'C' (67)|'D' (68)|'E' (69)|'F' (70)|'G' (71)|'H' (72)|'I' (73)|'J' (74)|'K' (75)|'L' (76)|'M' (77)|'N' (78)|'O' (79)|
|'P' (80)|'Q' (81)|'R' (82)|'S' (83)|'T' (84)|'U' (85)|'V' (86)|'W' (87)|'X' (88)|'Y' (89)|'Z' (90)|'[' (91)|'\' (92)|']' (93)|'^' (94)|'_' (95)|
|'`' (96)|'a' (97)|'b' (98)|'c' (99)|'d'(100)|'e'(101)|'f'(102)|'g'(103)|'h'(104)|'i'(105)|'j'(106)|'k'(107)|'l'(108)|'m'(109)|'n'(110)|'o'(111)|
|'p'(112)|'q'(113)|'r'(114)|'s'(115)|'t'(116)|'u'(117)|'v'(118)|'w'(119)|'x'(120)|'y'(121)|'z'(122)|'{'(123)|'|'(124)|'}'(125)|'~'(126)|''(127)|

最後のASCIIコード127は実は印字できない文字なので、 ここだけ垂直バー|がずれているのはご愛嬌です。

プログラムの構造解説

さて、プログラムにはコロン「：」で始まる行がありますが、 それが概ねプログラムの処理のひとかたまりを表します。

それらがどのような順で実行されるかを示したものが下図になります。

プログラムの処理順

詳しく解説します。

プログラム開始地点

まず、プログラムの開始地点は「:1」というブロックです。 そこから表の縦方向（行）のループの開始地点「:loopY」と、横方向（列）のループの開始地点「:loopX」を通ります。

プログラム開始地点

この間、スタックにはループカウンタの役割を果たす値がプッシュされます。

文字コード計算と出力

次に、「表示する文字コードを計算」から「文字コードを表示」までの処理です。次の部分にあたります。

表示処理（1文字）

例えば、文字コードが100(英小文字d)のときは、この処理で次の文字列が出力されます。

|'d'(100)

各ブロックの処理は次のとおりです。

ブロック名 処理説明
:loopX 文字コードの計算（X+16*Y）
:out_bar 垂直バー|の出力
:out_bar_return 次の処理の決定
:out_bar_return1 （次の処理）
:out_char 文字出力（例：'d'）
:out_char_return （次の処理）
:out_num, :out_num_out 文字コードの出力（例：(100)）

改行判定〜改行しない場合

次に、「:out_num_return」というブロックで改行判定をします。

まだ1行ぶんの出力が終わっていないなら改行不要と判定されます。この場合は、横方向のループカウンタxに1を足して、「:loopX」に戻り、 次の文字の出力を続けます。

同じ行で処理を続ける場合

このループで表の１行が出来上がっていきます。 ただし、右端に垂直バーが出ないことに注意です。

|'`' (96)
|'`' (96)|'a' (97)
|'`' (96)|'a' (97)|'b' (98)
|'`' (96)|'a' (97)|'b' (98)|'c' (99)
|'`' (96)|'a' (97)|'b' (98)|'c' (99)|'d'(100)
|'`' (96)|'a' (97)|'b' (98)|'c' (99)|'d'(100)|'e'(101)
...

改行判定〜改行する場合

１行ぶんの表示が終わった場合は、改行します。 ただし、改行の前に表の右端を閉じるため垂直バー|を出力します。 垂直バーを出力する処理は「:out_bar」ブロックで一度書いたので、使い回すことにします。 その後、ループカウンタを更新（yに1を足し、xを0にする）して、横方向のループを再開します。

改行処理は次の部分で行なっています。

次の行に移る場合

ブロック名 処理説明
:out_num_return 文字コード出力後の処理先兼、改行判定
:out_bar 垂直バー|の出力
:out_bar_return 次の処理の決定
:out_bar_return2 （次の処理）
:out_NL 改行文字出力
:out_NL_return （次の処理）

改行する前に、「:out_num_return」ブロックから「:out_bar」に入り、垂直バー|を出力します。

同じ「:out_bar」の処理でも、「:loopX」から入った時と、「:out_num_return」から入った時とで、処理ルートを変える必要があります。そのために「:out_bar」に入る直前にスタックにフラグをプッシュしておき、その値に応じて行き先を変えます。

プログラムをみると、「:loopX」と「:out_num_return」の最後はいずれもgoto:out_barです。 その直前で、「:loopX」ではpush1を、「:out_num_return」ではpush2を実行して、フラグをプッシュしています。 「:out_bar_return」では、フラグが1なら「:out_bar_return1」に進み、フラグが2なら「:out_bar_return2」に進むように設計されているため、処理ルートを変えることができます。

Pietはスタックが唯一のメモリですので、同じ処理を使い回す場合は、フラグを使って処理順序を変えます。

終了判定

「:out_NL_return」ブロックは、プログラムの終了判定もしています。ここでは、縦方向ループカウンタyの値をチェックし、7を超えたら終了、「:end」に進みます。

終了

おまけ〜表の見栄えを良くする

ここまでの説明に出てこなかった下図の部分の補足です。

表の幅の補正

この部分は、表の１マスのサイズを揃えるために、 半角スペースを出力する処理をしています。

この処理が抜けると、下に示すように、 文字コードの数値が2桁か3桁かによって表のマスの長さが変わり、垂直バーの位置がずれてしまいます。 （右端までスクロールするとわかりやすいです。申し訳ないですが、スマホだとわからないかもしれません・・・。）

|' '(32)|'!'(33)|'"'(34)|'#'(35)|'$'(36)|'%'(37)|'&'(38)|'''(39)|'('(40)|')'(41)|'*'(42)|'+'(43)|','(44)|'-'(45)|'.'(46)|'/'(47)|
|'0'(48)|'1'(49)|'2'(50)|'3'(51)|'4'(52)|'5'(53)|'6'(54)|'7'(55)|'8'(56)|'9'(57)|':'(58)|';'(59)|'<'(60)|'='(61)|'>'(62)|'?'(63)|
|'@'(64)|'A'(65)|'B'(66)|'C'(67)|'D'(68)|'E'(69)|'F'(70)|'G'(71)|'H'(72)|'I'(73)|'J'(74)|'K'(75)|'L'(76)|'M'(77)|'N'(78)|'O'(79)|
|'P'(80)|'Q'(81)|'R'(82)|'S'(83)|'T'(84)|'U'(85)|'V'(86)|'W'(87)|'X'(88)|'Y'(89)|'Z'(90)|'['(91)|'\'(92)|']'(93)|'^'(94)|'_'(95)|
|'`'(96)|'a'(97)|'b'(98)|'c'(99)|'d'(100)|'e'(101)|'f'(102)|'g'(103)|'h'(104)|'i'(105)|'j'(106)|'k'(107)|'l'(108)|'m'(109)|'n'(110)|'o'(111)|
|'p'(112)|'q'(113)|'r'(114)|'s'(115)|'t'(116)|'u'(117)|'v'(118)|'w'(119)|'x'(120)|'y'(121)|'z'(122)|'{'(123)|'|'(124)|'}'(125)|'~'(126)|''(127)|

これを防ぐため、文字コードが2桁の場合は、文字出力（'c'など）の後ろに半角スペース' 'を1文字出力してから、文字コードの出力（(99)など）をしています。これで垂直バーの位置ずれを防ぐことができます。

おわりに

今回は、プログラムの流れを図示しながら解説してみました。 ブログの更新を１週間サボってこれらの図を半自動で作成できるツールを作っていました。 おかげで説明する側としても労力がだいぶ減りましたし、 多少なりともわかりやすくなっていれば良いと思います。

今回はスタックの細かい変化は省きましたが、 Pietでプログラミングするときにはスタックの変化も追っていく必要があります。 今後はスタックの変化も図にできたらいいなあと思いつつ、 図示用ツールを作成中です。

次回は何を題材にしようかちょっと迷ってますが、 算数・数学チックな話になるのではないかと思います。 （素数判定とか、分数計算とか）

ではまた。