RE: Pass by reference in LISP

[Steve Strassmann <straz@cambridge.apple.com>]

>cons must be returning a pointer to a list, the problem that I'm having is that
>I'm afraid that a new list is being made up each time I call my "test2" function
>recursively.  I wish there was some low level way I could follow along with LISP
>so I can learn what it is actually doing as I call certain functions.  In my
>real problem the recursion could get VERY deep (and the list VERY long).


CONS does return a pointer to a list: in lisp, practically everything's
a pointer! Unlike C and Pascal, however, Lisp mercifully never makes you 
deal with pointers at the machine level.

If you want to follow along, perhaps you could define a procedure called
MY-CONS, and call it instead of CONS to see where it gets called. MY-CONS
would simply print some debugging info and then call CONS on its arguments.

CONS is an extremely primitive operation. It merely allocates a CONS cell (two
pointers) pointing to its two arguments, and returns it. It will never
copy its arguments!

Here's a much cleaner version with mostly the same behavior as your TEST2 
function for comparison. I assure you it does not create a new copy of alist 
every time it's called.

There's really only three cases to consider, so why not make it a three-way
COND? There's the base case, with N=0, so return ALIST. 
Then there are the cases for odd N or even N, either of which are recursively
defined. I added the improvement of counting down odd numbers by twos,
requiring the base case to account for the fact that you could get -1.

(defun test2 (n alist)
  "Recursively calls itself expanding its list"
  (cond ((<= n 0) alist)
        ((oddp n) (cons n (test2 (- n 2) alist)))
        (t (test2 (- n 1) alist))))

Lessons:
 1) Do not compare numbers with EQL, Use = or tests like zerop instead.
 2) Use COND for n-way conditionals.
 3) You don't need the "declare notinline", certainly not for
    a recursive function.
 4) "it's" is a contraction for "it is", 
    "its" is the possessive of "it"
 5) Don't side-effect a local variable (e.g. alist) when you can
    simply return the correct value. Why is this a good idea?
    Let's look at your code:

>1> (defun test2 (n alist)
>2>    "Recursively calls itself exanding it's list"
>3>     ;(declare (notinline test2))
>4>    (if (eql n 0)
>5>      nil
>6>      (setf alist (test2 (- n 1) alist)))
>7>    (if (oddp n) 
>8>      (cons n alist)
>9>      alist))

You bash the value of ALIST on line 6. How do you know
what ALIST will be like by the time you get to line 8 or 9?
This is why side-effects are as evil as GOTO's: you can't
be sure that the ALIST you got in line 1 is the same one
you use in line 8.