Hindley-Milner型推論アルゴリズムをF#で書いてみた
この記事は F# Advent Calendar 2014の21日目の記事です。昨日はc0hamaさんの「Linux で F# を始める」でした。
いきなり弁解から入りますが、この記事は「Hindley-Milner型推論アルゴリズムをGroovyで書いてみた」というid:uehajさんの記事を単にF#で写経しました。という話をします。
動機
そもそもなんでそんなことをしようと思ったのか、
- 今年のICFPC2014でSECDマシン用のコンパイラを作る課題が出てmini-ML文法の独自DSLを作る。
- その言語がMLっぽい文法のくせに型検査がなくて開発効率が悪かった。
- よし、型検査を入れよう。ついでに型推論も入れよう。
- ネットで調べると日本語のコメント付きですげーわかりやすいブログ発見。
- →とりあえず、すぐに試せるF#で書き写してみよう。
という感じで作業していたら、テストが通るようになったので勢いでアドベントカレンダーにも登録するという暴挙にでてしまいました。
「HM型推論といえばML」ぐらいの重要機能だし（と勝手に思ってる）、F＃もMLファミリーなのでなんか絡んでるだろうと思ったんです。しかし、実際に書いてみたらぜんぜんF#関係ありませんでした。ごめんなさい。
でも、そんな中２マインドの俺にHM型推論がわかった気にさせてしまうF＃ってすごいなーと思うんです。
HM型推論に関しては確実に元のGroovyとScalaのソースを見たほうがよいでしょう。
特にGroovy版についているコメントは大変わかりやすいのでお勧めです。
その他、ネットで調べられるものはmin-camlのtyping.mlがいいと思います。これも日本語の解説があるので分かりやすいです。
Groovy版についているコメントも残してF#で自分が書いたソースはGistに置きました。
最後に下のテストが通ったときは、超少ないコードで型推論できるなんてHindleyさんとMilnerさんマジ、スゲーと思った。
そして、とても分かりやすいコメントを書いてくれたid:uehajさんありがとうございました。
let testShowType() =
// 最終的な型判定のテスト群。
assert (typeInfer.showType(Var("true")) = "Boolean[]")
assert (typeInfer.showType(Var("xtrue")) = "\n cannot type: xtrue\n reason: undefined: xtrue")
assert (typeInfer.showType(Var("zero")) = "Int[]")
let intList = App(App(Var("cons"),
Var("zero")),
Var("nil"))
let zero = Var("zero")
let one = App(Var("succ"), Var("zero"))
assert (typeInfer.showType(intList) = "List[Int[]]")
assert (typeInfer.showType(App(Var("isEmpty"), intList)) = "Boolean[]")
assert (typeInfer.showType(App(Var("head"), intList)) = "Int[]")
assert (typeInfer.showType(App(Var("tail"), App(Var("head"), intList))).StartsWith("\n cannot type: zero\n reason: cannot unify Int[] with List["))
assert (typeInfer.showType(App(Var("tail"), App(Var("tail"), intList))) = "List[Int[]]") // runtime erro but type check is OK
assert (typeInfer.showType(App(App(App(Var("if"), Var("true")), zero), one)) = "Int[]")
assert (typeInfer.showType(App(App(App(Var("if"), Var("true")), intList), one)) = "\n cannot type: succ\n reason: cannot unify List[Int[]] with Int[]")
let listLenTest = LetRec("len",
Lam("xs",
App(App(App(Var("if"),
App(Var("isEmpty"), Var("xs"))),
Var("zero")),
App(Var("succ"),
App(Var("len"),
App(Var("tail"),
Var("xs"))))
)),
App(Var("len"),
App(
App(Var("cons"),
Var("zero")),
Var("nil"))
)
)
assert (listLenTest.ToString() = "letrec len = λ xs . (((if (isEmpty xs)) zero) (succ (len (tail xs)))) in (len ((cons zero) nil))")
assert (typeInfer.showType(listLenTest) = "Int[]")
F#化したときに感じたこと
- 判別共用体のコンストラクタをその型の派生クラスみたいに扱いたいけどやり方がわからない。
type Type =
| Tyvar of tyvar
| Arrow of Type * Type
| Tycon of string * Type list
with
override this.ToString() =
match this with
| Tyvar x -> x
| Arrow(t1, t2) -> sprintf "(%s -> %s)" <| t1.ToString() <| t2.ToString()
| Tycon(k, ts) -> k + "[" + (ts |> List.map string |> String.concat ",") + "]"
//F#: 本当はTypeを継承したTyvar型を定義したかったけど、
// うまいやり方が分からないのでstringの別名としてtyvarを作ってお茶を濁す
and tyvar = string このときTyvar of tyvarというのをTyvarという型として扱いたかった。
うまいやりかたがあれば誰か教えてください。
- F#関係ないけど、テスト重要。自明なものから始めてやりたいことの全容を書いておくというのは超大事。
それと、F#のテスト関連は何が標準なんだろうか？C#/C++みたいなMSTestがすぐ使えるのはないのだろうか？
- F#は.NETのクラスを利用できたりfloatの演算を+.みたいににしてないから、型推論が弱いのはわかる。だけど、ラムダのパラメーターとかよく型推論してくれないので、型注釈書かないといけない。F#もHM型推論の仲間ならもっとガンバレと思う。
- でも、F#がVisualStudioに標準で入っているという手軽さがやっぱりいい。もっと仕事で使えるようになりたい！
Vue.jsをjs_of_ocamlから使う方法
Vue.jsとはJavascriptでMVVMするための軽量なフレームワークです。
ですっていうか３日前に知ってこれはいいやと思い、js_of_ocamlから使う方法を考えていました。
ちなみに自分のJavascriptのレベルはほとんど０です。「Objectに動的にメソッドを追加できる」ってことを知ったのもこの３日間という感じ。
js_of_ocamlのレベルも似たり寄ったりかな。
動機
OCamlでコード書いててGUI付けたいと思いjs_of_ocamlでHTMLのGUI作ろうとしたけど、ViewとModelをうまく分離する方法がわからなかった。
そこで、F#+WPFみたくMVVMな感じで
を実現したいなーと思い調べたところVue.jsを知り、とりあえず作ってみました。
やったことはVue.jsの以下のサンプルコードをjs_of_ocamlで写経しました。
app.js(Vue.jsのサンプルコード)
var demo = new Vue({ el: '#demo', data: { branch: 'master' }, created: function () { this.$watch('branch', function () { this.fetchData() }) }, filters: { truncate: function (v) { var newline = v.indexOf('\n') return newline > 0 ? v.slice(0, newline) : v }, formatDate: function (v) { return v.replace(/T|Z/g, ' ') } }, methods: { fetchData: function () { var xhr = new XMLHttpRequest(), self = this xhr.open('GET', 'https://api.github.com/repos/yyx990803/vue/commits?per_page=3&sha=' + self.branch) xhr.onload = function () { self.commits = JSON.parse(xhr.responseText) } xhr.send() } } })
app_ml.ml(上記のjs_of_ocaml版)
open Js (* Vueオブジェクトのインスタンスパラメーターを定義 *) let param = let open Unsafe in (* Unsafeをよく使うので開いてしまう *) let created () = (* Javascriptのthisの有効範囲がよくわかってないのでその都度取り込む *) let this = Unsafe.variable "this" in meth_call this "$watch" [| inject (string "branch"); inject (fun () -> (* このthisの書き方でいいのかな *) meth_call this "fetchData" [||]) |] |> ignore in (* truncateとformatDateは実際にはModelの仕事なのでOCamlっぽく書いてみる *) let truncate v = try let str = to_string v in let newLine = String.index str '\n' in String.sub str 0 newLine |> string with _ -> v in let formatDate v = let str = to_string v in let rexp = Regexp.regexp "T|Z" in Regexp.global_replace rexp str " " |> string in let fetchData () = let this = Unsafe.variable "this" in let self = this in let branch_js = self##branch in Firebug.console##log(branch_js); let branch_ml = to_string (branch_js) in let url = "https://api.github.com/repos/yyx990803/vue/commits?per_page=3&sha=" ^ branch_ml in let (>>=) = Lwt.(>>=) in (* 記号を導入*) XmlHttpRequest.get url >>= fun r -> let msg = r.XmlHttpRequest.content in (* let json = Json.unsafe_input (string msg) in *) (* Firebug.console##log(json); *) (* こう書きたいんだけjs_of_ocamlのJsonオブジェクト内の文字列が mlstringになってて期待した通りに動かないのでJavascriptのJSONを輸入する *) let json = Unsafe.variable "JSON" in self##commits <- Unsafe.meth_call json "parse" [| inject (string msg) |]; Lwt.return msg in obj [| "el", inject (string "#demo"); "data", inject (obj [| "branch", inject (string "master") |]); "created", inject created; "filters", inject (obj [| "truncate", inject truncate; "formatDate", inject formatDate |]); "methods", inject (obj [| "fetchData", inject fetchData |]); |] (* JS Objectをコンストラクタの引数にとるVueオブジェクトを定義 *) let vue : 'a constr = Unsafe.variable "Vue" (* Vueオブジェクトのインスタンスを定義 *) let demo = jsnew vue(param)
感想
とりあえず、UnsafeいっぱいであんまりOCamlのお得感はないですね。
そして、なんとなくVue.jsはよくできているように思いました。こんな感じでJavascriptでもMVVMできるっていうのが新鮮。
あと、js_of_ocamlとVue.jsの日本語のブログ記事はほぼすべて目を通しました。超参考になりました。ありがとうございました。
たとえばjs_of_ocamlは
Vue.jsは
などが役に立ちました。
実行デモとソースは以下です。
http://toku.bitbucket.org/experiment/vuejs/index.html
OCamlでpa_monadを使わないでシンプルにモナドっぽく使う方法
すごいH本を読むとモナドが分かったような気になったので、OCamlでできないか試して見ました。
最初に調べるとOCamlではpa_monadを使ってHaskellのdo記法っぽい書き方をする方法があるのがわかった。
でも、p4でモジュールをリンクするのがたるいなーと思っていたらFunctorを使ってモナドを作る方法があるのも分かった。
ということで、なんとなく作ってたらリストモナドで虫食い算ができるようになったので記録しておきます。
参考にしたのは下のサイトのコード。これをpa_monadを使わないでやってみました。
自分が書いたソースは
module ListMonad = struct type 'a t = 'a list let bind lst f = List.concat (List.map f lst) let return x = [ x ] let ( >>= ) = bind let guard c = if c then return () else [] end let rec range a b = if a = b then [] else a::range (a+1) b let make = List.fold_left (fun x y -> x*10 + y) 0 let solve () = ListMonad.( range 1 10 >>= fun a -> range 0 10 >>= fun b -> range 0 10 >>= fun c -> range 0 10 >>= fun d -> range 0 10 >>= fun e -> let x = make [a;7;b;6;c] in let y = make [3;d;2;9;e;6] in guard (x * 7 = y) >>= fun _ -> return (x, y) )
https://bitbucket.org/toku/experiment/src/3efdb97202a77a452351de7be736e5e02dfeeaee/monad/monad.ml
Optionモナド(Maybeモナド)とListモナドがあればGoogleCodeJamとかICFPCで戦力になるんじゃないかと思う。
それと、OCamlのコード書くようになってF#のコードなら相当簡単に書けるようになったと実感した。
なんというかOCamlってC言語っぽいんだよね。必要十分の機能はある感じ。F#はそれに加えて.NETの豊富な機能を使えるのがいいと思う。
OCamlをC言語に例えるのはアレかもしれないけど、標準ライブラリだけじゃどうやって仕事するんだって思うのでそう間違ってないはず。
Haskellの数独ソルバーをOCamlで写経してみた
動機は、慶応SFCで数独の問題が出たという記事をみて、かっこいい数独ソルバーの実装はないかな〜とgoogleさんで調べたら、
Haskell sudoku solver in 707 bytesという超かっこいいソースがあったのでまたパクってみました。
作者さんありがとう。イタリア人っぽいのでグラッチェgrazie。
ソースはここ。
https://bitbucket.org/toku/experiment/src/d82f5d9b47c2/sudoku/sudoku.ml
感想
- Haskellすげー。ゴルフの結果だと思うけど記述量がハンパなく少ない。
- OCamlで[1..9]ってどう書けばいいんだろう。F#なら[1..9]でいけるのに。
- for i=1 to do 9ってやって最後List.revしてるところはどうにかならないかな。
- markの部分の理解に３日かかった。
type T = (Int,Int) -> [Int] mark :: ((Int,Int),Int) -> T -> T mark (p@(i,j),n) s q@(x,y) =
これ、型注釈は引数２つなのに、実際には３つあるのが意味不明だった。
最終的にはTが(int, int)をとる関数だとわかり、mark自体が「関数の部分適用」をした状態ということがわかった。
なるほどこれがカリー化ってやつなのかと理解できた。そしてこれは、俺には思いつかないなーってのも思った。
js_of_ocamlでゲームを作ってみた
自宅の開発環境について
会社では普段はWindows 7でVisual Studio 2012のC++とTFSでかなり快適に仕事しています。
ですが、家では違うことしようかな〜と思っていたところ、
ちょくちょく見ていたブログにOCaml開発環境について書かれていたので
http://d.hatena.ne.jp/camlspotter/20121204/1354588576
OCamlの環境を揃えてみることにしました。
まず、現在の自宅のマシン構成は
| マシン | OS | 開発環境 | 用途 |
|---|---|---|---|
| 自宅PC | Windows XP | Visual Studio 2010 C++, F# | プログラミングやSteamのゲーム用 |
| 自宅サーバ | NetBSD 5.1 | vim + gcc | 会社からアクセスするためのssh踏み台 |
| MacBook Air | Mac OS X | XCode 4.5 | ほぼ未使用（iPhoneアプリを作ろうとして購入） |
このうち、ほぼ未使用のMBAを対象にMacOSXに環境を作ってみました
参考にしたページは
http://tmaeda.s45.xrea.com/td/20121028.html
です。
OCaml 4.00系はtyperex2ならコンパイルできるようですが、MacOSXだとコンパイルできなかったのでtuareg+emacsでやってみました。
しかし結局、自分はemacsでコードを書くのがどうしても出来なかったので今はvim + omake -Pな環境でやっています。
