mps@ntcsd1.UUCP (Michael P. Smith) (11/29/89)
On both a TI and a Sun (using Sun Common Lisp (lucid)), the following occurs: >(DEFUN foo1 () '(a b c)) >FOO1 >(foo1) >(A B C) >(NCONC (foo1) '(d e f)) >(A B C D E F) >(foo1) >(A B C D E F) (DEFUN foo2 () (LIST 'a 'b 'c)) is unaffected in the same situation. I think I understand what is happening. NCONC is treating the pointer re- turned by evaluating (FOO1) just as if it were evaluating a variable FOO1. But I don't like it. There is no variable FOO1, and NCONC is in effect re- defining the function FOO1. I have been using the rule: don't use destructive operations on data struc- tures you care about. Now this turns out to be insufficient. Is there a rule regarding when destructive operations can affect the values returned by functions they are not part of? I'm told that even FOO2 is affected when running Franz on a DEC station. Thanks. Mike Smith ( mps@ntcsd1 | mcnc!ntcsd1!mps )
rshu@zodiac.ADS.COM (Richard Shu) (11/29/89)
In article <464@ntcsd1.UUCP> mps@ntcsd1.UUCP (Michael Smith) writes: > >On both a TI and a Sun (using Sun Common Lisp (lucid)), the following occurs: > > >(DEFUN foo1 () '(a b c)) > >FOO1 > >(foo1) > >(A B C) > >(NCONC (foo1) '(d e f)) > >(A B C D E F) > >(foo1) > >(A B C D E F) > >(DEFUN foo2 () (LIST 'a 'b 'c)) is unaffected in the same situation. Same thing happens on a Symbolics running Genera 7.2 >I think I understand what is happening. NCONC is treating the pointer re- >turned by evaluating (FOO1) just as if it were evaluating a variable FOO1. >But I don't like it. There is no variable FOO1, and NCONC is in effect re- >defining the function FOO1. I'm not an expert at Common Lisp or its implementation but I think your explanation is a little off base. The point is that '(a b c) is a constant and the compiler/interpreter is deciding to treat it that way. Thus, every call of FOO1 returns the SAME copy of '(a b c). This can be shown by evaluating (eq (FOO1) (FOO1)) and seeing that the value returned is T. For comparison (eq (FOO2) (FOO2)) returns NIL. All this is a little weird since (eq '(a b c) '(a b c)) also returns NIL. I understand your confusion but I'll bet somebody can give the "official" explanation why Common Lisp works this way. >I have been using the rule: don't use destructive operations on data struc- >tures you care about. Now this turns out to be insufficient. Actually, the rule is don't use destructive operations on data structures if there might be another pointer (direct or indirect) to the same object and that pointer should not reflect the change that a destructive operation would make. Using this rule requires real thought about the life history of the data structure you're about to change destructively. You have to consider every function that had a chance to reference the data structure since it was created (which means you have to know when it was created). This can be a real pain if data structure's life history is not readily apparent. As a result, I only use destructive operations when the life history is obvious. Typically, I do stuff like (setf (cdr x) y) where x is a cons cell of an alist that is not part of any other alist. You can see why the simplified version of this rule translates to: Don't use destructive operations at all. >Is there a >rule regarding when destructive operations can affect the values returned >by functions they are not part of? I guess there's a corollary that says: make sure you create new copies of lists if that's what you want. Don't use QUOTE (') to cons up data structures. If you don't like LIST, use the BACKQUOTE macro (`). I've been shafted by variations of your bug where the problem was using QUOTE instead of BACKQUOTE. Rich (responsible-p ADS message) NIL (si:halt)
barmar@think.com (11/29/89)
In article <464@ntcsd1.UUCP> mps@ntcsd1.UUCP (Michael Smith) writes: > >(DEFUN foo1 () '(a b c)) > >FOO1 > >(foo1) > >(A B C) > >(NCONC (foo1) '(d e f)) > >(A B C D E F) > >(foo1) > >(A B C D E F) Someone else already explained what is going on -- your NCONC is modifying the actual list that is in your function. Remember, QUOTE returns its argument, *not* a copy of it. >(DEFUN foo2 () (LIST 'a 'b 'c)) is unaffected in the same situation. Since this creates a new list every time it is called, destructive operations cannot affect it. >I have been using the rule: don't use destructive operations on data struc- >tures you care about. Now this turns out to be insufficient. A better rule is: don't return constant data structures from functions, unless the function is documented to return a constant (so the caller knows not to try to modify it). A compiler would be justified in storing constant data structures on read-only pages, so the above NCONC *could* result in a core dump! > Is there a >rule regarding when destructive operations can affect the values returned >by functions they are not part of? If you modify a constant that came from a function, you may be modifying the function. The wording of the rule in the ANSI CL working draft is "the consequences of using a destructive operation on a constant are undefined." > I'm told that even FOO2 is affected when >running Franz on a DEC station. That's a bug in Franz. Sounds like an incorrect compiler optimization to me -- it's translating a call to LIST all of whose arguments are quoted constants into a single quoted constant. Since LIST is supposed to cons a new list each time it is called, this changes the semantics drastically. Barry Margolin, Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
cox@Franz.COM (Charles A. Cox) (11/30/89)
In article <31792@news.Think.COM> barmar@think.com writes: In article <464@ntcsd1.UUCP> mps@ntcsd1.UUCP (Michael Smith) writes: > >(DEFUN foo1 () '(a b c)) > >FOO1 > >(foo1) > >(A B C) > >(NCONC (foo1) '(d e f)) > >(A B C D E F) > >(foo1) > >(A B C D E F) [ . . . ] >(DEFUN foo2 () (LIST 'a 'b 'c)) is unaffected in the same situation. > I'm told that even FOO2 is affected when >running Franz on a DEC station. That's a bug in Franz. There's no bug here since Allegro CL is doing the right thing (i.e. what Mr. Smith was told is incorrect). You are correct, though, that had it been the case that foo2 was affected, it would have been a bug. From the Decstation: <cl> (DEFUN foo2 () (LIST 'a 'b 'c)) FOO2 <cl> (NCONC (foo2) '(d e f)) (A B C D E F) <cl> (foo2) (A B C) <cl> (proclaim '(optimize (speed 3) (safety 0))) T <cl> (compile 'foo2) FOO2 <cl> (NCONC (foo2) '(d e f)) (A B C D E F) <cl> (foo2) (A B C) <cl> -- --- Charles A. Cox, Franz Inc. 1995 University Avenue, Suite 275 Internet: cox@franz.com Berkeley, CA 94704 uucp: uunet!franz!cox Phone: (415) 548-3600 FAX: (415) 548-8253
pf@islington-terrace.csc.ti.com (Paul Fuqua) (11/30/89)
Date: Tuesday, November 28, 1989 9:56pm (CST)
From: barmar at think.com
Subject: Re: NCONC & Functions
Newsgroups: comp.lang.lisp
In article <464@ntcsd1.UUCP> mps@ntcsd1.UUCP (Michael Smith) writes:
> >(DEFUN foo1 () '(a b c))
> >(NCONC (foo1) '(d e f))
A compiler would be justified in storing
constant data structures on read-only pages, so the above NCONC *could*
result in a core dump!
In fact, the Explorer compiler will put such constants into read-only
areas when compiling a file (just compiling a function won't do it).
For some reason, it causes lots of user confusion, so around Release 3
we modified the message for write-into-read-only errors to add the
phrase "the code was probably trying to modify a program constant" when
appropriate.
Paul Fuqua pf@csc.ti.com
{smu,texsun,cs.utexas.edu,rice}!ti-csl!pf
Texas Instruments Computer Science Center
PO Box 655474 MS 238, Dallas, Texas 75265HEP@smectos.gang.umass.edu (High Energy Physics Group) (11/30/89)
With some text deleted, >> >(DEFUN foo1 () '(a b c)) >> >FOO1 >> >(foo1) >> >(A B C) >> >(NCONC (foo1) '(d e f)) >> >(A B C D E F) >> >(foo1) >> >(A B C D E F) >> I'm told that even FOO2 is affected when >>running Franz on a DEC station. > >That's a bug in Franz. Sounds like an incorrect compiler optimization to >me -- it's translating a call to LIST all of whose arguments are quoted >constants into a single quoted constant. Since LIST is supposed to cons a >new list each time it is called, this changes the semantics drastically. I have a copy of Franz's Allegro CL on my DECstation 3100, and this is what happens: dribbling to file "/usr/users/kgk/junk" NIL <cl> (defun foo2 () (list 'a 'b 'c)) FOO2 <cl> (nconc (foo2) '(it works fine)) (A B C IT WORKS FINE) <cl> (foo2) (A B C) <cl> (defun foo2 () (declare (optimize (speed 3) (safety 0))) (list 'a 'b 'c)) FOO2 <cl> (compile 'foo2) FOO2 <cl> (nconc (foo2) '(it works fine)) (A B C IT WORKS FINE) <cl> (foo2) (A B C) <cl> (dribble) As far as I can see, Allegro CL does not seem to be in error! :-) -- Kleanthes
rar@KRONOS.ADS.COM (Bob Riemenschneider) (11/30/89)
=> From: mps@ntcsd1.UUCP (Michael P. Smith) => => On both a TI and a Sun (using Sun Common Lisp (lucid)), the following occurs: => => >(DEFUN foo1 () '(a b c)) => >FOO1 => >(foo1) => >(A B C) => >(NCONC (foo1) '(d e f)) => >(A B C D E F) => >(foo1) => >(A B C D E F) This seems to me to be just what you should have expected. You stuck a particular list structure in FOO1's function cell and destructively modified that list structure. Once you start using destructive operations, you have to abandon some abstraction and think about what's really going on in memory. That is, NCONC drags DEFUN down to it's own level. => (DEFUN foo2 () (LIST 'a 'b 'c)) is unaffected in the same situation. Again, this is reasonable. If you stick (LIST 'A 'B 'C) in the function cell, every call CONSes up a new list. => I have been using the rule: don't use destructive operations on data => structures you care about. Well, that may be a good rule, depending on what you mean by "care about". The rule I try to use is: don't use destructive operations unless code profiling shows you really need them in some function; then insert them, think carefully about whether any other changes are required to preserve correctness, and test the modified system carefully just in case you made a mistake. => I'm told that even FOO2 is affected when running Franz on a DEC station. I suppose one could argue that this is a legal optimization since (LIST 'A 'B 'C) and '(A B C) are clearly equivalent in some sense. But there are lots of different senses of equivalence, especially when you have destructive operations: see Ian Mason's _The Semantics of Destructive Lisp_. (Note that I couldn't reproduce this in the Franz on my Sun3, even compiling, even with a proclamation to crank optimization up all the way.) One last note: a lot of Lispers think of this behavior as a feature rather than a bug. Consider the following program for computing Fibonacci numbers, based on an example in Talcott and McCarthy's Lisp course notes: (defun fibon (n) (if (or (eq n 0) (eq n 1)) 1 (fibonaux n '(1 1)))) (defun fibonaux (n l) (if (null (cddr l)) (if (eq n 2) (cadr (rplacd (cdr l) (list (+ (car l) (cadr l))))) (fibonaux (- n 1) (rplacd (cdr l) (list (+ (car l) (cadr l)))))) (if (eq n 2) (caddr l) (fibonaux (- n 1) (cdr l))))) This function modifies it's own definition at run-time, making itself "smarter" by caching newly computed Fibonacci numbers. Mason says Although this example is trivial, it elegantly illustrates why Lisp is *the* language for artificial intelligence. Personally, I agree with John Allen's assessment: This technique is similar to the machine language tricks of self-modifying code and should be used with similar care. The freedom to hang yourself should not be construed as an invitation to do so, but it again points out the similarities of LISP to machine language and highlights the differences between LISP and contemporary high-level languages. When I recently taught a Lisp short course, I showed the example -- which is why I had all this stuff handy -- and warned against doing such things. It's nice to know you *can* even though you probably shouldn't. -- rar
mps@ntcsd1.UUCP (Michael P. Smith) (11/30/89)
In article <464@ntcsd1.UUCP> mps@ntcsd1.UUCP (Michael Smith) writes: > >On both a TI and a Sun (using Sun Common Lisp (lucid)), the following occurs: > > >(DEFUN foo1 () '(a b c)) > >FOO1 > >(foo1) > >(A B C) > >(NCONC (foo1) '(d e f)) > >(A B C D E F) > >(foo1) > >(A B C D E F) > >(DEFUN foo2 () (LIST 'a 'b 'c)) is unaffected in the same situation. > >by functions they are not part of? I'm told that even FOO2 is affected when >running Franz on a DEC station. Now I'm told by the same source that FOO2 is NOT affected in Franz. I apologize posting something I hadn't ascertained myself. BTW, thanks to some early responses I'm a little clearer about what bothers me about this. If FOO1 had referred to a variable whose value was changed as a result of NCONCing the result of calling FOO1 with something else, I would not have been surprised. I was surprised to find that even constants can be modified (just not re-assigned or bound), but I can live with it. I'm less happy that some apparently read p. 86 of Steele (1st ed.) to imply that quoted expressions are just like lisp constants in this respect (i.e., modifi- able). But what really bothers me is this: (SYMBOL-FUNCTION foo1) evaluated before the NCONC yields: (NAMED-LAMBDA FOO1 NIL (BLOCK FOO1 '(A B C))) After the NCONC, we get: (NAMED-LAMBDA FOO1 NIL (BLOCK FOO1 '(A B C D E F))). These look like different functions to me. (DEFUN foo3 () *glorp*), where *glorp* is a lisp constant assigned '(A B C) will exhibit the same behavior. But at least its function definition remains unchanged. Mike Smith ( mps@ntcsd1 | mcnc!ntcsd1!mps ) <The views expressed above are fictional. Any resemblance to real facts, whether living or dead, is purely coincidental.>
doug@zodiac.ADS.COM (Doug Morgan) (11/30/89)
When the lisp reader sees: (DEFUN foo1 () '(a b c)) it turns the text (a b c) into an internal representation as a list of conses pointing to symbols. At run time the ' (actually (quote ...)) returns THAT PARTICULAR internal representation. A later NCONC munches that representation and you get exactly what you saw. In the case of (DEFUN foo2 () (LIST 'a 'b 'c)), the reader creates a different internal representation. This one is 4 conses with the first pointing to the symbol named LIST. At run time, the evaluation of this representation causes a 3 cons list pointing to a b and c to be generated. Since these lists are generated upon each evaluation of (LIST ...), NCONC can't affect later ones. Again exactly as you saw. Any lisp that treats FOO2 like FOO1 is in error, no ifs ands or buts. I use destructive operations pretty much at will on lists that are created from nil and the operations are in the lexical scope of the point of creation (I get to look at everything that could be building pointers to such lists). Never (well, hardly ever) trust a list that's passed in from "outside." doug
barmar@think.com (11/30/89)
In article <465@ntcsd1.UUCP> mps@ntcsd1.UUCP (Michael Smith) writes: > But what really bothers me is this: (SYMBOL-FUNCTION foo1) evaluated >before the NCONC yields: > (NAMED-LAMBDA FOO1 NIL > (BLOCK FOO1 > '(A B C))) >After the NCONC, we get: > (NAMED-LAMBDA FOO1 NIL > (BLOCK FOO1 > '(A B C D E F))). >These look like different functions to me. Just because they look different doesn't mean they *are* different. That's the problem with destructive operations. Consider: (setq *foo* (list 1 2 3)) *foo* => (1 2 3) (nconc *foo* '(a b c)) *foo* => (1 2 3 A B C) The two values of *FOO* look different, but they are the same Lisp object. One of the fundamental concepts of Lisp is that programs and data are made up of the same "stuff". Therefore, when you NCONC a list that is in a program, you are modifying the program itself. By the way, Lisp is *not* unique in this regard. In C you are not permitted to modify a string that was created as a result of a literal string constant in the program. In implementations that don't put them on a read-only page you're likely to change the copy in the text section of the program. Consider the following program excerpt: func(x) int x; { char *string = "abcd"; if (x) string[0] = 'q'; printf ("%s ", string); } main() { func(0); func(1); func(0); } I believe that this will print out "abcd qbcd qbcd" in many implementations, because the string constant is modified during the second call. Barry Margolin, Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
hoey@ai.etl.army.mil (Dan Hoey) (11/30/89)
In article <8911292103.AA21810@kronos.ads.com> rar@KRONOS.ADS.COM (Bob Riemenschneider) writes: >One last note: a lot of Lispers think of this behavior [modifying quoted >structure in a function definition] as a feature rather >than a bug. Consider the following program .... I used to think so, too, but the designers of Common Lisp have decided that modifying quoted structure is an error. The rationale is to allow two features that they thought outweighed the utility of this technique: 1. The compiler is free to collapse all EQUAL quoted structures into one, saving some amount of space. I do not know if this is implemented by any compiler. 2. The system is free to put quoted structure into write-protected memory, and thus signal an error if the user accidentally modifies the structure. I am somewhat uncomfortable with this, since it also prevents the user from purposefully modifying the structure, but since some lisp machine manufacturers have implemented this feature, I don't think it's worth debating. The sort of work-around that I believe is approved is (1) for now, use a special variable, and (2) when enough lisps support it, go to DEFUNs with a lexical environment, such as (borrowing Bob's code) + (let ((aux (list 1 1))) (defun fibon (n) (if (or (eq n 0) (eq n 1)) 1 ! (fibonaux n aux)))) Dan
jeff@aiai.ed.ac.uk (Jeff Dalton) (01/09/90)
In article <373@ai.etl.army.mil> hoey@ai.etl.army.mil (Dan Hoey) writes: >In article <8911292103.AA21810@kronos.ads.com> rar@KRONOS.ADS.COM (Bob Riemenschneider) writes: >>One last note: a lot of Lispers think of this behavior [modifying quoted >>structure in a function definition] as a feature rather than a bug. > >I used to think so, too, but the designers of Common Lisp have decided that >modifying quoted structure is an error. It's not just Common Lisp. There were other Lisps (eg, Franz Lisp) in which modifying quoting constants might go wrong in compiled code. -- Jeff