soutaroのHaskellにっき

2008-02-02

[] 2008-02-02 - soutaroのHaskellにっき を含むブックマーク

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

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

[]どこまでやるか決める どこまでやるか決める - soutaroのHaskellにっき を含むブックマーク はてなブックマーク - どこまでやるか決める - soutaroのHaskellにっき

最初に,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が導入されている環境を前提でソースコードを書いていきます.私のコードをビルドしたい方はインストールしておいてください.

[]全体の構造を考える 全体の構造を考える - soutaroのHaskellにっき を含むブックマーク はてなブックマーク - 全体の構造を考える - soutaroのHaskellにっき

普通に…

モジュール名ファイル名説明
Mainmain.mlエントリポイントを書きます
Astast.ml抽象構文木(Abstract Syntax Tree)の定義と操作を書きます
Lexerlexer.mll字句解析器を書きます
Parserparser.mly構文解析器を書きます
Valuesvalues.ml値の定義と操作を書きます
Preludeprelude.ml組み込みの値の定義を書きます
Evaleval.ml評価器(evaluator)の定義を書きます
Debugdebug.mlデバッグプリンタの定義を書きます

ビルドの方法は

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

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

[]構文を考える 構文を考える - soutaroのHaskellにっき を含むブックマーク はてなブックマーク - 構文を考える - soutaroのHaskellにっき

構文を決めます.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)などがあります.残りは普通の二項演算子

letbindinglet 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モジュールに興味があるかたは実装を読んでも良いと思います.

2006-07-06

ひさびさ。

Haskell型推論は完全? Haskellの型推論は完全? - soutaroのHaskellにっき を含むブックマーク はてなブックマーク - Haskellの型推論は完全? - soutaroのHaskellにっき

ML型推論は完全である。

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

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

OCaml型推論も完全。

Haskellはどうなんだろ?

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

Polymorphic Recursionの例 Polymorphic Recursionの例 - soutaroのHaskellにっき を含むブックマーク はてなブックマーク - Polymorphic Recursionの例 - soutaroのHaskellにっき

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

確かにダメ

ふむふむ。

2006-06-13

Haskellにはvalue restriction(値多相)がない件 Haskellにはvalue restriction(値多相)がない件 - soutaroのHaskellにっき を含むブックマーク はてなブックマーク - Haskellにはvalue restriction(値多相)がない件 - soutaroのHaskellにっき

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は面白いなあ Haskellは面白いなあ - soutaroのHaskellにっき を含むブックマーク はてなブックマーク - Haskellは面白いなあ - soutaroのHaskellにっき

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

syd_sydsyd_syd2006/06/14 23:17value restrictionが何故必要なのか、僕も興味があります。。。

2006-06-12

IDE IDE - soutaroのHaskellにっき を含むブックマーク はてなブックマーク - IDE - soutaroのHaskellにっき

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

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

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

Visual Haskell Visual Haskell - soutaroのHaskellにっき を含むブックマーク はてなブックマーク - Visual Haskell - soutaroのHaskellにっき

結局、Visual Haskell

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

Polymorphic Recursion Polymorphic Recursion - soutaroのHaskellにっき を含むブックマーク はてなブックマーク - Polymorphic Recursion - soutaroのHaskellにっき

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

としてもエラーになる。

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

よし よし - soutaroのHaskellにっき を含むブックマーク はてなブックマーク - よし - soutaroのHaskellにっき

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

2006-06-11

所信表明 所信表明 - soutaroのHaskellにっき を含むブックマーク はてなブックマーク - 所信表明 - soutaroのHaskellにっき

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

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

IDE IDE - soutaroのHaskellにっき を含むブックマーク はてなブックマーク - IDE - soutaroのHaskellにっき

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

Haskell Visual Studio」とかでぐぐる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できなくてぶちきれた記憶があるのだが、今はちゃんとできるのね。さすがさすが。んで、終了できなくてはまる、とorzWindowsではEOFはCtrl+zだったか。

ふと気づいたこと ふと気づいたこと - soutaroのHaskellにっき を含むブックマーク はてなブックマーク - ふと気づいたこと - soutaroのHaskellにっき

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

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

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

↑はウソだな ↑はウソだな - soutaroのHaskellにっき を含むブックマーク はてなブックマーク - ↑はウソだな - soutaroのHaskellにっき

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

*1:なんでこんな読み間違いしたんだろ…orz

*2自信過剰

*3OCamlオブジェクトとかPolymorphic VariantとかSML#のレコードとか

syd_sydsyd_syd2006/06/13 14:00お久しぶりです。
>call-by-needのsemanticsを採用すると、型システムにも制限が加わる
コレも本当でしょうか?どっちかというとHaskellには値多相がないので「より自由」な気がしてたんですが…(レコード多相をよく知らないので何とも言えない) Haskellの「制限」といえばmonomorphism restrictionかなとは思うんですが。もうちょっとOCaml勉強します。

soutarosoutaro2006/06/13 14:58ウソだと思いますorz(本当かもしれませんが、積極的に主張するつもりはありません。)