braingrass

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 でいいや」というのに似ていると思うのです。

Grass について

関数型系の esoteric programming としてはバランスがいいと思います。unlambda は入出力がかっこ悪すぎてダメ。LazyK はいろいろクールだけど、とっつきが悪い。Grass は中間な感じ。

ちなみに Grass から brainfuck への変換は、もっと難しそうです。難しさの種類が違うというか。brainfuck で複数のスタックを表現するとか考えただけで死んじゃう。チューリングマシンλ計算の計算能力は等価だけど、書きやすさは圧倒的にλ計算の勝ちなのです。たぶん。