soutaroのHaskellにっき

■ [Haskell Hackathon]

これからしばらくHaskell Hackathonに向けた予習について書いていこうと思います．当日，東京での参加が不可能なことがわかったので，あらかじめ書いておいたほうが良いだろうと思うので．

ちなみにソースコードはhttp://svn.soutaro.com/has/trunkにあります．適宜チェックアウトしてみてください．まだまだ開発中なので，最新版は変更がどんどん加わると思いますが．

■ [Haskell Hackathon]どこまでやるか決める

最初に，Haskellのどこまでの機能を実装するのか決めてしまいたいと思います．後日，進み具合によって変更することはあるかもしれませんが，目標は決めておきたい．

現時点で，Haskellの興味深い機能を適当に挙げると次のようになります．便宜上，字句解析器・構文解析器・評価器・型システムに分けました．

1. 字句解析器
   1. オフサイドルール
2. 構文解析器
3. 評価器1
   1. パターンマッチ
   2. 遅延評価
4. 型システム
   1. 型推論
   2. 型クラス
5. 評価器2
   1. 型クラス
   2. Monadic IO

それぞれ上からの順で実装していけば良いと思います．オフサイドルールは飛ばしても問題ありませんね．パターンマッチは別に興味深くは無いのですが，私が実装したことがありませんでした．遅延評価も飛ばせますが，遅延評価が無いとMonadic IOがなんだかちょっと寂しいことになってしまいます．型クラスを実装しないとその下には進めません．

あと，コンパイラを書くのは面倒なので，全て再帰的なevalで評価器は書きます．また，型推論なんかもパフォーマンスは無視で，関数的に書いていこうと思います．あまりに遅かったらまた考えますが．

あとプログラミング言語はOCamlを使います．ocaml3.10とfindlib，ExtLibが導入されている環境を前提でソースコードを書いていきます．私のコードをビルドしたい方はインストールしておいてください．

■ [Haskell Hackathon]全体の構造を考える

普通に…

モジュール名	ファイル名	説明
Main	main.ml	エントリポイントを書きます
Ast	ast.ml	抽象構文木(Abstract Syntax Tree)の定義と操作を書きます
Lexer	lexer.mll	字句解析器を書きます
Parser	parser.mly	構文解析器を書きます
Values	values.ml	値の定義と操作を書きます
Prelude	prelude.ml	組み込みの値の定義を書きます
Eval	eval.ml	評価器(evaluator)の定義を書きます
Debug	debug.ml	デバッグプリンタの定義を書きます

ビルドの方法は

$ ocamlbuild -ocamlc "ocamlfind ocamlc -package extlib" -lib extlib main.byte

みたいな感じです．これはMakefileに書いてあります．

■ [Haskell Hackathon]構文を考える

構文を決めます．Astの定義を見てみましょう．

$ svn cat -r 5 http://svn.soutaro.com/has/trunk/ast.ml

• r 5ってどんなだったか覚えていませんが，最初はこんな感じで定義していました．

type id = string

type literal =
    String of string
  | Char of char
  | Int of int

type expr =
    Var of id
  | Lit of literal
  | App of expr * expr
  | Abs of id * expr
  | Let of let_binding * expr
      (* Binary operators *)
  | Plus of expr * expr
  | Minus of expr * expr
  | Mul of expr * expr
  | Div of expr * expr

and let_binding = id * expr

type decl =
    Val of id * expr
  | Print of expr

idが識別子の型です．ここでは単純にstringです．

literalは即値(literals)の型．文字列と整数と文字があります．文字列はリストがあれば必要ありませんが，とりあえず入れておきます．

exprが式の型です．変数(Var)，リテラル(Lit)，関数適用(App)，関数抽象(Abs)，Let式(Let)などがあります．残りは普通の二項演算子．

letbindingはlet x = e in exprの太字の部分のことを言います．これも，本当は関数が来たり，パターンが来たりするのですが，現時点ではこのままにしておきます．

最後のdeclはトップレベルの定義です．プログラム全体はdeclのリストになります．Valが，Haskellで

fact = ¥n -> if n = 0 then 1 else n * fact (n-1)

とか書くやつに相当します．値の定義です．Printは，ここで特別に入れた構文で，引数の式を評価した結果を出力します．Haskellには本当はこんな構文はありませんが，普通の関数として文字列を出力するやつを入れるのは，純粋関数型言語的にいかがなものかと思い，構文を新たに導入することにしました．Monadic IOまで実装したら，Printは消えます．

