2010/11/28

applyの引数リストの長さの制限

http://twitter.com/cddddr/status/8982330207117312

タイプ数削減が目的で (fold-left f acc xs) を (apply f xs) と書くとリストが長すぎる場合怒られる事があるので xargs みたいな要領の xapply を書こうかなと思ったけど面倒なので fold-left で良いやという結論に落ち着いた

処理系の制限で短く書けないというのは癪に障る。 昔はGaucheでもapplyの引数リストに長いリストを渡せなくていらついたものだった。 十分いらついたので、今はこの通り。

gosh> (apply + (make-list 10000000 1))
10000000

引数の長さの制限は依然として存在するんだけど、 それが問題になることがほぼ無くなった。

VMの引数渡しは原則スタック経由、つまりcallerが引数を順にスタックに積んで、 caller側はスタックポインタ相対で引数にアクセスするようになってる。 Gauche VMはスタックが溢れるとヒープに移すようになってるけど、 スタックフレーム単位の処理なので、ひとつのスタックフレームの大きさが VMのスタックエリアを越えるような事態は想定してない。

以前のapplyは引数リストを分解してスタックに積んでた。 なので上のような式だとスタックが足りなくなる。

けれど、長大な引数リストを取るような関数ってのは、まず確実に、 不定長引数を取るような関数なんだよね。で、不定長の残余引数は calleeからはリストに見える。 つまり以前のapplyでは、わざわざリストで渡ってきた引数を 一回ばらしてスタックに積んで、それをcallee側でまたリストに直してた。

今は、callerが不定長の引数リストをリストのままスタックに 積めるようになってて、callee側の必須引数の数に合わせて VMが必要な分だけスタックに展開するようにしてる。 + は必須引数が0なので、上の式だとリストは一切展開されない。

ただ、Schemeの規格上、残余引数リストはfreshなリストでなければならない (calleeが残余引数リストを破壊することが許されている)ので、 リストをコピーして渡さないとならない。CLだとコピーはcallee側の責任なんだけど。 このへんはまだ工夫の余地あり。

今のVMで引数の数の制限に引っかかるのは、 caller側が実際に10000個くらいの引数を列挙するか、 callee側が10000個くらいの仮引数を持っている場合。

前者はまあ、マクロ展開の結果として生じる可能性はあるけれど、 後者のケースでない限りはapply使えば回避できるんで、 実用上は問題ないかと。

今書いてて思いついたんだが、後者のケースでも処理系がコンパイル時に 一定数以上の仮引数は残余引数リストで受け取るようにしてlist-refで 参照する、とか変換かけちゃえばいいんだな。

Tags: Gauche, Lisp, Scheme, Programming