help understanding a simple function

This function is from the beginning of Barski's Land of Lisp.

1.  (defun my-length (list)
2.     (if list
3.          (1+ (my-length (cdr list)))
4.           0))

> (my-length '(list with four objects))
4

I don't think I understand how it works. Could someone kindly correct me.

1. We're defining the function 'my-length' which takes one argument 'list'
2. If the argument exists and is not empty, eg () or nil
3. do the following:
Pass '(with four objects) to the function my-length. It's recursive so then it'll pass '(four objects) to my-length until the list is empty.
What I don't understand here is "(1+" I thought that (1+ n) = (+ n 1). If that's correct, the recursive function adds:
'(list with four objects) + 1
'(with four objects) + 1
'(four objects) + 1
'(objects) + 1
Which doesn't make sense to me. How can you add strings and numbers? I can see that that's probably not the case. That each iteration 1 gets added to make the total of 4 (number of elements) but according to the code it seems to me that it gets added to the list of strings?!

Could you please explain how it really works? Thank you for your time and patience.

it's working like this:

(my-length '(list with four objects))
(1+ (my-length '(with four objects)))
(1+ (1+ (my-length '(four objects))))
(1+ (1+ (1+ (my-length '(objects)))))
(1+ (1+ (1+ (1+ (my-length '())))))
(1+ (1+ (1+ (1+ 0))))

p.s. you can (trace my-length) to see something like this

Thanks a lot. It seems somewhat clearer to me.
I still can't understand a few things:

That's the output of tracing the function:

1. Trace: (MY-LENGTH '(LIST WITH FOUR SYMBOLS))                                                           
2. Trace: (MY-LENGTH '(WITH FOUR SYMBOLS))                                                                
3. Trace: (MY-LENGTH '(FOUR SYMBOLS))                                                                     
4. Trace: (MY-LENGTH '(SYMBOLS))                                                                          
5. Trace: (MY-LENGTH 'NIL)                                                                                
5. Trace: MY-LENGTH ==> 0                                                                                 
4. Trace: MY-LENGTH ==> 1                                                                                 
3. Trace: MY-LENGTH ==> 2                                                                                 
2. Trace: MY-LENGTH ==> 3                                                                                 
1. Trace: MY-LENGTH ==> 4  

I still have a problem understanding why it doesn't spit out any errors before the last stage ((1+ (1+ (1+ (1+ 0))))
Before it reaches the last iteration, it seems to be adding numbers and strings (at least that's how I see it)
I know that when it adds, it never reaches the members of the list because first it will call the function recursively.
I understand it is something similar to:

(1+ (cdr (cdr `(john bill ,1))))  

which, by the way, doesn't work as I don't know how to switch to the code mode before 1. It can't add a number and a non-number element. That's logical and it ignores john and bill before it tries to return anything.

So coming back to the original question: why doesn't it give errors in the my-length function? My attempt of explaining it would be that it doesn't return anything until the final iteration, but
that would probably be wrong because it does return numbers like 2 and 3 before the last call of the function.

Really sorry for lame questions:)
Thank you.

sycamorex wrote:I still have a problem understanding why it doesn't spit out any errors before the last stage ((1+ (1+ (1+ (1+ 0))))
Before it reaches the last iteration, it seems to be adding numbers and strings (at least that's how I see it)

It's not adding numbers and strings. When it calls (1+ (my-length '(with four symbols))), it's adding 1 to whatever (my-length '(with four symbols)) returns. That's not a string, it's a number. It calls (my-length '(four symbols)), which calls (my-length '(symbols)), which calls (my-length '()), which returns 0, so (1+ (my-length '()) == (1+ 0) == 1 is the length of (objects). And (1+ (my-length '(symbols)) == (1+ 1) == 2 is the length of (four symbols), and so on back up the call stack.

(There are no strings involved, anyway: '(list with four symbols) is—as it says—a list of symbols, not strings!)

Paul wrote: It's not adding numbers and strings. When it calls (1+ (my-length '(with four symbols))), it's adding 1 to whatever (my-length '(with four symbols)) returns. That's not a string, it's a number. It calls (my-length '(four symbols)), which calls (my-length '(symbols)), which calls (my-length '()), which returns 0, so (1+ (my-length '()) == (1+ 0) == 1 is the length of (objects). And (1+ (my-length '(symbols)) == (1+ 1) == 2 is the length of (four symbols), and so on back up the call stack.

(There are no strings involved, anyway: '(list with four symbols) is—as it says—a list of symbols, not strings!)

Thank you. It's getting clearer and clearer, although I can't say I understand it 100%. I'm

Could anyone kindly provide another simple example illustrating the use of recursion (and/or the (1+...) construct)?

Thank you for your patience.

Well, how about a function adding 1 to each element of a list (assuming it contains only numbers):

(defun add-1 (lst)
    (if lst
        (cons (1+ (car lst)) (add-1 (cdr lst)))
        nil))

The key point that helped me understand recursion is not to try to follow the recursion.
If you recur on a list, you (well, basically) only have two cases to look at:
- The list you get is empty
If it is, you simply return the 'neutral' or final element to the operation you want to perform: In your first example,
you wanted to sum up numbers, so you pass zero in the end. Here we construct a list from the elements,
so we pass nil at last.
- The list is not empty
Then you perform the operation you want to perform using the value of the application
of your function to the 'cdr of the list. That can get as complicated as you like.
Here, we want to construct a list, so the operation is 'cons. (By the way we use '1+ to add 1 to the current car of the list.)

Try to write a function sum that sums all elements in a list!

Thank you for your post.

Philipp wrote: The key point that helped me understand recursion is not to try to follow the recursion.

Is it possible? LOL. I involuntarily do it which leads me to madness.

Philipp wrote: Try to write a function sum that sums all elements in a list!

I think it should be as follows:

(defun sum-of-numbers (lst)                                                                                 
  (if lst                                                                                     
      (+ (car lst) (sum-of-numbers (cdr lst)))                                               
      0))  

If hope the sum function above is ok.

Would it be too much if I asked you to give me a couple of tasks that would test my understanding of recursion?
I thought it'd be better if you guys set a task for me, because as I am a LISP newbie, unknowingly I might come up with some tasks that may
require deeper knowledge of LISP and would be to complex for me to implement.


Again, thank you for your time and patience.

If hope the sum function above is ok.

Very good!

It can be hard to wrap one's mind around some recursive functions,
and since you're learning from Barski (like I did and do) you'll want to have
a feel for it when it comes to 'dice of doom'
If you can afford it and like to improve yourself one little task after another, I'ld highly recomend
the 'little schemer'-book (and it's follower). Despite it's name, you can go through it with CL equally well.

Anyway and though I don't know anything about your general knowledge of CL, here are some tasks for you!

Find the position of an element in a list (you'll want to look at labels for this)!

(defun pos (elt lst) ...)
> (pos 3 '(0 1 2 3 4)) => 3

Reverse a list (look at append)

(defun rev (lst) ...)
> (rev '(1 2 3 4)) => (4 3 2 1)

Rewrite sum, so that it calculates the sum of *all* numbers (including sublists)

(defun sum2 (tree) ...)
> (sum2 '(1 2 (3 (4 5 (6)) 7) 8 9)) => 45

get-till returns the first elements of a list, from element 0 till element 'el':
(Look at nreverse and labels)

(defun get-till (el lst) ...)
> (get-till 4 '(1 2 3 4 5 6)) => (1 2 3)

You know numberp?
Check if a list contains only numbers (assume it's not empty).

(defun numbersp (lst) ...)
> (numbersp '(1 2 a)) => nil

Extract the numbers!

(defun numbers (lst) ...)
> (numbers '(1 2 a b 3 c 4 1)) => (1 2 3 4 1)

Again, thank you for your time and patience.

You're welcome!

Excellent. Thank you. I do appreciate it.
Just one question. Do I need to use recursion in each of the tasks?

In general, you can write an iterative algorithm to substitute a recursive and vice versa.
It's up to you...
But if you want to learn about recursion the answer is 'yes, you need to!'

hmm, I must say it's not easy for me. Let's start with:

Check if a list contains only numbers (assume it's not empty).

First I wrote the following:

CL-USER> (defun numbersp (lst)                                                                            
           (cond                                                                                          
             ((numberp (car lst)) 'car-is-a-number)                                                       
             (nil)))                                                                                      
NUMBERSP                                                                                                  
CL-USER> (numbersp '(1 2 3))                                                                              
CAR-IS-A-NUMBER                                                                                           
CL-USER> (numbersp '(a 2 3))                                                                              
NIL      

So I thought that I'll add recursion by:

CL-USER> (defun numb (lst)                                                                                
           (cond                                                                                          
             ((numberp (car lst)) (numb (cdr lst)))                                                       
             (nil)))     

But here it returns NIL in all cases:(

/me confused

Ok, you're on the right way, but:

First, think about the cases you need to express.
Though we defined the incoming list to be not nil, we'll find nil once we looked at each element (and found only numbers).
We want to use the two basic cases when working with lists:
If the car is nil, return ...
Else:
If the car is a number, return ...
Else, return ...

You can express this with a cond-form to avoid nested if's, as you tried, but then you should look at the rules of the cond-form again.
(Look here http://www.lispworks.com/documentation/ ... m_cond.htm, here http://www.cs.cmu.edu/Groups/AI/html/cl ... 0000000000 or in LoL).
cond returns nil by default if none of the test-forms evaluates to T.

Thanks a lot. The moment I read your post I realised my mistake. Of course, once the list is empty, it evaluates to NIL.

(defun numbersp (lst)                                                                            
           (cond                                                                                          
             ((null lst) T)                                                                               
             ((numberp (car lst)) (numbersp (cdr lst)))))  

It seems to work fine. Is that correct?

Time to look at another of the tasks.

Nearly. The current function returns T for an empty list, but an empty list obviously does not consist of only numbers, as it consists of nothing at all. So you need to handle the case of the function being called initially on an empty list as well.

For simlicity, the task was defined to work with not-empty lists only. So very good!

By the way, though cond returns nil by default, I think it's convention to always state the 'fall-through'-case in cond, like so:

(defun numbersp (lst)                                                                            
           (cond                                                                                          
             ((null lst) T)                                                                               
             ((numberp (car lst)) (numbersp (cdr lst)))
             (t nil)))

This way it's clear that you didn't just forgot a case.

Philipp wrote:For simlicity, the task was defined to work with not-empty lists only. So very good!

By the way, though cond returns nil by default, I think it's convention to always state the 'fall-through'-case in cond, like so:

(defun numbersp (lst)                                                                            
           (cond                                                                                          
             ((null lst) T)                                                                               
             ((numberp (car lst)) (numbersp (cdr lst)))
             (t nil)))

This way it's clear that you didn't just forgot a case.

Thanks a lot, both of you.
I think I need to pick you brains about the following. Just to make sure. I don't want to skip this bit. Is my understanding correct?
We have got three conditions here:
1. ((null lst) T) - After we've gone through the list, the list is empty. If the list is empty, return T, otherwise the numbersp function returns NIL in all cases (even if the list contains only numbers)
2. ((numberp (car lst)) (numbersp (cdr lst)))) - If (car lst) is a number, call the numbersp function feeding it (cdr lst) to recursively go through other elements.
3. (t nil))) - If neither 1 nor 2 is true (ie. an element of the list is not a number) return NIL. As it was mentioned above, cond returns nil (if none of the conditions have been met) by default, so we added it only as good practice.

I think slowly but steadily I'm getting there. Thank you for your help.

Ok, I think I got another one. The problem is that it is NOT done recursively - I've got a sneaking suspicion that's not the way it's meant to be solved.

Philipp wrote: Extract the numbers!

(defun numbers (lst) ...)
> (numbers '(1 2 a b 3 c 4 1)) => (1 2 3 4 1)

(defun numbers (lst)                                                                             
           (labels ((is-number (elt)                                                                      
                    (numberp elt)))                                                                       
             (delete-if-not #'is-number lst)))  

I modified the "objects-at" function from the Land of Lisp.

The last stab at trying to do it in a purely recursive way was like that:

 (defun numbers (lst)                                                                             
           (setq new-lst '())                                                                             
           (cond                                                                                          
             ((numberp (car lst)) (cons (car lst) new-lst) (numbers (cdr lst)))                           
             ((null lst) new-lst)                                                                         
             (t (numbers (cdr lst)))))           

Obviously, it doesn't work. My understanding was:
1. Create a new list (new-lst)
2. If (car lst) is a number:
a) Add (car lst) to new-lst
b) and call numbers (cdr lst)
3. If I've gone over the whole list (ie null lst)), return the new-lst list.
4. If it's true but didn't meet condition 2 and 3, call numbers (cdr lst)

Where am I wrong? Is my logic wrong or just my implementation of it?
Thanks

Well, for one, assuming that new-lst is a variable defined outside of the function, you're setting it to '() every time you call the function, so you never actually build a full list. the second problem is that you're using cons. Cons is a non-destructive function, meaning that (cons (car lst) new-lst) won't actually alter new-lst, but instead produce a new list, which is immediately discarded. There are 2 ways to get the effect you want. You either use push or (setq new-lst (cons (car lst) new-lst), both of which essentially do the same. If you do this you'll also note that you're building the list in reverse, so you'll have to use reverse (or it's destructive brother nreverse) to get it back in the right order. Note that these also do not alter new-lst, but return a new list that is a reversed variant of new-lst.

Now, to solve the first problem, you either need to make it so that new-lst is shared between the different instances of numbers (a so-called closure, closing over an external value) using

(let ((new-lst (list)))
    (defun numbers (lst) ...)

but that has the problem that you need to null the list by hand (or using a wrapper function) every time you call numbers. A better way would be to use labels to define a recursive function local to numbers and use that for recursion:

(defun numbers (lst)
    (let ((new-lst (list)))
        (labels ((list-walker (list) ....))
            (list-walker lst)
            (nreverse new-lst)) ;assuming you're using push or cons to build your list you need to reverse it when you're done

However, while using a closure is a good idea in this case, it misses a central point of recursion and that is how to handle return values. We could modify your specification as following:
1.) If the car of our list is a number, make a list of all numbers in the remaining list and cons them together.
2.) else, if there are still elements in the list beyond this one, return all numbers in that list
3.) else, return nil.

This takes advantage of the fact that consing to nil will result in a fresh list consisting of 1 element, the thing you consed to nil. I'll let you figure out the resulting definition yourself.

On a side note, don't use setq to introduce new variables, it's not common lisp compliant. To see what exactly happens if I run your function I would have to track down an implementation that does support this idiom instead of using the one I usually use. Used defvar to introduce globally-bound, special* variables or let to introduce local, lexical* variables.

*The difference between lexical and special is best illustrated with an example:

(defvar *a* 3) ;*a* is now defined as special

(defun test-a () *a*)

(test-a) ;This yields 3

(let ((*a* 5)) ;Even though we use let, *a* was already special and will not become lexical
    (test-a) ;Because *a* is special, we can shadow it at run-time with let, and the effect will propagate to functions defined earlier

(let ((b 4)) ;b is now lexical
    (defun test-b () b)) ;Since b is lexical, it's value will be locked in when we compile this function

(test-b) ;this yields 4

(let ((b 6))
    (test-b)  ;this also yields 4, because due to b's lexical nature, we cannot shadow it any more.

In essence, special variables behave like global variables in other languages, while lexical variables behave like local variables. This isn't perfectly correct of course, defining 2 functions that refer to the same lexical variable and you have a "local" variable that isn't local to either function, but it helps to think like that. Also if you really need to, you can use (declare (special variable)) directly after a let-form's variable definition to tell the compiler that variable is special, which allows shadowing, but prevents outside access since there is no global symbol associated with the variable, so you have a special local variable then.

sycamorex wrote:

(defun numbers (lst)                                                                             
           (labels ((is-number (elt)                                                                      
                    (numberp elt)))                                                                       
             (delete-if-not #'is-number lst)))  

Just do (delete-if-not #'numberp lst) -- is-number serves no purpose here. (But please name your argument "list" rather than "lst")

virex wrote:Also if you really need to, you can use (declare (special variable)) directly after a let-form's variable definition to tell the compiler that variable is special, which allows shadowing, but prevents outside access since there is no global symbol associated with the variable, so you have a special local variable then.

If you declare a variable special, it's accessible from any other function that uses that symbol name for a variable in a context where it's special. I.e., the symbol used to name it is a "global symbol associated with the variable."

Paul wrote:

virex wrote:Also if you really need to, you can use (declare (special variable)) directly after a let-form's variable definition to tell the compiler that variable is special, which allows shadowing, but prevents outside access since there is no global symbol associated with the variable, so you have a special local variable then.

If you declare a variable special, it's accessible from any other function that uses that symbol name for a variable in a context where it's special. I.e., the symbol used to name it is a "global symbol associated with the variable."

Oh thanks. I should realy have tested that

...

(defun numbers (lst)                                                                             
           (setq new-lst '())                                                                             
           (cond                                                                                          
             ((numberp (car lst)) (cons (car lst) new-lst) (numbers (cdr lst)))                           
             ((null lst) new-lst)                                                                         
             (t (numbers (cdr lst)))))

Actually, to solve the task recursively, I'ld propose a solution quite similar to your attempt above.
You just don't need this new-lst variable.
That is, if you do (cons 1 ()) you get a new list, so there is no need to establish an explicit binding in numbers...
Just cons each number on the value of the recursive application until you reach nil. Then return nil. So the call tree would evaluate to sth. like this:

(numbers '(1 2 a b 3 4)) => (cons 1 (cons 2 (cons 3 (cons 4 nil))))

I thought I'd post a quick update.

Once again, thank you everyone for the help so far. I haven't posted anything in a while. I haven't forgotten about this thread:)
The only reason for that is that I've got a very busy period at work and have to bring a lot of paperwork home so don't really
have time for lisp. I think I'll have more time in a week or so and will be able to come back to this thread.


See you soon.