This post is Private. Only a writer or those who know its URL can access this post.

【Otemachi.rb#10】Rubyでbrainfxck処理系作ってみた

自己紹介

  • Shu OGAWARA(@expajp )
    • リンカーズ株式会社
    • 社会人3年目
    • Rails歴は1年ちょい
    • 出身は鳥取で大学は神戸
    • 趣味は合唱

ご注意

プログラミング言語の名前にアレな単語が含まれていますが我慢してお聞きください


brainfxckとは?


難解プログラミング言語のひとつ

  • 「コンパイラをどれだけ小さくできるか?」という研究用に作られた言語
    • 開発者が作ったコンパイラのサイズは123バイト
  • 命令はたった8個しかなく、それ以外はすべてコメントとして扱われる
  • 実用性はゼロだが、チューリング完全
    • チューリング完全:(簡単に言えば)コンピュータで実行できるどんな計算も記述できるという意味

たった8個しかない命令

  • >, <, +, -, ., ,, [, ]、以上
  • 例えば、Hello World!と出力するプログラムは以下
>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++
++>-]<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>
++++++++[<++++>-]<+.[-]++++++++++.

計算モデル

プログラムポインタ

  • いま、何文字目を読んでいるかを表す数字
    • 命令が全部一文字でアタマから読んでいくため

バイト列

  • データを置くためにバイト列が与えられる
    • 配列と考えればよい
# バイト列
[0] [0] [0] [0] [0] [0] [0] [0] [0] [0] 

データポインタ

  • いま、配列の何番目のデータを見ているかを表す数字

各命令の意味


値の増減

  • +, -
    • いま見ているデータの値を1ずつ増やしたり減らしたりする
    • 2以上まとめてデータを変えたり、かけ算わり算をやったりする贅沢な機能は存在しない

データポインタの移動

  • <, >
    • 「配列の中で、いまデータを見ている箇所」を1つずつ移動する
[0] [0] [0] [0] [0] [0] [0] [0] [0] [0] 
     ↑いまここ

# > を実行後
[0] [0] [0] [0] [0] [0] [0] [0] [0] [0] 
         ↑1つ右に移った

入出力

  • .
    • 今見ているデータを文字コードとして扱ったとき、対応する文字を出力する
    • 例えば、Hello, World!のHは0x48 = 72
  • ,
    • 入力から1バイト読み込み、今見ているデータに代入する
    • 2以上の数字を一度に入力する方法はこれだけ
    • さっきのHello, World! コードには登場していない

制御

  • [, ]
    • 今見ているデータが0なら、カッコの中身を飛ばす
    • 今見ているデータが0でないなら、カッコの中身をもう一度繰り返す
  • 制御はすべてこれを使って記述する
    • 条件分岐もループもみんなこれを使うしかない
    • かけ算もループを使って書く


'hoge'と出力

  • それぞれ、文字コードは10進数で104, 111, 103, 101
    • 104を作ればあとはちょっとずつ値を変えるだけ
++++++++++[>++++++++++<-]>++++. # hと出力
+++++++.--------.--. # o, g, eと出力

'h'と出力する部分

  • まず、配列の最初の要素に10を格納
++++++++++

# 配列
[10] [0] ...

'h'と出力する部分

  • これをループ用の変数にして、2番目の要素に10を10回足す
[>++++++++++<-]

# 1シーケンス実行後の配列
[10] [0]...
   ↓
[9] [10] ...

'h'と出力する部分

  • これをループ用の変数にして、2番目の要素に10を10回足す
[>++++++++++<-]

# ループ実行後の配列
[0] [100] ...

'h'と出力する部分

  • あとは4足して出力
++++.

# ループ実行後の配列
[0] [104] ...

残りを出力する部分

  • 足したり引いたりして、順に111, 103, 101を作って出力
+++++++.--------.--. 

実用性はゼロ


処理系をRubyで作ってみた

