Haskell Hackathon

Program D

とりあえず D BOF は後で。

http://shinh.skr.jp/koneta/dhc.tgz

眠いなーと思いつつ D BOF の後で行った。たぶん2時くらいについた。なんかみんな飯喰ってたのでだべる。チャットから時間を起こそう。

とりあえずパーサとかどうでもいいので構文木を喰わせる実装にすることは決まってたので、 Haskell についてあれこれ考えてから S 式パーサを書いた。 3:30

んで型をなんかするのを作った。なんか int, bool, string, IO という 4 つの型があって、そのどれかか、決定できないかを調べる程度。 IO はモナドでもなんでもない。 5:13

Hello world 動いた。 6:13

(
 (funcdef gen_hello (v) (let x (++ "Hello, " v) x))
 (funcdef hello () (putStr (gen_hello "world!\n")))
 (funcdef main () (hello))
)

if とか作って再帰大丈夫にして fizzbuzz 動いた。 7:30

(
 (funcdef fb (n) (if (== (mod n 15) 0) (putStr "FizzBuzz\n")
                   (if (== (mod n 5) 0) (putStr "Buzz\n")
                     (if (== (mod n 3) 0) (putStr "Fizz\n")
                       (>> (putInt n) (putStr "\n"))))))
 (funcdef fizzbuzz(n)
          (if (== n 101) (return) (>> (fb n) (fizzbuzz (+ n 1)))))
 (funcdef main() (fizzbuzz 1))
)

そっからがなんか辛くて遅延評価をやろうとたらい回し関数を書いてみてちょっとバグを潰す。

(
 (funcdef tarai (x y z)
          (if (<= x y) y
            (tarai (tarai (- x 1) y z)
                   (tarai (- y 1) z x)
                   (tarai (- z 1) x y))))
 (funcdef main ()
          (>> (putInt (tarai 52 122 10)) (putStr "\n")))
)

遅延評価がなかなか実装できなくて苦しんだ。 10:26 にたらい高速化終了。

あとは多相関数なんとかしたいなーと思ったけど現状の構造をかなりいじらにゃならんと気付いた。けどまぁ id はインチキで通るようになってます。

(
 (funcdef id (x) x)
 (funcdef main ()
   (putStr (id "hoge\n")))
)

ちなみにたらい回し関数はこんな D コードに変換される。

import rt;
extern(C) int _tarai(Thunk!(int) x,Thunk!(int) y,Thunk!(int) z) {
 return thunk(thunk({ return ___60__61(thunk(x), thunk(y));})() ? thunk(y) : thunk({ return _tarai(thunk({ return _tarai(thunk({ return ___45(thunk(x), thunk(1));}), thunk(y), thunk(z));}), thunk({ return _tarai(thunk({ return ___45(thunk(y), thunk(1));}), thunk(z), thunk(x));}), thunk({ return _tarai(thunk({ return ___45(thunk(z), thunk(1));}), thunk(x), thunk(y));}));}))();
}
extern(C) IO _main() {
 return thunk({ return ___62__62(thunk({ return _putInt(thunk({ return _tarai(thunk(52), thunk(122), thunk(10));}));}), thunk({ return _putStr(thunk(new Thunk!(string)("\n")));}));})();
}

全く読めん。 Thunk はこんな感じになった。久々にメタなことやったのですごい時間かかった…

class ThunkBase {}

class Thunk(T) : ThunkBase {
    this(T t0) {
        t = t0;
        done = true;
    }
    this(Thunk t0) {
        t = t0.t;
        dg = t0.dg;
        done = t0.done;
    }
    this(T delegate() dg0) {
        dg = dg0;
    }
    T opCall() {
        if (done) return t;
        done = true;
        return t = dg();
    }
    T t;
    T delegate() dg;
    bool done;
    static const bool is_thunk = true;
}

template ThunkType(T) {
    static if (is(T : ThunkBase)) {
        alias T ThunkType;
    }
    else static if (is(T R == return)) {
        alias Thunk!(R) ThunkType;
    }
    else {
        alias Thunk!(T) ThunkType;
    }
}

template thunk(T) {
    ThunkType!(T) thunk(T t) { return new ThunkType!(T)(t); }
}

お疲れさまでした。会場提供やら運営やらありがとうございました。 > サイボウズ☆ラボ

nanka

