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は
   ２引数関数の引数の順を入れ換える高階関数とします。

確かに。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を分かりやすく説明しているページをみつけた。

Combinators and Graph Reduction

やっぱり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 は１個以上の任意個数の引数をとることができてしまうからだと思います。私の場合、強い静的型付けになじんでいるので、任意個引数の手続きと相性がよくないようです。:-) --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)

Tags: Currying, Haskell

Last modified : 2013/04/29 01:29:57 UTC