難解プログラミング言語のひとつ、Brainfuckのインタプリタを書いてみました。命令は8つしかありませんが、立派にチューリング完全です。

言語仕様

処理系の構成要素

  • インストラクションポインタ – プログラム中のある文字を指す。
  • 少なくとも30000個の要素を持つバイトの配列 – 各要素はゼロで初期化される。
  • データポインタ – 前述の配列のどれかの要素を指す。最も左の要素を指すよう初期化される。
  • 入力と出力の2つのバイトストリーム

命令

  1. > ポインタをインクリメントする。ポインタをptrとすると、C言語の「ptr++;」に相当する。
  2. < ポインタをデクリメントする。C言語の「ptr--;」に相当。
  3. + ポインタが指す値をインクリメントする。C言語の「(*ptr)++;」に相当。
  4. - ポインタが指す値をデクリメントする。C言語の「(*ptr)--;」に相当。
  5. . ポインタが指す値を出力に書き出す。C言語の「putchar(*ptr);」に相当。
  6. , 入力から1バイト読み込んで、ポインタが指す先に代入する。C言語の「*ptr=getchar();」に相当。
  7. [ ポインタが指す値が0なら、対応する ] の直後までジャンプする。C言語の「while(*ptr){」に相当。
  8. ] ポインタが指す値が0でないなら、対応する [ にジャンプする。C言語の「}」に相当。

コード

bfi.c (Gist)

#include <stdio.h>
#define RAMSIZE 30000

int main(int argc, char **argv)
{
  FILE *f;                /* インストラクションポインタ */
  int *p;                 /* データポインタ */
  int b[RAMSIZE] = { 0 }; /* バッファ */
  char c;                 /* 文字 */
  int i;                  /* カウンタ */

  p = b;
  if ((f = fopen(argv[1], "r")) == NULL) {
    f = stdin;
  }

  while ((c = (char)fgetc(f)) != EOF) {
    switch (c) {
    case '>':
      p++;
      break;
    case '<':
      p--;
      break;
    case '+':
      (*p)++;
      break;
    case '-':
      (*p)--;
      break;
    case '.':
      fputc(*p, stdout);
      break;
    case ',':
      *p = fgetc(stdin);
      break;
    case '[':
      if (*p == 0) {
        for (i = 0; c != ']' || i;) {
          if ((c = (char)fgetc(f)) == EOF) {
            return 1;
          }
          if (c == '[') {
            i++;
          }
          else if (c == ']' && i) {
            i--;
          }
        }
      }
      break;
    case ']':
      if (*p != 0) {
        for (i = 0; c != '[' || i;) {
          if (fseek(f, -2, SEEK_CUR)) {
            return 1;
          }
          if ((c = (char)fgetc(f)) == EOF) {
            return 1;
          }
          if (c == ']') {
            i++;
          }
          else if (c == '[' && i) {
            i--;
          }
        }
      }
      break;
    }
  }

  return 0;
}

hello.bf (Gist)

+++++++++[>++++++++>+++++++++++>+++++<<.>++.+++++++..+++.>-.------------.+.

hello.bf を食わせてやると、”Hello, world!” と表示されます。

ビルド

gcc -o bfi bfi.c

実行

./bfi hello.bf
# または
./bfi < hello.bf

注意

実行するスクリプトによっては、危険な振舞いをする可能性があります。十分に注意してください。