Scheme:手続きのcurry化
nobsun で出た話題。
例えば
(define-curry (add x y) (+ x y))
としたときに、
(add 2 3) === (+ 2 3) ==> 5
は当然として、
(add 2) === (lambda (y) (+ 2 y)) ((add 2) 3) ==> 5
となるようにできないか。
- Found there was a thread in comp.lang.scheme recently.
とりあえずナイーブな実装
(define-syntax lambda-currying (syntax-rules () ((_ (arg0 arg1 arg2 ...) . body) (letrec ((curried (lambda args (if (null? args) curried (apply (let ((arg0 (car args))) (lambda-currying (arg1 arg2 ...) . body)) (cdr args)))))) curried)) ((_ (arg0) . body) (lambda args (cond ((null? args) (lambda (arg0) . body)) ((null? (cdr args)) (let ((arg0 (car args))) . body)) (else (error "too many args"))))) ((_ () . body) (lambda () . body))))
(define-syntax define-curry (syntax-rules () ((_ (fn . args) . body) (define fn (lambda-currying args . body))) ((_ var val) (define var val)) ))
実行例
gosh> (define-curry (add x y z) (+ x y z)) add gosh> (add 1 2 3) 6 gosh> (add 1 2) #<closure 101970c0> gosh> ((add 1 2) 3) 6 gosh> ((add 1) 2 3) 6 gosh> (((add 1) 2) 3) 6
問題点
- (lambda (x . y) body ...) のようなオプショナルな引数の定義は考慮していない
- 規定の引数をすべて渡した場合でも、applyが何度も呼ばれるので遅い。
後者に関しては、補助マクロを使えば引数の数でディスパッチするようなコードを 生成できると思います。
追記(2002/01/11 01:29:45 PST) : nobsunから、
通常の手続きをcurry化できるとさらに嬉しいなあ (define curried-proc (curry normal-proc))
とのことだが、残念ながら現在のGaucheでは渡された手続きの 引数の個数を知ることができないのでこれを一般的に実装する 方法はない。procedure-arity とか作ろうかな。
でも、たとえ分かっても、normal-procが既にcurry化されているか どうかを知る方法がないから、やっぱりダメだ。
curryを呼ぶ人が引数の数を知っていてそれを指定してやれば できる。
(use srfi-1) (define-macro (curry proc num-args) (let ((vars (list-tabulate num-args (lambda (_) (gensym))))) `(lambda-currying ,vars (,proc ,@vars))))
でもそれなら、既知のnormal-procに対して
(define-curry (curried-proc x y z) (normal-proc x y z))
と書くのと本質的に同じことだし。
もし既にまとまった量のライブラリを持っていて、
それをcurry化して使いたいのなら、Gaucheではちょっと強引な手がある。 モジュールを作って、その中でdefineやlambdaなどのglobal syntactic bindingをdefine-curryなどに置き換えてから、ライブラリをロードするのだ。 global-syntactic-bindingを置き換えられるかどうかは完全に処理系依存だが。
さらに追記(2002/01/11 03:29:32 PST): たとえprocedure-arityがあったとしても、 generic functionなんかが渡された場合にはうまくいかない。 generic functionのarityは引数によるディスパッチが済まないと 確定しないからだ。
だがふと思い付いた。too few argumentsエラーのハンドラを 書けるようにしておいて、そのハンドラ内でcurry化してしまうというのは どうだろう。
too few argumentsが起きたら、
Generic Function: too-few-arguments proc args
みたいに呼ばれるようにしといて、デフォルトメソッド は従来通り "too few arguments" エラーを投げる。でも、
(define-method too-few-arguments ((proc <procedure>) args) (lambda more-args (apply proc (append args more-args))))
としておけば、curry化された関数が返される。 発想としては、slot-missing generic functionなんかと同じ。
Gauche specificだからGaucheの方で議論すべきだったかな。まあいいや。
(→ Gauche:Currying)
(2002/01/11 13:46:01 PST) : nobsunにて議論の続き。curry化のメリットについて。
高階関数を使う場面では、関数がcurry化されているとlambdaを書かずに すませられることが多いのではないでしょうか。たとえば、 「複数 の集合ssから特定の条件pの要素をもつ集合だけを取り出したい」 ような場合を考えると、指定した条件をみたす要素を指定した集合が含んでい るかどうかを 判定する述語 (have? <条件> <集合>) があれば (filter (have? p) ss) と書けます。 (filter (lambda (x) (have? p x)) ss) と書くより楽です。また、 「特定の集合sが、複数の条件psのどれをとっても その条件をみたす要素を含んでいるかどうか」 を判定する場合、 (all (map (flip have? s) ps)) のように書けます。ここで、all はブーリアンのリストの要素が全て真かどうかを判定 する述語。flipは 2引数関数の引数の順を入れ換える高階関数とします。
確かに。Schemeプログラマはlambdaの存在をほとんど意識しないように条件づけられて いるが、それでも書くのが鬱陶しいと思うことはよくある。
妥協案としてこんなのはどうか。
(define (curry fn . args) (lambda more-args (apply fn (append args more-args))))
つまり明示的にcurryする。これだと、nobsunの例は
(filter (curry have? p) ss)
(all (map (curry flip have? s) ps))
と書ける。
実行例:
(use srfi-1) (define (flip f a b) (f b a)) (define (all blist) (every identity blist))
(any odd? '(1 2 3)) => #t (any odd? '(2 4 6)) => #f
(filter (curry any odd?) '((1 2 3) (2 4) (3 5 6))) => ((1 2 3) (3 5 6)) (all (map (curry flip any '(1 2 3)) (list odd? positive?))) => #t (all (map (curry flip any '(1 2 3)) (list odd? negative?))) => #f (all (map (curry flip any '(1 -2 3)) (list odd? negative?))) => #t
curryはマクロ定義にすればパフォーマンスペナルティを減らせる。
(define-syntax curry (syntax-rules () ((_ fn) fn) ((_ fn a) (lambda args (apply fn a args))) ((_ fn a b) (lambda args (apply fn a b args))) ((_ fn a b c) (lambda args (apply fn a b c args))) ((_ fn . more) (lambda args (apply fn (append more args))))))
まあ、SchemeプログラマがCommonLispを見たときに、「いちいちfuncallつけるのが ウゼェ」と思うように、関数プログラマはこれを見て「いちいちcurryつけるのが ウゼェ」と思うかもしれないが。
(2002/01/29 14:55:04 PST) Schemeを使ってcombinatorを分かりやすく説明しているページをみつけた。
やっぱりcurryは引数の数がわかってないとダメっぽい。ただ、combinatorスタイル のプログラミングはちょっと良い感じなので、Gaucheにライブラリとして 取り込んでみることを考える。
案:module util.comb
- function papply
Partial application. ((papply f x y) z) === (f x y z)
- function flip
(flip f x y) == (f y x)
- function combine
((combine f g) x) == (f (g x))
- function curry
(((curry f) x) y) == (f x y) ; これは手続きに関するmandatoryな引数の数を 知る必要があるので、そういうプリミティブを本体に追加する。
curryはgeneric functionとの相性が悪いのだけれど、まあ暫く使って 様子を見てみようか。
アイディアがあったらここに追加してくださいな。
- ちょっと質問です。 generic function との相性というのはどういう意味でしょう?--nobsun
CLOS系では、generic functionはapplyされた時点での引数を元に 実際にapplyされるメソッドを決定します。CLOSでは必須引数の数は 少なくとも決まっているのですが、STklosやGaucheではそれさえも ディスパッチの対象になります。例えば
(define-method foo ((x <integer>)) body1) (define-method foo ((x <integer>) (y <integer>)) body2) (define-method foo ((x <integer>) (y <integer>) (z <integer>)) body3)
のようにメソッドが定義されていると、(foo 1)と呼び出せばbody1が、 (foo 1 2) と呼び出せばbody2が、(foo 1 2 3)と呼び出せばbody3が 実行されます。すると、 ((curry foo) 1) は第一の形式の引数が saturatedしたとしてbody1を呼ぶべきでしょうか、それとも第二あるいは 第三の形式のpartial applicationとみなして (lambda args (apply foo 1 args)) を返すべきでしょうか。
つまり本質的にgeneric functionは可変個の引数を取る関数となってしまうのです。
- 可変個の引数がある場合、一まとめにしてリストでくれば、saturated にするというのは どうでしょう。
((curry foo) 1) は部分適用、((curry foo) '(1)) は全体適用 ((curry foo) 1 2) は部分適用 ((curry foo) '(1 2)) は全体適用
うーん、それだと、リスト(1)を唯一の引数として呼び出したいときに 困ってしまいますね。
- '((1)) あれ、だめか。strongly typed じゃないから難しいなあ。 カリー化については、オプション引数をもつものは、あきらめるのが良いような気が しますねぇ。でも、そうするとオプション引数を受け入れる手続きかどうかを一々 判断しなくてはならなくなりますが。
(2002/02/06 13:08:00 PST) ちょうど良いタイミングというか、curryingに関する新しいSRFIが提出されました。
- SRFI-26
Simple Notation for Specializing Parameters (Currying)
基本的には、ちょっと上で書いたマクロ版curry (実際はpartial application)と 同じですが、最初の方の引数だけでなく任意の箇所の引数をspecifyすることが できるようになっています。
(2002/02/12 17:19:41 PST) やっぱりというか、"curry" という名はふさわしくない、 という議論がsrfi-26 MLで。"partial-apply" とか "partial call" とか。
- うーむ。「カリー化された手続きを生成する手続き」か「部分適用手続き」かということかな。オプション引数の問題など、「カリー化された手続き」を正確に規定しにくいので、「部分適用手続き」を考える方が筋がいいということかなぁ。nobsun
- SRFI-26 の curry は「部分適用手続き」なので、確かに名前としては、ふさわしくないと感じますね。
Gauche に部分適用手続きが追加されましたね。パチパチ。 で早速、ドキュメントにある dot-product の定義を見ました。一瞬、理解できなかったです。 なぜかというと、この dot-product は1個以上の任意個数の引数をとることができてしまう からだと思います。私の場合、強い静的型付けになじんでいるので、任意個引数の手続きと相性 がよくないようです。:-) --nobsun (2002/05/28 22:42:45 PDT)
- 私がHaskell風の書き方に慣れてないせいもあるかもしれません… ぼちぼち使い始めてますが、書き方が変わりますね。 なお、将来的にはpa$等が効率良く実行できるようにVMに手を加える予定です。 --Shiro (2002/05/29 04:25:11 PDT)
- いえ、私が Scheme の任意個数をとる手続きになれていないせいです。^^;
Haskell 風で書くなら
(define (add x y) (+ x y)) (define (mul x y) (* x y)) (define (zipWith bop xs ys) (cond ((null? xs) '()) ((null? ys) '()) (else (cons (bop (car xs) (car ys)) (zipWith bop (cdr xs) (cdr ys)))))) (define sum (pa$ fold add 0))
が標準ライブラリにあることを前提に
(define (dot-prod xs) (compose sum (pa$ zipWith mul xs)))
かな。こうすると、Scheme だと、(dot-prod xs ys) と書けなくなるなぁ。
(define (dot-prod xs ys) (sum (zipWith mul xs ys)))
か。すなおに。--nobsun
- なるほど。値そのものと値のリストとを結構明確に意識して使い分けている ような印象がありますね。ちなみに(pa$ fold ...) は便利なので fold$というのが 定義されています。さらに、Schemeのfoldは複数個のリストが取れてしまうので こんなふうにも書けてしまいますな。--Shiro
(define (zipWith$ bop) (fold-right$ (lambda (x y knil) (cons (bop x y) knil)) '()))
((zipWith$ *) '(1 2 3) '(4 5 6)) ==> (4 10 18)
- いちいち部分適用版と全体適用版の違いを考えながら書かなければいけない、 という点では、Haskellerにとっては不便かもしれませんね。 --Shiro
SRFI-26の新版が出ました。
"Notation for Specializing Parameters without Currying" http://srfi.schemers.org/srfi-26/srfi-26.html
'curry' という名前は落とされて、'cut' になっています。
Gaucheの 'pa$' との違いは、free variableの位置を明示的に指定できることです。
(pa$ cons 2) == (cut cons 2 <>) == (lambda (x) (cons 2 x))
'<>'によってHaskellのflipみたいなのは不要になりますが、'<>'が最後に 来る場合は 'pa$' の方が短いし、いずれにせよGaucheでは両方サポートする ことになるでしょう。 --Shiro (2002/06/05 02:39:17 PDT)