The Common-User-Package's Function: copy-seq is not deep enough to
copy old list to a new list as it's more fit for sequence, So here is
a new deep-copy function:
(defun my-copylist (list)
(if (or (not list) (not (listp list)))
list
(cons (my-copylist (first list))
(my-copylist (rest list))))
This works well even for the lists like ( (a b) (c d) ), However I
don't know how can this function create these new cons cells. I still
remember, In C, returning new variables created in a function needs
"malloc" functions, and this new variable must be linked with the
outside variables. But in 'my-copylist' function, it seems that the
variable -- 'list' is bound from the parameter -- 'list'. Then how
could this new list be created?
I don't know whether i have clearly stated my question, so i wanted to
ask it again: What's the difference in local/dynamic variables
creating/binding inside a function? Between CL and the C-style
programming language...
(message (Hello ··········@gmail.com)
(you :wrote :on '(Mon, 30 Jul 2007 03:17:37 -0700))
(
d> The Common-User-Package's Function: copy-seq is not deep enough to
d> copy old list to a new list as it's more fit for sequence, So here is
d> a new deep-copy function:
COPY-TREE does deep copy.
d> (defun my-copylist (list)
d> (if (or (not list) (not (listp list)))
d> list
d> (cons (my-copylist (first list))
d> (my-copylist (rest list))))
d> This works well even for the lists like ( (a b) (c d) ), However I
d> don't know how can this function create these new cons cells.
each time you call CONS it creates a new cell.
d> outside variables. But in 'my-copylist' function, it seems that the
d> variable -- 'list' is bound from the parameter -- 'list'. Then how
d> could this new list be created?
if thing is CONS, it gets copied -- you create a new CONS calling CONS
function.
if thing is ATOM (not-a-cons), old value is referenced.
d> I don't know whether i have clearly stated my question, so i wanted to
d> ask it again: What's the difference in local/dynamic variables
d> creating/binding inside a function? Between CL and the C-style
d> programming language...
still i do not clearly understand your question, but i suspect that you get
confusion because C often passes variables by value, while Lisp passes by
reference (that's not always strictly true, but it's closest analogy).
suppose cons defined in such way:
struct cons : object { object * car; object * cdr;
//a constructor that initializes fields
cons( object * car, object* cdr)
: car(car), cdr(cdr)
{}
}
copy_tree can have following prototype in C:
cons * copy_tree (object * thing);
as you see, it receives and returns pointer. but we do not need to write *
in Lisp because everything is passed as a pointer.
then we probe if thing is a cons (i'm using C++ syntax here):
cons* p_cons = dynamic_cast<cons*> (thing);
//and if it's a cons we'll copy it:
if (p_cons) {
return new cons (
copy_tree(p_cons->car),
copy_tree(p_cons->cdr)
);
} else return thing; //otherwise return thing as is.
in a low level war new_cons can be implemented as a function in C:
cons* new_cons( object * car, object * cdr) {
cons * pc = (cons*) malloc (sizeof(cons));
pc->car = car;
pc->cdr = cdr;
return pc;
}
in Lisp semantics is pretty same, but it doesn't need to specially denote
pointers as everything is a pointer, indirections are done automatically,
and memory management is done automatically.
as for variables, i hope at this point you see that they are not much
important and they do not participate in creation of anything -- they are
just pointers, you can have many pointers pointing to single value, or just
pointing to nothing.
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"scorn")
>
> each time you call CONS it creates a new cell.
>
> if thing is CONS, it gets copied -- you create a new CONS calling CONS
> function.
> if thing is ATOM (not-a-cons), old value is referenced.
>
OH... I get it now...
The new variables are created by CONS function, and the CONS function
can automatically create
new cons Object as your code show.
Some code here:
(defvar *x* '( (a b) (c d) ))
(setf *y* (copy-tree *x*))
(setf (first (first *y*)) 'e)
Then *x* and *y* are different.
*x* => ( (A B) (C D))
*y* => ( (E B) (C D))
No share atoms between *x* and *y* !
Does this mean ATOM (like 'a or 'e in *x* and *y*) also is copied not
just be referenced? I mean that if ATOM is only referenced, *x* and
*y* should be the same, because their (first (first ...)) point the
same Place in memoery.
> in Lisp semantics is pretty same, but it doesn't need to specially denote
> pointers as everything is a pointer, indirections are done automatically,
> and memory management is done automatically.
>
> as for variables, i hope at this point you see that they are not much
> important and they do not participate in creation of anything -- they are
> just pointers, you can have many pointers pointing to single value, or just
> pointing to nothing.
"Each time a function is called, Lisp creates new bindings to hold the
arguments passed by the function's caller"
The Book-- 'Practical Lisp'
Does this sentence mean that every time a function is called, Lisp
will create new variables to hold the value( or pointer? ) of the
arguments?
(message (Hello ··········@gmail.com)
(you :wrote :on '(Mon, 30 Jul 2007 04:42:22 -0700))
(
d> OH... I get it now...
d> The new variables are created by CONS function,
no, CONS does not create variables. you can create a variable in your code
:)
variable is not a data, it just points to data.
d> (defvar *x* '( (a b) (c d) ))
d> (setf *y* (copy-tree *x*))
d> (setf (first (first *y*)) 'e)
d> Then *x* and *y* are different.
d> *x* => ( (A B) (C D))
d> *y* => ( (E B) (C D))
d> No share atoms between *x* and *y* !
err, after copy-tree conses in *x* and *y* point to same atoms (more
preciously, they point to symbols interned into your current package).
however, *y* have different conses. so you change CAR pointer in the first
cons, so it points to symbol E. certainly, first cons in *x* still points to
symbol A. symbols here are not touched at all.
d> Does this mean ATOM (like 'a or 'e in *x* and *y*) also is copied not
d> just be referenced? I mean that if ATOM is only referenced, *x* and
d> *y* should be the same, because their (first (first ...)) point the
d> same Place in memoery.
ehm, i hope C++ code can clarify this..
struct symbol {};
symbol * A = new symbol;
cons * x = new cons( A, NULL);
cons * y = copy_tree(x);
//in this case it's equivalent to:
cons * y = new cons( x->car, x->cdr);
symbol * E = new symbol;
y->car = E;
now we have x being (A) and y being (E).
you should see here that conses provide indirection. when you change car of
cons, it doesn't change symbol which this car point to, but merely a pointer
itself.
to change symbol, you need additional dereference in C++:
*(y->car) = *E;
it Lisp it's not possible to do this dereference -- you can only change
pointers. some objects are immutable in Lisp -- for example, you cannot
change a number. however, if you have a number in a CONS cell, you can make
that CONS pointing to another number.
d> "Each time a function is called, Lisp creates new bindings to hold the
d> arguments passed by the function's caller"
d> The Book-- 'Practical Lisp'
d> Does this sentence mean that every time a function is called, Lisp
d> will create new variables to hold the value( or pointer? ) of the
d> arguments?
yes, you can think it creates new variables that hold pointers to values.
but it's not always some physical place -- Lisp is very flexible on this. it
can hold those variables in CPU registers in some cases, or it can
completely eliminate variable creation if compiler can prove that
eliminating variable won't change semantics.
for example, in function
(defun foo (x)
(let ((y x))
(print y)))
there are two bindings created -- for x and for y. but compiler can see that
this can be reduced to:
(defun foo (x)
(print x))
moreover, if you have function bar:
(defun bar (z)
(foo z))
in some cases compiler can inline foo function call, making bar effectively:
(defun bar (z)
(print z))
so, as you see, there will be no call to function foo when calling bar, and
no bindings for function foo will be created.
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"choose no life")
··········@gmail.com" <·········@gmail.com> writes:
> >
> > each time you call CONS it creates a new cell.
> >
> > if thing is CONS, it gets copied -- you create a new CONS calling CONS
> > function.
> > if thing is ATOM (not-a-cons), old value is referenced.
> >
>
> OH... I get it now...
> The new variables are created by CONS function,
No. Variables are not created, except as a result of the compiler
processing source code. Local variables are a construct of the
compiler. They use symbols to provide names for reference in source
code. Internally, variables are bound (point to) some object.
> and the CONS function
> can automatically create
> new cons Object as your code show.
Cons only creates new cons objects.
>
> Some code here:
>
> (defvar *x* '( (a b) (c d) ))
> (setf *y* (copy-tree *x*))
> (setf (first (first *y*)) 'e)
>
> Then *x* and *y* are different.
> *x* => ( (A B) (C D))
> *y* => ( (E B) (C D))
Correct. They refer to different cons structures
> No share atoms between *x* and *y* !
This is not warranted. Symbols (precisely, interned symbols) are
objects that are identified by their print name. As objects, they have
unique identity. So, the symbols B, C and D are, in fact, shared inside
the different list structures that *X* and *Y* are bound to.
> Does this mean ATOM (like 'a or 'e in *x* and *y*) also is copied not
> just be referenced? I mean that if ATOM is only referenced, *x* and
> *y* should be the same, because their (first (first ...)) point the
> same Place in memoery.
Many locations can point to the same place in memory with out being the
same. A much simpler case is just the use of two variables:
(defvar *A*)
(defvar *B*)
(setq *a* 10)
(setq *b* 10)
Now *A* and *B* are bound to the same object, but they are separate
bindings or pointers. If you change one, the other stays the same.
Similarly with cons cells.
As an excercise to understanding this, it would be useful for you to try
drawing some of the traditional box-and-pointer diagrams of cons cells.
A good example would be something like this:
(defvar *shared* (list 'a 'b))
(defvar *x* (list *shared* (list 'c 'd)))
(defvar *y* (list *shared* (list 'c 'd)))
Come up with a diagram for this and then see if you can predict the
effects of the following operations:
(setf (first (first *x*)) 'M)
(setf (first (second *x*)) 'N)
What do *x* and *y* look like?
> "Each time a function is called, Lisp creates new bindings to hold the
> arguments passed by the function's caller"
> The Book-- 'Practical Lisp'
>
> Does this sentence mean that every time a function is called, Lisp
> will create new variables to hold the value( or pointer? ) of the
> arguments?
It means that new bindings will be created for the scope of that
function. To use some standard programming language terminology, when
you define a procedure, you establish "formal arguments", which are the
variables that a call will bind. Within each call, the formal arguments
will be bound to values and become "actual arguments".
This binding mechanism is what lets you write encapsulated functions and
also makes it possible for recursive functions to be written (easily [*])
in the programming language.
=========
[*] I don't want to stir up the debate about the necessity of this for
recursion, because you could always implement your own stack in a
language that didn't use a stack-based binding scheme. See the thread
on whether recursion is more powerful than interation....
--
Thomas A. Russ, USC/Information Sciences Institute