Zenn
🔨

bcコマンドで配列を使わずにBrainf**kインタプリタ本体を作ってみた

2023/01/19に公開
2件
Brainfuck
bc
tech

作った理由は特にありません．強いて申し上げれば，筆者いつものお遊びでしょうか．

【参考】

経緯としては，別件でタグシステム（抽象機械）をGNU bcで配列を使わず多倍長整数演算のみで実装してみたのですが（他サイト記事参照），これができるなら，とりあえず文字コード変換さえ外部にお任せすれば，Brainf**kのインタプリタ本体実装にも使えるんじゃないかと思い，やってみたら，タグシステムにおけるキュー構造よりもはるかに簡単に実装できたという次第です．よくわかりませんね．

【追記】今回の記事内容のデモ動画を作成してみました．

YouTubeのvideoIDが不正ですhttps://youtube.com/shorts/Kn9-cjCXTnU

bcコマンドによる言語処理系実装

bcは，UNIX系OSのシェル上でお手軽に数式演算を行うコマンドbcとして重宝されていますが，C言語ライクな各種構文も利用でき，プログラミング言語処理系としても相応に利用できます．また，リソース上限まで無限の桁数が利用可能な多倍長整数に基づく任意精度演算が可能なことから，たとえば，そのような演算が不可能な言語処理系のプログラムから，bcを外部プログラムとして呼び出して演算させる，という例もあります．bcのうち，GNU bcはPOSIX仕様を拡張した独自実装で，変数名として2文字以上を使用することができるなどの特徴があります．

一方で，数値演算特化ということもあって，データ構造としては，値や添字が数値のみの配列構造しかありません．また，リテラルとしての指定以外，文字列操作を行う機能もありません．このため，bcを用いて言語処理系の類を実装するということは，普通はありません．ただ，逆に，そのあたりさえなんとかできれば，少なくともBrainf**kのような，チューリングマシンをモデルとした簡易処理系はすぐに実装できることになります．さしあたり文字コード変換を別の処理系に任せれば，あとは数値配列で処理系本体が作れそうです．

でも，そこまで制約がある言語なら，仕様上の配列も使わず，任意精度演算を生かした疑似配列構造を作ればいいじゃないという発想の下，パフォーマンスを一切無視して実装してみました（標準仕様のbcには外部読み込みがなく，配列に文字コード化したプログラムを読み込みにくいというのもあります）．これがうまくいけば，豊富な数学関数と単純な繰り返し実行機能をもつ関数電卓でも，チューリング完全な処理系が作れるかもしれない…という目論見もありました．意味不明ですね．

多倍長整数演算による整数配列の模倣

基本的な考え方は，10進数表現の桁上り処理を数式演算で行い，ひとつの配列セル内の整数を決まった桁数で表現するというものです．たとえば，+[]という文字配列を，外部プログラムで次のようにASCIIコード変換したとします．

+[] => 43 91 93

これを，それぞれの数値を10進数3桁で表現することとし，次のようにひとつの整数に変換します．

43 91 93 => 93 91 43 => 93 * 1000^2 + 91 * 1000^1 + 43 * 1000^0 = 93091043

下位から上位に向かう並びにするのは，次のように，添字iに対応する値が整数演算（割り算結果は小数部切り捨て）によって比較的求めやすくなるためです．

d = 3, c = 93091043

i = 0
c / (10^(d * i)) - c / (10^(d * i)) / (10^d) * (10^d)
= 93091043 / (10^0) - 93091043 / (10^0) / (10^3) * (10^3)
= 93091043 - 93091043 / 1000 * 1000
= 93091043 - 93091 * 1000
= 93091043 - 93091000
= 43

i = 1
c / (10^(d * i)) - c / (10^(d * i)) / (10^d) * (10^d)
= 93091043 / (10^3) - 93091043 / (10^3) / (10^3) * (10^3)
= 93091 - 93091 / 1000 * 1000
= 93091 - 93 * 1000
= 93091 - 93000
= 91

i = 2
c / (10^(d * i)) - c / (10^(d * i)) / (10^d) * (10^d)
= 93091043 / (10^6) - 93091043 / (10^6) / (10^3) * (10^3)
= 93 - 93 / 1000 * 1000
= 93 - 0 * 1000
= 93 - 0
= 93

また，添字iに対応する値のインクリメント／デクリメントはとても簡単です．

d = 3, c = 93091043

i = 2
c + 10^(d*i)
= 93981943 + 10^6
= 93981943 + 1000000
= 94981943

