Recursive function using Apply

[kevy1210]

Hello All,

I am new to the boards, and I was looking for help on specific function I can't seem to understand. In Paul Graham's book On Lisp he defines a function called fint (for function intersection) like this:

(defun fint (fn &rest fns)
(if (null fns)
fn
(let ((chain (apply #'fint fns))
#'(lambda (x) (and (funcall fn x) (funcall chain x)))))

The function is supposed to allow us to return a single function that does the same thing as
(lambda (x) (and (fn1 x) (fn2 x) (fn 3)...)).

I was wondering if any one could help me reason out how the function actually works. Up to this point in using lisp i have never seen a recursive call using apply. If you need me to clarify anything please let me know. Any help is greatly appreciated.

[edgar-rft]

Here is a readable version with all parentheses where they belong:

Code: Select all

(defun fint (fn &rest fns)
  (if (null fns)
      fn
      (let ((chain (apply #'fint fns)))
        #'(lambda (x) (and (funcall fn x) (funcall chain x))))))

Above the text box where you type the forum posts there are some buttons to click on, one of them is called "Code". If you mark your Lisp code with the mouse and then click on the "Code" button there appear two [code] and [/code] tags at the beginning and the end of the marked text. If you click the "Preview" Button below the text box you can see that everything inside the [code] and [/code] will look like the fixed-width code above. More information about BBCode tags for text formatting can be found in the BBCode Guide here in the forum.

The key to understand the function is that there is one required argument FN and a undefined number of &rest arguments, collected in a list bound to the symbol FNS. It's important to notice that APPLY calls #'fint only on the &rest arguments in FNS, but not on the first argument FN. This means that FN behaves like the CAR or FIRST argument of a list, and FNS behaves like the CDR or REST of a list.

Here is what I do when I try to understand what's going on in such a function.

First I add some code that prints all interesting values to the screen:

Code: Select all

(defun fint (fn &rest fns)
  (if (null fns)
      (progn (format t "----------------------------------------------~%")
             (format t "The function was called with the arguments:~%")
             (format t "(fint ~a~{ ~a~})~%" fn fns)
             (format t "fn  = ~a~%" fn)
             (format t "fns = ~a~%" fns)
             (format t "Return the fn argument:~%")
             (format t "~a ; value of fn~%" fn)
             fn)  ; return the FN argument
      (let ((chain (apply #'fint fns)))
        (format t "----------------------------------------------~%")
        (format t "The function was called with the arguments:~%")
        (format t "(fint ~a~{ ~a~})~%" fn fns)
        (format t "fn  = ~a~%" fn)
        (format t "fns = ~a~%" fns)
        (format t "Compute the chain variable:~%")
        (format t "(apply #'fint ~a)~%" fns)
        (format t "chain = ~a~%" chain)
        (format t "Return the lambda form:~%")
        (format t "(lambda (x)~%")
        (format t "  (and (funcall ~a x) ; fn~%" fn)
        (format t "       (funcall ~a x))) ; chain~%" chain)
        ;; retun the lambda form
        #'(lambda (x) (and (funcall fn x) (funcall chain x))))))

Then I test the function using builtin Common Lisp predicate functions as arguments, so I do not need to define anything extra:

Code: Select all

CL-USER> (fint #'symbolp #'numberp #'stringp)
----------------------------------------------
The function was called with the arguments:
(fint #<FUNCTION STRINGP>)
fn  = #<FUNCTION STRINGP>
fns = NIL
Return the fn argument:
#<FUNCTION STRINGP> ; value of fn
----------------------------------------------
The function was called with the arguments:
(fint #<FUNCTION NUMBERP> #<FUNCTION STRINGP>)
fn  = #<FUNCTION NUMBERP>
fns = (#<FUNCTION STRINGP>)
Compute the chain variable:
(apply #'fint (#<FUNCTION STRINGP>))
chain = #<FUNCTION STRINGP>
Return the lambda form:
(lambda (x)
  (and (funcall #<FUNCTION NUMBERP> x) ; fn
       (funcall #<FUNCTION STRINGP> x))) ; chain
----------------------------------------------
The function was called with the arguments:
(fint #<FUNCTION SYMBOLP> #<FUNCTION NUMBERP> #<FUNCTION STRINGP>)
fn  = #<FUNCTION SYMBOLP>
fns = (#<FUNCTION NUMBERP> #<FUNCTION STRINGP>)
Compute the chain variable:
(apply #'fint (#<FUNCTION NUMBERP> #<FUNCTION STRINGP>))
chain = #<CLOSURE (LAMBDA (X) :IN FINT) {10049134EB}>
Return the lambda form:
(lambda (x)
  (and (funcall #<FUNCTION SYMBOLP> x) ; fn
       (funcall #<CLOSURE (LAMBDA (X) :IN FINT) {10049134EB}> x))) ; chain
#<CLOSURE (LAMBDA (X) :IN FINT) {100491923B}>

Because it's a recursive function the first set of printed values is from the innermost call:

Code: Select all

The function was called with the arguments:
(fint #<FUNCTION STRINGP>)
fn  = #<FUNCTION STRINGP>
fns = NIL
Return the fn argument:
#<FUNCTION STRINGP> ; value of fn

In the second-innermost call you can see that the value #<FUNCTION STRINGP> gets assigned to the chain variable and then inserted into the returned lambda form:

Code: Select all

The function was called with the arguments:
(fint #<FUNCTION NUMBERP> #<FUNCTION STRINGP>)
fn  = #<FUNCTION NUMBERP>
fns = (#<FUNCTION STRINGP>)
Compute the chain variable:
(apply #'fint (#<FUNCTION STRINGP>))
chain = #<FUNCTION STRINGP>
Return the lambda form:
(lambda (x)
  (and (funcall #<FUNCTION NUMBERP> x) ; fn
       (funcall #<FUNCTION STRINGP> x))) ; chain

In the third and outermost call there suddenly appears a strange value:

Code: Select all

#<CLOSURE (LAMBDA (X) :IN FINT) {10049134EB}>

That's because SBCL has compiled the lamda form returned by the second-innermost call above into a closure object:

Code: Select all

The function was called with the arguments:
(fint #<FUNCTION SYMBOLP> #<FUNCTION NUMBERP> #<FUNCTION STRINGP>)
fn  = #<FUNCTION SYMBOLP>
fns = (#<FUNCTION NUMBERP> #<FUNCTION STRINGP>)
Compute the chain variable:
(apply #'fint (#<FUNCTION NUMBERP> #<FUNCTION STRINGP>))
chain = #<CLOSURE (LAMBDA (X) :IN FINT) {10049134EB}>
Return the lambda form:
(lambda (x)
  (and (funcall #<FUNCTION SYMBOLP> x) ; fn
       (funcall #<CLOSURE (LAMBDA (X) :IN FINT) {10049134EB}> x)))

All you need to do is to replace the #<CLOSURE...> object with the printed lambda form of the second-innermost call above to see what's happening:

Code: Select all

The function was called with the arguments:
(fint #<FUNCTION SYMBOLP> #<FUNCTION NUMBERP> #<FUNCTION STRINGP>)
fn  = #<FUNCTION SYMBOLP>
fns = (#<FUNCTION NUMBERP> #<FUNCTION STRINGP>)
Compute the chain variable:
(apply #'fint (#<FUNCTION NUMBERP> #<FUNCTION STRINGP>))
chain = (lambda (x)
          (and (funcall #<FUNCTION NUMBERP> x)
               (funcall #<FUNCTION STRINGP> x)))
Return the lambda form:
(lambda (x)
  (and (funcall #<FUNCTION SYMBOLP> x) ; fn
       (funcall (lambda (x)
                  (and (funcall #<FUNCTION NUMBERP> x)
                       (funcall #<FUNCTION STRINGP> x))) ; chain
                x)))

The lambda form from the second-innermost call first gets assigned to the chain variable and then inserted into the returned lambda form, so the returned lambda form effectively becomes a nested lambda form. With more than three arguments the nesting gets deeper and deeper.

With four arguments the returned lambda form would look like this:

Code: Select all

(fint #'fn-1 #'fn-2 #'fn-3 #'fn-4)
  => (lambda (x)
       (and (funcall #<FUNCTION FN-1> x)
            (funcall (lambda (x)
                       (and (funcall #<FUNCTION FN-2> x)
                            (funcall (lambda (x)
                                       (and (funcall #<FUNCTION FN-3> x)
                                            (funcall #<FUNCTION FN-4> x)))
                                     x)))
                     x)))

And so on...

[kevy1210]

Dear edgar-rft,

Thank you very much for responding to my post. Your explanation is fantastic. I can't thank you enough for taking the time to help a newbie like myself out, I really do appreciate it.

Also, I will make sure to use the code formatting option next time