Currying

[ ugh... need to decide what's technically currying and what isn't... and provide a precise definition.]

Above I showed that we can "specialize" a procedure by having it take an argument that specifies an action to take. It is often useful to have a procedure that can create procedures of some general type, producing a specialized procedure each time it's called.

For example, rather than having to specialize mem by hand, we can provide a procedure that automates the process. This procedure make-mem-proc will take a comparison routine as an argument, and return a specialized version of mem that uses that procedure.

(define (make-mem-proc pred?)
   (lambda (target lis)
      (mem pred? target lis)))

Each time this procedure is called, it will bind its argument variable pred?, and create a new procedure that will call mem. Each new procedure will "remember" the binding of pred? that was created for it, so each one can do something different.

Now we can define member, memv, and memq, by using this procedure to create three new procedures, each with its own captured binding of pred?.

(define member (make-mem-proc equal?))
(define memq   (make-mem-proc eq?))
(define memv   (make-mem-proc eqv?))

(Notice that we're using plain variable definition syntax here. We're just defining variables member, memq, and memv, and initializing them with procedures (closures) returned by make-mem-proc.)

Of course, if we only use mem in this way, then we don't actually need separate mem and and make-mem-proc procedures. We can just write make-mem-proc using a lambda expression that's equivalent to mem:

(define (make-mem-proc pred?)
   (letrec ((mem-proc (lambda (thing lis)
                         (if (null? lis)
                             #f
                             (if (pred? (car lis) thing)
                                 lis
                                 (mem-proc pred? thing (cdr lis)))))))
      mem-proc))

Here I've used a letrec so that the procedure will be able to call itself recursively. Each time we call make-mem-proc, it will bind its argument pred?, initializing it with the procedure argument we pass. Then it will bind mem-proc and create the specialized procedure using lambda. Note that the bindings of both pred? and mem-proc will be remembered by the closure created by lambda. This allows the new closure to see both the predicate it should use, and itself, so that it can call itself recursively.

[ A picture would be nice here, showing what we get when we define mem, memq, and memv using make-mem-proc... three variable bindings, holding three closures, each of which is closed in an environment with its own binding of mem-proc scoped inside its own binding of pred?. ] There are two advantages to coding make-mem-proc this way. One is that it avoids cluttering up our code with a definition of mem that's external to make-mem-proc. [ another advantage is that a good compiler will be able to optimize the code better, because it can tell that the value of a bindings of pred? or mem-proc will never change once the binding is created. It may use that information to generate better code... ]

Discussion and Review