i = 2
c - 10^(d*i)
= 93981943 - 10^6
= 93981943 - 1000000
= 92981943

bcの多倍長整数演算を用いたBrainf**kインタプリタ本体の実装例

上記を踏まえて今回実装したのが，次のbc用コードです．

  • 内部配列相当のaとその添字pは，前節の例の通り3桁でひとつの配列セルを表現しています．
  • プログラムコード配列相当のcとその添字iは，命令が8文字相当しかないため，1～8の1桁のみで表現しています．
  • ここでは整数変換したBrainf**kコードを代入する変数cは定義されていません．
  • bcが文字を直接読み込めないため，『,』は実装していません．
bf-mpi_skel.bc
scale = 0; b = 1; d = 3; i = 0; a = 0; p = 0
while (i < length(c)) {
  r = c/(10^(b*i))-c/(10^(b*i))/(10^b)*(10^b)
  if (r == 1) a += 10^(d*p)
  if (r == 2) a -= 10^(d*p)
  if (r == 3) p += 1
  if (r == 4) p -= 1
  if (r == 5) a/(10^(d*p))-a/(10^(d*p))/(10^d)*(10^d)
  if (r == 7) {
    s = a/(10^(d*p))-a/(10^(d*p))/(10^d)*(10^d)
    if (s == 0) {
      n = 1
      while (n != 0) {
        i += 1
        r = c/(10^(b*i))-c/(10^(b*i))/(10^b)*(10^b)
        if (r == 7) n += 1
        if (r == 8) n -= 1
      }
    }
  }
  if (r == 8) {
    s = a/(10^(d*p))-a/(10^(d*p))/(10^d)*(10^d)
    if (s != 0) {
      n = 1
      while (n != 0) {
        i -= 1
        r = c/(10^(b*i))-c/(10^(b*i))/(10^b)*(10^b)
        if (r == 8) n += 1
        if (r == 7) n -= 1
      }
    }
  }
  i += 1
}

次は，tr，rev，cat等を組み合わせて作成した，文字と数値を相互変換して上記bcコードを実行するためのシェルスクリプトです．ファイルから読み込んだBrainf**kコードを文字置換で整数表現にし，上記bcコードに変数cへの代入文として追加してbcに出力します．その後，bcからのASCIIコード出力を文字に変換しています．

bf-bc.sh
#!/bin/sh
BFC=`cat $1 | tr '+-' '12' | tr '><' '34' |\
              tr '.,' '56' | tr '[]' '78' | rev`
(printf "c = $BFC\n" && cat bf-mpi_skel.bc) | bc |
while read c; do printf "$(printf '\\%o' $c)"; done

今回は，Brainf**kコードの例として，次の2から100までの間の整数から素数を求めるプログラムを用います．

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

この例を用いた実行結果は次の通りです．

$ sh bf-bc.sh primes.bf
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

※Debian GNU/Linux 11のシェル環境＋GNU bc 1.07.1にて実行を確認しています．

備考

記事に関する補足

  • 次は，bcの配列を用いた実装例です．bcがファイルや標準入力から数値を配列に直接読み込むということが厳しいので，配列への代入を行うbcのコードをシェルスクリプトの文字列処理として生成しています．メタプログラミング？
