How does this code behave (function composition in funcall)

Question

I have the following function in lisp:

(defun F(F)
  #'(lambda (n)
      (if (zerop n)
         (funcall F n)
         (1+ (funcall (F F) (1- n))))))

How does this code behaves if I call:

(funcall (F #'(lambda (x) (+ 2 x))) 2)

I dont understand why the output is 4.

Thanks in advance

Please have some patience. People often take a few hours to respond, especially if the tag isn't [c#] or [java]. ;-) — Chris Jester-Young, Oct 28 '14 at 19:37
Just a question, can I expand the line (1+ (funcall (F F) (1- n))) like this: (1+ (funcall (F (+ 2 x)) (1- n))). Is this like a composition of functions? — Luis Alves, Oct 28 '14 at 19:48
also, i noticed that the argument and the function have the same name does this hava any implication? — Luis Alves, Oct 28 '14 at 19:49
You might want to read up on [multiple namespaces in Common Lisp](http://stackoverflow.com/questions/3328512/why-multiple-namespaces). — uselpa, Oct 28 '14 at 19:53

score 3 · Accepted Answer · answered Oct 28 '14 at 20:12

3

Since we know the argument, we can simplify the if statement in the function:

(funcall (F #'(lambda (x) (+ 2 x))) 2)
(1+ (funcall (F #'(lambda (x) (+ 2 x))) 1))
(1+ (1+ (funcall #'(lambda (x) (+ 2 x)) 0)))
(1+ (1+ 2))
4

The first 2 transformations replace (if false A B) with B, while the 3rd replaces (if true A B) with A.

answered Oct 28 '14 at 20:12

sds

so, in the line (1+ (funcall (F F) (1- n)))))), in funcall (F F) he is calling himself again and not the argument. Right? – Luis Alves Oct 28 '14 at 20:23
@LuisAlves: both :-) it's calling itself on its argument – sds Oct 28 '14 at 20:24
Can you explain me how does he knows the first F corresponds to the funtion itself and not to the argument? – Luis Alves Oct 28 '14 at 20:28
I found out it's because in LISP if in a compound form the first element (the car) is a symbol, then it must be evaluated as a funtion. If the first element it's not a symbol than it must be a lambda expression. Thanks. Also I add this link with a better explanation http://cl-cookbook.sourceforge.net/functions.html – Luis Alves Oct 28 '14 at 20:43

score 3 · Answer 2 · answered Oct 28 '14 at 20:23

First, untangle the two F:

(defun foo (fun)
  #'(lambda (n)
      (if (zerop n)
          (funcall fun n)
          (1+ (funcall (foo fun) (1- n))))))

Now, you call:

(funcall (foo #'(lambda (x) (+ 2 x))) 2)

We can give the inner lambda a name, I'll call it add-2.

(funcall (foo #'add-2) 2)

(Foo #'add-2) then returns the function

(lambda (n)
  (if (zerop n)
      (funcall #'add-2 n) ; n is always 0 here
      (1+ (funcall (foo #'add-2) (1- n)))))

This gets called with 2, which is not zerop, so it is:

(1+ (funcall (foo #'add-2) 1))

We already know what (foo #'add-2) returns, and it gets called with 1 now, which still is not zerop:

(1+ (1+ (funcall (foo #'add-2) 0)))

Now the argument is 0, so we get to the base case:

(1+ (1+ (funcall #'add-2 0)))

We now can see that foo creates a function that adds n to the result of calling (fun 0).

2 Answers2