Javascript で Brainf**k のインタプリタを書いてみた

※Brainf**k の正しい名称には問題のある単語が含まれているため、本記事では伏せ字を使用しています。

Brainf**k とは

実行形式のコンパイラ・インタプリタともに100バイト前後という驚異的小型さで有名な難解プログラミング言語です。

実行系は内部に以下の4つの変数を持っています。

1. データの入った配列
2. データポインタ
3. 命令の入った配列
4. 命令ポインタ

データの入った配列とデータポインタ

単なるオクテット列（バイト列）です。
通常のプログラミング言語における変数に相当するものと考えてよいでしょう。
可変長配列でも問題ないのでArrayでも良いのですが、今回はUint8Arrayとします。

データポインタはデータの入った配列の特定の要素を指す添字です。
データポインタの指す要素だけが、後述する命令での操作対象になります。

命令の入った配列と命令ポインタ

命令は全部で8種類あります。

命令	意味
>	データポインタの値を加算します。
<	データポインタの値を減算します。
+	データを加算します。
-	データを減算します。
.	データを出力します。
,	入力から 1 バイトをデータにします。
[	データが 0 なら、命令ポインタを対応する]のところまで進めます。
]	データが 0 ではないなら、命令ポインタを対応する[のところまで戻します。
※表内の「データ」は「データポインタの指しているデータ配列の値」を意味します。

命令の入った配列は Brainf**k のソースコードに等しいです。
ここであえてソースコードと呼んでいないのは 命令に該当しない文字は無視する というルールがあるためです。
後述する理由により、実装ではソースコードとは別の配列を用意しました。
もちろん、特に理由がなければソースコードと同一でも問題ありません。

命令ポインタは1つの命令を実行するたびに加算します。
[や]で命令ポインタが変動した場合、その直後の命令から実行されます。
命令ポインタが命令の入った配列の長さに等しくなったら、プログラムの実行終了です。

実装

Brainf**k の仕組みについてわかったところで、本題のインタプリタの実装に入ります。

まずは構文解析する（parse）

インタプリタでソースコードを実行する前にまずは構文解析します。
その理由としては以下の3つ。

1. コードが正当か事前にチェックしたい
   [と]の対応関係を確認するだけですが、構文エラーならば実行前に確認できた方が良いでしょう。

2. いずれは派生系に対応したい
   Brainf**k はその単純な構文から8つの命令に相当する文言を様々なものに置き換えたたくさんの派生があります。派生に対応できるような処理をインタプリタに組み込むと必要以上に複雑化してしまうでしょう。

3. いずれはコンパイラも作りたい
   構文解析をインタプリタと共有させることができます。また、コンパイラも派生系に対応できるようになります。

これらの要求はコードと命令の対応関係を解決する処理をインタプリタから切り離せば容易に達成できます。

インプリタ本体

入出力は Node.js であれば標準入出力を使えば良いでしょう。
しかし、Web クライアントではその Web によって異なります。
よって実行時に指定できるように、入出力先はインタプリタから切り離します。
方法としては入力をイテレーターで受け取り、逆に出力はプログラムの実行メソッドで返すようにします。

構文解析は既にされているため、実行時エラーは既に入力が閉じられているのに入力を読もうとした場合にのみ発生します。

完成したソースコード

以上の仕様を盛り込んで完成したソースコードがこちらです。

/*
 * 0x01などの値に特に意味はありません。
 * 重複しなければなんでもOKです。
 */
const Instruction = Object.freeze( {
  INCREMENT_POINTER: 0x01,
  DECREMENT_POINTER: 0x02,
  INCREMENT: 0x03,
  DECREMENT: 0x04,
  OUTPUT: 0x05,
  INPUT: 0x06,
  JUMP_FOWARD: 0x07,
  JUMP_BACK: 0x08,
} )

const DEFAULT_DATA_SIZE = 30000

/*
 * ただ0のみを返すダミーの入力です。
 * /dev/zeroのようなものです。
 */
const DEFAULT_INPUT_STREAM = (function*(){
  for (;;) yield 0
})()

class BrainFKSyntaxError extends Error {

  constructor( ...args ) {
    super( ...args )
  }

}

class BrainFKRuntimeError extends Error {

  constructor( ...args ) {
    super( ...args )
  }

}

const parseCode = ( code ) => {

  /*
   * 以下の3つが戻り値です。
   * instructions: 命令の入った配列
   * jumpInfo    : [, ]でジャンプする先の命令ポインタの値の入った連想配列
   * debugInfo   : 命令ポインタの値とソースコード上の文字列位置の対応関係の入った連想配列
   */
  const instructions = [],
        jumpInfo = new Map,
        debugInfo = new Map

  const stack = []
  let index = 0, instructionPointer = 0
  for ( ; index < code.length; index ++ ) {

    let instruction

    switch ( code[ index ] ) {

      case ">":
        instruction = Instruction.INCREMENT_POINTER
        break

      case "<":
        instruction = Instruction.DECREMENT_POINTER
        break

      case "+":
        instruction = Instruction.INCREMENT
        break

      case "-":
        instruction = Instruction.DECREMENT
        break

      case ".":
        instruction = Instruction.OUTPUT
        break

      case ",":
        instruction = Instruction.INPUT
        break

      case "[":
        instruction = Instruction.JUMP_FOWARD
        stack.push( instructionPointer )
        break

      case "]":
        instruction = Instruction.JUMP_BACK
        if ( stack.length == 0 ) {
          throw new BrainFKSyntaxError( `missing "[" index=${ index }` )
        }
        const foward = stack.pop()
        jumpInfo.set( foward, instructionPointer )
        jumpInfo.set( instructionPointer, foward )
        break

      default:
        continue

    }

    debugInfo.set( instructionPointer, [ index, index + 1 ] )
    instructions.push( instruction )
    instructionPointer ++

  }

  if ( stack.length > 0 ) {
    throw new BrainFKSyntaxError( `missing "]" index=${ index }` )
  }

  return {
    instructions: Uint8Array.from( instructions ),
    jumpInfo,
    debugInfo,
  }

}

class BrainFKInterpreter {

  #instructions
  #jumpInfo
  #data
  #inputStream
  #debugInfo

  constructor( code, { dataSize = DEFAULT_DATA_SIZE, inputStream = DEFAULT_INPUT_STREAM } = {} ) {

    const { instructions, jumpInfo, debugInfo } = parseCode( code )
    this.#instructions = instructions
    this.#jumpInfo = jumpInfo
    this.#data = new Uint8Array( Number( dataSize ) )
    this.#inputStream = inputStream
    this.#debugInfo = debugInfo

  }

  async execute() {

    const outputs = []

    for await ( const [ ,,, output ] of this.step() ) {

      if ( output != null ) {

        outputs.push( output )

      }

    }

    return Uint8Array.from( outputs )

  }

  /*
   * ジェネレーターにすることで、命令ごとにステップ実行できます。
   */
  async * step() {

    const instructions = this.#instructions
    const jumpInfo = this.#jumpInfo
    const data = this.#data
    const debugInfo = this.#debugInfo

    for ( let instructionPointer = 0, dataPointer = 0; instructionPointer < instructions.length; instructionPointer ++ ) {

      let output = null

      switch ( instructions[ instructionPointer ] ) {

        case Instruction.INCREMENT_POINTER:
          ++ dataPointer
          break

        case Instruction.DECREMENT_POINTER:
          -- dataPointer
          break

        case Instruction.INCREMENT:
          ++ data[ dataPointer ]
          break

        case Instruction.DECREMENT:
          -- data[ dataPointer ]
          break

        case Instruction.OUTPUT:
          output = data[ dataPointer ]
          break

        case Instruction.INPUT:
          const input = await this.#inputStream.next()
          if ( input.done ) {
            throw new BrainFKRuntimeError( `input is already closed.` )
          }
          data[ dataPointer ] = input.value
          break

        case Instruction.JUMP_FOWARD:
          if ( data[ dataPointer ] == 0 ) {
            instructionPointer = jumpInfo.get( instructionPointer )
          }
          break

        case Instruction.JUMP_BACK:
          if ( data[ dataPointer ] != 0 ) {
            instructionPointer = jumpInfo.get( instructionPointer )
          }
          break

      }

      yield [ dataPointer, data[ dataPointer ], debugInfo.get( instructionPointer ), output ]

    }

  }

}

おわり

以上！
Brainf**k 自体は実用的とは言い難いですが、インタプリタやコンパイラを書く練習にはなるかもしれませんね。