他にPretty Printerの定義があります．OCamlのFormatモジュールに興味があるかたは実装を読んでも良いと思います．

ひさびさ。

■ Haskellの型推論は完全？

MLの型推論は完全である。

エラーなく実行できるプログラムは、必ず型推論できる

というのが「型推論が完全」の意味。

OCamlの型推論も完全。

Haskellはどうなんだろ？

Polymorphic Recursionは完全じゃなかったはず(型推論が止まらなくなることがある)なので、Haskellは完全じゃないのかな。

■ Polymorphic Recursionの例

data Seq a = Nil | Cons a (Seq (a,a))
size :: Seq a -> Int
size Nil = 0
size (Cons a b) = 1 + 2 * size b

ghciに食わせてみる。

  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.4.2, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base-1.0 ... linking ... done.
Compiling Main             ( pr.hs, interpreted )
Ok, modules loaded: Main.

大丈夫。

OCamlだと…

        Objective Caml version 3.09.2

# type 'a seq = Nil | Cons of 'a * ('a * 'a) seq;;                                                                                       
type 'a seq = Nil | Cons of 'a * ('a * 'a) seq
# let rec size = function                                                                                                                
    Nil -> 0                                                                                                                             
  | Cons(a,b) -> 1 + 2 * size b;;                                                                                                        
This expression has type ('a * 'a) seq but is here used with type 'a seq

確かにダメ。

ふむふむ。

■ Haskellにはvalue restriction(値多相)がない件

syd_sydさんのコメントに

Haskellには値多相がない

とあり、ええええ？？？？と思ったので、試してみる。

まず、value restrictionはこういうやつ。OCamlで。

# let id x = x;;
val id : 'a -> 'a = <fun>
# let f = List.map id;;
val f : '_a list -> '_a list = <fun>
# f [1;2;3];;
- : int list = [1; 2; 3]
# f;;
- : int list -> int list = <fun>

ここで、List.map idは値ではないので、fの型は単相型になり、一度int listに適用するとそれ以降ではfの型はint listになってしまう。こういう「値ではないやつ」の型が多相型にならないことを、value restrictionという。ちなみに「値」の定義はややこしいので省略するが、とりあえず「関数適用の途中のやつ」が値ではないと考えておけばよい。\x -> xは値だが、(\x y -> y) 1は値ではない。

では、ghciで。

Prelude> let f = map id
Prelude> f [1,2,3]
[1,2,3]
Prelude> f ["a"]
["a"]

ふむ。value restrictionを仮定すれば、fの型は単相になるので、f [1,2,3]の後のf ["a"]でエラーになるはず。だが、なっていないので、value restrictionはないということになる。

ほおーーー

うーむ、value restrictionって、なんで必要なんだっけ…

■ Haskellは面白いなあ

MLとほとんど同じ型システムだと思っていたが、全然違う。(遅延評価とかに興味がない人)

■ IDE

結局、eclipsefpはEclipseの使い方がよくわからないので、Visual Studio 2003を探してきて(押入れにあった)、Virtual PCにインストールすることにし、Visual Haskellを使ってみることに決めた。Visual Haskellがダメなら、しかたがないMeadowかxyzzyでHaskell modeを使うことにしよう。

で、現在Visual Studioのインストール中。

ところで、いつになったら、Haskellプログラミングを始められるんでしょう。

■ Visual Haskell

結局、Visual Haskell。

入力補完も効くみたいだし、シンタクスのチェックもしてくれるし、まあいいだろう。

■ Polymorphic Recursion

Haskellのwhere以下は相互再帰的に処理される。

OCamlのletはデフォルトで再帰関数を定義できないのでちょっとびっくり。大丈夫なんかな。というのは、ML多相の範疇では、再帰関数は定義の中では多相的に利用できないから。多相性が制限され過ぎそうな気がしてしまう。

実は、HaskellはPolymorphic Recursionがあるので大丈夫。再帰関数も多相型が推論される。

module Main where

main = do
	print $ f 1
	print $ g "b"

id' x = x

f x = id' 1 + x
g x = id' "a" ++ x

ここで、id'がfとgの中でそれぞれ多相的に利用されていることがポイント。

OCamlで同じプログラムにしようとして、

