Concurrent Clean : Finger Trees : 正格性

正格性をどの程度設定するかを検討している。
http://www.kmonos.net/wlog/76.html#_1947070805
にあるように、ある程度の非正格性を残して置く方がよいケースもあるのだけれど、一般的には正格にできるところは正格にしておく方が効率がよい。
Annotated finger treesなので、measureするところで計算が発生する。この計算は、最悪で全要素をなめるので、この計算のところで木全体が評価されてしまう。さらに、この計算は、要素の追加削除で計算結果が捨てられる可能性があり、計算全体が無駄になる可能性がある。なので、この計算は非正格にしておく方がよい。
しかし、それ以外の部分はどうだろうか？
例えば、append操作をしたときに、追加する要素のリストのスパインを正格評価するということは、許容できるのだろうか？
このあたりは、内部の処理がリストよりも複雑なので、リストのように評価順がわかりやすいわけではなく、Finger treeの性質上、後ろの方の要素が先に評価されることもあるので、非正格にしてもあまりメリットはなさそう。なので、入力するリストのスパインを正格評価するのは避ける必要はないと思う。
避けることを検討するべきは、k.inabaさんが指摘しているケースだけで、それを避けるには再帰している木のところだけを非正格にすればよいということになると思う。はたして、それを避けることはどの程度メリットがあるのだろう？

Concurrent Clean : Re: reduceとtoList

先の話は、ちょっと間違ってるな。
同じ高階関数でも、mapはマクロではない。マクロで定義しているのはfoldl/foldrだけだ。
そういえば、この件は、Clean入門の記事を書いていたときに、一度考察していた。
foldl/foldrは、正格性解析の結果で最適な評価順序が変わる種類の関数だったので、正格性解析を適切に機能させるためにマクロにしているのでした。
http://www.geocities.jp/lethevert/clean/gettingStarted17.html
で、reduceを関数として提供してしまうと、同じ問題が起きるので、toListでリストにしてからfoldl/foldrで処理する方が効率的に処理できるケースがあるというのが正しいのかな。

UPS

http://www.jmuk.org/diary/2007/08/11/0
うちは電化製品が多いので、夏とか冬とか消費電力があがる時期はちょくちょくブレーカーが落ちるので、デスクトップマシンをかった時には電力消費のピークの時期までにはUPSを買っておかないとと思っていたのでした。
で、前から目を付けていた下のUPSを２ヶ月くらい前に買って使っています。ざっと調べた感じ一番安かったので。すでに何回か助けられています。
http://www.soundhouse.co.jp/shop/ProductDetail.asp?Item=233%5EUPS500II

Concurrent Clean : reduceとtoList

まえに、toListがあればreduceいらないけど・・・という話を書いた。
[id:lethevert:20070802:p1]
reduceとtoListは表裏なのだけれど、効率のことを考えてみると（思考実験だけ）
reduceは、コレクションに含まれている要素に直接関数適用していくので効率よさそうに思える。それに対し、toListとfoldrの組み合わせは一度リストを作ってしまうので、オーバーヘッドがありそうに思える。
しかし、多分、現実は逆ではないか。
というのは、高階関数の呼び出しはオーバーヘッドが大きい。

foldr f [] z = z
foldr f [a:aa] z = f a (foldr f aa z)

という関数では、fには

add a b = a + b
add a = add_a
　where add_a b = a + b

という２種類の関数を与えることが許される。
そのため、foldrをコンパイルするときには、fの関数適用では、１引数ずつ適用してその都度関数オブジェクトを生成しなければならず、動的な関数ディスパッチと併せてかなりのオーバーヘッドが発生する。
そのため、Cleanでは、foldrを含む基本的な高階関数は全てマクロで定義している。また、マクロで定義しにくいケースでも、型クラスを使った上でspecial指定することで関数引数を渡すことをさける。
これを踏まえて、reduceとtoListを考えると、reduceは効率の悪い高階関数を使わざるを得ないのに対して、toListは適用すべき関数がconsに決め打ちであるため高階関数のオーバーヘッドが発生しない。さらに、toListと組み合わせるfoldrはマクロである。
Cleanは遅延評価なので、toListとfoldrを組み合わせても、中間データが大きなメモリを占めることがないため、全体としてtoList+foldrの方がreduceよりも効率よく処理を行うことができるのではないか？

      • -

という仮説をもって、toListで生成されたABCコードを眺めてみた。結果、

jmp_ap 2
jsr_ap 2

という命令があって、２引数を同時に適用している。
ところで、この命令は以前CleanJをやったときにはテストケースで作り出せなかった命令なので、ABC machine instructionsにはデータがない。

      • -

うーむ。そうでもないな。
reduceを作ってみたけれど、同じようなコードになる。
FingerTreeのケースでは、Treeが再帰的なので、toListの内部処理が高階関数化することを避けられないからかな。
だとすれば、むしろtoList+foldrになるよりも、reduceを作る方が合理的ということになる。