雑記

M氏のおかげでacm.uva.esのオンラインコンテストを
忘れずに済んだ。
その復習?などをやっていたらこれまたえらい時間がかかってしまった
というかなんと言うか。

Domain Specific Language (或いはコンビネータ言語)

というわけで、前回の続きである。
続きである、とはいっても、前回のようなしょうもない話ではない。
(…しかしながら、なんだかぐだぐだで中途半端な話に…)。

唐突だが、何かを実現するのに小規模な言語を実装するのが
適当だと判断された場合、いかなる解決法を取るのが良いだろうか。
例えば、ゲームのシナリオだったり、また例えば、
今回のICFPのように蟻コードを生成するような場合だったり。
私が行ったのは、これがいかにも普通のやり方だと思っていたのだが、
小規模なスクリプト言語コンパイラを実装するという手法であった。
要するにプログラムとしては、String→Stringなる関数であり、
これを普通に字句解析、構文解析、…とやって適当に作った。

が、Lisp界隈ではよく用いられている(?)もっと別な解決法も有る。
それが表題に書いたDSLと呼ばれる手法なのであるが、
(Domain Specific Languageはドメイン特化言語…そのものの意味では
別段小規模スクリプト言語とあまり違いがないのだが、
ここでは言語内にそのような言語様の物を構成することを考える)
蟻言語生成に関して具体的に述べると、基本的に目的の蟻言語を生成する
プログラムを書き、その際に書きやすくなるようなライブラリを作る。
ということになるのだろうか。
(HaskellでもHtmlのライブラリはこのような方法によっている。)

