One of the few things i miss when programming in Scheme is ML-style function currying. ML, Haskell and OCaml come with this handy feature that allows you to obtain new functions from a given one by calling it with an ‘incomplete’ number of arguments.
Fortunately, we have macros in our programmable programming language, and actually there’re lots of them floating around providing implementations of currying in Lisp. But today, Piet Delport posted (during a discussion in #scheme) the nicest currying macro i’ve seen so far:
(define-syntax curried
(syntax-rules ()
((curried () body ...) (lambda () body ...))
((curried (arg) body ...) (lambda (arg) body ...))
((curried (arg args ...) body ...)
(lambda (arg . rest)
(let ((next (curried (args ...) body ...)))
(if (null? rest)
next
(apply next rest)))))))
(define-syntax define-curried
(syntax-rules ()
((define-curried (name args ...) body ...)
(define name (curried (args ...) body ...)))))
;;;; Sample usage:
(define-curried (foo x y z) (+ x (/ y z))) ;; foo has arity 3
((foo 3) 1 2) ;; (foo 3) is a procedure with arity 2
((foo 3 1) 2) ;; (foo 3 2) is a procedure with arity 1
This code shows the elegance and power of hygienic syntax-rules macros, which allow you to extend the language seamlessly, incorporating new features as if they were native. It also makes for a pretty instructive demonstration of how to take advantage of higher-order functions and recursion, nicely combined. All that in just a few lines!
If you’re new to Scheme and want to learn more about similar magic, be sure to read JRM’s syntax-rules Primer for the Merely Eccentric. You’ll have a great time.
February 4, 2007 at 12:58 pm
currying works fine with languages in the ML family because
functions there take a single argument. This “single argument” might, of course, be a tuple. This works transparently to the user because of pattern matching, so that it *looks* like you’re calling a function with multiple arguments.
Scheme, on the other hand, has functions with multiple arguments and multiple arity. And these don’t match with currying.
February 5, 2007 at 3:17 pm
> (define (curry func . curry-args)
(lambda args
(apply func (append curry-args args))))
> ((curry + 1) 2)
3
> ((curry + 1 2) 3)
6
> ((curry + 1 2) 3 4)
10
February 5, 2007 at 6:32 pm
Phil,
I guess I have been missing something, but your code above strikes me as brilliant. I don’t completely understand it and I very much want to. What is the significance of the dotted pair in the function definition? and lambda’s “arg” not being enclosed in parenthases? Can you point me toward a tutorial or something? I have PLT. Thanks.
February 5, 2007 at 9:42 pm
Follow the trail PLT -> Help -> Software: Manuals -> R5RS -> Contents -> 4.1.4 Procedures for a description of the various forms of lambda. Briefly, both curry-args and args collect the function arguments in a list. The curry function takes a function and a list of arguments and returns a new function that saves the original function and the given arguments. The returned function then takes the additional arguments, appends them to the arguments given to the curried function, and applies the original function to the entire list of arguments.
February 5, 2007 at 9:57 pm
Thanks a lot for your reply Phil. I’m off to learn something new.
February 21, 2007 at 3:18 pm
Not quite. When you make a call that looks like you’re calling a function with multiple arguments in, e.g., Haskell, what’s going on with the idea that a function should take multiple arguments is that the function returns another function. That is:
myFunc 3 4
Is equivalent to the scheme code:
((myFunc 3) 4)
And automatic currying works properly only in the presence of a defined, definite arity. So currying can’t work automatically with arbitrary scheme functions, but the given define-syntax forms let currying work automatically and reasonably efficiently with function definitions that take a fixed number of parameters. With the above definitions, I can still run this:
(repeat 100000
((foo 3) 1 2)
((foo 3 1) 2)
(((foo 3) 1) 2) )
on a rather slow machine (500Mhz K6) in ~7.1 seconds. (under “bigloo -i”)
As Phil shows, manual currying can be done quite easily in scheme, without even a need to get into define-syntax.
September 24, 2008 at 5:44 am
[...] anyway for the toy cases like the + function. If your language has macros, then you can do like some people have done and make macros that allow you to auto-curry individual [...]
August 29, 2009 at 4:42 pm
[...] found a very elegant macro by Piet Delport that handles partial application, but that doesn't deal with the partial application of no arguments or that I'd like to also be [...]
August 29, 2009 at 4:45 pm
[...] found a very elegant macro by Piet Delport that handles partial application, but that doesn't deal with the partial application of no arguments or that I'd like to also be [...]