純粋関数型言語が非正格である理由
HaskellやConcurrent Cleanは、純粋関数型言語です。つまり、副作用を持たず、関数を第一級として扱える言語です。（関数プログラミングとか関数型言語とかって何？ → [id:lethevert:20060105:p3]）
しかも、非正格（normal order）な評価をするという特徴があります。これは、関数の引数や返値として式を渡したときに、その式をいつ計算するかということについて、式の計算結果が必要になるまで計算を行わないという評価戦略を取っていることを意味していて、遅延評価と呼ぶこともあります。（参照透過性について考察 → [id:lethevert:20060108:p5]）
どうして評価戦略を非正格としているのかについて、その意図を考えていたのですが（まさか無限ループを避けるためじゃないでしょ？）SICPの"2.2.3 Sequences as Conventional Interfaces"を読んでいて、一つの理由になりそうなことに気づきました。
-
-
- -
-
SICPの"2.2.3 Sequences as Conventional Interfaces"では、signal processingと対比させて、list操作関数を使った手続きの抽象・汎用化を説明しています。個々の操作の結果をリストを介して受け渡すことで、手続きを分解して再利用しやすい形にできるということなのです。
(define (sum-odd-square tree)
(accuulate +
0
(map square
(filter odd?
(enumerate-tree tree)))))ただし、このようにリストを介して受け渡すやり方は、正格（applicative order）な言語では、何度もループを回したり、不要な計算を行ったりすることになって、効率を犠牲にしてしまいます。また、そのままでは無限リストを使えないという制限もあります。
しかし、非正格（normal order）な言語では、このような問題が起こらないため、効率よくリストを介した抽象化を行うことができます。
-
-
- -
-
このあたりの計算量と非正格な評価戦略の利点については、以前、samefringe problemというところで考察したことが参考になる。
[id:lethevert:20051119:p1]
http://practical-scheme.net/wiliki/wiliki.cgi?Shiro%3alog%3a2005%b8%e5%c8%beの(2005/11/15 12:02:39 PST)
-
-
- -
-
ちなみに、上述の関数をConcurrent Cleanて定義すると、こうかな。
sum_odd_square tree
= foldr (+) 0
$ map sqare
$ filter is_odd
$ enumerate_tree tree
