Scheme code capsule: currying

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.

About these ads
Posted in Scheme. 9 Comments »

9 Responses to “Scheme code capsule: currying”

  1. eclig Says:

    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.

  2. Phil Says:

    > (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

  3. Chris Says:

    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.

  4. Phil Says:

    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.

  5. Chris Says:

    Thanks a lot for your reply Phil. I’m off to learn something new.

  6. Daniel Martin Says:

    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.

    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.

  7. Auto-Currying vs. Variable-Arity :: I am Richard :: Entries :: Says:

    [...] 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 [...]

  8. The Comonad.Reader » A Robust Currying Macro for Scheme Says:

    [...] 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 [...]

  9. The Comonad.Reader » Curried Scheme Says:

    [...] 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 [...]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 42 other followers

%d bloggers like this: