brainfuck から Grass への変換器を書いてみました。brainfuck はできるけど、Grass はちょっと……という人向け。
# brainfuck のプログラム $ cat hello.bf +++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-. ------------.<++++++++.--------.+++.------.--------.>+. # grass のプログラムに変換 $ ruby19 braingrass.rb hello.bf > hello.www # 実行 $ ruby19 yagi.rb hello.www; echo Hello, world!
ソースはこちら。
http://github.com/mame/grass-misc/tree/master/braingrass.rb
アルゴリズム
おおよそ以下の二段階。
- 1. brainfuck のプログラムをλ式 (+ let) に変換する。
- 1.1. 不動点演算子や church encoding (数字、3 つ組、リスト) の関数たちを作る。
- 1.2. これらを使って zipper の関数たちを作る (参考) 。後段で Closure 変換をさぼるため、自由変数がないようにしておく。
- 1.3. brainfuck の各命令を zipper の操作に変換する。
> => let state = next state in < => let state = prev state in + => let state = set (get state + 1) state in - => let state = set (get state - 1) state in , => let state = set (getc) state in . => let state = putc (get state); state in [ => let rec func state = if (get state) == 0 then state else ] => state in
- 2. λ式をに Grass に変換する。
- 2.1. λ式を K 正規化する (参考) 。
- 2.2. K 正規化したλ式を de Bruijn Index に変換する (参考)。
- 2.3. K 正規化したλ式を de Bruijn Index で表現したものは、自明に Grass の命令に対応する。終わり。
ソースコードでは 1 と 2.1 を同時にやっているので、こんがらがってます。
Ruby 1.9 で
明らかに Haskell 向きのプログラムだけど、むりやり Ruby 1.9 で書いてみました。せっかくなので、Ruby 中に関数型言語の DSL みたいなのを作ってλ式を表現してみました。文法のイメージ。
# # E ::= X -- X -- 変数 # | [E, E, ..., E] -- (E E ... E) -- 関数 # | abs.call {|X1, X2, ..., Xn| E } -- (λ X1 X2 ... Xn. E) -- λ抽象 # | let.call(E) {|X| E } -- let X = E in E -- let #
108 行目の global functions 以下がそれ。うーん、気持ち悪い。
しかしやっぱり、Ruby は抽象構文木とかを扱うには向いてない言語だと思います。今回もα変換とか自由変数の一覧を得るとか億劫だったので、手動で Closure 変換してごまかしちゃった。これはたぶん、C を書いてるときによくある「リストの方が効率いいけど、struct 定義するの面倒だから malloc でいいや」というのに似ていると思うのです。