bobuel
...@yahoo.com writes:
> The referenced article
http://www.nhplace.com/kent/PS/EQUAL.html begins
> with
> --- snip ---
> "Why is there no generic COPY function?'' Common Lisp programmers often
> ask this question.
> This glossary entry from dpANS Common Lisp [CL93] provides some useful
> background information and a brief rationale for the absence of a
> generic COPY function:
> copy n.
> 1. (of a cons C) a fresh cons with the same car and cdr as C.
(if (atom? object)
object
(cons (car object) (cdr object))))
> 2. (of a list L) a fresh list with the same elements as L..
> (Only the list structure is fresh; the elements are the same.) See the
> function copy-list.
(define (copy-list object)
(if (null? object)
object
(cons (car object) (copy-list (cdr object)))))
> 3. (of an association list A with elements Ai) a fresh list B
> with elements Bi, each of which is nil if Ai is nil, or else a copy of
> the cons Ai. See the function copy-alist.
(define (atom? object)
(not (pair? object)))
(define (copy-alist object)
(cond
((atom? object) object)
((atom? (car object)) (cons (car object) (copy-alist (cdr object))))
(else (cons (cons (car object) (copy-list (cdr object)))
(copy-alist (cdr object))))))
> 4. (of a tree T) a fresh tree with the same leaves as T. See the
> function copy-tree.
(define (copy-tree object)
(if (atom? object)
object
(cons (copy-tree (car object)) (copy-tree (cdr object)))))
> 5. (of a random state R) a fresh random state that, if used as
> an argument to the function random would produce the same series of
> ``random'' values as R would produce.
> 6. (of a structure S) a fresh structure that has the same type
> as S, and that has slot values, each of which is the same as the
> corresponding slot value of S.
Here is a function that will help us see the effect of the various
copying functions defined above:
(define (compare-conses a b)
(cond ((atom? a) (eq? a b))
((atom? b) #f)
((eq? a b))
(else (cons (compare-conses (car a) (car b))
(compare-conses (cdr a) (cdr b))))))
(define foo '((a . 1) () (b . (2 3 4)) ((c . d) . (5 6 7))))
(map (lambda (copy)
(newline)
(display (car copy))(newline)
(display foo)(newline)
(let ((c ((cdr copy) foo)))
(display c)(newline)
(display (compare-conses foo c)) (newline)))
(list (cons 'copy-cons copy-cons)
(cons 'copy-list copy-list)
(cons 'copy-alist copy-alist)
(cons 'copy-tree copy-tree)))
prints:
COPY-CONS
((A . 1) () (B 2 3 4) ((C . D) 5 6 7))
((A . 1) () (B 2 3 4) ((C . D) 5 6 7))
(#T . #T)
COPY-LIST
((A . 1) () (B 2 3 4) ((C . D) 5 6 7))
((A . 1) () (B 2 3 4) ((C . D) 5 6 7))
(#T #T #T #T . #T)
COPY-ALIST
((A . 1) () (B 2 3 4) ((C . D) 5 6 7))
((A . 1) () (B 2 3 4) ((C . D) 5 6 7))
((#T . #T) #T (#T #T . #T) (#T #T . #T) . #T)
COPY-TREE
((A . 1) () (B 2 3 4) ((C . D) 5 6 7))
((A . 1) () (B 2 3 4) ((C . D) 5 6 7))
((#T . #T) #T (#T #T #T #T . #T) ((#T . #T) #T #T #T . #T) . #T)
1- note how all the copies are displayed equally: the scheme printer
doesn't distinguish them.
2- note how the result of compare-conses is different for each copy
function. A #T means that the subtree is identical, the same.
In the case of copy-cons, only one new cons is allocated.
In the case of copy-list, a new cons for each element in the list
is allocated.
In the case of copy-alist, two new conses for each associations in
the a-list are allocated.
In the case of copy-tree, a new cons for all the conses of the tree
are allocated.
All these copies of conses either refer the same objects in their
car and/or cdr as their originals, or refer new copies of these
objects.
In Common Lisp we could get this output:
COPY-CONS
((#1=(A . 1) . #2=(NIL (B 2 3 4) ((C . D) 5 6 7)))
(#1# . #2#))
(T . T)
COPY-LIST
((#1=(A . 1) NIL #2=(B 2 3 4) #3=((C . D) 5 6 7))
(#1# NIL #2# #3#))
(T T T T . T)
COPY-ALIST
(((A . 1) NIL (B 2 . #1=(3 4)) (#2=(C . D) 5 . #3=(6 7)))
((A . 1) NIL (B 2 . #1#) (#2# 5 . #3#)))
((T . T) T (T T . T) (T T . T) . T)
COPY-TREE
(((A . 1) NIL (B 2 3 4) ((C . D) 5 6 7))
((A . 1) NIL (B 2 3 4) ((C . D) 5 6 7)))
((T . T) T (T T T T . T) ((T . T) T T T . T) . T)
#1= identifies an object number 1
#1# is printed where this very same object number 1 is also present.
(The numbers restart from 1 for each copy function).
Notice how there's no common part (but the atoms) with COPY-TREE,
while all the elements in the list copied by copy-list are also in the
original.
VERY IMPORTANT:
+-------------------------------------------------------------------------+
| (Note that since the difference between a cons, a list, and a tree |
| is a matter of ``view'' or ``intention,'' there can be no |
| general-purpose function which, based solely on the type of an object, |
| can determine which of these distinct meanings is intended. The |
| distinction rests solely on the basis of the text description within |
| this document. For example, phrases like ``a copy of the given list'' |
| or ``copy of the list x'' imply the second definition.) |
+-------------------------------------------------------------------------+
> --- snip ---
> I've read this four times and I still don't understand it.
> An object A is defined in the memory. No matter how complicated the
> object A is I can make a copy B of it in some other part of memory
> (provided that I don't require that A and B share something). I can do
> this for list, for trees for everything, so why is a generic copy
> procedure impossible?
Procedures work mechanically on the _form_ of the data, not on what the data is.
Note how the functions copy-cons, copy-list, copy-alist and copy-tree
above all work on the same type of objects: conses. Why one would you
choose?
Imagine I define an object as cons whose car is a class, and cdr a
list of fields. The method table would be implemented as an a-list of
method names and lambda expressions.
(define account-class '(
; method table:
( (withdraw . (lambda (amount) ...))
(cash-in . (lambda (amount) ...))
...)
; list of instance fields:
( iban currency debit credit owner )
; other class stuff:
...))
(define person-class '( ( (change-address . (lambda (newaddress ...))))
( first-name name country ...)
...))
(define myself (cons person-class
(list "Pascal" "Bourguignon" "Spain")))
(define account-instance (cons account-class
(list "ES01 2345 7890 1234 5678 9012 34"
"EUR" 0 1000.00 myself)))
Now, imagine the bank runs a concurse and I win the first prize which
consists in doubling my accounts, creating new accounts with the same
amounts as my existing accounts. How will then copy the
account-instance object? If you ask the lisp printer, it will only
show lists:
account-instance -->
((((withdraw lambda (amount) |...|) (cash-in lambda (amount) |...|) |...|)
(iban currency debit credit owner) |...|)
"ES01 2345 7890 1234 5678 9012 34" "EUR" 0 1000.0
((((change-address lambda (newaddress |...|))) (first-name name country |...|)
|...|)
"Pascal" "Bourguignon" "Spain"))
Should we copy-tree it? No because they don't clone me! And they
don't clone the class of account, neither the classes of account or of
person. Only "THE account" must be copied, not the structures it
refers like the classes and the person.
Even the strings such as "EUR" don't need to be duplicated. These
strings are constant literals, and there's no need to copy them, both
account can refer the same string object.
Unfortunately, there is no general copy function that would be able to
know what car and what cdr must be copied and what mustn't.
You must design for each kind of object, how to copy it, therefore,
how to compare it.
In the case of an account-instance, we'd have:
(define (copy-account instance)
(cons ; make a new instance
(car instance) ; don't copy the class,
; just keep a reference to the original class
(list (make-new-account-number) ; don't copy the account number,
; but make a new one!
(second (cdr instance)) ; keep a reference to the devise
(third (cdr instance)) ; copy or keep a reference to debit
; it doesn't matter since it's immutable
(fourth (cdr instance)) ; copy or keep a reference to credit
; it doesn't matter since it's immutable
(fifth (cdr instance)) ; keep a reference to the owner
)))
> In the 6 paragraphs above what does it mean when they say a thing like
> "2. (of a list L) a fresh list with the same elements as L.. (Only the
> list structure is fresh; the elements are the same.)"
> Do they mean that the original list A and the new list B share the
> elements? If that's the meaning, then I wouldn't call object B a "copy
> of A" but something else. If two Siamese twins share the body but have
> different heads I would'nt call the first twin a copy of the other (as
> I might say for two one-egg twins).
very-deep-copy, there are all nuances of depth of copy.
> And what is the meaning of
> "Note that since the difference between a cons, a list, and a tree is a
> matter of "view'' or "intention,'' there can be no general-purpose
> function which, based solely on the type of an object, can determine
> which of these distinct meanings is intended."
> Is it that a list can be viewed as a list or as a cons or as a tree
> and that depending on which "view" you choose the copy procedure should
> somehow be different?
(define bar '((A . 1) (B 2 3) ((C . D) 5 6)))
is displayed under the form of cons diagrams:
+---+---+
|car|cdr|-->
+---+---+
|
v
after being copied as a cons, a list, an alist, or a tree.
Can you see a difference?
There's none other than what conses are considered to belong to the
data structure.
- only the topleftmost in the case of a CONS,
- only the top row in the case of a LIST,
- only the top row and the first conses referenced by the CAR of the
top row, and their CARs in the case of an A-LIST,
- all the conses in the case of a TREE.
Consider a rock about 0.5 m x 0.5 m x 0.5 m with the top coarsely
flat and horizontal.
What is it?
Could be a meteorite.
Could be some valuable piece of iron mineral.
Could be an anchor: just attach a rope to it and drop it into the lake!
Could be a chair: sit down on it!
Could be a $1,000,000.00 sculpture.
It could be anything you want. What imports is how you consider it.
> (I feel silly asking all these questions, but ..)
They are important questions.
Diagrams:
[344]> (mapc (lambda (f)
(terpri)
(princ (COM.INFORMATIMAGO.COMMON-LISP.CONS-TO-ASCII:DRAW-LIST
(funcall f bar) :title (string f))))
'(identity copy-cons copy-list copy-alist copy-tree))
+-----------------------------------------------------------+
| IDENTITY |
| |
| +---+---+ +---+---+ +---+---+ |
| | * | * |-->| * | * |-->| * |NIL| |
| +---+---+ +---+---+ +---+---+ |
| | | | |
| | | v |
| | | +---+---+ +---+---+ +---+---+ |
| | | | * | * |-->| * | * |-->| * |NIL| |
| | | +---+---+ +---+---+ +---+---+ |
| | | | | | |
| | | | v v |
| | | | +---+ +---+ |
| | | | | 5 | | 6 | |
| | | | +---+ +---+ |
| | | v |
| | | +---+---+ +---+ |
| | | | * | * |-->| D | |
| | | +---+---+ +---+ |
| | | | |
| | | v |
| | | +---+ |
| | | | C | |
| | | +---+ |
| | v |
| | +---+---+ +---+---+ +---+---+ |
| | | * | * |-->| * | * |-->| * |NIL| |
| | +---+---+ +---+---+ +---+---+ |
| | | | | |
| | v v v |
| | +---+ +---+ +---+ |
| | | B | | 2 | | 3 | |
| | +---+ +---+ +---+ |
| v |
| +---+---+ +---+ |
| | * | * |-->| 1 | |
| +---+---+ +---+ |
| | |
| v |
| +---+ |
| | A | |
| +---+ |
+-----------------------------------------------------------+
+-----------------------------------------------------------+
| COPY-CONS |
| |
| +---+---+ +---+---+ +---+---+ |
| | * | * |-->| * | * |-->| * |NIL| |
| +---+---+ +---+---+ +---+---+ |
| | | | |
| | | v |
| | | +---+---+ +---+---+ +---+---+ |
| | | | * | * |-->| * | * |-->| * |NIL| |
| | | +---+---+ +---+---+ +---+---+ |
| | | | | | |
| | | | v v |
| | | | +---+ +---+ |
| | | | | 5 | | 6 | |
| | | | +---+ +---+ |
| | | v |
| | | +---+---+ +---+ |
| | | | * | * |-->| D | |
| | | +---+---+ +---+ |
| | | | |
| | | v |
| | | +---+ |
| | | | C | |
| | | +---+ |
| | v |
| | +---+---+ +---+---+ +---+---+ |
| | | * | * |-->| * | * |-->| * |NIL| |
| | +---+---+ +---+---+ +---+---+ |
| | | | | |
| | v v v |
| | +---+ +---+ +---+ |
| | | B | | 2 | | 3 | |
| | +---+ +---+ +---+ |
| v |
| +---+---+ +---+ |
| | * | * |-->| 1 | |
| +---+---+ +---+ |
| | |
| v |
| +---+ |
| | A | |
| +---+ |
+-----------------------------------------------------------+
+-----------------------------------------------------------+
| COPY-LIST |
| |
| +---+---+ +---+---+ +---+---+ |
| | * | * |-->| * | * |-->| * |NIL| |
| +---+---+ +---+---+ +---+---+ |
| | | | |
| | | v |
| | | +---+---+ +---+---+ +---+---+ |
| | | | * | * |-->| * | * |-->| * |NIL| |
| | | +---+---+ +---+---+ +---+---+ |
| | | | | | |
| | | | v v |
| | | | +---+ +---+ |
| | | | | 5 | | 6 | |
| | | | +---+ +---+ |
| | | v |
| | | +---+---+ +---+ |
| | | | * | * |-->| D | |
| | | +---+---+ +---+ |
| | | | |
| | | v |
| | | +---+ |
| | | | C | |
| | | +---+ |
| | v |
| | +---+---+ +---+---+ +---+---+ |
| | | * | * |-->| * | * |-->| * |NIL| |
| | +---+---+ +---+---+ +---+---+ |
| | | | | |
| | v v v |
| | +---+ +---+ +---+ |
| | | B | | 2 | | 3 | |
| | +---+ +---+ +---+ |
| v |
| +---+---+ +---+ |
| | * | * |-->| 1 | |
| +---+---+ +---+ |
| | |
| v |
| +---+ |
| | A | |
| +---+ |
+-----------------------------------------------------------+
+-----------------------------------------------------------+
| COPY-ALIST |
| |
| +---+---+ +---+---+ +---+---+ |
| | * | * |-->| * | * |-->| * |NIL| |
| +---+---+ +---+---+ +---+---+ |
| | | | |
| | | v |
| | | +---+---+ +---+---+ +---+---+ |
| | | | * | * |-->| * | * |-->| * |NIL| |
| | | +---+---+ +---+---+ +---+---+ |
| | | | | | |
| | | | v v |
| | | | +---+ +---+ |
| | | | | 5 | | 6 | |
| | | | +---+ +---+ |
| | | v |
| | | +---+---+ +---+ |
| | | | * | * |-->| D | |
| | | +---+---+ +---+ |
| | | | |
| | | v |
| | | +---+ |
| | | | C | |
| | | +---+ |
| | v |
| | +---+---+ +---+---+ +---+---+ |
| | | * | * |-->| * | * |-->| * |NIL| |
| | +---+---+ +---+---+ +---+---+ |
| | | | | |
| | v v v |
| | +---+ +---+ +---+ |
| | | B | | 2 | | 3 | |
| | +---+ +---+ +---+ |
| v |
| +---+---+ +---+ |
| | * | * |-->| 1 | |
| +---+---+ +---+ |
| | |
| v |
| +---+ |
| | A | |
| +---+ |
+-----------------------------------------------------------+
+-----------------------------------------------------------+
| COPY-TREE |
| |
| +---+---+ +---+---+ +---+---+ |
| | * | * |-->| * | * |-->| * |NIL| |
| +---+---+ +---+---+ +---+---+ |
| | | | |
| | | v |
| | | +---+---+ +---+---+ +---+---+ |
| | | | * | * |-->| * | * |-->| * |NIL| |
| | | +---+---+ +---+---+ +---+---+ |
| | | | | | |
| | | | v v |
| | | | +---+ +---+ |
| | | | | 5 | | 6 | |
| | | | +---+ +---+ |
| | | v |
| | | +---+---+ +---+ |
| | | | * | * |-->| D | |
| | | +---+---+ +---+ |
| | | | |
| | | v |
| | | +---+ |
| | | | C | |
| | | +---+ |
| | v |
| | +---+---+ +---+---+ +---+---+ |
| | | * | * |-->| * | * |-->| * |NIL| |
| | +---+---+ +---+---+ +---+---+ |
| | | | | |
| | v v v |
| | +---+ +---+ +---+ |
| | | B | | 2 | | 3 | |
| | +---+ +---+ +---+ |
| v |
| +---+---+ +---+ |
| | * | * |-->| 1 | |
| +---+---+ +---+ |
| | |
| v |
| +---+ |
| | A | |
| +---+ |
+-----------------------------------------------------------+
--
__Pascal Bourguignon__ http://www.informatimago.com/
Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.
