Gauche:Currying

Gauche:Currying

Shiro(2008/08/31 18:57:02 PDT): Scheme:手続きのcurry化 で6年以上前に議論されたことなんだけど、 最近になって有用そうな場面が出てきたので試しに実装してみることにした。

なお、Schemeの基本機能のみでcurry化可能な手続きを定義することはできる (Scheme:手続きのcurry化のページのlambda-currying, define-curryマクロ)。 ただ、Schemeの基本機能のみで作った場合、出来た手続きは不定長引数を取ることになる。 で、不定長引数の処理というのは固定長引数に比べて重いのだ。 ほんのわずかな差ではあるけれど、100万回呼ばれる手続きだとその差が 問題になることがある。

今回応用しようと思ったケースでは、case-lambdaでも実装できたんだが case-lambdaはやはり出来た不定長引数手続きを作ってしまうので 性能がクリティカルな場面では使いにくい。

なお、ランタイムが頑張れば不定長引数の扱いを軽くすることはできる。 (現在、caller側でrest引数をリストにしているが、そのまま渡してcallee側で 必要に応じてリストにすれば良い。curry化とかオプショナル引数みたいに rest引数がリストであることを必要としないケースならリスト化のオーバヘッドが 避けられる)。 ただ、VMをかなりいじる必要がありそうなので今回は避けた。

テスト実装のアイディアはScheme:手続きのcurry化にあげてたものと同じで、 引数が足りない時に呼ばれるエラーハンドラ内でクロージャを作ってやるというもの。 ただしgeneric function呼び出しをはさむとオーバヘッドがあるので エラーハンドラにハードコードした。

この方法なら、十分な引数が与えられた場合には通常の手続き呼び出しとまったく 同等の性能であり、また引数が足らずにcurry化された場合でもクロージャを 作って返すオーバヘッドだけだ。

すべての手続きをcurry化可能にしてしまうこともできるが、静的型でないSchemeの 場合、引数の不一致でエラーを出してくれることもデバッグに役に立ったりするので、 <procedure>の方にcurry化可能かどうかのフラグを設けた。

んで、ランタイムでのサポートは簡単だったんだけれどもいくつかまだ検討すべき事項がある。

ローカルで定義された手続きがcurry化呼び出しされている場合の適切な処理を

どうすべきか。

現在、ローカルな手続きはコンパイラがclosure optimizationをかけるときに 引数の数のチェックを行う。数が一致していればgotoに変換できたりインライン展開 できたりするからだ。で、数が一致してない場合はcompile errorにしてるんだが、 curry化可能であれば別の方法を考えないとならない。 curry化された新たなクロージャを作るようにコード変換をかけるのが順当だが 若干手間がかかりそうだ。

curry化可能手続きのarityは?

GaucheRefj:arityは何を返すべきか。今のままだとcurry化可能かどうかに かかわらず、元々の手続きの必須引数の数を見に行っているんだけど、 curry化可能であればそれ以下の引数を与えてもエラーにはならない。

#<arity-at-least 1> にしてしまう、という手はあるんだが、これだと (lambda (a . b) ...) という手続きと区別がつかない。 で、arityをチェックして動作を変えるようなトリッキーなコードでは、 両者を区別したい場合が生じると思う。

順当なのは、例えば必須引数が3個でcurry化可能なら (1 2 3) のように リストで返すことか。つまり多重定義されているとみなす。 必須引数が3個かつ不定長引数であれば(#<arity-at-least 1> #<arity-at-least 2> #<arity-at-least 3>) となる。

generic functionとの絡み

generic functionのcurry化はどう解釈すべきか。

ひとつの解釈としては、「与えられた引数の数がどのメソッドの必須引数の数よりも 少ない場合、(lambda args (apply gf (append given-args args)))を返す」 というのをfallback methodにしておくという手はある。効率は悪いけど。

ただ、例えば (<integer> <integer>) という特定化子リストを持つメソッドと、 (<string> <string> <string>) という特定化子リストを持つメソッドがあって、 二つの文字列が引数として与えられた場合、とかなると難しい。 2番めのメソッドの部分適用と考えるべきだろうか、それとも引数ふたつで 一致するメソッドがないのでエラーとすべきだろうか。

API

curry化可能かどうかは手続き本体の属性なので、 lambda-curryのようなマクロで無名かつcurry化可能な手続きを 作れるようにしとく、というのが順当。

ただ、上に示したissueを解決しないうちは、ローカルで無名のcurry化可能手続きが 出てくると一貫性のある扱いが難しい。したがって当面はdefine-curryのように トップレベルの名前つき手続きのみcurry化可能にできるという制限を設けることも ありかもしれない。

既にある手続きをcurry化可能にできるか? テクニカルには可能 (フラグをたてるだけだから)。 しかしインライン化可能な手続きはコンパイル時に引数の個数をチェックしてたりするので 一貫性のある動作を保証するのが面倒くさそう。 (curry <procedure>) で新しいprocedureを作って返すというのが楽かもしれない。 元の<procedure>がインライン化可能であっても、新しいprocedureはそうではないということで。

ただ、そうすると (define cons (curry cons)) とかやられると ものすごく性能が落ちる。

コンパイラが選択的にインライン化できればいいんだけど、 たぶんそれは上に書いたローカル手続きの処理と重なって来るんで、将来の課題ということに しとく。

Status

2008/09/01 01:42:29 PDT: うーん、元の手続きが不定長引数を取る場合の処理がいまいち綺麗にならないことが判明。 VMのAPIを変更すればいけるんだけど、そうすると「ちょっとしたハック」からは 逸脱してくる。

一旦脇に置いてみて後で考え直そう。

とりあえずコードはコメントアウトした状態でcommit (rev6373) 試したい人はsrc/vm.cのwnaの部分、src/proc.cの"Currying"の下、 src/autoloads.scmのgauche.procedureの中、および lib/gauche/procedure.scmの"Curryable procedures" のところ、 のコメントを外してくださいな。

Tags: Currying, Arity, Haskell

More ...