let rec id' x = x
and f x = id' 1 + x
and g x = id' "a" ^ "b"

let _ = begin
  Printf.printf "%d\n" (f 1);
  Printf.printf "%s\n" (g "b");
end

としてもエラーになる。

と思ったんだけど本当だろうか。上のプログラムだと、本質的には相互再帰的ではないので、順に宣言していくプログラムに書きなおせるはず。うーん、ちょっと気になるな。

■ よし

明日からMLのインタプリタを書いてみよう。

■ 所信表明

いつもはOCamlで型推論アルゴリズムの実装をしています。

Haskellは、タイプクラスが面白そうだなあというのと、ちょっと前までタイプクラスタイプクラス連呼してた知り合いがいるのと、3年くらいモナドが理解できずに悔しいのと、誰かがなんかの拍子にHaskellのコードを書いたときに「さっぱり読めなくて悔しい」のくらいで気合を入れて勉強してみようと思いました。

■ IDE

まずはIDEのインストールから。Emacsとかmakeとかありえなーい。

「Haskell Visual Studio」とかでぐぐると404 Not FoundとかVHSとかがヒットする。どっちがいいかはわからないんだけど、Haskell Workshopとかに論文を出してるチームであるということと、あとは単純にもう一方が繋がらなかったので、Visual Haskellをインストールすることに。うちのVS2005なんだけど、入るかなー？

あれ？Haskell処理系はいいのかな？いや、これ入ってるのか。すげ

とか書いてたら、インストーラがコケた。なぜだー

一度、FirefoxとかVirtualPCとかiTunesとか終了して試してみよう

⇒当然ダメ。よく読むと「なんかインストーラおかしいねんけど」と言っているように見える。なんなんだ。もう一度インストーラをダウンロードしてみることに。これでダメなら、VS2003じゃないとダメなんだと判断しよう。

ダメだ。

ところで

In order to use Visual Haskell, you need Visual Studio .NET 2003. Right now, this is the only supported version of Visual Studio - unfortunately we haven't yet added support for the 2005 Beta. The Express languages (Visual C++ Express etc.) also will not work, because they don't have support for plugins.

とかWebサイトに書いてあるのがちょっと面白いと思った。microsoft.comのメールアドレスだから、中の人じゃないかと思うのだが。中の人でもbeta版持ってないとかあるのかなあ…

*1

うーむ、とりあえずmsi除くくらいならやってみてもいいと思ったし、中身をハックしても良いと思うし、そうするとHaskellグループなのになんかC#とかVBとかのコードが書き散らかされてて斬新な感じになると思っていたのだが、MSの中の人に対して「VSのコード見てやるからよこせ*2」というのはさすがにアレなので、やっぱり止めとこう。

あきらめよう。次はVHSにチャレンジ！

が、やっぱりWebサイトに繋がらない。

EclipseFP - Functional programming support for Eclipseに行くべきだろうか。おお、haskellのほうは結構更新されてるじゃないか。よしよし。OCamlのほうは2年くらいメンテされてないっぽかったから、完璧に終わったプロジェクトだと思ってたんだが。こっちはGHCのインストールからしないとだめなのね…

ghcのインストールはこともなく終了。あ、このやろーc:\の直下に入れやがったな…

まずghciを動かしてきちんとインストールできてるか試すことに。

let a = 3

うは。何年か前はインタプリタでletできなくてぶちきれた記憶があるのだが、今はちゃんとできるのね。さすがさすが。んで、終了できなくてはまる、とorz。WindowsではEOFはCtrl+zだったか。

■ ふと気づいたこと

OCamlやSML#ではletの右辺は、変数の定義に先立って評価されます。そうしないと、右辺が多相レコードの式*3だった場合に、型が定められません。多相レコード型の自由変数の定義がメソッドの型を含むからです。

Haskellでは右辺は必要になるまで評価されません。つまり、型も定まりません。普通のML多相の範囲ではそこに型変数を割り当てておけばそれで型が付くのですが、多相レコード計算のようなStructural Polymorphism(構造的多相？)が入ると、自由型変数が必要になるのでそれではうまくいかないのです。

つまり、call-by-needのsemanticsを採用すると、型システムにも制限が加わるわけです。今まで気づかなかったんですが、これはちょっと面白いかも。

■ ↑はウソだな

型とランタイムの振る舞いは関係がないな。多分。したがって上のはウソ。普通に式の型だけ計算すればよい。