Scheme currying icon Nested parentheses with lambda symbol representing Scheme currying Schemeでカリー化実装を
考える
（Lisp-1）

by
  • SchemeはLisp-1なので、カリー化したクロージャをfuncallなしで呼び出せますが、Haskellのような自動カリー化はなく、lambdaを省くには自分で仕組みを用意する必要があります。
  • define-curry マクロを使うと引数を段階的に受け取る関数を定義でき、filter (greater-than 10) xs のようなHaskell風の書き方に近づけられます。
  • ただし引数の数が実行時に取得できないため、既存関数の一括カリー化は難しく、可変長引数やgeneric functionとの組み合わせも原理的に曖昧さが残ります。
  • SRFI-26はこの限界を認めて「カリー化」という名称を捨て、プレースホルダー<>で任意の引数位置を固定できる部分適用の記法cutとして設計されました。

関連記事

1. Lisp-1でfuncallは不要になった、それでも…

Common Lispでは、カリー化したクロージャを呼び出すたびに funcall が必要になる問題がありました。
原因はLisp-2、つまり関数名前空間と変数名前空間が分離していることでした。

一方、SchemeはLisp-1です1。
関数と変数が同じ名前空間を使うので、define で束縛したクロージャをそのまま呼び出せます。

(define add5
  (lambda (x) (+ x 5)))

(add5 3)   ; => 8  ← funcallは不要Code language: Scheme (scheme)

Common Lispなら (funcall add5 3) と書く箇所が、Schemeではそのまま呼べます。

ただし、Haskellのように「引数が足りない呼び出しは自動でクロージャになる」わけではありません2。
Schemeでも引数の数が合わなければエラーになります。

(define (greater-than n x) (< n x))

(greater-than 10)
; => エラー：引数の数が合わない

(filter (lambda (x) (greater-than 10 x)) '(5 8 11 14 17))
; => (11 14 17)Code language: Scheme (scheme)

Haskellなら filter (greater-than 10) xs と書けますが、Schemeでは lambda を書く必要があります。
この lambda を省ける仕組みをどう作るか。
それがSchemeでのカリー化の出発点です。

1.1. define-curry マクロで段階適用を作る

define-curry マクロを定義して、greater-than をカリー化された形で使えるようにしてみます。
define-syntax と syntax-rules はSchemeの衛生的マクロシステムで、マクロ展開時に変数名の衝突を自動的に防ぎます3。

(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))))Code language: Scheme (scheme)

これを使うと、先ほどの greater-than はこう書けます。

(define-curry (greater-than n x) (< n x))

