brainfuck to 数学ゴルフ

brainfuck Ruby C

数学ゴルフが終了したようです。僕の解答も niha さんのと同じです。それはともかく、数学ゴルフの言語の入出力拡張版*1を提案されていました。とりあえず turing 完全であることを確かめるため brainfuck インタプリタを書こうと思ったのですが、面倒だったので brainfuck から数学ゴルフへの変換を定義してみました。

テープのエンコード

僕も変数の数は有限な方がかっこいいと思うので、テープをエンコードするために多倍長倍数を使うことにしました。テープ上の各セルは 1 バイトとして、以下の 3 変数でエンコードします。

  • l : ポインタ位置より左側の数字を多倍長で表現する
  • m : ポインタ位置の数字を表現する
  • r : ポインタ位置より右側の数字を多倍長で表現する

例えばテープが [1, 2, 3, 4, 5, 6, 7] で、ポインタが 4 の位置を指している状態は

  • l = 3 | (2 << 8) | (1 << 16)
  • m = 4
  • r = 5 | (6 << 8) | (7 << 16)

というようにエンコードします。

変換規則

上記のエンコードの上で、brainfuck の各命令は以下のように定義できます。多分。

brainfuck 数学ゴルフ 疑似コード
+ +m m += 1
- 0x m(xm +x) m -= 1
> a(l(+l)) m(+l) 0z 0m r(+m my b(0x y(xy +x)) y(0m +z)) zr l = l * 256 + m; m = r % 256; r /= 256
< a(r(+r)) m(+r) 0z 0m l(+m my b(0x y(xy +x)) y(0m +z)) zl r = r * 256 + m; m = l % 256; l /= 256
, >m m = getc
. <m putc(m)
[ m[ while(m > 0)
] ] end

a は定数 8 、b は定数 255 、x 、y 、z は一時変数です。

実例

wikipedia にある brainfuck の Hello, world! は以下のように変換されます。

0a +a +a +a +a a(+a) 0b +b a(b(+b)) 0x b(xb +x) 0l 0m 0r +m +m +m +m +m +m +m
+m +m m[ a(l(+l)) m(+l) 0z 0m r(+m my b(0x y(xy +x)) y(0m +z)) zr +m +m +m +m
+m +m +m +m a(l(+l)) m(+l) 0z 0m r(+m my b(0x y(xy +x)) y(0m +z)) zr +m +m +m
+m +m +m +m +m +m +m +m a(l(+l)) m(+l) 0z 0m r(+m my b(0x y(xy +x)) y(0m +z))
zr +m +m +m +m +m a(r(+r)) m(+r) 0z 0m l(+m my b(0x y(xy +x)) y(0m +z)) zl a(r(
+r)) m(+r) 0z 0m l(+m my b(0x y(xy +x)) y(0m +z)) zl a(r(+r)) m(+r) 0z 0m l(+m
my b(0x y(xy +x)) y(0m +z)) zl 0x m(xm +x) ] a(l(+l)) m(+l) 0z 0m r(+m my b(0x
y(xy +x)) y(0m +z)) zr <m a(l(+l)) m(+l) 0z 0m r(+m my b(0x y(xy +x)) y(0m +z))
zr +m +m <m +m +m +m +m +m +m +m <m <m +m +m +m <m a(l(+l)) m(+l) 0z 0m r(+m my
b(0x y(xy +x)) y(0m +z)) zr 0x m(xm +x) <m 0x m(xm +x) 0x m(xm +x) 0x m(xm +x)
0x m(xm +x) 0x m(xm +x) 0x m(xm +x) 0x m(xm +x) 0x m(xm +x) 0x m(xm +x) 0x m(xm
+x) 0x m(xm +x) 0x m(xm +x) <m a(r(+r)) m(+r) 0z 0m l(+m my b(0x y(xy +x)) y(0m
+z)) zl +m +m +m +m +m +m +m +m <m 0x m(xm +x) 0x m(xm +x) 0x m(xm +x) 0x m(xm
+x) 0x m(xm +x) 0x m(xm +x) 0x m(xm +x) 0x m(xm +x) <m +m +m +m <m 0x m(xm +x)
0x m(xm +x) 0x m(xm +x) 0x m(xm +x) 0x m(xm +x) 0x m(xm +x) <m 0x m(xm +x) 0x
m(xm +x) 0x m(xm +x) 0x m(xm +x) 0x m(xm +x) 0x m(xm +x) 0x m(xm +x) 0x m(xm
+x) <m a(l(+l)) m(+l) 0z 0m r(+m my b(0x y(xy +x)) y(0m +z)) zr +m <m

実行の様子。

$ ruby braintak.rb hello.bf > hello.tak
$ ruby tak2c.rb hello.tak > hello.c
$ gcc -O3 -o hello hello.c
$ time ./hello
Hello, world!
real    0m6.631s
user    0m6.580s
sys     0m0.020s

コード

Ruby で実装した変換器。

table = {
  ?+ => "+m",
  ?- => "0x m(xm +x)",
  ?> => "a(l(+l)) m(+l) 0z 0m r(+m my b(0x y(xy +x)) y(0m +z)) zr",
  ?< => "a(r(+r)) m(+r) 0z 0m l(+m my b(0x y(xy +x)) y(0m +z)) zl",
  ?, => ">m",
  ?. => "<m",
  ?[ => "m[",
  ?] => "]"
}

code = "0a +a +a +a +a a(+a) "        # a = 8
code << "0b +b a(b(+b)) 0x b(xb +x) " # b = 255
code << "0l 0m 0r "
$<.read.each_byte {|c| code << table[c] << " " if table[c] }
puts code.chop

Ruby で実装した数学ゴルフ言語のインタプリタ。でも遅すぎて Hello, world! の動作は確認できてません。

code = File.read(ARGV[0])
data = (?a..?z).map {|c| "#{ c.chr } = nil" }
code.scan(/\G(\d\w|\w\w|\+\w|\w\(|\)|\w\[|\]|>\w|<\w)\s*/) do |c|
  data << case c.first
  when /^(\d)(\w)$/ then "#$2 = #$1"
  when /^(\w)(\w)$/ then "#$2 = #$1"
  when /^\+(\w)$/   then "#$1 += 1"
  when /^(\w)\($/   then "#$1.times do"
  when ")"          then "end"
  when /^(\w)\[$/   then "while(#$1 > 0)"
  when "]"          then "end"
  when /^<(\w)$/    then "#$1 = STDIN.getc"
  when /^>(\w)$/    then "print #$1.chr"
  end
end
eval data.join("\n")

Ruby で実装した数学ゴルフ言語から C への変換器。多倍長整数じゃないので、最大テープ長は sizeof(unsigned int) です (笑)

code = File.read(ARGV[0])
data = []
vid = 0
code.scan(/\G(\d\w|\w\w|\+\w|\w\(|\)|\w\[|\]|>\w|<\w)\s*/) do |c|
  case c.first
  when /^(\d)(\w)$/ then data << "#$2 = #$1;"
  when /^(\w)(\w)$/ then data << "#$2 = #$1;"
  when /^\+(\w)$/   then data << "#$1++;"
  when /^(\w)\($/   then t = "t#{ vid += 1 }"; data << "for(#{t} = #$1; #{t}; #{t}--) {"
  when ")"          then data << "}"
  when /^(\w)\[$/   then data << "while(#$1) {"
  when "]"          then data << "}"
  when /^>(\w)$/    then data << "#$1 = getchar();"
  when /^<(\w)$/    then data << "putchar(#$1);"
  end
end
vars = (?a..?z).map {|c| c.chr }.to_a + (1..vid).map {|v| "t#{ v }" }.to_a
puts <<CODE
#include <stdio.h>
int main(void) {
  unsigned int #{ vars.join(", ") };
#{ data.map {|d| "  #{ d }" }.join("\n") }
  return 0;
}
CODE

*1:名前つけませんか？