bf-bc_arr.sh
while read L; do P=$P$L; done < $1
(while [ $P ]; do T=${P%${P#?}}; printf 'c[e]=%d;e+=1;' \'$T; P=${P#?}; done &&
while read L; do printf '%s\n' "$L"; done < bf-arr_skel.bc) | bc |
while read c; do printf $(printf '\\%o' $c); done

i = 0; p = 0
while (i < e) {
  if (c[i] == 43) a[p] += 1
  if (c[i] == 45) a[p] -= 1
  if (c[i] == 62) p += 1
  if (c[i] == 60) p -= 1
  if (c[i] == 46) a[p]
  if (c[i] == 91) {
    if (a[p] == 0) {
      n = 1
      while (n != 0) {
        i += 1
        if (c[i] == 91) n += 1
        if (c[i] == 93) n -= 1
      }
    }
  }
  if (c[i] == 93) {
    if (a[p] != 0) {
      n = 1
      while (n != 0) {
        i -= 1
        if (c[i] == 93) n += 1
        if (c[i] == 91) n -= 1
      }
    }
  }
  i += 1
}

$ cat primes.bf
>++++[<++++++++>-]>++++++++[<++++++>-]<++.<.>+.<.>++.<.>++.<.>------..<.>.++.<.>--.++++++.<.>------.>+++[<+++>-]<-.<.>-------.+.<.>-.+++++++.<.>------.--.<.>++.++++.<.>---.---.<.>+++.-.<.>+.+++.<.>--.--.<.>++.++++.<.>---.-----.<.>+++++.+.<.>.------.<.>++++++.----.<.>++++.++.<.>-.-----.<.>+++++.+.<.>.--.>++++++++++.
$ sh bf-bc_arr.sh primes.bf
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
  • 文字コード変換等にPython使うのはちょっと重すぎる気がするので，後でもうちょっとお手軽なツールを使うことを考えています．専用のコマンドをCで書いた方がいいかな？ ⇒各種コマンドを組み合わせたシェルスクリプトに変更しました．旧版のPythonコードをここに移動しておきます．
bf-codes2bcmpi.py
codes = input().rstrip()
bcmpicodes = 0
cnum = {"+":1 ,"-":2 ,">":3 ,"<":4 ,".":5 ,",":6 ,"[":7, "]":8}
for e in range(len(codes)): bcmpicodes += cnum[codes[e]]*(10**e)

bcprog = f'c = {bcmpicodes}; '
with open('bf-mpi_skel.bc') as f: r = f.readlines()
print(bcprog+''.join(r))
bf-bc2chars.py
from sys import stdin
for s in stdin: print(chr(int(s)), end='')
print()
  • 計算可能性という観点では，文字に対応する数値の入出力であってもオリジナルと等価と捉えることができ，むしろ，仕様上の配列の長さが多倍長整数演算によって無限が想定されることから，今回の実装例を踏まえると，標準仕様のbcはチューリング完全と言って差し支えないかと思います．あるシステムがチューリング完全であるかを判断する際に，無限長のテープ装置に相当するものがないことを理由に『チューリング完全ではない』とすることがあるのですが，（ハードウェアリソースを食いつぶそうとしてしまうという意味で）油断はできないかもしれません．

更新履歴

  • 2023-01-24：記事に関する補足にbcの配列を用いる場合の実装例を追加
  • 2023-01-21：文字コード変換を各種コマンドを組み合わせたシェルスクリプトに変更
  • 2023-01-20：記事に関する補足に記述を追加
  • 2023-01-20：各プログラムを更に修正・変更
  • 2023-01-20：bfコード相当を1配列セル/1桁で表現した修正版に変更
  • 2023-01-19：デモ動画のURLを追加
  • 2023-01-19：初版公開

Discussion

ko1nksmko1nksm

いつものお遊びで bc コマンド以外の外部コマンド依存をなくしてみました。eval あたりを駆使するともう少し行数は減らせると思います。理論上実現可能とは言え面倒です。コード行数を減らすために rev の部分は bfc に組み込んでいます。

set を駆使しないで普通に変数を使えばもっとわかりやすコードになると思います。私が set を使ってるのはローカル変数の使用を減らすためで、すでに手元にこのようなコードがいくつもあるので書き直したくなかっただけです。

#!/bin/sh

shcat() {
  while IFS= read line; do
    printf '%s\n' "$line"
  done < "$1"
}

bfc() {
  set -- "$1" "$2" ""
  while [ "$2" ]; do
    case $2 in
       +*) set -- "$1" "${2#?}" "1${3}";;
       -*) set -- "$1" "${2#?}" "2${3}";;
      \>*) set -- "$1" "${2#?}" "3${3}";;
      \<*) set -- "$1" "${2#?}" "4${3}";;
       .*) set -- "$1" "${2#?}" "5${3}";;
       ,*) set -- "$1" "${2#?}" "6${3}";;
      \[*) set -- "$1" "${2#?}" "7${3}";;
      \]*) set -- "$1" "${2#?}" "8${3}";;
        *) set -- "$1" "${2#?}" "${2%"${2#?}"}${3}" ;;
      # " シンタックスハイライターの誤判断を修正するためのダミー
    esac
  done
  eval "$1=\$3"
}

bfc BFC "$(shcat "$1")"
(printf "c = $BFC\n" && shcat bf-mpi_skel.bc) | bc | {
  while read c; do
    printf "$(printf '\\%o' $c)"
  done
}
TAKIZAWA YozoTAKIZAWA Yozo

バッチリ動きました．お見事です．ありがとうございました．

しかしこうなると，POSIXシェルだけでBrainf**kインタプリタ作りたくなってきますねえ…．既にいくつも作られているような気はしますが．