Scheme:手続きのcurry化

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

となるようにできないか。


とりあえずナイーブな実装

 (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

問題点

後者に関しては、補助マクロを使えば引数の数でディスパッチするようなコードを 生成できると思います。


追記(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との相性が悪いのだけれど、まあ暫く使って 様子を見てみようか。

アイディアがあったらここに追加してくださいな。

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は可変個の引数を取る関数となってしまうのです。

  ((curry foo) 1)  は部分適用、((curry foo) '(1))  は全体適用
  ((curry foo) 1 2) は部分適用 ((curry foo) '(1 2)) は全体適用

うーん、それだと、リスト(1)を唯一の引数として呼び出したいときに 困ってしまいますね。


(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" とか。


Gauche に部分適用手続きが追加されましたね。パチパチ。 で早速、ドキュメントにある dot-product の定義を見ました。一瞬、理解できなかったです。 なぜかというと、この dot-product は1個以上の任意個数の引数をとることができてしまう からだと思います。私の場合、強い静的型付けになじんでいるので、任意個引数の手続きと相性 がよくないようです。:-) --nobsun (2002/05/28 22:42:45 PDT)

        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
  (define (zipWith$ bop)
    (fold-right$ (lambda (x y knil) (cons (bop x y) knil)) '()))
  ((zipWith$ *) '(1 2 3) '(4 5 6)) ==> (4 10 18)

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)

Tags: Currying, Haskell

More ...