(greater-than 10)                          ; => クロージャが返る
(filter (greater-than 10) '(5 8 11 14 17)) ; => (11 14 17)Code language: Scheme (scheme)

lambda が消えました。
Haskellの filter (> 10) xs と同じ構造です。
引数を全部渡せば普通に動き、足りなければクロージャが返ります4。

(define-curry (scale-and-shift a b x) (+ (* a x) b))

(scale-and-shift 2 1 5)       ; => 11  (2×5+1)
((scale-and-shift 2 1) 5)     ; => 11
(((scale-and-shift 2) 1) 5)   ; => 11Code language: Scheme (scheme)

2. 既存の関数をカリー化したい

define-curry は新しく関数を定義するときには使えますが、既存の関数には使えません。
filter や map に部分適用を渡したい場合、別のアプローチが要ります。

シンプルな解決策は curry 関数です。

(define (curry fn . args)
  (lambda rest (apply fn (append args rest))))Code language: Scheme (scheme)

使い方はこうなります。

(define double (curry * 2))
(double 5)    ; => 10

(map (curry * 2) '(3 5 7))
; => (6 10 14)

(filter (curry < 10) '(5 8 11 14 17))
; => (11 14 17)Code language: Scheme (scheme)

Common Lispの alexandria:curry と概念は同じですが、funcall がない分すっきりしています。
curry を明示的に書かなければならない点は同じで、Haskellのように関数そのものが自動でカリー化されるわけではありません。

パフォーマンスが気になる場合、引数の数が分かっているならマクロ版が append を避けられます。

(define-syntax curry
  (syntax-rules ()
    ((_ fn)      fn)
    ((_ fn a)    (lambda rest (apply fn a rest)))
    ((_ fn a b)  (lambda rest (apply fn a b rest)))))

(map (curry * 2) '(3 5 7))   ; => (6 10 14)Code language: Scheme (scheme)

2.1. 「通常の関数を自動でカリー化できないか」という問い

既存の関数を一括でカリー化する仕組みは作れないか、という疑問が出てきます。

; こういうものが欲しい
(define curried-filter (curry-fn filter))
((curried-filter odd?) '(1 2 3 4 5))
; => (1 3 5)Code language: Scheme (scheme)

実装しようとすると、すぐ壁にぶつかります。
渡された関数が何個の引数を必要とするか、実行時には取得できないからです5。

仮に procedure-arity のようなプリミティブを追加して引数の数が分かったとしても、次の問題が待っています。
渡された関数がすでにカリー化されているかどうか判断できず、カリー化済みの関数を二重にカリー化すると意図しない動作になります。

引数の数を呼び出し側が指定するなら実装できます6。

(define-macro (curry-fn proc num-args)
  (let ((vars (list-tabulate num-args (lambda (_) (gensym)))))
    `(lambda-currying ,vars (,proc ,@vars))))Code language: Scheme (scheme)

ただしこれは実質的に、(define-curry (curried-filter pred lst) (filter pred lst)) と書くのと同じことで、汎用性のメリットはほとんどありません。

3. generic functionとの相性問題

さらに難しいケースがあります。
Gaucheのgeneric functionは、引数の数そのものがディスパッチの対象になります。

(define-method describe ((x <integer>))
  (format #t "整数: ~a\n" x))

(define-method describe ((x <integer>) (label <string>))
  (format #t "~a: ~a\n" label x))Code language: Scheme (scheme)

(describe 42) と (describe 42 "値") は両方正しい呼び出しです。
このとき (curry describe) に 42 を渡すと、「引数が揃った」と判断してよいか、それとも「まだ label が来るかもしれない」と見るか、原理的に決められません。

オプション引数も同様です。

(define (clamp x . bounds)
  (if (null? bounds)
      x
      (max (car bounds) (min (cadr bounds) x))))Code language: Scheme (scheme)

(curry clamp 0) は「0 を下限としてxをclampする関数」を返してほしい気がしますが、clamp は引数が1個でも動きます。
曖昧さが解決できません。

define-curry は引数の数が固定された関数にしか安全に使えません。
可変長引数やgeneric functionとの組み合わせは避けるのが現実的です。

3.1. SRFI-26の cut：カリー化ではなく部分適用として

2002年に提出されたSRFI-26は、この問題を別の角度から解決しています。
「カリー化」という概念を諦めて、「部分適用の記法」として設計されました。
名前も最終的に curry から cut に変更されています7。

<> をプレースホルダーとして使い、どの引数を固定してどの引数を残すかを明示します。

(cut < 10 <>)        ; => (lambda (x) (< 10 x))
(cut + <> 5)         ; => (lambda (x) (+ x 5))
(cut list <> 2 <>)   ; => (lambda (a b) (list a 2 b))Code language: Scheme (scheme)

curry と比べたときの利点は、先頭以外の引数も固定できることです。
flip のような補助関数が不要になる場面があります。

; flip不要で引数の順を入れ替えられる
(filter (cut < <> 10) '(5 8 11 14 17))
; => (5 8)   ← x < 10 を満たすもの

; curryで同じことをするにはflipが必要
(define (flip f a b) (f b a))
(filter (curry flip < 10) '(5 8 11 14 17))Code language: Scheme (scheme)

ただし cut も部分適用の記法であり、Haskellの自動カリー化とは異なります。
どの引数を残すかを <> で明示的に書く必要があります。

3.2. Haskellとの距離感

Schemeはfuncallが不要な分、Common Lispより一歩Haskellに近づいています。
ただしカリー化に関しては、まだ距離があります。

Haskellでは filter (> 10) xs と書けます。
Schemeで同じことをするには、define-curry や curry や cut のどれかを使って意図を明示する必要があります。

言語レベルで自動カリー化するには、関数呼び出しの評価規則そのものを変える必要があります。
マクロはコードを変換できますが、評価規則は変えられません。
define-curry でできるのは「カリー化された関数を定義すること」であって、「既存のすべての関数をカリー化すること」ではないのです。

SRFI-26が最終的に curry という名前を手放したのは、この限界を正直に認識した結果です。
Schemeでカリー化スタイルを追求するとき、どこかで自動化の夢を諦めて明示的な記法と折り合いをつける選択に迫られます8。

  1. 「Lisp-1」「Lisp-2」という用語はRichard P. GabrielとKent M. Pitmanが1988年の論文で定義したもので、名前空間が1つか2つかによって区別されます。 – Technical Issues of Separation in Function Cells and Value Cells (Lisp and Symbolic Computation, 1:1, 1988)
  2. Haskellでは言語仕様として「すべての関数は引数を1つだけ受け取る」と定義されており、複数引数の関数は実際には引数を一つ受け取って関数を返す関数の連鎖です。これは型システムと評価規則に組み込まれた性質です。 – Currying – HaskellWiki
  3. 衛生的マクロ（hygienic macros）はR4RSで初めて導入され、R5RS以降に標準化されました。マクロ内で導入された識別子が展開先の変数名を意図せず捕捉しないことを保証する仕組みで、Common Lispのgensymに相当する操作を自動で行います。 – Scheme Documentation: Macros
  4. 実装で letrec を使っているのは、curried が自分自身を参照する必要があるためです。let では束縛名は本体の中で参照できないため、再帰的な自己参照には letrec が必要になります。 – Revised⁷ Report on the Algorithmic Language Scheme (R7RS)
  5. 記事が書かれた2002年時点では Gauche に procedure-arity がなかったのですが、現在は arity として実装されています。しかし generic function の場合はメソッドが追加されるたびに値が変化するため、「引数の数が固定」とは言えないという問題は依然として残ります。 – Procedures and continuations (Gauche Users’ Reference)
  6. 手続きのarity取得をScheme標準に追加しようという試みはSRFI-102（2009年）として提出されましたが、実装によって情報の精度にばらつきがあり、ラッパー手続きなどでは実際のarityが隠れてしまう問題があるため、ポータブルな保証は難しいとされています。 – SRFI 102: Procedure Arity Inspection
  7. 実装ファイルのコメントによると curry から cut への改名は2002年2月27日に行われました。MLでの議論で「これはカリー化ではなく部分適用だ」という指摘が相次ぎ、著者のSebastian Egnerが名称変更を決断しています。cut という名前は「operator section」の概念に由来します。 – SRFI 26: Notation for Specializing Parameters without Currying
  8. この問題には後日談があります。2022年にSRFI-232（Flexible curried procedures）が策定され、curried というlambdaの変形で真のカリー化された手続きを作れるようになりました。引数を1つずつ渡しても、全部まとめて渡しても動き、新しい構文も不要です。ただし既存のすべての関数に透過的に適用される仕組みではなく、明示的に curried で定義した関数にのみ有効です。 – SRFI 232: Flexible curried procedures