Dear Gentle Persons,
I am unable to make sense of when a recursive algorithm has side effects
at the original calling level. Given the following:
(setf x1 '( a b c d e f)
y1 '(h i j k l m o)
x2 '((1 2 3) 4 5 6)
y2 '((7 8 9) 10 11 12))
(defun my_copy ( c1 p1 c2 p2)
(setf (first c1) (first p1)) ;; E1
(setf c2 (append (rest p2) (first p2)) ; E2
(if (not (equal c1 p1))
(return-from my_copy (my_copy (rest c1) (rest p1) c2 p2)
(return-from my_copy T))
)
What determines if x1 etc. are changed. I have a different program that
the only difference I can see is that in one case the setf is like E1 and
the
the other its like E2. In the E1 case the top level is changed, and the
other
it is not.
I would be thankfull for any help.
Muddy
rposey <············@worldnet.att.net> wrote in message
··················@flash.seas.smu.edu...
> Dear Gentle Persons,
>
> I am unable to make sense of when a recursive algorithm has side effects
> at the original calling level. Given the following:
>
>
> (setf x1 '( a b c d e f)
> y1 '(h i j k l m o)
> x2 '((1 2 3) 4 5 6)
> y2 '((7 8 9) 10 11 12))
>
> (defun my_copy ( c1 p1 c2 p2)
> (setf (first c1) (first p1)) ;; E1
> (setf c2 (append (rest p2) (first p2)) ; E2
>
> (if (not (equal c1 p1))
> (return-from my_copy (my_copy (rest c1) (rest p1) c2 p2)
> (return-from my_copy T))
>
> )
>
>
> What determines if x1 etc. are changed. I have a different program that
> the only difference I can see is that in one case the setf is like E1 and
> the
> the other its like E2. In the E1 case the top level is changed, and the
> other
> it is not.
Lisp is a call-by-value language, so a function cannot change the value
of any variable that isn't lexically visible. (The fact that x1 is a global
variables is unimportant). So calling my_copy on x1 will not change the
value of x1.
But, you say, X1 is different after I call my_copy! Well, you have to look
closely at what is going on. Conceptually, X1 is a list of six elements,
but
X1 is implemented as a container with two slots (a CONS cell) with an 'a
in the first and a pointer to another container in the second.
When you call my_copy on x1, you are passing that container to my_copy,
which (in line E1), modifies the first slot in that container. Since X1
still
points to that container, it sees the modification. But X1 itself is not
modified it is still pointing to that same container.
In line E2, you are not modifying a container, you are modifying a variable
to
have a different value.
Just to reiterate, in neither case is the top level changed (in this code),
just the shared structure that the top level refers to.
> I would be thankfull for any help.
Even from Erik?
~jrm
Joe Marshall wrote:
>
> rposey <············@worldnet.att.net> wrote in message
>
> Lisp is a call-by-value language, so a function cannot change the value
> of any variable that isn't lexically visible. (The fact that x1 is a global
> variables is unimportant). So calling my_copy on x1 will not change the
> value of x1.
The strangest thing is it reacts differently for different (setf ) actions
in the recursive routine. The only different I can see in my actual case is
that one (setf (first x) (first y)) and it changes the value of the list
that is not name x, at the level of the original call. The other does
this (setf x (append (rest x) (first y)) and it works find until it gets
to the top and calling level. I have tried calling the function both in
a let and at the top level with the same effects. I am baffled.
In Graham's A CL book on page 202 he is apparently using side effects in the
same way, though since he doesn't give examples I will have to try it to see
for sure.
>
>
> > I would be thankfull for any help.
>
> Even from Erik?
I understand Erik is a great LISP Programmer, and I have never had any problem
with him. I don't even disagree with any of his major points, I was trying to
explain the realities of where I work. I pretty sure I have better knowledge
about the people I work with, but apparently not :)
Muddy
>
> ~jrm
In article <·················@raytheon.com>,
Robert Posey <·····@raytheon.com> wrote:
> Joe Marshall wrote:
> > Lisp is a call-by-value language, so a function cannot change
> > the value of any variable that isn't lexically visible. (The
> > fact that x1 is a global variables is unimportant). So calling
> > my_copy on x1 will not change the value of x1.
>
> The strangest thing is it reacts differently for different (setf )
> actions in the recursive routine.
You said you do embedded programming, right? Mostly C, I guess?
Well, C is also a call-by-value language. You could just as well
say: "C reacts differently for different '=' actions."
> The only different I can see in my actual case is that one
> (setf (first x) (first y)) and it changes the value of the list
> that is not name x, at the level of the original call.
void func1 (x, y) a_structure *x, *y;
{ x->a_member = y->a_member; }
> The other does this (setf x (append (rest x) (first y)) and it
> works find until it gets to the top and calling level.
void func2 (x) a_structure *x;
{ x = a_function (some_arguments); }
> I have tried calling the function both in a let and at the top
> level with the same effects. I am baffled.
If you understand C, think about the difference between func1 and
func2 above, and see if you're still baffled.
-- Robert Munyer <······@mcs.com>
In article <·················@raytheon.com>,
Robert Posey <·····@raytheon.com> wrote:
>
>
>Joe Marshall wrote:
>>
>> rposey <············@worldnet.att.net> wrote in message
>>
>> Lisp is a call-by-value language, so a function cannot change the value
>> of any variable that isn't lexically visible. (The fact that x1 is a global
>> variables is unimportant). So calling my_copy on x1 will not change the
>> value of x1.
>
>The strangest thing is it reacts differently for different (setf ) actions
>in the recursive routine. The only different I can see in my actual case is
>that one (setf (first x) (first y)) and it changes the value of the list
>that is not name x, at the level of the original call.
It's changing the contents of the cons cell that x refers to. The outer
variable contains a reference to that same cons cell, so the change is
visible via both references.
> The other does
>this (setf x (append (rest x) (first y)) and it works find until it gets
>to the top and calling level. I have tried calling the function both in
>a let and at the top level with the same effects. I am baffled.
In this case you're just changing what the local variable x refers to.
That has no effect on anything else.
The best way to understand these things is to draw pictures of variables
and conses, with arrows going from them to what they refer to. When you
perform assignments, it just changes one of those arrows. Unfortunately,
it's difficult to show this in a text message like this.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Robert Posey <·····@raytheon.com> wrote in message
······················@raytheon.com...
>
>
> Joe Marshall wrote:
> >
> > rposey <············@worldnet.att.net> wrote in message
> >
> > Lisp is a call-by-value language, so a function cannot change the value
> > of any variable that isn't lexically visible. (The fact that x1 is a
global
> > variables is unimportant). So calling my_copy on x1 will not change the
> > value of x1.
>
> The strangest thing is it reacts differently for different (setf ) actions
> in the recursive routine. The only different I can see in my actual case
is
> that one (setf (first x) (first y)) and it changes the value of the list
> that is not name x, at the level of the original call. The other does
> this (setf x (append (rest x) (first y)) and it works find until it gets
> to the top and calling level. I have tried calling the function both in
> a let and at the top level with the same effects. I am baffled.
It's often instructive to make `box and pointer' diagrams in this case.
My ascii art is terrible, so I'll just try to describe what's happening.
Let me reproduce your original code here:
(setf x1 '( a b c d e f)
y1 '(h i j k l m o)
x2 '((1 2 3) 4 5 6)
y2 '((7 8 9) 10 11 12))
(defun my_copy ( c1 p1 c2 p2)
(setf (first c1) (first p1)) ;; E1
(setf c2 (append (rest p2) (first p2)) ; E2
(if (not (equal c1 p1))
(return-from my_copy (my_copy (rest c1) (rest p1) c2 p2)
(return-from my_copy T))
)
First, let me disentange the two implementations:
(defun my_copy1 (copy original)
(setf (first copy) (first original))
(if (not (equal copy original))
(return-from my_copy1 (my_copy1 (rest copy) (rest original)))
(return-from my_copy1 T)))
(defun my_copy2 (copy original)
(setq copy (append (rest original) (first original)))
(if (not (equal copy original))
(return-from my_copy2 (my_copy2 (rest copy) (rest original)))
(return-from my_copy1 T)))
Ok. Let's consider this call:
(my_copy1 x1 y1)
Now, when entering my_copy1, the variable COPY gets the value of
x1, and ORIGINAL gets the value of y1. These are both CONS cells.
The SETF replaces the CAR of COPY with the CAR of ORIGINAL,
then if the copy and original aren't EQUAL, you recurse on the cdrs
of both COPY and ORIGINAL.
Why does this seem to cause an effect on X1? Because X1 is actually
a POINTER to the first cons cell in your list. When we first enter
my_copy1, the variable COPY will be bound to that pointer. The
SETF replaces the CAR in the object pointed to. So when we return
from the function, the changes made to that object are visible and
it appears that x1 has been modified.
However, you haven't changed what X1 *is*. X1 points to a container
(a cons cell), and you replaced the contents of the container. But it
is still the same container. If X1 weren't a container but, say, a number,
there is no way you could change its value without explicitly writing
(setq x1 ...)
Ok, now consider this call:
(my_copy2 x1 y1)
When entering my_copy2, the variable COPY gets the value of
x1, and ORIGINAL gets the value of y1. These are both CONS cells.
We construct a brand new list by appending the tail of the original
to the head (I suspect that you want to do something different here)
Then you ASSIGN the variable COPY to be this new list. The original
list you passed in (which is what x1 is pointing to), is forgotten (at
least this function no longer knows about it, x1 still points to it).
my_copy2 then recursively traverses the list (well, it would, but
there are other bugs...)
Does that help clarify things?
~jrm
In article <·············@flash.seas.smu.edu>,
"rposey" <············@worldnet.att.net> writes:
> Dear Gentle Persons,
>
> I am unable to make sense of when a recursive algorithm has side effects
> at the original calling level. Given the following:
>
>
> (setf x1 '( a b c d e f)
> y1 '(h i j k l m o)
> x2 '((1 2 3) 4 5 6)
> y2 '((7 8 9) 10 11 12))
>
> (defun my_copy ( c1 p1 c2 p2)
> (setf (first c1) (first p1)) ;; E1
> (setf c2 (append (rest p2) (first p2)) ; E2
>
> (if (not (equal c1 p1))
> (return-from my_copy (my_copy (rest c1) (rest p1) c2 p2)
> (return-from my_copy T))
>
> )
>
>
> What determines if x1 etc. are changed. I have a different program that
> the only difference I can see is that in one case the setf is like E1 and
> the
> the other its like E2. In the E1 case the top level is changed, and the
> other
> it is not.
this has nothing to do with recursion, it is simply a question of side
effects of function calls.
the basic rule (to be elaborated upon further down: there aren't any.
in lisp arguments are passed to functions by value, and there is no way
that a function can change something that was passed as argument in a
way that it effect the environment from where the call was made.
to understand what is happening in your example, you need to have some
understanding on lisp's data structures and how exactly arguments get
passed to functions (you appear to be fairly new to lisp, and i have no
idea how far you have come so far, so i'll keep it pretty brief: what
gets passed to the function is essentialy a pointer to the cons cell
that makes up the start of the list. note that that is unchanged: the
variables x1 etc still have the same value after the return from the
function.. what you did you have done is use some of the features in
lisp to change the contents of a data structure you have access to
--
Hartmann Schaffer
It is better to fill your days with life than your life with days