pointer-free な C 言語はチューリング完全か
ってのが、id:mame っちのところにあったので似非実装
char code[1024]; char input[1024]; struct V { #define REEVAL 0 #define RETURN 1 #define COMPLETE 2 int state; int value; }; /* * ret_step ステップ実行した後の * ret_cursor の値を返す。 */ int re_eval(int ret_step, int ret_cursor); /* * ret_step ステップ実行して結果を返す * step はこれまで実行したステップ数 * pc は実行を開始するコード位置 * cursor は現在のカーソル位置 * cell は現在のカーソル位置の値 * ipos は入力位置 * * i) ret_step == -1 の場合 * プログラムは最後まで実行され * { state = COMPLETE; value = 0} が返される。または終了しない。 * ii) ret_step >= の場合 * プログラムは ret_step まで実行される。 * a) 実行し終わったときのカーソルが ret_cursor と一致した場合 * { state = RETURN; value = カーソル位置の値 } * b) 実行し終わったときのカーソルが ret_cursor と異なっている場合 * { state = REEVAL; value = step } * */ struct V eval(int step, int ret_step, int ret_cursor, int pc, int cursor, int cell, int ipos) { int step_save = step; struct V v; /* * ret_step まで実行しなくても * 値は0であることが確定している。 */ if (ret_step >= 0 && ret_step <= ret_cursor) { v.state = RETURN; v.value = 0; return v; } while (ret_step == -1 || step < ret_step) { switch (code[pc]) { case '+': cell++; pc++; step++; break; case '-': cell--; pc++; step++; break; case '<': pc++; step++; { /* カーソルを左に移動する前に * step_save での cursor-1 が必要 */ int left_cell = re_eval(step_save, cursor-1); return eval(step, ret_step, ret_cursor, pc, cursor-1, left_cell, ipos); } case '>': pc++; step++; { /* カーソルを右に移動する前に * step_save での cursor+1 が必要 */ int right_cell = re_eval(step_save, cursor+1); return eval(step, ret_step, ret_cursor, pc, cursor+1, right_cell, ipos); } case '.': pc++; step++; { v = eval(step, ret_step, ret_cursor, cursor, cell, ipos, exec); if (v.state == COMPLETE) { putchar(cell); } return v; } case ',': pc++; step++; { cell = input[ipos++]; break; } case '[': pc++; step++; { if (!cell) { int n; for (n = 1; n > 0;) { if (code[pc] == '[') n++; if (code[pc] == ']') n--; pc++; } } break; } case ']': step++; { int n; for (n = 1; n > 0;) { pc--; if (code[pc] == '[') n--; if (code[pc] == ']') n++; } } case 0: { if (ret_step == -1) { v.state = COMPLETE; v.value = 0; } else { v.state = REEVAL; v.value = step_save-1; } return v; } default: pc++; step++; break; } } if (ret_cursor == cursor) { v.state = RETURN; v.value = cell; } else { v.state = REEVAL; v.value = step_save-1; } } int re_eval(int ret_step, int ret_cursor) { struct V v; for (;;) { v = eval(0, ret_step, ret_cursor, 0, 0, 0, 0); if (v.state == RETURN) return v.value; ret_step = v.value; } } int main() { read_code(); read_input(); eval(0, -1, 0, 0, 0, 0, 0); return 0; }
コンパイルすらしてない。
va_arg 使うよりはましだが、これじゃ不完全。
現在のカーソル位置の値だけおぼえといて、隣に移動したときは最初から実行しなおして、隣の値を思い出してから実行する。