まず、もっともプリミティブなものを考える。
ターゲット言語はまぁ、一応蟻アセンブリということにしておく。
命令の詳細はICFPのページを見ていただくしかないが、
(http://www.cis.upenn.edu/proj/plclub/contest/ants.html これの2.8節かな)
まぁ、知らなくても大体は分かるのではないかと。
私自身もさっぱり覚えていないので。

Sense LeftAhead 518 510 Home
Turn Left 57
Move 512 518
PickUp 826 518
Sense RightAhead 514 518 Food

↑は、うちの蟻から適当に引っこ抜いてきたプログラムである。
例えば、このような"プログラム"を生成するプログラムは、

main = mapM_ putStrLn
  ["Sense LeftAhead 518 510 Home"
  ,"Turn Left 57"
  ,"Move 512 518"
  ,"PickUp 826 518"
  ,"Sense RightAhead 514 518 Food"]

このように書ける。
なんじゃこれは…?と思われるかもしれないが、
PerlでCGIとか書いたら似たようなコードになるのではなかろうか。
このようなプログラムの生成をとことんまでに補佐するものを
作成しつつプログラム生成プログラムを書くのが、
この手法の主なアイデアである。

まず、上のコードのどこがまずいのか。
まぁ、明らかに上のようなコードは書く意味すら無いようなコードなのであるが、
ここはあえて順を追って考えていこう。
まず一つ目に、表示しているコードが間違っていてもそれを知る手段が無いこと。
つまり、

main = putStrLn "Tuen Loft 57"

とかになってしまうのをコンパイル時にチェックできないということ。

ここで一つ抽象化の度合いを上げる。
この時点で"蟻プログラム"というものは単なる"文字列"にされている。
単なる文字列ではなくて"蟻プログラム"というものを定義し、それを用いることにする。

data Mnemonic =
    Sense  Direction Int Int Condition
  | Mark   Int Int
  | Unmark Int Int
  | PickUp Int Int
  | Drop   Int
  | Turn   Direction Int
  | Move   Int Int
  | Flip   Int Int Int

data Direction = ...
...

type Program = [Mnemonic]

さて、今度はプログラムが単に文字列ではないので、
表示する際に文字列に変換する必要がある。

compile :: Program -> String

なる関数を作成すれば良いだろう。
ちなみに、この程度のデータ構造であれば
deriving(Show)して、compile = concat . intersperse "\n" . map show
でちゃんと表示できてしまいそうな気がしないでもない…。
ここで定義したものを用いると先の例は

main = putStrLn $ compile progn

progn =
  [ Sense  LeftAhead 518 510
  , Turn   Left 57
  , Move   512 518
  , PickUp 826 518 ]

等と出来る。これにてミスタイプが検出できるし、
ようやく少しだけまともになってきた。

次に、別方向にこれを拡張する。
今回、直書きが良くない最大の理由は自分で行番号を
書かなければならないことだったように思う。
…ので、上プログラム中、518とか、510とか、
どうでもいい数字を自分で管理するのはいやなのである。
(いやというか、ほとんど不可能だろう…)
そこで、今単にリストになっているプログラムに構造を与えて
その辺の管理を自動化させることにする。

蟻アセンブリを再度見てみると、
分岐する命令 ：Sense PickUp Move Flip
分岐しない命令：Mark Unmark Drop Turn
分岐するものと分岐しないものがあることが分かる。
このうち分岐しないものは、ジャンプアドレスに
常に次の命令のアドレスでもおいておけばよい。
分岐する命令も、片方はそうしておけばよい。
そうすると、分岐する命令の片方をなんとか指定できれば、
それ以外のアドレスは結構自明に管理できるということになる。

data Fragment = (コード片)

mark   :: Int -> Fragment
unmark :: Int -> Fragment
drop   :: Fragment -- Preludeと名前が被る…
turn   :: LeftOrRight -> Fragment

 -- 失敗時の分岐先を渡す。
sense  :: Direction -> Condition -> Fragment -> Fragment
pickup :: Fragment -> Fragment
move   :: Fragment -> Fragment
flip   :: Int -> Fragment -> Fragment -- これも名前が被る…

makeProgram :: Fragment -> Program
compile     :: Program -> String

プログラムの一部をコード片として表現し、
それらを組み立ててプログラムを作っていく。

 -- 逐次実行
seq :: Fragment -> Fragment -> Fragment

このようなものを作ると

clearAndSet a b = unmark a `seq` mark b

適当につなげられるようになって組み合わせの幅が広がる。
さらに、Fragmentに適当に文字列を設定してラベル付けが
出来るようになるといいかもしれない。

label :: String -> Fragment -> Fragment

goto :: String -> Fragment

全く実装の無いコードが続いてしまったが…
次のような使い方をするものと考えている。
(ちなみに、上記のコードは適当にでっち上げたので、
どう実装していいのか分からない)

main = putStr $ compile start

start = forever nop

forever f = label "forever" $ f (goto "forever")

nop next = flip 1 next

何もしない蟻…のつもり。
なんかすごく独りよがりなコードになってしまっているような?気がする。
Fragmentの実装をどうするのか…?という重要な問題をひとまず放置しているが、
参考にさせてもらった 'Team Dunkosmiloolump'
(http://urchin.earth.li/icfpcontest/2004/Introduction)
のコードがまさしくこのアプローチなので、私のしょぼい実装よりは
ここを参照してもらうほうが遥かに良いと思う。
(ライブラリ部分は難しくてよく分からなかったんだけど…)
http://urchin.earth.li/icfpcontest/2004/sub/tools/compiler/Test.hs
最終的には、このように蟻プログラムを表現できるようである。

と、説明はこの辺にしておいて。
コンパイラを実装するのではなくて言語内にDSLを作るメリットは何だろうか。
これはおそらく、用いた言語のパワーをそがれることなく
目的のプログラムの記述に使うことができる、ということだろう。
私の作ったスクリプト言語でも見てもらえば分かるであろう。
単に繰り返しとかですら、わざわざ実装しない限り使えないので、
今回のように3日限定等というコンテストではHaskellなみに強力な
コンパイラが出来上がるわけが無い。
"the language of choice for discriminating hackers!"
であるHaskellが蟻プログラムの記述にも使えるということは
その時点でかなり有利であるといえるのだろう。

反面、デメリットはというと、
コードの生成にHaskell処理系が必要なこと、ぐらいであろうか。
これはおそらくゲームのシナリオの記述にこの手法を使ってしまったりした場合、
その実行にHaskell処理系が必要になってしまいよくないかもしれない。
まぁ、今回はHaskellで終始開発を行うものなので、なんら問題は無いだろう。

しかしまぁ、公開されてるソースとかを見ていると、
DSL的な手法を用いているチームが結構あるような感じだ。
こんなことに今更驚くなよ、という方も、ICFPに参加したのは
Haskellを本格的に勉強しようと思ってそう日も立たないころだったので、
温かく見守っていただけると幸いだったりする…。
とりあえず、今後こういうものを書かなければならない
ケースが出てきたときに使ってみようかと。