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 使うよりはましだが、これじゃ不完全。

現在のカーソル位置の値だけおぼえといて、隣に移動したときは最初から実行しなおして、隣の値を思い出してから実行する。