https://gist.github.com/expajp/c443f14944d114e94fb5c82c4e4b13fb


作ってみてどうだったか

  • 「言語処理系を作る」というなかなかない経験をできた
    • 字句解析をしなくても良いが、言語処理系を作る難しさを少しだけ味わえた
    • 実行時の処理の順番が
    • デバッグが死ぬほどしんどい

作ってみてどうだったか

  • オブジェクト指向設計の勉強になった
    • 処理系自身、命令列、データ列、命令自身
    • どこにメソッドをもたせるか?
    • ポリモーフィズムを使わずcase文で対応したのが心残り

実は


派生言語がたくさんある

  • 8つの記号に何を当てはめてもよいため、好きな8つの言葉に置き換えるだけ
    • A、Nyaruko、Oak!、ジョジョ言語... etc.
    • もちろん、複数の言葉を1つの命令に当てても良い
  • 機能追加が容易なので、ネタ機能を追加できる
    • BrainCrash...etc
    • この言語処理系に空のプログラムを読み込ませると、Hello, World!と出力する

ジョジョ言語のHello World!


ジョジョ言語のHello World!

オラオラオラオラオラオラオラオラオラッ!!

「あ・・・ありのまま今起こったことを話すぜ
俺は奴の前で階段を登っていたと思ったら、いつの間にか降りていた
な…何を言っているのかわからねーと思うが、
俺も何をされたのかわからなかった…
頭がどうにかなりそうだった…催眠術だとか超スピードだとか、
そんなチャチなもんじゃあ断じてねえ。
もっと恐ろしいものの片鱗を味わったぜ…」

スターフィンガー!
オラオララララ!
オラッ!オラオラララララオラオラオラァ!!!
スターフィンガー!!!
オラァオラオラオラオラオラオラッオラ!!
オラオラァァァァァオララララララララララ!
スターフィンガー!

オラオラオラオラオラ! つけの領収書だぜ!

力比べというわけか!
知るがいい…!『ザ・ ワールド』の真の能力は…まさに!『世界を支配する』能力だと言うことを!

「ロードローラだ!ロードローラだ!ロードローラだ!」
無駄ッッッ!

ザ・ワールドッッ

スターフィンガー!
「ハーミットパープル」
スターフィンガー
オラオラ!

「ハーミットパープル」

オラオラオラオラオラオラオラ
ハーミットパープル!ハーミットパープル!

オラオラオラ

ハーミットパープル!
スターフィンガー!

無駄ァ!
ハーミットパープル

無駄!無駄!
無駄無駄無駄無駄無駄無駄無駄無駄無駄無駄
WRYYYYYYYYYYYYYY!
“ジョースター・エジプト・ツアー御一行様”は貴様にとどめを刺して全滅の最後というわけだな

ハーミットパープル!
ロードローラだ!

オーラオラオーラオラオラオラオーラオラオラオラオラッ!
ハーミットパープル!
無駄無駄無駄無駄無駄無駄無駄無駄ッ
ハーミットパープル!
オラオラオラアアアアアアアア!
ハーミットパープル!
無駄ッ無駄ッ無駄ッ無駄無駄無駄ァツ!

ハーミットパープル

もうおそい! 脱出不可能よッ! 無駄無駄無駄無駄無駄無駄無駄無駄ぁぁ!
ハーミットパープル!

最高に『ハイ!』ってやつだアアアアア!アハハハハハハハハハーッ!!
スターフィンガー
オラ
ハーミットパープル!

てめーの敗因は・・・たったひとつだぜ・・・DIO たったひとつの単純(シンプル)な答えだ・・・ 『てめーは おれを怒らせた』

brainf*ckでジョジョ言語 - 旧toyoshiの日記 http://d.hatena.ne.jp/toyoshi/20100208/1265587511


出力結果

Hello World!

みなさんもチャレンジしてみては?

Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account log in.