λx. x K S K @はてな

このブログ内に記載された文章およびコードの著作権は,すべて Keisuke Nakano に帰属します.

Glid: Grass/Let interpreter and decompiler

草言語Grassが流行っているようなので,Grassプログラミング支援ツールGlidを公開します. Objective Camlで実装されているという点ではYTさんに先を越されてしまいましたが, より多くの機能を提供しています. といっても,実装の効率はあまりよくないので,速いGrass処理系が欲しいだけの方にはあまり役に立ちません. Glidは,簡単にいうと言語Grassと言語Letの間の双方向の翻訳ツールです. 言語Letは,次の文法で与えられる単純な関数型言語でGrassよりは楽にプログラムが書けます.

Prog := Def*
Def := let Var Var* = Exp
Exp := Var | Exp Exp | let Var = Exp in Exp | Exp;Exp
Var := In | Out | Succ | W | [_a-zA-Z0-9]+

主な使用目的は,

  • Grassを書く代わりに,Letでプログラムを書く.
  • 他人の書いたGrassを読む.
の2点です. 詳細は,配布物のREADMEに任せるとして(といっても大したことは書いていませんが), ここでは使い方を簡単に紹介します..

言語Letでは以下のようなプログラムが書けます.

(* echo.let : An echo program in Let *)
let f x =
  Out(In _);
  x x

変数_は,使用しない変数を表しGrassでは最も近い変数への参照に変換されます. Grassと同様に,最後に定義した変数が自己適用されるので, このプログラムは入力をそのまま出力するループになります. 今回提供するプログラムをglidとすると以下のコマンドで実行できます.

$ glid echo.let
また,このプログラムからGrassのコードへ変換するには,
$ glid echo.let -o echo.grass
とするだけです.-o echo.grassの代わりに-とすれば標準出力に出力されます. なお,Grassコードは glid echo.grass で実行できます.

さて,GlidではGrassコードからLetプログラムへの変換も可能です. たとえば,先ほど得られた Grass の echo プログラム

wWWWWWwWWWwWWWwww
は,
$ glid echo.grass -o echo2.let
などと実行すればLetプログラムへ翻訳できます.ちなみに,得られたプログラムは
let _ x1 = Out (In x1);
           x1 x1
となります. また,変数名に数字も使えるので,以下のようなプログラムが書けます.

(* hello.let: Print "Hello, world!" *)
let one f x = Succ(f(f x))
let zero f x = f(f x)
let 1 x f = f (one x)
let 0 x f = f (zero x)
let 0b1 f = f Succ
let putchar x = Out(x(one(zero(zero(one(zero(zero(zero Succ))))))W))
let H =   0b1 0 0 1 0 0 0 putchar
let e =   0b1 1 0 0 1 0 1 putchar
let l =   0b1 1 0 1 1 0 0 putchar
let l =   0b1 1 0 1 1 0 0 putchar
let o =   0b1 1 0 1 1 1 1 putchar
let comma = 0b1 0 1 1 0 0 putchar
let space = 0b1 0 0 0 0 0 putchar
let w =   0b1 1 1 0 1 1 1 putchar
let o =   0b1 1 0 1 1 1 1 putchar
let r =   0b1 1 1 0 0 1 0 putchar
let l =   0b1 1 0 1 1 0 0 putchar
let d =   0b1 1 0 0 1 0 0 putchar
let bang =  0b1 0 0 0 0 1 putchar
let nl =        0b1 0 1 0 putchar

ゴルフ的には無駄だらけです,念のため. ちなみに,このプログラムをGrassに変換してからLetに戻すとこんな感じ.

let f1 x1 x2 = Succ (x1 (x1 x2))
let f2 x1 x2 = x1 (x1 x2)
let f3 x1 x2 = x2 (f1 x1)
let f4 x1 x2 = x2 (f2 x1)
let f5 x1 = x1 Succ
let f6 x1 = Out (x1 (f1 (f2 (f2 (f1 (f2 (f2 (f2 Succ)))))) W))
let _ = f5 f4 f4 f3 f4 f4 f4 f6
let _ = f5 f3 f4 f4 f3 f4 f3 f6
let _ = f5 f3 f4 f3 f3 f4 f4 f6
let _ = f5 f3 f4 f3 f3 f4 f4 f6
let _ = f5 f3 f4 f3 f3 f3 f3 f6
let _ = f5 f4 f3 f3 f4 f4 f6
let _ = f5 f4 f4 f4 f4 f4 f6
let _ = f5 f3 f3 f4 f3 f3 f3 f6
let _ = f5 f3 f4 f3 f3 f3 f3 f6
let _ = f5 f3 f3 f4 f4 f3 f4 f6
let _ = f5 f3 f4 f3 f3 f4 f4 f6
let _ = f5 f3 f4 f4 f3 f4 f4 f6
let _ = f5 f4 f4 f4 f4 f3 f6
let _ = f5 f4 f3 f4 f6

そんなに読みやすくないのは,元のプログラムにも問題があるんだと思います. ちなみに,Glidでは,GlassからLetへ変換してそれをGrassに戻しても 束縛の順序等が変更されるため同じになるとは限りませんが, おそらく冪等性は成り立つはずです.

その他,構文エラーについては行や桁の表示がされるのは少し便利かも. ダウンロードはこちらからどうぞ[追記 (08/09/19)] 密かにバージョンアップ. ビルドには,Objective Caml (>=3.08.4) が必要です.