Scheme 中的柯里化 | Yuandi's Webpage

Intro

柯里化 是一种将多参数函数转化成多个单参数函数的复合的技巧，e.g., F(x, y) 经过柯里化之后会变成 (F(x))(y). 在所谓的纯函数式语言如 Haskell 中，所有函数都是隐式柯里化的。

但是在 Scheme 的函数参数机制中没有柯里化的容身之所，至少看上去如此。很多 Schemer 不觉得柯里化会给这个语言带来多少应用上的裨益，事实上我也持相同的观点。但是这里我还是要试着给 Scheme 添加上柯里化机制，毕竟这门语言自身也难言有多少实际应用……

The Easy Way

如果不考虑一个普遍的语法形式，我们可以用 case-lambda 手动写出一个简单的柯里化函数：（此处和之后都只从左开始柯里化）

(define add
  (case-lambda [() add]
               [(x) (lambda (y) (add x y))]
               [(x y) (+ x y)]))

看着还行。但是这种方法有两个明显的缺点：

对于 n 个参数我们要手动处理 n+1 种情况，其中大部分大差不差。当 n 很大时写程序成了纯体力活，有点弱智。
这个方法没法处理匿名函数的情况。或者你情愿再多干点体力活，在每个 case 里重写一遍函数……

抛开手动柯里化的方案，根据定义我们能很轻松的写出来一个实现柯里化的语法形式：

(define-syntax ez-curried
  (syntax-rules ()
    [(_ (x . args) . body) (lambda (x) (ez-curried args . body))]
    [(_ () . body) (begin . body)]))

注意这里无参数的柯里化不会返回一个函数，而是直接返回 body 的运行结果。这一方面是为了保证递归能够收敛，另一方面也符合定义：无参函数的柯里化是没有意义的。

现在我们能处理匿名函数的柯里化了：

((((ez-curried (a b c) (+ a b c)) 1) 2) 3) ; => 6

但这种方法的不便也是显然的：我们必须一次向柯里化函数提供一个参数，想要提供多个参数就会陷入嵌套括号的迷宫之中。虽然可以在定义一个新宏来方便传递参数：

(define-syntax apply-curried
  (syntax-rules ()
    [(_ f x) (f x)]
    [(_ f x . args) (apply-curried (f x) . args)]))

(apply-curried (ez-curried (a b c) (+ a b c)) 1 2 3) ; => 6

It works, 但远非理想。接下来的小节我将给出一个更加合理一致的 curried 接口及其实现。

(maybe) The Right Way

返回柯里化函数的语法形式 (curried <formals> <body>) 应满足

能接受无参数、定参数、可变参数形式。
其返回的柯里化函数应满足
- 当接受的参数无法“填满” <formals> 时，返回被部分求值的柯里化函数:
```
(procedure? ((curried (a b c) (+ a b c)) 1 2)) ; => #t
```
- 当接受的参数超过 <formals> 能匹配的参数时, <body> 会应用匹配上的参数进行评估，同时参数多出的部分会传递给 <body> 的返回结果，e.g,:
```
((curried (a) (curried (b) (curried (c) (+ a b c)))) 1 2 3) ; => 6
```
- 如果接受的参数正好匹配 <formals>, 过程进行和 (lambda <formals> <body>) 一致。

我们先给出一个 curried 实现的雏形：

(define-syntax curried
  (syntax-rules ()
    [(_ () exp ...)
     <<currying-null-list>>]
    [(_ (x x1 ...) exp ...)
     <<currying-proper-list>>]
    [(_ (x x1 ... . rest) exp ...)
     <<currying-improper-list>>]
    [(_ args exp ...) (lambda args exp ...)]))

其中最后一种情况 (curried args <body>) 显然无需柯里化，因为函数可以接受任意多的参数作为合法参数，是故结果直接返回等效的 lambda 表达式。

第一种情况中合法参数为空列表也比较方便讨论。如果柯里化的无参数函数应用于空参数，直接返回 (begin <body>); 如果其应用于非空参数，其只需将提供给它的参数传递给 <body> 运行结果即可。故有：

; currying-null-list
(lambda args
  (if (null? args)
      (begin exp ...)
      (apply (begin exp ...) args)))

接下来我们处理参数列表分别是正规列表与非正规列表的情况。

Proper List

由前讨论可知, (curried (x x1 ...) <body>) 返回一个接受任意项参数的函数：

参数匹配 (x x1 ...) 时，返回 <body> 运行结果；
参数个数大于 (x x1 ...) 长度时，将多余参数传递进 <body>;
参数个数小于 (x x1 ...) 长度时，返回一个新函数，其接受新的参数，将新参数增补到原参数后应用于原先的柯里化函数。特别地，当参数列表为空时，返回柯里化函数自身。

这里函数运行取决于参数模式匹配的情况，很自然地想到用 case-lambda:

; currying-proper-list
(letrec ([rec (case-lambda
                [() rec]
                [(x x1 ...) (begin exp ...)]
                [(x x1 ... . rest) (apply (rec x x1 ...) rest)]
                [fewer-args
                 (let ([waiting-for-more
                        <<waiting-for-more>>])
                   (waiting-for-more rec fewer-args))])])
  rec)

waiting-for-more 接受柯里化函数 rec 和参数列表 fewer-args, 返回前述新函数：

; waiting-for-more
(lambda (rec fewer-args)
  (lambda more-args (apply rec (append fewer-args more-args))))

Improper List

参数为非正规表 (x x1 ... . rest) 时，情况与正规表大致相同，只是如果应用于柯里化函数的参数匹配 (x x1 ...) 后仍有剩余，多余参数不会传递进 <body>, 因为这部分参数总会被 rest 捕捉，因此 case-lambda 少一种匹配模式。

; currying-improper-list
(letrec ([rec (case-lambda
                [() rec]
                [(x x1 ... . rest) (begin exp ...)]
                [fewer-args
                 (let ([waiting-for-more
                        <<waiting-for-more>>])
                   (waiting-for-more rec fewer-args))])])
  rec)

Epilogue

就这样，我们得到了一个接口更友好、泛用性更高的柯里化函数方法。这有什么用？也许能在组合子逻辑的构建中派上用场，不过那是另一个话题了。

另外，我们可以在定义一个新的宏方便我们直接定义命名柯里化函数：

<<implementation-of-curried>>

(define-syntax define-curried
  (syntax-rules ()
    [(_ (f . args) . body) (define f (curried args . body))]))

这次我使用了 DEK 的文学编程方法来编写程序，tangle 输出的代码可在这里查看。

Prev:
Tcl Advocacy