たらいが尋常じゃなく遅いな。適当に実装したとはいえいらん Thunk オブジェクト作りすぎだボケ。と思ったのでちょっと修正したら速くなった。 tarai 122 52 10 に対して、

> time ./tarai
122
./tarai  0.94s user 0.00s system 95% cpu 0.978 total

だったのが

> time ./tarai
122
./tarai  0.03s user 0.00s system 98% cpu 0.029 total

GHC には全然負ける。

> time ./a.out
122./a.out  0.00s user 0.00s system 0% cpu 0.006 total

D BOF

Program D

で D BOF で話してきました。あとでまとめてあがるみたいだけどとりあえずどうでもいいスライドはこんな感じ。

http://www.slideshare.net/shinh/dreflection

http://docs.google.com/Presentation?id=dhf5wwff_79g93d9xcc

まぁなんか色々グダグダだったのはホントすいませんという感じだったけど、まぁ内容は面白かった。 Skype の下調査とか結局あんま意味なくてアレだった。にんとも。

とりあえず動画撮影して頂いた cojiさんにとても感謝でした。

その後で上述の通り Haskell Hackathon があったわけですが、ゲーム作るしか脳が無いと思われがちな D は言語作るのにも割にいいなーと思いました。

  • 参加するからには勝たなければならない。
  • どう考えても実装力で勝てるわけないので誰も勝負しなさそうな速度とかで勝てばいい。 → C++, D, OCaml
  • 木いじるのは GC 欲しい。クロージャも欲しい。 → D, OCaml
  • 実は OCaml とか最初から一考だにしていなくて脳内に C++ と D しかなかった。 → D

というような思考でもなんでもない理由だったのですが、まぁ割と良かったと思いました。インタプリタよりはトランスレータの方が速いし、リッチな言語にトランスレートすればむしろインタプリタより楽なんじゃないかなーと思ってトランスレータにしておいた。これもまぁ良かったんじゃないかな。 Haskell の実行時に template やらクロージャやら欲しかったし。クロージャは例えば let 作る時に

 (funcdef gen_hello (v) (let x (++ "Hello, " v) x))

を

string _gen_hello(string v) {
  return ((string x){ return x; })(string_add("Hello, ", v));
}

というようにコンパイルしたりしてラクができた。あと mixin でなんかマングルとかやりたかったんだけどうまいこといかんかったから TODO として放置されてるので今度やろうと思う。

言語作る人に魅力的な点は

  • コンパイラ作るのに十分な表現力。 (GC、OOP、ハッシュ、printf) (パターンマッチないのはアレかもね)
  • ランタイム作る表現力も十分にある。 (GC、クロージャ、template、mixin)
  • 適当に作ってもできたものはそれなりに速い。
  • C 脳でも大丈夫。
  • 言語仕様がガンガン変わるので言語作るくらいの言語オタにはぴったり。

とかがあるかと思った。書いてて OCaml でも良かったんじゃないのと少し思ってきたので最後の方に無理な根拠を足した。まぁ OCaml はライブラリがダサいとか文法がまどろっこしいとか(完全に主観)。

あと最近の C# とかそいう VM 回りの言語(知らんけど Nemerle とか Scala とか?)も上記の要求をそれなりに満たしてたりするんだろうな。

たぶん k.inaba さんとかが、 D にはアレがあるじゃないか的なことを教えてくれる気がする。

Top Coder Marathon Match 31

Misc

なんか問題ちらっと見たら面白そうなのでやってみようと思いました。とりあえずやる気ないコード書いて15位らへんに入った。

http://www.topcoder.com/longcontest/?module=ViewStandings&rd=11136

mark たんがいるですよなんか。問題は4人オセロとかなんだけど、普通こういう CPU 書く時って相手も同じ条件の CPU であることを想定して min-max でほげほげーとかすると思うんだけど、このオセロでは CPU のアルゴリズム固定でかつえらい弱いので、相手が全然 min な戦略を選べない。だからいかに圧勝するかというちょっと普段と違う条件になる感じで、面白いかも。

D BOF

の内容書いてないし！

とりあえず D で納品 && D で SIGRAPH の勇者*2 がすごかった。特に SIGRAPH の方は終わってからデモしてもらったんだけど、これはかなり面白かった。

なんか任意の二次元 bmp からエッジ検出→メッシュ検出とかして、あとは自在に動きとかを与えられるとかそんな感じだったんだと思う。

ちょっと作ってみたくなった。

なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h