(compose) in Common Lisp

Question

We find this function builder to realize composition in P.Graham's "ANSI Common Lisp" (page 110). The arguments are n>0 quoted function names. I don't understand it completely, so I'll quote the code here and specify my questions underneath it:

(defun compose (&rest fns)
  (destructuring-bind (fn1 . rest) (reverse fns)
    #'(lambda (&rest args)
        (reduce #'(lambda (v f) (funcall f v)) 
                rest
                :initial-value (apply fn1 args)))))

The argument list to compose is reversed and unpacked, its (now first) element bound to 'fn1' and the rest to 'rest'. The body of the outermost lambda is a reduce: (funcall fi (funcall fi-1 ... ) ), with operands in inverted order to restore the initial one.

1) What is the role of the outermost lambda expression? Namely, where does it get its 'args' from? Is it the data structure specified as the first argument of destructuring-bind? 2) Where does the innermost lambda take its two arguments from?

I mean I can appreciate what the code does but still the lexical scope is a bit of a mystery to me. Looking forward to any and all comments! Thanks in advance, //Marco

Answer 1

It's probably easier if you consider first a couple of practical examples:

(defun compose1 (a)
  (lambda (&rest args)
    (apply a args)))

(defun compose2 (a b)
  (lambda (&rest args)
    (funcall a (apply b args))))

(defun compose3 (a b c)
  (lambda (&rest args)
    (funcall a (funcall b (apply c args)))))

So the outermost lambda is the return value: a function that takes any arguments, what it does with it is applying the last function and chaining all the others in reverse order on the result got from last function.

Note: compose1 could be defined more simply as (defun compose1 (a) a).

A somewhat equivalent but less efficient version could be

(defun compose (&rest functions)
  (if (= (length functions) 1)
      (car functions)
      (lambda (&rest args)
        (funcall (first functions)
                 (apply (apply #'compose (rest functions))
                        args)))))

Answer 2

1) The outermost lambda creates a closure for you, because the result of (combine ...) is a function that calulates the composition of other functions.

2) The innermost lambda gets ists argument from the function reduce. Reduce takes a function (the innermost lambda) of two arguments and applies it stepwise to a list, e.g.

 (reduce #'- '(1 2 3 4))  is   (- (- (- 1 2) 3) 4)