Haskellの評価
出典: どう書くwiki
目次 |
[編集] yukobaの考え
純粋関数型言語と非純粋関数型言語では処理の仕方が大きく異なります。 Schemeなどの非純粋関数型言語は手続き型言語に近いです。 それに対して、Haskell は同じ宣言型プログラミングであり、論理プログラミングである Prolog に近いです。 関数名なども似ています。
論理プログラミングはパターンマッチングによって成立しています。 Haskell も同じ処理の方法が基本です。「式変形」が基本です。 「遅延評価」というのは、非純粋関数型言語のパラダイムから見たときの言い方であり、 宣言的プログラミングの発想からいうと、何かを遅延しているわけではありません。 数学的な数式処理の発想から来ていて、左辺 = 右辺でつながったものを、 main から順番に式変形していくだけです。
非純粋関数型言語では、「プロミス」というのを作って、それこそ、文字通り、評価を遅延します。 そのやり方でも実装できると思いますが、本質的な手法ではありません。
パターンマッチングで置換していく際の注意事項として、Clean入門(14)：評価戦略 でも書かれていますが、頭から、つまり、関数名から置換していくことが最重要です。 それを非純粋関数型言語のパラダイムでは「遅延評価」と言います。
純粋関数型言語の世界において、Lazy K という組み込み関数が3つしかない言語があります。 外見上似た者として、非純粋関数型言語のミニマムを作った、Unlambda というのがあります。 外見上は似ていますが、その本質は大きく異なります。
プリミティブ、つまり、それ以上評価できないものは、手続き型言語なら、 数値であったり文字だったりします。 Lazy K の場合は、プリミティブに相当するものはラムダ式になります。
たとえば、cons = 2つの要素の連結、car = 先頭、cdr = 末尾
cons x y = \f -> f x y car l = l (\a b -> a) cdr l = l (\a b -> b)
は上記のようになります。直感的には意味不明です。 実際に代入して、式変形を行うと、理解できます。
car (cons X Y) = (cons X Y) (\a b -> a) = (\f -> f X Y) (\a b -> a) = (\a b -> a) X Y = X
式変形をすると、なるほどという感じです。
- 頭から式変形をする
- ラムダになってしまったら、ラムダ式の変数に代入する。
- 頭が式変形できなくなったら、引数を式変形していく。（一部の組み込み関数が該当します）
- 最後に、もう、式変形できなくなったら終了。
という手順を踏みます。
無限リストの場合こんな感じになります。ちゃんと扱えています。
repeat x = cons x (repeat x) car (repeat X) = (repeat X) (\a b -> a) = (cons X (repeat X)) (\a b -> a) = (\f -> f X (repeat X)) (\a b ->a) = (\a b -> a) X (repeat X) = X
Haskell の場合、数値や文字はプリミティブ型があるので、そのまま使えますが、 Lazy K の場合、これらも、ラムダ式になります。 ラムダ式の世界では、数字の2は
2 = \f x -> f (f x)
という形になります。fを作用させた回数が自然数の値です。これまた、非常に直感的ではありません。 Wikipediaのラムダ計算にいろいろ書いてあります。加減乗除のラムダ式とセットで式変形してみると理解できます。
一連のラムダ式は、手作業で式変形をやってみて練習しておくと、理解できるようになると思います。 ただし、手続き型言語の処理系の実装にはあまり役に立ちませんし、Haskell はプリミティブ型がいろいろありますし、リストもプリミティブ型ですし、深追いしても無駄かも。
上記に基づいて実装してみたブログ：Haskellの評価戦略を作ったよ
↓以下、yukoba以外の方が書いてくださった文章↓
[編集] 概要
Haskellインタプリタなら右辺をどんどん崩していけばいい。
[編集] 遅延評価
Thunkと呼ばれる、 [評価すべきもののシンボル名→(ポインタ)→それを評価してくれる関数]のマップを用意。 必要になったとこから関数を実行して、評価後の値にポインタを差し替える。
[編集] パターンマッチ
左辺がパターンだったら、パターンマッチを行うのかな？ パターンの木構造を上から順番に一致するかどうか調べればいい。
