whitespaceプログラムをc++プログラムに変換するrubyプログラムを書きました
- ifを並べ立ててラベルを表現しました
- ワンパスで変換したかった
背景
学校で｢whitespaceプログラムを実行するrubyプログラムを書け｣という課題が出たので書くことにしました.
whitespaceのラベルは静的なので, c++に変換できるはずだと思ったので, c++に変換して実行するプログラムを書きました.
参考
この記事はWhitespaceをC言語ソースに変換する - koturnの日記を多大に参考にしています.
labelを実装する
whitespaceには他の言語で言うgotoとgosubがあります.
サブルーチンではない場合, 処理はそのまま進むことになります.
つまり各ラベルはgotoとgosubの両方に対応する必要があるということでです.
これがwhitespaceからの変換の1番の問題点です. 他の部分は普通にワンパスで書き換えることが可能なので, 問題ありません.
longjmpを使う
WhitespaceをC言語ソースに変換する - koturnの日記ではこの方法を使っていました.
で, これを見てしまったので, この方法は使わないことにしました.
whileとcontinueを使う
while(true)の内部にswitchを書き,
サブルーチン呼び出しの時は引数を指定して再帰します.
ジャンプするときはswitchのキーとなる変数を変更してcontinueします.
起動時のみgoto initでwhileの内部にジャンプします.
これでgotoとgosubが両立できます.
と思いきや,
サンプルコードが2203406793343056047716という巨大な値をラベルに指定しているので,
ラベルが表現できないことがわかりました.
しばらく自分の作った整数パーサーがバグっているのだと思いましたが,
他のwhitespaceの実装を読んでみると,
整数が固定長の言語ではラベルは文字列で表現するのが一般的だということがわかりました.
また,
整数表記にすると-0になるラベルを指定するプログラムもあるので,
そもそも整数で表現できると考えたのが間違いだとわかりました.
whileの内部でifを書きまくる
仕方がないのでラベルは文字列で表現し,
ifを連発して分岐することにしました.
ifの複文の最後には次のラベルの文字列をスイッチ用変数に代入して,
returnしない場合はそのまま次のラベルに突入するようにします.
この方針で完成したのが以下のプログラムです.
このプログラムでhostilefork/whitespacers: Interpreter Collection for the Whitespace Languageのexamples/hworld.wsを変換すると,
以下のようになります.
#include <cstdint>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int t1, t2;
vector<int> s;
map<int, int> h;
int popv() {
auto r = s.back();
s.pop_back();
return r;
}
int entry(string l) {
while (true) {
if (l == "") {
s.emplace_back(0);
s.emplace_back(72);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(1);
s.emplace_back(101);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(2);
s.emplace_back(108);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(3);
s.emplace_back(108);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(4);
s.emplace_back(111);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(5);
s.emplace_back(44);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(6);
s.emplace_back(32);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(7);
s.emplace_back(119);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(8);
s.emplace_back(111);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(9);
s.emplace_back(114);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(10);
s.emplace_back(108);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(11);
s.emplace_back(100);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(12);
s.emplace_back(32);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(13);
s.emplace_back(111);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(14);
s.emplace_back(102);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(15);
s.emplace_back(32);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(16);
s.emplace_back(115);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(17);
s.emplace_back(112);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(18);
s.emplace_back(97);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(19);
s.emplace_back(99);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(20);
s.emplace_back(101);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(21);
s.emplace_back(115);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(22);
s.emplace_back(33);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(23);
s.emplace_back(0);
t1 = popv();
t2 = popv();
h[t2] = t1;
s.emplace_back(0);
entry("STTTSTTTSTTTSSTSSTTSTSSTSTTTSTSSSTTSSTST");
entry("STTSTTTSSTTSSTSTSTTTSTTTSTTSTTSSSTTSTSSTSTTSTTTSSTTSSTST");
return 0;
l = "STTSSSSTSTTSSTSSSTTSSTSS";
}
if (l == "STTSSSSTSTTSSTSSSTTSSTSS") {
t1 = popv();
t2 = popv();
s.emplace_back(t2 + t1);
return 0;
l = "STTTSTTTSTTTSSTSSTTSTSSTSTTTSTSSSTTSSTST";
}
if (l == "STTTSTTTSTTTSSTSSTTSTSSTSTTTSTSSSTTSSTST") {
s.emplace_back(s.back());
s.emplace_back(h[popv()]);
s.emplace_back(s.back());
if (popv() == 0) {
l = "STTTSTTTSTTTSSTSSTTSTSSTSTTTSTSSSTTSSTSTSTSTTTTTSTTSSTSTSTTSTTTSST"
"TSSTSS";
continue;
}
cout << static_cast<char>(popv());
s.emplace_back(1);
t1 = popv();
t2 = popv();
s.emplace_back(t2 + t1);
l = "STTTSTTTSTTTSSTSSTTSTSSTSTTTSTSSSTTSSTST";
continue;
l = "STTTSTTTSTTTSSTSSTTSTSSTSTTTSTSSSTTSSTSTSTSTTTTTSTTSSTSTSTTSTTTSSTTS"
"STSS";
}
if (l == "STTTSTTTSTTTSSTSSTTSTSSTSTTTSTSSSTTSSTSTSTSTTTTTSTTSSTSTSTTSTTTSS"
"TTSSTSS") {
s.pop_back();
s.pop_back();
return 0;
l = "STTTSSTSSTTSSTSTSTTSSSSTSTTSSTSS";
}
if (l == "STTTSSTSSTTSSTSTSTTSSSSTSTTSSTSS") {
s.emplace_back(s.back());
s.emplace_back(s.back());
h[popv()] = cin.get();
s.emplace_back(h[popv()]);
s.emplace_back(s.back());
s.emplace_back(10);
t1 = popv();
t2 = popv();
s.emplace_back(t2 - t1);
if (popv() == 0) {
l = "STTTSSTSSTTSSTSTSTTSSSSTSTTSSTSSSTSTTTTTSTTSSTSTSTTSTTTSSTTSSTSS";
continue;
}
s.pop_back();
s.emplace_back(1);
t1 = popv();
t2 = popv();
s.emplace_back(t2 + t1);
l = "STTTSSTSSTTSSTSTSTTSSSSTSTTSSTSS";
continue;
l = "STTTSSTSSTTSSTSTSTTSSSSTSTTSSTSSSTSTTTTTSTTSSTSTSTTSTTTSSTTSSTSS";
}
if (l ==
"STTTSSTSSTTSSTSTSTTSSSSTSTTSSTSSSTSTTTTTSTTSSTSTSTTSTTTSSTTSSTSS") {
s.pop_back();
s.emplace_back(1);
t1 = popv();
t2 = popv();
s.emplace_back(t2 + t1);
s.emplace_back(0);
t1 = popv();
t2 = popv();
h[t2] = t1;
return 0;
l = "STTSTTTSSTTSSTSTSTTTSTTTSTTSTTSSSTTSTSSTSTTSTTTSSTTSSTST";
}
if (l == "STTSTTTSSTTSSTSTSTTTSTTTSTTSTTSSSTTSTSSTSTTSTTTSSTTSSTST") {
s.emplace_back(10);
s.emplace_back(13);
cout << static_cast<char>(popv());
cout << static_cast<char>(popv());
return 0;
}
return -1;
};
return -1;
}
int main() { entry(""); }
このプログラムでhostilefork/whitespacers: Interpreter Collection for the Whitespace Languageのexamplesのsudoku.ws以外は実行できたので,
課題の答えとしては良しとしました.
(sudoku.wsは他の実装でも実行できないのでそもそも壊れていると判断しました)
実装の反省点
popvしかc++の関数を用意しませんでしたが,
かなり変換後のプログラムが肥大化してしまったので,
他の命令にもc++の関数を用意するべきでした.
ifを並べる方法の問題点
このifを並べる方法には重大な問題点があります.
ラベルを素朴に線形探索しているため, 効率がとなってしまうことです.
この問題を解決するのは, ラベル名の一覧を保存しておいて, 変換の最後の過程に関数として並べるとかの方法がありますが, 今回はコードを素朴にワンパスで文字列に変換したかったので, その方法は使わないことにしました.
hatena-bookmark