Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 4 Jul 88 03:07:42 EDT Received: from MCC.COM by SAIL.Stanford.EDU with TCP; 3 Jul 88 23:56:23 PDT Received: from BRAHMA.ACA.MCC.COM by MCC.COM with TCP/SMTP; Mon 4 Jul 88 01:55:55-CDT Date: Mon, 4 Jul 88 01:55 CDT From: David Vinayak Wallace Subject: What have hashing and equality to do with each other? To: common-lisp@sail.stanford.edu In-Reply-To: <19880703165454.6.GREENWALD@SWALLOW.SCRC.Symbolics.COM> Message-ID: <880704015545.4.GUMBY@BRAHMA.ACA.MCC.COM> There has been some discussion of hashing algorithms spawned by the assertion that (= (compute-hash-index-for a) (compute-hash-index-for b)) is a sufficient definition of (equal a b). Nobody has said so, but "it ain't so!" The point of hashing is to map a large, sparse space into a smaller (hopefully more) dense one. Once you compute a hash index you have to peek into the table and look for a collision (what you do then is up to you). What's this rumour I heard about the CLOS people having defined EQUAL as a generic function....  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 3 Jul 88 18:30:49 EDT Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 3 Jul 88 15:09:52 PDT Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0) id AA20651; Sun, 3 Jul 88 15:08:15 PDT Received: from clam.sun.com by snail.sun.com (4.0/SMI-3.2) id AA03866; Sun, 3 Jul 88 15:03:47 PDT Received: by clam.sun.com (3.2/SMI-3.2) id AA16720; Sun, 3 Jul 88 15:11:07 PDT Date: Sun, 3 Jul 88 15:11:07 PDT From: cperdue@Sun.COM (Cris Perdue) Message-Id: <8807032211.AA16720@clam.sun.com> To: common-lisp@sail.stanford.edu, trwrb!smpvax1!jrg@ucbvax.Berkeley.EDU Subject: Re: dynamic extent lisp objects > Speaking as a representative from a company that has a reasonably > successful lisp-based software product, having the ability to declare an > object to have dynamic extent is of great benefit in building a > practical lisp-based product. How clear are you on the issue of whether a declaration facility for variables would be adequate for your needs? One can imagine a form named something like "with-dynamic-extent" that causes all storage allocation "within" its body that would ordinarily be done on the heap to be done on the stack instead. My personal guess is that the variable declarations wind up being more controllable, but that a "with" form would prove somewhat more powerful. Certainly the "with" form could handle complex backquotes easier than variable declarations could. Any practical experience one way or the other? -Cris  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 3 Jul 88 13:17:01 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 3 Jul 88 09:56:25 PDT Received: from SWALLOW.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 428227; Sun 3-Jul-88 12:55:06 EDT Date: Sun, 3 Jul 88 12:54 EDT From: Michael Greenwald Subject: EQUAL, and hash tables, and value/object distinctions To: barmar@Think.COM, Greenwald@STONY-BROOK.SCRC.Symbolics.COM cc: jrose@sun.com, edsel!jonl@labrea.stanford.edu, goldman@vaxa.isi.edu, common-lisp@sail.stanford.edu In-Reply-To: <19880701191544.6.BARMAR@OCCAM.THINK.COM> Message-ID: <19880703165454.6.GREENWALD@SWALLOW.SCRC.Symbolics.COM> Date: Fri, 1 Jul 88 15:15 EDT From: Barry Margolin Date: Thu, 30 Jun 88 16:36 EDT From: Michael Greenwald For example, one cannot construct a hash-function for #'= unless you limit the valid keys to not include both a floating point number and two integers that both coerce to that same float. (i.e. (let* ((a (expt 2 56)) (b (1+ a)) (c (float a))) (values (= a b) (= a c) (= b c))) => NIL T T ) Actually, it's not that difficult to construct such a hash function. All it has to do is coerce its argument before hashing, e.g. I think you are confused. The problem isn't in having a valid hash-function ( (DEFUN TRIVIAL-=-HASH (NUMBER) 1) is legal and valid, but inefficient), the problem is which bucket you put a, b, and c in my example above. In other words, what does (DEFUN TEST-BARMAR-HASH () (SETF (GETHASH a TABLE) 0) (SETF (GETHASH b TABLE) 1) (SETF (GETHASH c TABLE) 2) (VALUES (GETHASH a TABLE) (GETHASH b TABLE) (GETHASH c TABLE))) return?) Unless you restrict the domain as specified above, you are in a quandary. If you coerce them all to long-floats, then (TEST-BARMAR-HASH) => 2,2,2 If you coerce them all to integers then (depending on the implementation) you can get (TEST-BARMAR-HASH) => 0,1,2 or 0,2,2 or 2,1,2 (defun =-hash (number) (let ((real (realpart number)) (imag (imagpart number))) (setq number (complex (coerce real 'long-float) (coerce imag 'long-float)))) ) I admit that this isn't a great hash function if you expect your keys to include many bignums that are near each other. But it is guaranteed to be a correct hash (assuming is well behaved). The hash isn't a problem. It's the fact that #'= isn't transitive. barmar  Received: from SAIL.Stanford.EDU (TCP 4425400302) by AI.AI.MIT.EDU 2 Jul 88 14:58:58 EDT Received: from ucbvax.Berkeley.EDU by SAIL.Stanford.EDU with TCP; 2 Jul 88 11:45:05 PDT Received: by ucbvax.Berkeley.EDU (5.59/1.28) id AA13200; Fri, 1 Jul 88 20:21:33 PDT From: trwrb!smpvax1!jrg@ucbvax.Berkeley.EDU Received: by trwrb (5.51/1.36) id AA03450; Fri, 1 Jul 88 18:56:03 PDT Date: Fri, 1 Jul 88 18:56:03 PDT Message-Id: <8807020156.AA03450@trwrb> To: common-lisp@sail.stanford.edu Subject: dynamic extent lisp objects Speaking as a representative from a company that has a reasonably successful lisp-based software product, having the ability to declare an object to have dynamic extent is of great benefit in building a practical lisp-based product. I strongly support this addition to the language. I prefer the declaration form for many of the same reasons already mentioned by its other advocates. But I'd rather have either or even some other syntax supporting similar functionality than nothing. While I believe several of the other clean-up language changes are beneficial and several of the proposed additions to the language are useful, this is the first issue that I've been motivated to actively support. Being able to use a feature such as this can be the difference between having a practical product that many customers can use and having one that is impossible to deploy in many, if not most, environments. --Joe Ginder  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 1 Jul 88 15:34:14 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 1 Jul 88 12:17:22 PDT Return-Path: Received: from sauron.think.com by Think.COM; Fri, 1 Jul 88 15:17:41 EDT Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 1 Jul 88 15:15:26 EDT Date: Fri, 1 Jul 88 15:15 EDT From: Barry Margolin Subject: EQUAL, and hash tables, and value/object distinctions To: Michael Greenwald Cc: jrose@sun.com, edsel!jonl@labrea.stanford.edu, goldman@vaxa.isi.edu, common-lisp@sail.stanford.edu In-Reply-To: <19880630203650.3.GREENWALD@SWALLOW.SCRC.Symbolics.COM> Message-Id: <19880701191544.6.BARMAR@OCCAM.THINK.COM> Date: Thu, 30 Jun 88 16:36 EDT From: Michael Greenwald For example, one cannot construct a hash-function for #'= unless you limit the valid keys to not include both a floating point number and two integers that both coerce to that same float. (i.e. (let* ((a (expt 2 56)) (b (1+ a)) (c (float a))) (values (= a b) (= a c) (= b c))) => NIL T T ) Actually, it's not that difficult to construct such a hash function. All it has to do is coerce its argument before hashing, e.g. (defun =-hash (number) (let ((real (realpart number)) (imag (imagpart number))) (setq number (complex (coerce real 'long-float) (coerce imag 'long-float)))) ) I admit that this isn't a great hash function if you expect your keys to include many bignums that are near each other. But it is guaranteed to be a correct hash (assuming is well behaved). barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 1 Jul 88 02:12:47 EDT Received: from Xerox.COM by SAIL.Stanford.EDU with TCP; 30 Jun 88 22:56:21 PDT Received: from Burger.ms by ArpaGateway.ms ; 30 JUN 88 22:55:28 PDT Sender: "Larry_Masinter.PARC"@Xerox.COM Date: 30 Jun 88 22:54:22 PDT (Thursday) Subject: Re: Issue: STACK-LET (Version 1) From: masinter.PARC@Xerox.COM To: KMP@STONY-BROOK.SCRC.Symbolics.COM cc: Scott.Fahlman@B.GP.CS.CMU.EDU, KMP@STONY-BROOK.SCRC.Symbolics.COM, Common-Lisp@SAIL.Stanford.EDU In-Reply-to: KMP%STONY-BROOK.SCRC.Symbolics:COM's message of Monday, June 27, 1988 1:53 pm Reply-to: masinter.PARC@Xerox.COM Message-ID: <880630-225528-6029@Xerox> While I would like very much to find some way to express dynamic extent within the language, I'm unhappy with either (declare (dynamic-value ...)) or stack-let for two reasons: a) it is disturbing to introduce a construct within which a casual change of (CONS X (LIST Y Z)) to (LIST X Y Z) could introduce a serious bug (e.g., if the tail were stashed away somewhere.) b) the construct really only allows dynamic extent on one-level structures . If you wanted to create a copy of (A (B C) (D E (F G))) you would have to say something like (stack-let* ((part2 (list 'b 'c)) (part3c (list 'f 'g)) (part3 (list 'd 'e part3c)) ((whole-thing (list 'a part2 part3))) ...) Your proposal did not mention objects other than lists; what of DEFSTRUCT or CLOS instances?  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 30 Jun 88 17:54:51 EDT Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 30 Jun 88 14:38:31 PDT Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0) id AA01182; Thu, 30 Jun 88 14:36:25 PDT Received: from lukasiewicz.sun.com by snail.sun.com (4.0/SMI-3.2) id AA27554; Thu, 30 Jun 88 14:32:01 PDT Received: by lukasiewicz.sun.com (4.0/SMI-4.0) id AA01962; Thu, 30 Jun 88 14:38:29 PDT Date: Thu, 30 Jun 88 14:38:29 PDT From: jrose@Sun.COM (John Rose) Message-Id: <8806302138.AA01962@lukasiewicz.sun.com> To: Greenwald@STONY-BROOK.SCRC.Symbolics.COM Cc: edsel!jonl@labrea.stanford.edu, goldman@vaxa.isi.edu, common-lisp@sail.stanford.edu In-Reply-To: Michael Greenwald's message of Thu, 30 Jun 88 16:36 EDT <19880630203650.3.GREENWALD@SWALLOW.SCRC.Symbolics.COM> Subject: EQUAL, and hash tables, and value/object distinctions Date: Thu, 30 Jun 88 16:36 EDT From: Michael Greenwald Date: Thu, 30 Jun 88 12:40:54 PDT From: jrose@Sun.COM (John Rose) Two remarks on EQUAL and hash tables, from a hash table fan. ... Date: Wed, 29 Jun 88 18:57:09 PDT From: Jon L White As you pointed out in subsequent discussion, a user-supplied EQUAL method, whether for CLOS classes or as a defstruct option, leaves open the question of mechanically verifying that the alleged predicate is reflexive, symmetric, and transitive. ... [Flame from Rose...] (EQUALITY-PREDICATE X Y) ==> (= (HASH-FN X) (HASH-FN Y)) Yes, but the equality-predicate must be transitive over the domain of possible keys in order for a hash-function to work. For example, one cannot construct a hash-function for #'= unless you limit the valid keys to not include both a floating point number and two integers that both coerce to that same float. (i.e. (let* ((a (expt 2 56)) (b (1+ a)) (c (float a))) (values (= a b) (= a c) (= b c))) => NIL T T ) I'm not voting for condescension, nor for protecting programmers from themselves. I just want to point out that it is slightly more complicated than you make it seem. Well, for the record, I'll try not to gloss over the fact that the EQUALITY-PREDICATE must be an equality predicate (:-). That is, it must be reflexive, symmetric, and transitive. In my experience, equality predicates are not difficult to write, and are verified by inspection, so "reflexive, symmetric, and transitive" is not really a burden. Writing a hash function takes a little more effort, since you've got to make sure its structure accurately mirrors the equality predicate you've already written. Your point about #'= and domains is well taken. I had forgotten about the CL numeric conversions. I think the general principle here is that if you're comparing equality over domains inside of which there are implicit conversions that lose information, equality testing and hashing should be performed in such a way that the information is reliably thrown out, or reliably retained. (And these two choices yield key domains of different granularities.) For example, a hash table over real numbers including floats might use one of these equality predicates instead of #'=: ;; Coarser grain: #'(lambda (x y) (= (float x 0L0) (float y 0L0))) ;; Finer grain: #'(lambda (x y) (= (rational x) (rational y))) -- John  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 30 Jun 88 16:59:21 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 30 Jun 88 13:40:04 PDT Received: from SWALLOW.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 427334; Thu 30-Jun-88 16:36:56 EDT Date: Thu, 30 Jun 88 16:36 EDT From: Michael Greenwald Subject: EQUAL, and hash tables, and value/object distinctions To: jrose@Sun.COM, edsel!jonl@labrea.stanford.edu cc: goldman@vaxa.isi.edu, common-lisp@sail.stanford.edu In-Reply-To: <8806301940.AA01804@lukasiewicz.sun.com> Message-ID: <19880630203650.3.GREENWALD@SWALLOW.SCRC.Symbolics.COM> Date: Thu, 30 Jun 88 12:40:54 PDT From: jrose@Sun.COM (John Rose) Two remarks on EQUAL and hash tables, from a hash table fan. ... Date: Wed, 29 Jun 88 18:57:09 PDT From: Jon L White As you pointed out in subsequent discussion, a user-supplied EQUAL method, whether for CLOS classes or as a defstruct option, leaves open the question of mechanically verifying that the alleged predicate is reflexive, symmetric, and transitive. Another major problem with using hash-tables on objects with non-default EQUAL methods is that the SXHASH function must be similarly extended for these data types; SXHASH must obey the property that (equal x y) imples (= (sxhash x) (sxhash x)) See CLtL p285. At one time, there was a suggestion that hash tables admit a user-supplied equivalence predicate; but it never got very far for just this reason, that the equivalence predicate must be *** paired up** with an appropriate "numericalizer" function, and many implementors felt that users wouldn't understand these issues and wouldn't be able to construct up their own versions of sxhash to go with their alleged equivalence predicates. Yuck. Who are these brilliant Implementors, that we may all worship at their feet? For they are the curators of such profound knowledge as (EQUALITY-PREDICATE X Y) ==> (= (HASH-FN X) (HASH-FN Y)) Yes, but the equality-predicate must be transitive over the domain of possible keys in order for a hash-function to work. For example, one cannot construct a hash-function for #'= unless you limit the valid keys to not include both a floating point number and two integers that both coerce to that same float. (i.e. (let* ((a (expt 2 56)) (b (1+ a)) (c (float a))) (values (= a b) (= a c) (= b c))) => NIL T T ) I'm not voting for condescension, nor for protecting programmers from themselves. I just want to point out that it is slightly more complicated than you make it seem. My personal opinion is that CLtL should have allowed both the predicate and hash-function to be defined once it included hash tables in the language spec. In a real application the programmer will probably want to construct a custom hash function anyway, even for :TEST 'EQ. If the table has a known, or typical, set of keys, that might allow a much more efficient, or more collision-free, hash function. Hash tables aren't so complicated that one can't construct them yourself. My guess (and only a guess) is that the only reason they're included in the language spec is to give a portable way of hashing on %pointer where that might be useful. SXHASH would have been enough, and that allows easy implementation of the common case of EQUAL hash tables, too. The minimalist in me still wonders why hash tables were included in CLtL. Seriously, I hear an alarming amount of condescension in the above reasoning. The above logical implication is ALL THAT IS NEEDED to construct an appropriate hash function. It is the sole and fundamental insight which makes hash tables work; I have relied on it for years, building many a hash table in various extensible frameworks. What's the problem of requiring a hash-table builder from promising that his hash and equality functions bear the simple relation to each other? And if he can't handle that, what chance does he have of building a working stream type, or making sense out of CLOS? (Note that many vendors have supplied more or less hairy stream definition facilities, which usually require invariants much more complex than the hash invariant above.)  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 30 Jun 88 16:04:28 EDT Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 30 Jun 88 12:41:10 PDT Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0) id AA14063; Thu, 30 Jun 88 12:38:47 PDT Received: from lukasiewicz.sun.com by snail.sun.com (4.0/SMI-3.2) id AA24101; Thu, 30 Jun 88 12:34:26 PDT Received: by lukasiewicz.sun.com (4.0/SMI-4.0) id AA01804; Thu, 30 Jun 88 12:40:54 PDT Date: Thu, 30 Jun 88 12:40:54 PDT From: jrose@Sun.COM (John Rose) Message-Id: <8806301940.AA01804@lukasiewicz.sun.com> To: edsel!jonl@labrea.stanford.edu Cc: goldman@vaxa.isi.edu, common-lisp@sail.stanford.edu In-Reply-To: Jon L White's message of Wed, 29 Jun 88 18:57:09 PDT <8806300157.AA15565@bhopal.lucid.com> Subject: EQUAL, and hash tables, and value/object distinctions Two remarks on EQUAL and hash tables, from a hash table fan. First, if EQUAL is going to descend structures and arrays to test for isomorphism, it should compare hash tables for equality according to their contents. That is, it should verify that two possibly-equal hash tables have the same set of keys, and that for each key the two stored values are EQUAL. Key equality testing must be done using each table's key comparison function. [Rationale & discussion are below, on the next page. But first I've got to respond to something else.] Date: Wed, 29 Jun 88 18:57:09 PDT From: Jon L White From: goldman@vaxa.isi.edu Date: Fri, 24 Jun 88 18:15:43 PDT ... If programmers to extend EQUAL in CLOS style -- which means with arbitrary procedural definitions for their new classes -- could EQUAL hash tables be implemented efficiently? How would they hash values belonging to the new classes? As you pointed out in subsequent discussion, a user-supplied EQUAL method, whether for CLOS classes or as a defstruct option, leaves open the question of mechanically verifying that the alleged predicate is reflexive, symmetric, and transitive. Another major problem with using hash-tables on objects with non-default EQUAL methods is that the SXHASH function must be similarly extended for these data types; SXHASH must obey the property that (equal x y) imples (= (sxhash x) (sxhash x)) See CLtL p285. At one time, there was a suggestion that hash tables admit a user-supplied equivalence predicate; but it never got very far for just this reason, that the equivalence predicate must be *** paired up** with an appropriate "numericalizer" function, and many implementors felt that users wouldn't understand these issues and wouldn't be able to construct up their own versions of sxhash to go with their alleged equivalence predicates. Yuck. Who are these brilliant Implementors, that we may all worship at their feet? For they are the curators of such profound knowledge as (EQUALITY-PREDICATE X Y) ==> (= (HASH-FN X) (HASH-FN Y)) If we mere Users cannot be trusted with such wisdom, how are we to navigate the Streams of Extensibility, or handle the Objects of Genericity? Oh great Implementors, save us, we pray, from overmuch functionality. Seriously, I hear an alarming amount of condescension in the above reasoning. The above logical implication is ALL THAT IS NEEDED to construct an appropriate hash function. It is the sole and fundamental insight which makes hash tables work; I have relied on it for years, building many a hash table in various extensible frameworks. What's the problem of requiring a hash-table builder from promising that his hash and equality functions bear the simple relation to each other? And if he can't handle that, what chance does he have of building a working stream type, or making sense out of CLOS? (Note that many vendors have supplied more or less hairy stream definition facilities, which usually require invariants much more complex than the hash invariant above.) As for "mechanical verification" of the hashing and equality invariants, that's a red herring. Since when do we mechanically verify any of the required properties of functional arguments to Lisp primitives? (I'm thinking particularly of the :KEY and :TEST arguments to sequence functions.) Just say that unless the supplied functions satisfy the required conditions "it is an error". The "pairing up" of equality and hashing could be done cleanly in CLOS by defining generic equality and hashing methods for particular hash table types. [SXHASH is required to be "good enough" for the EQUAL equivalence releation, and for subsets of that relation such as STRING=, but it is unlikely that any vendor makes it "good enough" for, say, EQUALP. Lucid has EQUALP hash tables, but they don't use SXHASH.] -- JonL -- ! Proposal: EQUAL should check for isomorphism of hash tables. The effect of this rule is to treat hash tables like lists, structures, and arrays for equality testing, under the following reasonable theory of the semantics of lists, structures, arrays, and hash tables: The meaning of any such data structure is determined by a small set of (call them) "access keys" and a value stored under each access key. The set of access keys for each kind of data structure is {CAR,CDR}, a set of slot access functions, an initial setquence of non-negative integers, and a set of Lisp objects, respectively. Other than the differences in these "access keys", all four of the above data structures are tuple types, in that they store a finite set of values, each accessible under its own key. An equality function which performs an isomorphism check on any of those tuple types should perform it on all of them, or have a very specific reason not to. If two hash tables differ not in their contents but in their implementation parameters (such as size or equality function), we must choose whether to compare structure abstractly (looking only at contents) or concretely (looking also at implementation parameters). This question comes up with respect to array structural equality also. For example, do we allow a fill pointer to define an array's length (i.e., its "access key" set), or do we look at the length of the underlying allocated storage? What about comparing an (array t) having a fill pointer, with a string? I believe the people working on this problem will come to a more or less abstract viewpoint, and if so, that viewpoint should be applied consistently to hash tables. An interesting question arises when two hash tables have different key equality predicates, and (suppose) we've already decided to treat equality predicates as implementation details, and ignore them directly. Here's one answer: Declare two hash tables EQUAL if they include each other. That is, for every key K in hash table A, require that (EQUAL (GETHASH A K) (GETHASH B K *UNIQUE-UNKNOWN-VALUE*)) and the same for every key in table B. Possible specific reasons not to test for hash table isomorphism, with comments or rebuttals in brackets: (1) It's too hard to implement. [No, it's actually pretty easy to implement this test portably using a MAPHASH over each table; each MAPHASH tests one direction of inclusion by performing GETHASHs.] (2) It's too slow to implement. [Any recursive descent takes a long time to do. But hash tables can probably be made faster to compare than corresponding CONS structures, because they can use saved key hash values to advantages. A hash table's key set can be hashed by combining all its key hash values.] (3) Recursive descent into hash tables is too unexpected. [For programmers unfamiliar with hash tables, many of their properties are going to be pretty surprising. Programmers who understand their nature and use are also going to understand their correspondence with lists, structures, and (especially) arrays; it is these programmers whose expectations we should design for.] (4) Hash tables are different because we expect frequent side effects on them, and so momentary isomorphism between two of them is not significant. [This is the best argument against, I think. See below.] About (4): Cons cells, structures, arrays, and hash tables can all be used either as pure values (that is, no updates after initial construction, and object identity is not important) or as updatable objects (updates are expected, and shared object identities are crucial). Under current Lisp practice, hash tables are rarely used as pure values. (Cons cells usually are, and structures and arrays occasionally are.) We may call types which are used as pure values "value-like" and types which are used as shared objects "object-like". Notice that EQUAL and EQL differ in their theory of cons cells: EQUAL treats them as pure values, and EQL as sharable objects. I believe a consistent way of accounting for this is to say that the behavior of EQUAL and EQL differ for types which have this dual nature, of value-like and object-like. (For types which are only value-like, such as complex numbers, EQL compares substructures, just as EQUAL does. For types which are only object-like, such as streams, EQUAL compares object identity, just as EQL does.) So, if you believe all that about EQUAL and EQL, the question of EQUAL on hash tables gets down to this: Are hash tables so object-like that no one is likely to think of them as pure values? Consider this: Hash tables can be used to implement sets, if you need to optimize the speed of the set-inclusion operator. Sets are value-like types. Hash tables can be used to implement finite functions; if they themselves are hashable and comparable, one can build higher-order functional systems out of them (and get memoization as a bonus). -- John  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 30 Jun 88 11:23:59 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 30 Jun 88 08:03:59 PDT Received: by labrea.stanford.edu; Thu, 30 Jun 88 08:03:29 PDT Received: from bhopal.lucid.com by edsel id AA14758g; Wed, 29 Jun 88 18:50:50 PDT Received: by bhopal id AA15565g; Wed, 29 Jun 88 18:57:09 PDT Date: Wed, 29 Jun 88 18:57:09 PDT From: Jon L White Message-Id: <8806300157.AA15565@bhopal.lucid.com> To: goldman@vaxa.isi.edu Cc: common-lisp@sail.stanford.edu In-Reply-To: goldman@vaxa.isi.edu's message of Fri, 24 Jun 88 18:15:43 PDT <8806250115.AA22390@vaxa.isi.edu> Subject: [Re: EQUAL] [Neil, I'm cc'ing my reply to the whole list, since I think you questions are of general relevance. Apologies in advance if you really didn't want to "go public" with your question. -- JonL --] From: goldman@vaxa.isi.edu Date: Fri, 24 Jun 88 18:15:43 PDT . . . (2) Descend defstructs, except possibly for "system" defstructs ... What are potential "system" defstructs? Is the phrase limited to the list of types on page 13? If so, then it sounds ok, since EQUAL is already (independently) appropriately defined on BIGNUMS and PATHNAMES. But it just says "such as ..." on page 13, which leaves some doubt. I was certainly thinking of those types on page 13, since they are the ones addressed by the "cleanup" issue "type-hierarchy-underspecfied". (3) Require that EQUAL be a "generic" function, so that CLOS methods can be written for it, likely, the "default" method for non-built-in classes would be some sort of error, meaning that mindless descent isn't a good default. First, I would think that (OBJECT OBJECT) would have an EQUAL method that applied EQL, not ERROR, and that method would inherit to all standard classes under OBJECT. I must misunderstand your intent -- you certainly would want EQUAL to be TRUE whenever EQ was true, not an error? I'm not 100% certain that one would want this. Perhaps the CLOS subcommittee of x3j13 will tackle it. Mostly, the default method is just to say that you shouldn't be doing this (calling EQUAL) on an object of this type. But just having no applicable method may in fact be a better kind of error. Of course, a default method could check for EQ before causing any other kind of error. If programmers to extend EQUAL in CLOS style -- which means with arbitrary procedural definitions for their new classes -- could EQUAL hash tables be implemented efficiently? How would they hash values belonging to the new classes? As you pointed out in subsequent discussion, a user-supplied EQUAL method, whether for CLOS classes or as a defstruct option, leaves open the question of mechanically verifying that the alleged predicate is reflexive, symmetric, and transitive. Another major problem with using hash-tables on objects with non-default EQUAL methods is that the SXHASH function must be similarly extended for these data types; SXHASH must obey the property that (equal x y) imples (= (sxhash x) (sxhash x)) See CLtL p285. At one time, there was a suggestion that hash tables admit a user-supplied equivalence predicate; but it never got very far for just this reason, that the equivalence predicate must be *** paired up** with an appropriate "numericalizer" function, and many implementors felt that users wouldn't understand these issues and wouldn't be able to construct up their own versions of sxhash to go with their alleged equivalence predicates. [SXHASH is required to be "good enough" for the EQUAL equivalence releation, and for subsets of that relation such as STRING=, but it is unlikely that any vendor makes it "good enough" for, say, EQUALP. Lucid has EQUALP hash tables, but they don't use SXHASH.] . . . [Pardon me if I am impuning more to your suggestion than you intended. This discussion that started on the meaning of DEFCONSTANT and QUOTE has spread out quite a bit, and maybe you are just suggesting this as an improvement to EQUAL with no implications about it clarifying defconstant/quote]. Yes, the Subject line of this interchange has been "EQUAL" -- not "constant folding/smashing" as before. Jim MacDonald was simply inspired by the defconstant/quote issue to open up the EQUAL one. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 30 Jun 88 11:22:46 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 30 Jun 88 08:03:16 PDT Received: by labrea.stanford.edu; Thu, 30 Jun 88 08:02:46 PDT Received: from bhopal.lucid.com by edsel id AA14691g; Wed, 29 Jun 88 18:44:42 PDT Received: by bhopal id AA15550g; Wed, 29 Jun 88 18:50:58 PDT Date: Wed, 29 Jun 88 18:50:58 PDT From: Jon L White Message-Id: <8806300150.AA15550@bhopal.lucid.com> To: edsel!jlm@labrea.stanford.edu Cc: common-lisp@sail.stanford.edu, cl-cleanup@sail.stanford.edu In-Reply-To: Jim McDonald's message of Fri, 24 Jun 88 16:40:01 EST <8806242339.AA18154@bhopal.lucid.com> Subject: EQUAL Date: Fri, 24 Jun 88 16:40:01 EST From: Jim McDonald My concern about having EQUAL descend structures and arrays is that they are much more likely than lists to be circular. ... As a rule of thumb, I'd bet that less than .0001% of all lists are circular, and that less than 1% of all arrays are circular, but only that less than 30% of all structures are circular. Probabilities can be very misleading here -- for any given application, the probability is typically either 0 or 1. And even for those cases that do utilize circular stucture (I'm including lists here), the relevance to the EQUAL question is entirely moot if they are never given as arguments to EQUAL. One would surely suspect that to be the case for the many programs that deal in circular lists! -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 29 Jun 88 01:55:51 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 28 Jun 88 22:39:48 PDT Received: by labrea.stanford.edu; Tue, 28 Jun 88 22:39:17 PDT Received: from bhopal.lucid.com by edsel id AA10285g; Tue, 28 Jun 88 22:24:31 PDT Received: by bhopal id AA11440g; Tue, 28 Jun 88 22:30:47 PDT Date: Tue, 28 Jun 88 22:30:47 PDT From: Jon L White Message-Id: <8806290530.AA11440@bhopal.lucid.com> To: jrose@sun.com Cc: Common-Lisp@sail.stanford.edu In-Reply-To: John Rose's message of Mon, 27 Jun 88 13:38:40 PDT <8806272038.AA21955@lukasiewicz.sun.com> Subject: Issue: STACK-LET (Version 1) re: The DYNAMIC-EXTENT declaration is a smaller, cleaner addition than a new STACK-LET special form. It's less of a burden on implementors and users to ignore a declaration than to expand one special form into another. It was for just such reasons that Lucid chose (about one year ago) to use a DYNAMIC-EXTENT declaration rather than specialized "stack list" primtives, when implementing "stack list consing" for &rest arguments. The suggestion is entertained to extend it to more contexts, such as any LAMBDA-binding (or LET-binding if you must) where the value is something that would have to be "consed up" afresh. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 28 Jun 88 21:45:10 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 28 Jun 88 18:01:40 PDT Received: by labrea.stanford.edu; Tue, 28 Jun 88 17:59:02 PDT Received: from bhopal.lucid.com by edsel id AA08970g; Tue, 28 Jun 88 17:46:02 PDT Received: by bhopal id AA09433g; Tue, 28 Jun 88 17:52:16 PDT Date: Tue, 28 Jun 88 17:52:16 PDT From: Jon L White Message-Id: <8806290052.AA09433@bhopal.lucid.com> To: cperdue@sun.com Cc: ELIOT@cs.umass.edu, Moon@stony-brook.scrc.symbolics.com, common-lisp@sail.stanford.edu In-Reply-To: Cris Perdue's message of Fri, 24 Jun 88 18:17:23 PDT <8806250117.AA09741@clam.sun.com> Subject: #. re: . . . Really, there is a need for users to able to define their own types, *including* syntax for reading them in. Once I start thinking of user-defined syntax, #. starts looking more attractive again. I.e., as a "cop out"? Shades of YACC and LEX! -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 28 Jun 88 15:10:31 EDT Received: from msr.epm.ornl.gov (MILNETH.ORNL.GOV) by SAIL.Stanford.EDU with TCP; 28 Jun 88 11:50:50 PDT Received: by msr.epm.ornl.gov (5.51/4.9) id AA16545; Tue, 28 Jun 88 14:50:18 EDT Date: Tue, 28 Jun 88 14:50:18 EDT From: pjo@msr.EPM.ORNL.GOV (Pedro Otaduy) Message-Id: <8806281850.AA16545@msr.epm.ornl.gov> To: common-lisp@sail.stanford.edu Subject: please subscribe this worthless person to the mail list... thanks!  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 27 Jun 88 18:59:08 EDT Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 27 Jun 88 15:47:44 PDT Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0) id AA04567; Mon, 27 Jun 88 15:46:13 PDT Received: from clam.sun.com by snail.sun.com (4.0/SMI-3.2) id AA03142; Mon, 27 Jun 88 15:41:54 PDT Received: by clam.sun.com (3.2/SMI-3.2) id AA11771; Mon, 27 Jun 88 15:48:53 PDT Date: Mon, 27 Jun 88 15:48:53 PDT From: cperdue@Sun.COM (Cris Perdue) Message-Id: <8806272248.AA11771@clam.sun.com> To: KMP@STONY-BROOK.SCRC.Symbolics.COM Subject: Re: Issue: STACK-LET (Version 1) Cc: Common-Lisp@SAIL.Stanford.EDU > * I sometimes get more results by suggesting something overly conservative > and letting people suggest that it's not right or not enough than I do by > suggesting originally the thing in full blown form. The latter strategy > often gets me not taken seriously, whereas the first strategy offers a > foot in the door to people who readily grasp the concepts of the stripped > down proposal and who might after admitting the topic for discussion still > arrive at the same position as I'd have originally wanted to propose. Whoah up, here. We'd better watch what we do, or we could get into a nontechnical intellectual discussion here. (Thanks Kent for the thoughts.) -Cris  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 27 Jun 88 16:54:27 EDT Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 27 Jun 88 13:38:24 PDT Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0) id AA01974; Mon, 27 Jun 88 13:36:34 PDT Received: from lukasiewicz.sun.com by snail.sun.com (4.0/SMI-3.2) id AA28150; Mon, 27 Jun 88 13:32:21 PDT Received: by lukasiewicz.sun.com (4.0/SMI-4.0) id AA21955; Mon, 27 Jun 88 13:38:40 PDT Date: Mon, 27 Jun 88 13:38:40 PDT From: jrose@Sun.COM (John Rose) Message-Id: <8806272038.AA21955@lukasiewicz.sun.com> To: KMP@STONY-BROOK.SCRC.Symbolics.COM Cc: Common-Lisp@SAIL.Stanford.EDU In-Reply-To: Kent M Pitman's message of Mon, 27 Jun 88 14:37 EDT <880627143734.6.KMP@RIO-DE-JANEIRO.SCRC.Symbolics.COM> Subject: Issue: STACK-LET (Version 1) ... It is always permissible for STACK-LET to behave like LET. Its use is merely advice to an implementation about the use of a variable which might not otherwise be provable. ... It would also be possible to unify this proposal with REST-ARGUMENT-EXTENT. The technique would be to allow (LET ((X (LIST ...))) (DECLARE (DYNAMIC-EXTENT X)) ...) to be rewritten by the compiler as: (SYSTEM::STACK-LET ((X (LIST ...))) ...) for example. The DYNAMIC-EXTENT declaration is a smaller, cleaner addition than a new STACK-LET special form. It's less of a burden on implementors and users to ignore a declaration than to expand one special form into another. -- John  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 27 Jun 88 16:23:46 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 27 Jun 88 13:05:55 PDT Received: from RIO-DE-JANEIRO.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 425412; Mon 27-Jun-88 16:04:37 EDT Date: Mon, 27 Jun 88 16:04 EDT From: Kent M Pitman Subject: Re: Issue: STACK-LET (Version 1) To: Scott.Fahlman@B.GP.CS.CMU.EDU cc: KMP@STONY-BROOK.SCRC.Symbolics.COM, Common-Lisp@SAIL.Stanford.EDU In-Reply-To: The message of 27 Jun 88 15:40 EDT from Scott.Fahlman@B.GP.CS.CMU.EDU Message-ID: <880627160423.1.KMP@RIO-DE-JANEIRO.SCRC.Symbolics.COM> Date: Mon, 27 Jun 88 15:40:27 EDT From: Scott.Fahlman@B.GP.CS.CMU.EDU Is there any reason, aside from compatibility with the current Symbolics usage, Moon has our vote, not me. I usually leave it to him to evaluate what is good or bad for Symbolics as a company. The extent to which Symbolics usage plays into this is neither more or less than the extent to which any company offering this primitive plays into this. why you prefer (stack-let ((x (list a b c))) ...body ...) to (let ((x (list a b c))) (declare (dynamic-value x)) ... body ) Since the idea is to give advice to the compiler about a specific binding, it seems to me that a declaration would be more consistent with the rest of the language than a new special form. For example, that's how we handle advice about type restrictions. Also, this would allow one to mix dynamic and non-dynamic bindings in the same LET form. -- Scott No really big reason. A couple of little reasons. * In implementations where a related facility (eg, Zetalisp's older WITH-STACK-LIST and WITH-STACK-LIST* primitives) exists, it's easy to write a macro to translate STACK-LET into the other stuff. Whether it's easy to add a declaration depends on how declarations are implemented. * Since some implementations provide STACK-LET and not the modified LET, I thought I'd get stronger support from people who do provide it. People always seem to be more likely to vote for things that involve the least work on their own part. * I was afraid that some people would see this as a hairing up of LET. In retrospect, however, I guess you're right. It could be useful for DO, PROG, etc. if you had the declaration. Note well, however, that it's not useful for any case where the construction form is not lexically apparent to the binding form. Eg, (DEFUN F (X) (DECLARE (DYNAMIC-EXTENT X)) ...) would violate modularity boundaries to optimize (F (LIST 1 2 3)) although I suppose some argument could be made that in block compilation it was ok. By putting it in a STACK-LET form, this issue is made to not come up. * I sometimes get more results by suggesting something overly conservative and letting people suggest that it's not right or not enough than I do by suggesting originally the thing in full blown form. The latter strategy often gets me not taken seriously, whereas the first strategy offers a foot in the door to people who readily grasp the concepts of the stripped down proposal and who might after admitting the topic for discussion still arrive at the same position as I'd have originally wanted to propose. In fact, the modified LET is fine with me. My main criterion is to have something which has the highest likelihood of a yes vote in X3J13.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 27 Jun 88 15:57:01 EDT Received: from SEF1.SLISP.CS.CMU.EDU by SAIL.Stanford.EDU with TCP; 27 Jun 88 12:42:12 PDT Received: from SEF1.SLISP.CS.CMU.EDU by SEF1.SLISP.CS.CMU.EDU; 27 Jun 88 15:40:52 EDT To: Kent M Pitman cc: Common-Lisp@SAIL.Stanford.EDU Subject: Re: Issue: STACK-LET (Version 1) In-reply-to: Your message of Mon, 27 Jun 88 14:37:00 -0400. <880627143734.6.KMP@RIO-DE-JANEIRO.SCRC.Symbolics.COM> Date: Mon, 27 Jun 88 15:40:27 EDT From: Scott.Fahlman@B.GP.CS.CMU.EDU Is there any reason, aside from compatibility with the current Symbolics usage, why you prefer (stack-let ((x (list a b c))) ...body ...) to (let ((x (list a b c))) (declare (dynamic-value x)) ... body ) Since the idea is to give advice to the compiler about a specific binding, it seems to me that a declaration would be more consistent with the rest of the language than a new special form. For example, that's how we handle advice about type restrictions. Also, this would allow one to mix dynamic and non-dynamic bindings in the same LET form. -- Scott  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 27 Jun 88 14:54:24 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 27 Jun 88 11:38:03 PDT Received: from RIO-DE-JANEIRO.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via INTERNET with SMTP id 425330; 27 Jun 88 14:37:47 EDT Date: Mon, 27 Jun 88 14:37 EDT From: Kent M Pitman Subject: Issue: STACK-LET (Version 1) To: Common-Lisp@SAIL.Stanford.EDU Message-ID: <880627143734.6.KMP@RIO-DE-JANEIRO.SCRC.Symbolics.COM> Issue: STACK-LET References: None Category: ADDITION Edit history: 27-Jun-88, Version 1 by Pitman Related-Issues: REST-ARGUMENT-EXTENT Status: For Internal Discussion Problem Description: Sometimes a programmers knows that a particular data structure will have only dynamic extent. In some implementations, it is possible to allocate such structures in a way that will make them easier to reclaim than by general purpose garbage collection (eg, on the stack or in some temporary area). Currently, however, there is no way to request the use of such an allocation mechanism. Proposal (STACK-LET:NEW-MACROS): Introduce the new macros: STACK-LET bindings &BODY forms [Macro] STACK-LET* bindings &BODY forms [Macro] Like LET and LET*, but the objects which are the initial values of the variables in the binding list have only dynamic extent. For each initial binding, the form is macroexpanded (as if by MACROEXPAND-1) until either no further macro expansion is possible or a form which is recognized by STACK-LET is seen. For example: (CONS x y) permits STACK-LET to allocate a cons on the stack. (LIST x y z) permits STACK-LET to allocate a list on the stack. (LIST* x y z) permits the first two conses of the resulting list to be allocated on the stack. (MAKE-ARRAY ...) permits an array to be allocated on the stack. (MAKE-xxx ...) where MAKE-xxx is a defstruct constructor permits the structure type to be allocated on the stack. Note that an initial value form of (LIST X Y) is not the same as (CONS X (LIST Y)) since STACK-LET may arrange for two cells of the former to be stack-allocated, and only one cell of the latter (the one created by CONS). Note further that in (LIST (LIST 1 2) 3), only the top level list (the one containing a cons and 3) may be stack allocated. The list (1 2) must be allocated normally. It is always permissible for STACK-LET to behave like LET. Its use is merely advice to an implementation about the use of a variable which might not otherwise be provable. Test Case: (STACK-LET ((X (LIST 1 2 3))) (PRINT X) NIL) prints (1 2 3) Rationale: It permits a programmer to offer advice to an implementation about what may be stack-allocated for efficiency. It may be difficult or impossible for a compiler to infer this same information statically. Since a number of implementations offer this capability and there is demand from users for access to the capability, this ``codifies existing practice.'' Current Practice: Symbolics Genera and Symbolics Cloe offer this extension. Cost to Implementors: No cost is forced since implementations are permitted to treat STACK-LET and STACK-LET* as LET and LET*, respectively. Cost to Users: None. This change is upward compatible. Cost of Non-Adoption: Some portable code would be forced to run more slowly (due to GC overhead), or to use non-portable primitives. Benefits: The cost of non-adoption is avoided. Aesthetics: This primitive allows a fairly low level optimization to work by asking the user to provide only very high level information. The alternatives (sharpsign conditionals, some of which may lead to more bit-picky abstractions) are far less aesthetic. Discussion: It would also be possible to unify this proposal with REST-ARGUMENT-EXTENT. The technique would be to allow (LET ((X (LIST ...))) (DECLARE (DYNAMIC-EXTENT X)) ...) to be rewritten by the compiler as: (SYSTEM::STACK-LET ((X (LIST ...))) ...) for example. Pitman supports the STACK-LET:NEW-MACROS. A better name might be chosen, but since some existing dialects use this name, the name STACK-LET was suggested in an attempt to not be gratuitously incompatible. (Also, the name DYNAMIC-LET, which might seem more intuitive, is in use in other dialects to mean that a dynamic variable is being bound, not that a lexical variable is being bound to a dynamic object. It might, therefore, be confusing to recycle that name here.)  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 25 Jun 88 14:39:37 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 25 Jun 88 11:26:45 PDT Received: from EUPHRATES.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 424628; Sat 25-Jun-88 14:26:28 EDT Date: Sat, 25 Jun 88 14:26 EDT From: David A. Moon Subject: Source code analysis tools To: Common-Lisp@SAIL.STANFORD.EDU File-References: AI.AI.MIT.EDU: MOON; ANNOTA >, AI.AI.MIT.EDU: MOON; MAPFOR >, AI.AI.MIT.EDU: MOON; MAPFEX >, AI.AI.MIT.EDU: MOON; SUBST >, AI.AI.MIT.EDU: MOON; TEMPLA > Message-ID: <19880625182620.5.MOON@EUPHRATES.SCRC.Symbolics.COM> Recently there have been some renewed inquiries about the source code analysis tools I wrote five years ago. I've reconstructed these as best I was able and placed them in the files referenced in the header of this message. These files can be retrieved by anonymous FTP. These tools are freely available to anyone and can be used for any purpose. For example, Symbolics have incorporated an improved version of the tools into their product. You can port these into any Common Lisp that has LOOP if you tweak a few things. They are missing full support for lexical scoping (principally FLET) and stylistically suffer from excessive attention to minimization of consing. However they may be useful as a guidepost or as a source of ideas. Certainly the interface is more worthwhile than the implementation. I regret that I cannot provide any support or documentation (beyond what is included in the files themselves) for these tools. They are provided as-is and I have not even tested them. I'll answer a reasonable number of questions, if sent by electronic mail, as best I can.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 24 Jun 88 21:32:25 EDT Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 24 Jun 88 18:16:45 PDT Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0) id AA03073; Fri, 24 Jun 88 18:14:40 PDT Received: from clam.sun.com by snail.sun.com (4.0/SMI-3.2) id AA26600; Fri, 24 Jun 88 18:10:34 PDT Received: by clam.sun.com (3.2/SMI-3.2) id AA09741; Fri, 24 Jun 88 18:17:23 PDT Date: Fri, 24 Jun 88 18:17:23 PDT From: cperdue@Sun.COM (Cris Perdue) Message-Id: <8806250117.AA09741@clam.sun.com> To: edsel!jonl@labrea.stanford.edu Subject: Re: #. Cc: ELIOT@cs.umass.edu, Moon@stony-brook.scrc.symbolics.com, common-lisp@sail.stanford.edu > Thus while #. could be viewed as an adequate escape mechanism, it certainly > couldn't be part of a general interchange language. I have no very strong objections to special syntax for hash tables. The same argument for special syntax does apply to other objects including pathnames (for which Lucid (+ others) have the #P syntax), readtables, and random-states. Really, there is a need for users to be able to define their own types, *including* syntax for reading them in. Once I start thinking of user-defined syntax, #. starts looking more attractive again. -Cris  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 24 Jun 88 20:26:22 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 24 Jun 88 17:08:57 PDT Received: by labrea.stanford.edu; Fri, 24 Jun 88 17:08:56 PDT Received: from bhopal.lucid.com by edsel id AA08136g; Fri, 24 Jun 88 16:56:18 PDT Received: by bhopal id AA19214g; Fri, 24 Jun 88 16:56:00 PDT Date: Fri, 24 Jun 88 16:56:00 PDT From: Jon L White Message-Id: <8806242356.AA19214@bhopal.lucid.com> To: cperdue@sun.com Cc: ELIOT@cs.umass.edu, Moon@stony-brook.scrc.symbolics.com, common-lisp@sail.stanford.edu In-Reply-To: Cris Perdue's message of Fri, 17 Jun 88 10:16:38 PDT <8806171716.AA01554@clam.sun.com> Subject: #. re: > (I don't count #.(make-hash-table...) because it's so gross.) . . . I would like to add my agreement to David Moon's statement. With the #. readmacro you don't have to learn extra syntax to understand the printed representation, and it is nothing if not adequately general. Let's just say that it is "nothing". The problem with #. is precisely that it is not syntax; rather, it is an "out" where the designers of the language failed to come up with a syntax. To see this more clearly, consider writing a trivial C program to read in "simple" Lisp expressions into equivalent data structures of the C world. Parsing is no real problem [maybe could even be yacc'd away], INTERNing of symbols is just a table lookup, numbers is numbers [hey, even C can do fixnums and floats!], defstructs can be structs, strings are strings, and so on; cons cells etc. can be cut out of mallocated space, and pointer-type variables make it easly to link things together. But there is no reasonable equivalent for the #. requirements -- no matter how trivial the data-type returned, it implies the existence of a Lisp EVALuator just to parse-&-build the representation. That's a LOT to require for merely constructing up some simple data structures. Thus while #. could be viewed as an adequate escape mechanism, it certainly couldn't be part of a general interchange language. And yet the hard problems are not limited to the "interchange" cases. Consider file-processors other than LOAD or COMPILE-FILE (such as the cross-reference program described by Tom Gruber in the first issue of Lisp Pointers). Such a processor will want to READ a file of Lisp code, but not necessarily evaluate anything in it. How will it react to the file [named, say "/u/loser/trojan-horse.lisp"]: (defun gift-horse (x) #.(progn (punch-paper-tape) (delete-all-user-files) (logout) 'x)) -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 24 Jun 88 20:02:42 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 24 Jun 88 16:47:22 PDT Received: by labrea.stanford.edu; Fri, 24 Jun 88 16:46:48 PDT Received: from bhopal.lucid.com by edsel id AA08086g; Fri, 24 Jun 88 16:40:19 PDT Received: by bhopal id AA18154g; Fri, 24 Jun 88 16:39:58 PDT Date: Fri, 24 Jun 88 16:39:58 PDT From: Jim McDonald Message-Id: <8806242339.AA18154@bhopal.lucid.com> To: edsel!jonl@labrea.stanford.edu Cc: common-lisp@sail.stanford.edu, cl-cleanup@sail.stanford.edu In-Reply-To: Jon L White's message of Fri, 24 Jun 88 14:38:13 EST <8806242138.AA16670@bhopal.lucid.com> Subject: EQUAL My concern about having EQUAL descend structures and arrays is that they are much more likely than lists to be circular. Typically, a list is created after its elements, whereas a structure or array is created before its elements. (*Typically*, not always!) As a rule of thumb, I'd bet that less than .0001% of all lists are circular, and that less than 1% of all arrays are circular, but only that less than 30% of all structures are circular. I think there is a tendancy to include fields like CHILDREN and PARENTS, or PREVIOUS and NEXT, etc. in structures, which are thus almost guaranteed to be circular. In fact, when I'm creating circular data I tend to think first of using structures, because I am then less likely to get screwed by EQUAL, etc. I don't have time now to think through the algorithmic details, but maybe DEFSTRUCT could let you specify that specific slots are "back-pointers". Then EQUAL could record them when descending and perform a more sophisticated comparison than it would for all other pointers. Thus you would only pay at runtime for the specific complications you did introduce, not those you might have. Making backpointers explicit might help human readability as well. [As something of an aside, I think you should also be able to specify *print-level* and *print-length* for specific structure fields, to avoid losing on some fields when trying to see others.] jlm  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 24 Jun 88 19:33:46 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 24 Jun 88 16:14:24 PDT Received: by labrea.stanford.edu; Fri, 24 Jun 88 16:14:19 PDT Received: from bhopal.lucid.com by edsel id AA07969g; Fri, 24 Jun 88 16:02:57 PDT Received: by bhopal id AA17926g; Fri, 24 Jun 88 16:02:36 PDT Date: Fri, 24 Jun 88 16:02:36 PDT From: Jon L White Message-Id: <8806242302.AA17926@bhopal.lucid.com> To: RWK@ai.ai.mit.edu, NGALL@g.bbn.com Cc: common-lisp@sail.stanford.edu, goldman@vaxa.isi.edu In-Reply-To: "Robert W. Kerns"'s message of Mon, 13 Jun 88 02:31:18 EDT <396377.880613.RWK@AI.AI.MIT.EDU> Subject: constant folding/smashing re: Date: Mon, 13 Jun 88 02:31:18 EDT From: "Robert W. Kerns" . . . [jonl: Symbols are atomic, and don't have 'components'] . . . [rwk:] (SETF (SYMBOL-VALUE 'X) 1) is the same as (SETQ X 1), for X being special. The X in either piece of code is a REFERENCE to a non-constant object, shared between occurrances of read. It is a PUBLIC structure published by INTERN. Modifications to its value cell are modifications to the global variable environment. They're already EQified as much as makes sense. If you had quoted my full message to which you are replying, there would have been a reference to the several implemtations of Common Lisp that do not implement special variables via a "component, value-cell". It was the explicit intent of the authors of CLtL that "deep binding" schemes not be proscribed; your description quoted just above is a model for a shallow- binding implementation. As moon has also pointed out, one should not mistake the accidents of a paritcular implementation for the underlying semantics of a construct. Now, I will admit that Lisp'ers frequently speak of a symbol's value-cell, or it's function cell; but this is language rooted in a now outdated past. It's ok to use that language, so long as everyone understands that there need not be an actual record structure with such components in it. Remember in VAX/NIL how the only implementation component was a "multiplex" cell, which would lazily create an auxiliary four-component data structure when necessary? The term "value-cell" in that implementation was merely a shorthand for a much more complex implementational scheme. re: Date: 13 Jun 1988 18:50-EDT Sender: NGALL@G.BBN.COM . . . If you want to suggest that the interpreter should be changed to make QUOTE return a RO-EQUAL-copy of its arg when possible*** (as I think JonL may have been suggesting?), then consider what a pain it will cause at the top-level: > (setf foo '(1 2 3)) (1 2 3) > (push 0 foo) >>>>> Error ... First off, you should re-examine the semantics of PUSH -- I think you will find that it modifies the value of the variable FOO rather than the quoted data structure of your example. In virtually every implementation of CL, (macroexpand-1 '(push 0 foo)) ==> (setq foo (cons 0 foo)) You may also want to remember the potential for read-only objects [which I think I discussed in a previous note -- Interlisp-D had read-only strings?]. I suppose it would almost be an acceptable implementation of QUOTE to make it's "argument" be a read-only object (when possible), rather than returning a non-EQ-but-EQUAL read-only copy; but I dislike this approach since it requires modifying the data-structure representing the program during the running of the program itself. re: All QUOTE can do [is] to cons in RO-space an EQUAL COPY of its argument and return that copy. But there is NO SUCH THING as an EQUAL "COPY" of a hashtable. It doesn't matter that its gross, it just won't work. If you are referring to my "canonicalization" version of QUOTE, you should recall that two "quoted" constants were coalesced *not* when they were EQUAL, but under a more permissive predicate. It is not an EQUAL copy that one wants, but an "equivalent" one. There are such things as "coalescable" hash-tables, and they work quite well in Lucid Common Lisp; I described their use in my note to Eliot dated Sat, 11 Jun 88 17:46:49 PDT. -- JonL -- P.S.: That the "push" typo/braino should go unnoticed so long suggests that no one else is really reading these interchanges. If anyone on the mailing list feels they are not useful interchanges (and is actually reading this post-script!), he should speak up now!  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 24 Jun 88 19:15:42 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 24 Jun 88 15:52:08 PDT Received: by labrea.stanford.edu; Fri, 24 Jun 88 15:52:02 PDT Received: from bhopal.lucid.com by edsel id AA07541g; Fri, 24 Jun 88 14:38:25 PDT Received: by bhopal id AA16670g; Fri, 24 Jun 88 14:38:05 PDT Date: Fri, 24 Jun 88 14:38:05 PDT From: Jon L White Message-Id: <8806242138.AA16670@bhopal.lucid.com> To: RWK@ai.ai.mit.edu Cc: edsel!jlm@labrea.stanford.edu, common-lisp@sail.stanford.edu, cl-cleanup@sail.stanford.edu In-Reply-To: "Robert W. Kerns"'s message of Mon, 13 Jun 88 02:05:15 EDT <396357.880613.RWK@AI.AI.MIT.EDU> Subject: EQUAL [apologies for so late a reply -- have been out of town for over a week] Jim's point about the historical reference of EQUAL seemed to me to be that it was made to work for the datatypes that were "in common use" in the Lisps of that day, namely the datatypes necessary for writing programs in the Lisp language. Hence, conses, symbols, numbers, maybe strings, and not much else. However, I certainly wouldn't expect anything productive to come from a discussion on how to determine whether two programs/functions *really* are "equal"! Possibly you took MacDonald's argument to an extreme that he didn't originally intend? What would be the objections to extending EQUAL to accommodate the serious modern datatypes of Common Lisp? in particular: (1) Do component-wise EQUAL comparisons on arrays [this implies "descent" for pointer arrays]. Unlike with EQUALP, the arrays must be of the same type, but the presence of fill-pointers, array-element-type "upgrading", adjustability, and displacement may require some refinements of this clause. (2) Descend defstructs, except possibly for "system" defstructs that are built-in by the implementation [i.e., an implementation can use defstruct to implement a STREAM, but impose a "private" definition of EQUAL for streams; probably same for all types discussed in the cleanup issue TYPE-HIERARCHY-UNDERSPECIFIED]. Possibly extend defstruct to admit an option :equal, similar to the :copier option, but this isn't a critical requirement now. (3) Require that EQUAL be a "generic" function, so that CLOS methods can be written for it; likely, the "default" method for non-built-in classes would be some sort of error, meaning that mindless descent isn't a good default. By analogy with defstructs, you can compare two defstuct-instances of the same type with the :equal functions, and you could only compare two clos instances for which there is an appropriate EQUAL method supplied. This definition would imply that hashtables of :type EQUAL will operate in the manner expected by so many users of Common Lisp. Somehow, people have been lured into thinking that this is already the current practice; but of course something much more limiting is the current state. Finally, I might point out that recent discussions about EQUALP seem to have overlooked it's variations on numerical equality and array-type indifference. Extending EQUAL to descend structures is *not* the same as retracting EQUALP to be case-sensitive. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 23 Jun 88 15:08:09 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 23 Jun 88 11:44:24 PDT Received: from relay2.cs.net by RELAY.CS.NET id ad08061; 23 Jun 88 12:54 EDT Received: from cs.umass.edu by RELAY.CS.NET id dl18009; 23 Jun 88 12:41 EDT Date: Thu, 23 Jun 88 11:21 EDT From: ELIOT@cs.umass.edu Subject: constant smashing To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.EDU" >From: IN%"NGALL@G.BBN.COM" 17-JUN-1988 07:02 >Subj: Re: Constant Smashing > > From: ELIOT@cs.umass.edu > > ... > Further supporting the idea that a general mechanism apart from QUOTE > is required to properly support read-only data structures, if read > only data becomes a Common Lisp concept. > >Agreed. > ... > > (defun foo () > > '(a b c)) > > > > Really means > > > > (defun foo () > > G00047) > > (setq G00047 '(a b c)) > > >What IS mutable (which neither def. suggests strongly enough) is >the list itself. Again this suggests a different notation for RO is >needed. THAT is my point. In particular def. 1 does not suggest it strongly enough for it to be a reasonable interpretation. In fact, def. 1 strongly suggests that it will always return (A B C). The source code makes this reading so natural that I think it must be chosen as the defined semantics, regardless of the context that FOO is executed in. It is completely unnatural to allow some other function to reach out of nowhere and dig around in the guts of FOO resulting in changes to its behavior. Intentionally modifying a quoted constant does not provide any functionality that cannot be achieved using a global variable. The global variable can be encapsulated in a lexical closure to make its use even clearer. This easilly produces the same effects and the code will more closely approximate its true intention. >> >> >It is also the >> >semantics of all (?) CL interpreters. QUOTE MUST have the same >> >behavior in the compiler and the interpreter. To do otherwise is to >> >introduce a compiler/interpreter incompatibility as confusing and >> >error-prone as the SPECIAL variable incompatibility used to be. Agreed? >> >>No. QUOTE must have the same *semantics* in the compiler and >>interpreter. >I was unclear. I meant that the compiler and >interpreter must BEHAVE identically. My point is a pedagogical one: >people learn lisp in the interpreter. Textbooks use (and motivate) >QUOTE as if ALL that it does it to prevent evaluation and interpreters >support this model. I feel would not be sufficient for CLtL to merely >state that "it is an error" to modify the arg of QUOTE and enforce in >in the compiler but not the interpreter. This is what leads to the >continual confusion of neophytes. (1) If Common Lisp does not specify the behavior in some case an implementation is free to do anything at all. It could be said that Common Lisp will "Signal an error if any attempt is made to modify a quoted constant" and then the compiler/interpreter would have to behave identically. Since this is not practical for all implementations the phase "It is an error" must be used instead. (2) Textbooks can only be granted limited authority over *proposed* changes. If Common Lisp changes or gets clarified then the textbooks will have to be updated. Otherwise the situation is a little like having the tail wag the dog. (3) You can't learn *any* portable language by experimenting with it if any part of the specification is incomplete. Experimentation shows the behavior of the *implementation* but cannot distinguish between the core language and its extensions. Before Common Lisp the implementation was the specification, so this was not a problem. In the future textbooks and teaching material must emphasize the difference, and provide cautions about assuming trusting experimentally revealed behavior. If it is not DOCUMENTED then you can't trust it. > > In the case of QUOTE some errors might go undetected. This is not good, > but it is not as dangerous a flaw as the SPECIAL variable problem, > which is characterized by different compiled/interpreted behavior > where neither behavior draws attention to the actual source of the > problem. It is relatively straightforward to debug a problem that > causes the debugger to freeze execution near the actual cause. > >Three: 1) What if the the RO-ness of the object was the bug. >Finding the source of the object could be very difficult. One measure of bug "complexity" is how much of the actual cause of the bug (code or data) will be "obvious" when the bug occurs. Wrong numbers might have come from anywhere, so they can be very hard to debug. RO-ness will at least cause the debugger to point at the data structure that is involved, but probably not the code. Thus, at worst, it would be classified as a medium difficult bug. >2) I have >heard from at least 2 lisp implementors (on stock harware) that they >will not enforce the RO-ness of a QUOTEd object until system build >time, not compile time! It takes us over an hour to build our system. >What a debug cycle! :-) Patching avoids the need to go all the way around the debug cycle. >[Actually this brings up the general issue of >a third kind of "code": interpreted, compiled, and "built".] 3) Its >not the debugging difficulty alone that bothers me, it is mere >difference in behavior between the compiler and interpreter in a very >common case. To rationally decide if a difference is "reasonable" requires something like a cost/benefit analysis. The benefit is measured in terms of efficieciency and simplicify of the implementation. What measures the cost? It must be a combination of the likelihood that a bug will come of it, and the difficulty of finding the bug. So I claim that you *should* be primarilly concerned with the difficulty of finding the bug that *should* determine if the mere difference alone is bothersome. > > To support this argument I must make one more claim. I must claim that > compiling a function produces a *new* function definition that is > semantically equivalent to the old one, but it does not have to > be composed of the 'same' forms. >Agreed. > This is because of the definition of > CONSTANTP on p.324 (CLtL) which (in my reading) implies (eq (foo) (foo)) > when FOO is defined as above. [Because of (constantp (quote a b c))] > >Disagree. CONSTANTP uses the vague expression "evaluate to the same >thing". Which version of SAME is it talking about? EQ EQL or EQUAL >Can't be EQ since CONSTANTP is true of numbers. I claim SAME means >EQUAL, because of CLtLs EQUAL constant collapsing which IN THEORY >allows QUOTE to cons an EQUAL copy of its argument each time the QUOTE >form is evaluated. (As my pseudo-definition of QUOTE stated in a >previous message.) I assumed that SAME meant EQL. Obviously that should be clarified. I never heard of CONSTANTP before, so I speak from experience: none of it. > Therefore: [1] > (eq (foo) (foo)) => T > (setq x (foo)) > (compile 'foo) [2] > (eq x (foo)) => Ambiguous [3] > (eq (foo) (foo)) => T > >No. (eq (foo) (foo)) => Ambiguous. This is why I want to flush EQUAL >constant collapse from CLtL. I want it to be T. I agree that [1] & [3] *should* be T, especially if EQL is substituted for EQ. I don't care about EQUAL constant collapse, but it seems harmless if you accept RO. > > And no identity holds accross the act of compilation. Chris Eliot  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 20 Jun 88 15:55:43 EDT Received: from gremlin.nrtc.northrop.com by SAIL.Stanford.EDU with TCP; 20 Jun 88 12:37:05 PDT Received: from tribble by gremlin.nrtc.northrop.com id a018817; 20 Jun 88 12:22 PDT To: Sandra J Loosemore cc: common-lisp@sail.stanford.EDU, cl-compiler@sail.stanford.EDU, jbarnett@gremlin.nrtc.northrop.COM Subject: Re: #, read macro In-reply-to: Your message of Sun, 19 Jun 88 18:15:25 -0600. <8806200015.AA01138@cs.utah.edu> Date: Mon, 20 Jun 88 12:22:53 -0700 From: jbarnett@gremlin.nrtc.northrop.COM One use of this construct is to simulate ALGOL-like OWN variables; to wit: (defun foo (arg ... &aux (var '#,)) body that references var...) where the is computed in terms of previously defined defvars, defuns, etc., and you don't want to create yet another only-used-in one-place special variable, e.g., (defvar *foos-own* ) (defun foo (args ...) body that reference *foos-own* insteadof var...) By the way, there's not much use to trying to clean up the use of #, until you do a better job of defining EVAL-WHEN (or whatever you call it now). If you do that properly, not only will #, be easy to understand, implement, and use, but I'd guess that several natural and useful extentions will occur. Jeff  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 20 Jun 88 13:18:56 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 20 Jun 88 10:06:29 PDT Return-Path: Received: from sauron.think.com by Think.COM; Mon, 20 Jun 88 13:11:08 EDT Received: from OCCAM.THINK.COM by sauron.think.com; Mon, 20 Jun 88 13:11:05 EDT Date: Mon, 20 Jun 88 13:03 EDT From: Barry Margolin Subject: #, read macro To: Christopher Maeda Cc: sandra@cs.utah.edu, common-lisp@sail.stanford.edu, cl-compiler@sail.stanford.edu, bug-cyc@mcc.com In-Reply-To: <19880620065222.1.MAEDA@PELE.ACA.MCC.COM> Supersedes: <19880620170243.2.BARMAR@OCCAM.THINK.COM> Message-Id: <19880620170302.3.BARMAR@OCCAM.THINK.COM> Date: Mon, 20 Jun 88 01:52 CDT From: Christopher Maeda We are implementing a frame system where each frame is a defstruct. We use a reader macro to reference case sensitive frame names, permitting the frame namespace to be disjoint from the symbol namespace. The reader macro also lets us hook into a completion package that is very handy for longer names. I would be interested in hearing what alternatives the cleanup committee is considering. Being able to dispatch to an arbitrary read function is hard to beat. --Chris No one is talking about removing reader macros in general. We are considering removing the "#," reader macro. "#," is a relatively obscure cousin of "#."; it causes the form following it to be evaluated at load time rather than at read time as "#." does. To see how it currently works, put the following definition in a file: (defun sharp-comma-example () (quote #,*sharp-comma-var*)) Compile the file, type (setq *sharp-comma-var* 'a), then load the binary file. Then type (setq *sharp-comma-var* 'b) and (sharp-comma-example). It should return A. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 20 Jun 88 03:08:06 EDT Received: from MCC.COM by SAIL.Stanford.EDU with TCP; 19 Jun 88 23:55:38 PDT Received: from PELE.ACA.MCC.COM by MCC.COM with TCP/SMTP; Mon 20 Jun 88 01:53:45-CDT Date: Mon, 20 Jun 88 01:52 CDT From: Christopher Maeda Subject: #, read macro To: sandra@cs.utah.edu, common-lisp@sail.stanford.edu, cl-compiler@sail.stanford.edu cc: bug-cyc@MCC.COM In-Reply-To: <8806200015.AA01138@cs.utah.edu> Message-ID: <19880620065222.1.MAEDA@PELE.ACA.MCC.COM> We are implementing a frame system where each frame is a defstruct. We use a reader macro to reference case sensitive frame names, permitting the frame namespace to be disjoint from the symbol namespace. The reader macro also lets us hook into a completion package that is very handy for longer names. I would be interested in hearing what alternatives the cleanup committee is considering. Being able to dispatch to an arbitrary read function is hard to beat. --Chris  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 19 Jun 88 20:26:09 EDT Received: from cs.utah.edu by SAIL.Stanford.EDU with TCP; 19 Jun 88 17:17:02 PDT Received: by cs.utah.edu (5.54/utah-2.0-cs) id AA01138; Sun, 19 Jun 88 18:15:26 MDT From: sandra@cs.utah.edu (Sandra J Loosemore) Message-Id: <8806200015.AA01138@cs.utah.edu> Date: Sun, 19 Jun 88 18:15:25 MDT Subject: #, read macro To: common-lisp@sail.stanford.edu, cl-compiler@sail.stanford.edu One of the items currently before the X3J13 compiler cleanup subcommittee is tightening up the definition of how the #, (sharp-sign comma) read macro should work, and where it may legitimately appear in code to be compiled. We are considering (among other options) removing it from Common Lisp entirely. Since this would clearly be an incompatible change to the language, we would like to hear from people who actually use #, to find out how it is being used and whether some other technique(s) couldn't be used to solve the same problems. Please send replies on this subject to cl-compiler@sail.stanford.edu. -Sandra -------  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 17 Jun 88 13:34:11 EDT Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 17 Jun 88 10:17:17 PDT Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0) id AA17871; Fri, 17 Jun 88 10:13:58 PDT Received: from clam.sun.com by snail.sun.com (4.0/SMI-3.2) id AA03167; Fri, 17 Jun 88 10:10:15 PDT Received: by clam.sun.com (3.2/SMI-3.2) id AA01554; Fri, 17 Jun 88 10:16:38 PDT Date: Fri, 17 Jun 88 10:16:38 PDT From: cperdue@Sun.COM (Cris Perdue) Message-Id: <8806171716.AA01554@clam.sun.com> To: ELIOT@cs.umass.edu, Moon@STONY-BROOK.SCRC.Symbolics.COM Subject: Re: constant folding/smashing Cc: common-lisp@SAIL.STANFORD.EDU > (I don't count #.(make-hash-table...) because it's so gross.) > > I object to the characterization of doing something through the normal > syntax, instead of inventing a special weird syntax that people have > to learn as a special case, as "gross." > I would like to add my agreement to David Moon's statement. With the #. readmacro you don't have to learn extra syntax to understand the printed representation, and it is nothing if not adequately general.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 16 Jun 88 13:29:48 EDT Received: from cs.utah.edu by SAIL.Stanford.EDU with TCP; 16 Jun 88 10:16:37 PDT Received: by cs.utah.edu (5.54/utah-2.0-cs) id AA09783; Thu, 16 Jun 88 11:15:22 MDT Received: by cons.utah.edu (5.54/utah-2.0-leaf) id AA10799; Thu, 16 Jun 88 11:15:20 MDT Date: Thu, 16 Jun 88 11:15:20 MDT From: kessler%cons@cs.utah.edu (Robert R. Kessler) Message-Id: <8806161715.AA10799@cons.utah.edu> To: common-lisp@sail.stanford.edu Subject: More on L&FP Registration Forms According to the US Post Office, 16,000 pieces were mailed on May 10... (the rest that had to go overseas and first class were mailed before that). Sigh.... Bob.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 16 Jun 88 13:26:25 EDT Received: from cs.utah.edu by SAIL.Stanford.EDU with TCP; 16 Jun 88 10:04:33 PDT Received: by cs.utah.edu (5.54/utah-2.0-cs) id AA09090; Thu, 16 Jun 88 11:03:06 MDT Received: by cons.utah.edu (5.54/utah-2.0-leaf) id AA10764; Thu, 16 Jun 88 11:02:58 MDT Date: Thu, 16 Jun 88 11:02:58 MDT From: kessler%cons@cs.utah.edu (Robert R. Kessler) Message-Id: <8806161702.AA10764@cons.utah.edu> To: common-lisp@sail.stanford.edu, scheme@sail.stanford.edu Subject: L&FP Registration Forms Apparently many people have not yet received the advance registration forms from ACM. Supposedly, it was sent to all members of SIGPLAN, SIGART, and SIGACT, along with about 250 of the people who attended the 1986 conference (this was supposed to go to over 20,000 people). Anyway, here is a pseudo electronic version of registration form. Please provide ACM with all of this information detailed here. Thanks. Bob. ====================== L&FP 88 Registration Form ==================== The registration fees for applications prior to June 24 are: Student $75 ACM or SIG (PLAN, ART, or ACT) Member Only $250 ACM and SIG Member $225 Non-Member $290 The registration fees for applications after that date are: Student $100 ACM or SIG (PLAN, ART, or ACT) Member Only $300 ACM and SIG Member $275 Non-Member $350 Additional banquet tickets (for students or guests) are $40 Additional luncheon tickets are $12.50 Make your own application form including Your Name Company/Institution Address Telephone E-mail Address Membership status in ACM and SIGPLAN/SIGART/SIGACT including membership number Your fee category (as described above) Your order for any extra banquet or luncheon tickets Total fees enclosed Form of payment (check/credit card) Credit card type (Mastercard, Visa, or Amer Express), number, and signature if paying by credit card Mailing List Restriction: (one of No Restictions, ACM and Other Society Announcements, ACM Announcements) If paying by check, make check payable (in US funds only!) to: ACM LFP '88 Mail your form and payment to: ACM LFP '88 P.O. Box 12105 Church Street Station New York, NY 10249  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 16 Jun 88 00:14:38 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 15 Jun 88 20:56:33 PDT Received: from RIO-DE-JANEIRO.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 420390; Wed 15-Jun-88 23:55:17 EDT Date: Wed, 15 Jun 88 23:55 EDT From: Kent M Pitman Subject: copy To: DALY@ibm.com cc: common-lisp@sail.stanford.edu In-Reply-To: <061588.225242.daly@ibm.com> Message-ID: <880615235500.0.KMP@RIO-DE-JANEIRO.SCRC.Symbolics.COM> Date: 15 Jun 88 22:52:41 EDT From: Timothy Daly Is there some reason why there isn't a general purpose COPY function in common lisp? Tim DALY@IBM.COM This question gets asked a lot. Here's my personal assessment. I suspect the answers will vary widely, though: You don't know how much to copy without understanding the intent of an object. If there were just 1 copy function and you wrote: (COPY '((A . B) . ((C . D) . NIL))) how would you know whether to use COPY-CONS (if there were such a thing), COPY-LIST, or COPY-ALIST? In my opinion, the issues are the same for COPY as they are for EQUAL. We did provide EQUAL but people complain all the time that it doesn't "do the right thing". The truth is that there is no unique right thing in either case. In the case of COPY, whether you've copied enough depends on what parts you consider "the container" and what parts you consider the "contents". Since there can be different views on the same object, no unique function can do the whole job. In the case of EQUAL, the issue is similar. The function you should be calling to determine if two things are "enough alike" (which is pretty much what equal seems to mean to people) really depends on your intended use. I claim that read about EQUAL and then try to invent uses and that's why it always seems to be broken -- because they want minor perturbations around this thing they started from. If we'd not given them something to center their misconceptions around, they would be more likely to just think of equality as an ill-defined (read: application-specific) problem rather than to think that it must be uniquely determined in the absence of an application. Consider having your boss say "Go get me someone who's Sally's equal." It might help to know if he was looking for someone to use on the next important work-related project or someone to substitute on the bowling team tonight. It is not a property of Sue, Bill, or George what EQUAL means; it is a property of the thing you intend to do with them afterward, so (EQUAL SUE SALLY) is not the right thing. Instead, you want (WORK-EQUAL SUE SALLY) and (BOWLING-EQUAL SUE SALLY) and so on. Similarly, if someone was writing something down on a piece of paper and someone asked you to "copy what they were writing", it would help for you to know if they were planning to film your actions, take the copy of what they'd written home to read later, or use your copy as a forgery. Depending on the application, your actions might be very different. The issue of what to do to fix EQUAL is before the cleanup committee and a zillion solutions have been raised. I've suggested that the most reasonable thing is to flush EQUAL but for pragmatic reasons we probably will not. Still, by retaining it, people are left with the sense that EQUAL computes "uniquely determined generic equality" when in fact it computes "often useful but quite arbitrary equality". Perhaps someday someone will add COPY (though I will steadfastly oppose it) but at the very least I hope the documentation will make clear how arbitrary the choice of its action is. Note: It recently occurred to me that saying (EQUAL X Y 'CONS), (EQUAL X Y 'TREE), (EQUAL X Y 'BOWLER), etc. -- that is, adding an "abstract view" argument -- might give us a handle on things. I think people would tend to see this as redundant, and maybe it could even default to (TYPE-OF object). Similarly, (COPY X Y 'CONS), (COPY X Y 'BOWLER), etc. might give you enough information to know what the salient aspects were... Naturally, to be really useful, you'd need to be able to customize the way in which any user-defined type was copied,etc. Anyway, I'm not endorsing this idea, just mentioning it as a thing to be looked at.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 15 Jun 88 23:15:58 EDT Received: from IBM.COM by SAIL.Stanford.EDU with TCP; 15 Jun 88 20:03:54 PDT Date: 15 Jun 88 22:52:41 EDT From: Timothy Daly To: common-lisp@sail.stanford.edu Message-Id: <061588.225242.daly@ibm.com> Subject: copy Is there some reason why there isn't a general purpose COPY function in common lisp? Tim DALY@IBM.COM  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 15 Jun 88 19:38:48 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 15 Jun 88 16:24:19 PDT Return-Path: Received: from sauron.think.com by Think.COM; Wed, 15 Jun 88 19:29:37 EDT Received: from OCCAM.THINK.COM by sauron.think.com; Wed, 15 Jun 88 19:29:31 EDT Date: Wed, 15 Jun 88 19:21 EDT From: Barry Margolin Subject: Constant Smashing To: ELIOT@cs.umass.edu Cc: common-lisp@sail.stanford.edu In-Reply-To: <8806150722.AB20102@Think.COM> Message-Id: <19880615232125.4.BARMAR@OCCAM.THINK.COM> Date: Tue, 14 Jun 88 13:20 EDT From: ELIOT@cs.umass.edu If you agree with what I said about *external* modification of *internal* behavior then it would have to apply to strings, characters etc. also. But the added complexity is negligable, since "Foo" or #\Foo could be treated as (quote "Foo") or (quote #\Foo). Minor nit: Characters do not have mutable components. (let* ((char #\Foo) (char2 char)) (setf (char-code char) (char-code #\Bar)) char2) will return #\Foo, not #\Bar. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 15 Jun 88 11:34:21 EDT Received: from G.BBN.COM ([8.2.0.18]) by SAIL.Stanford.EDU with TCP; 15 Jun 88 08:17:47 PDT Date: 15 Jun 1988 11:15-EDT Sender: NGALL@G.BBN.COM Subject: Re: Constant Smashing From: NGALL@G.BBN.COM To: common-lisp@SAIL.STANFORD.EDU Message-ID: <[G.BBN.COM]15-Jun-88 11:15:54.NGALL> In-Reply-To: The message of Tue, 14 Jun 88 13:20 EDT from ELIOT@cs.umass.edu Date: Tue, 14 Jun 88 13:20 EDT From: ELIOT@cs.umass.edu ... Further supporting the idea that a general mechanism apart from QUOTE is required to properly support read-only data structures, if read only data becomes a Common Lisp concept. Agreed. > (defun foo () > '(a b c)) > > Really means > > (defun foo () > G00047) > (setq G00047 '(a b c)) > I'm not sure the code expresses my point clearly. Functions that return quoted constants are subject to *external* modification of their *internal* behavior. Its likely that you can get accidentally self modifying code. I've seen this cause obscure bugs. I don't think it is intuitive. The source code for the first definition of FOO makes it notationally "obvious" (incorrectly) that FOO always returns the list (A B C). The source code for the second definition makes it notationally clear that there is some global and mutable state involved. I think the 2nd definition is MORE misleading. Yes it does suggest "that there is some global and mutable state involved", but it suggests that the wrong thing is modifiable. By using a special var, it suggests that the reference is mutable. But that is exactly what is CONSTANT (and I claim the ONLY thing that is constant) in the 1st def. What IS mutable (which neither def. suggests strongly enough) is the list itself. Again this suggests a different notation for RO is needed. >It is also the >semantics of all (?) CL interpreters. QUOTE MUST have the same >behavior in the compiler and the interpreter. To do otherwise is to >introduce a compiler/interpreter incompatibility as confusing and >error-prone as the SPECIAL variable incompatibility used to be. Agreed? No. QUOTE must have the same *semantics* in the compiler and interpreter. I was unclear. I meant that the compiler and interpreter must BEHAVE identically. My point is a pedagogical one: people learn lisp in the interpreter. Textbooks use (and motivate) QUOTE as if ALL that it does it to prevent evaluation and interpreters support this model. I feel would not be sufficient for CLtL to merely state that "it is an error" to modify the arg of QUOTE and enforce in in the compiler but not the interpreter. This is what leads to the continual confusion of neophytes. In the case of QUOTE some errors might go undetected. This is not good, but it is not as dangerous a flaw as the SPECIAL variable problem, which is characterized by different compiled/interpreted behavior where neither behavior draws attention to the actual source of the problem. It is relatively straightforward to debug a problem that causes the debugger to freeze execution near the actual cause. Three: 1) What if the the RO-ness of the object was the bug. Finding the source of the object could be very difficult. 2) I have heard from at least 2 lisp implementors (on stock harware) that they will not enforce the RO-ness of a QUOTEd object until system build time, not compile time! It takes us over an hour to build our system. What a debug cycle! :-) [Actually this brings up the general issue of a third kind of "code": interpreted, compiled, and "built".] 3) Its not the debugging difficulty alone that bothers me, it is mere difference in behavior between the compiler and interpreter in a very common case. To support this argument I must make one more claim. I must claim that compiling a function produces a *new* function definition that is semantically equivalent to the old one, but it does not have to be composed of the 'same' forms. Agreed. This is because of the definition of CONSTANTP on p.324 (CLtL) which (in my reading) implies (eq (foo) (foo)) when FOO is defined as above. [Because of (constantp (quote a b c))] Disagree. CONSTANTP uses the vague expression "evaluate to the same thing". Which version of SAME is it talking about? EQ EQL or EQUAL Can't be EQ since CONSTANTP is true of numbers. I claim SAME means EQUAL, because of CLtLs EQUAL constant collapsing which IN THEORY allows QUOTE to cons an EQUAL copy of its argument each time the QUOTE form is evaluated. (As my pseudo-definition of QUOTE stated in a previous message.) Therefore: (eq (foo) (foo)) => T (setq x (foo)) (compile 'foo) (eq x (foo)) => Ambiguous (eq (foo) (foo)) => T No. (eq (foo) (foo)) => Ambiguous. This is why I want to flush EQUAL constant collapse from CLtL. I want it to be T. And no identity holds accross the act of compilation. >If you want to suggest that the interpreter should be changed to make >QUOTE return a RO-EQUAL-copy of its arg when possible*** (as I think JonL >may have been suggesting?), then consider what a pain it will cause at >the top-level: > >> (setf foo '(1 2 3)) >(1 2 3) >> (push 0 foo) >>>>>> Error ... Tsk, Tsk. THAT won't cause an error. You meant: (setf (car foo) 'one)? Yes. Sorry about that. I really meant (push 0 (rest foo)). -- Nick  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 15 Jun 88 04:52:16 EDT Received: from MCC.COM by SAIL.Stanford.EDU with TCP; 15 Jun 88 01:39:53 PDT Received: from BRAHMA.ACA.MCC.COM by MCC.COM with TCP/SMTP; Wed 15 Jun 88 03:38:14-CDT Date: Wed, 15 Jun 88 03:37 CDT From: David Vinayak Wallace Subject: smashed constants To: ELIOT@cs.umass.edu cc: common-lisp@SAIL.STANFORD.EDU In-Reply-To: The message of 14 Jun 88 12:18 CDT from ELIOT@cs.umass.edu Message-ID: <880615033739.2.GUMBY@BRAHMA.ACA.MCC.COM> Date: Tue, 14 Jun 88 13:18 EDT From: ELIOT@cs.umass.edu Still, I think my abstract point holds. QUOTE is a very good way to construct small and simple data structures, but there are many data structures that cannot *reasonably* be constructed with it. So QUOTE can't support a general mechanism for constructing read only data. If Common Lisp is going to have a notion of read-only, (for those implementations capable of it) then it would be best to support a general mechanism for it. I think this is also KMP's point, but I can't dig up that message, so: It should never be the Lisp's responsibility. If an implementation wants to support read-only-ness then it should be explicit. Perhaps one may say (copy-list-into-read-only-space ) or (copy-tree... ). That removes from the implementation the responsibility of deciding the level provided (i.e. you can move whatever you want into read-only space, as you wish. You could have a read-only array containing lists which existed in read/write space, for instance.) Note that you can then get the quote behavior you want by doing (defvar +some-internal-list+ (copy-list-into-read-only-space *another-list*)) (defun foo (x) (cons x (quote #,+some-internal-list+))) I think you are confusing the meaning of QUOTE, which is merely a kind of SUPPRESS-EVAL.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 15 Jun 88 03:28:25 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 15 Jun 88 00:14:22 PDT Received: from relay2.cs.net by RELAY.CS.NET id ad05994; 15 Jun 88 3:09 EDT Received: from cs.umass.edu by RELAY.CS.NET id al11087; 15 Jun 88 3:00 EDT Date: Tue, 14 Jun 88 13:20 EDT From: ELIOT@cs.umass.edu Subject: Constant Smashing To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.EDU" >From: IN%"NGALL@G.BBN.COM" 14-JUN-1988 03:53 >Subj: Re: constant folding/smashing > > Date: Fri, 10 Jun 88 11:32 EDT > From: ELIOT@cs.umass.edu > > What about constant hash-tables? No variety of QUOTE can build > a constant hash table because there is no notation for them. > (I don't count #.(make-hash-table...) because it's so gross.) > >Once again, I will state that the problem is not notation. QUOTE >cannot cons its argument into RO-space because the argument has ALREADY >BEEN CONSED. All QUOTE can do it to cons in RO-space an EQUAL COPY of >its argument and return that copy. But there is NO SUCH THING as an >EQUAL "COPY" of a hashtable. It doesn't matter that its gross, it >just won't work. Further supporting the idea that a general mechanism apart from QUOTE is required to properly support read-only data structures, if read only data becomes a Common Lisp concept. > In general I like the idea of quoted constants being read-only, > because it ensures that the semantics of a function at run-time > are apparent from its textual representation as code. If constants > are not read-only then: > > (defun foo () > '(a b c)) > > Really means > > (defun foo () > G00047) > (setq G00047 '(a b c)) > >Funny, this is the semantics that most Lisper's have as their initial >mental model (and I assume find the most intuitive). I'm not sure the code expresses my point clearly. Functions that return quoted constants are subject to *external* modification of their *internal* behavior. Its likely that you can get accidentally self modifying code. I've seen this cause obscure bugs. I don't think it is intuitive. The source code for the first definition of FOO makes it notationally "obvious" (incorrectly) that FOO always returns the list (A B C). The source code for the second definition makes it notationally clear that there is some global and mutable state involved. >It is also the >semantics of all (?) CL interpreters. QUOTE MUST have the same >behavior in the compiler and the interpreter. To do otherwise is to >introduce a compiler/interpreter incompatibility as confusing and >error-prone as the SPECIAL variable incompatibility used to be. Agreed? No. QUOTE must have the same *semantics* in the compiler and interpreter. However, there may be aspects of the semantics that are not fully defined and an implementation may have differences in those areas. (The binding environment of a variable is deemed much too important to leave unspecified.) It would be coherent to specify that it is "an error" to modify a quoted constant without requiring an implementation to ever detect it. A legitimate implementation might detect it some of the time (on tuesdays and thursdays perhaps) but not at other times. In the case of QUOTE some errors might go undetected. This is not good, but it is not as dangerous a flaw as the SPECIAL variable problem, which is characterized by different compiled/interpreted behavior where neither behavior draws attention to the actual source of the problem. It is relatively straightforward to debug a problem that causes the debugger to freeze execution near the actual cause. To support this argument I must make one more claim. I must claim that compiling a function produces a *new* function definition that is semantically equivalent to the old one, but it does not have to be composed of the 'same' forms. This is because of the definition of CONSTANTP on p.324 (CLtL) which (in my reading) implies (eq (foo) (foo)) when FOO is defined as above. [Because of (constantp (quote a b c))] Therefore: (eq (foo) (foo)) => T (setq x (foo)) (compile 'foo) (eq x (foo)) => Ambiguous (eq (foo) (foo)) => T And no identity holds accross the act of compilation. >If you want to suggest that the interpreter should be changed to make >QUOTE return a RO-EQUAL-copy of its arg when possible*** (as I think JonL >may have been suggesting?), then consider what a pain it will cause at >the top-level: > >> (setf foo '(1 2 3)) >(1 2 3) >> (push 0 foo) >>>>>> Error ... Tsk, Tsk. THAT won't cause an error. You meant: (setf (car foo) 'one)? An implementation can go either way on this. Experience with several different implementations may show what the happy compromise is. Actually I think that QUOTE should produce read only data structures and BACKQUOTE should create newly CONSed mutable data structures. > >Instead, you'll have to do: > >> (setf foo (list 1 2 3)) Or use backquote. >(1 2 3) >> (push 0 foo) >(0 1 2 3) > >A lot of Lisp textbooks will have to be rewritten! > >-- Nick > >*** Actually, the interpreter's handling of self-evaluating forms will >have to be changed too. If you agree with what I said about *external* modification of *internal* behavior then it would have to apply to strings, characters etc. also. But the added complexity is negligable, since "Foo" or #\Foo could be treated as (quote "Foo") or (quote #\Foo).  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 15 Jun 88 03:27:26 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 15 Jun 88 00:14:10 PDT Received: from relay2.cs.net by RELAY.CS.NET id ac05994; 15 Jun 88 3:09 EDT Received: from cs.umass.edu by RELAY.CS.NET id ak11087; 15 Jun 88 3:00 EDT Date: Tue, 14 Jun 88 13:18 EDT From: ELIOT@cs.umass.edu Subject: smashed constants To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.EDU" >From: IN%"Moon@SCRC-STONY-BROOK.ARPA" "David A. Moon" 14-JUN-1988 03:46 >To: ELIOT@cs.umass.EDU >Subj: constant folding/smashing > > Date: Fri, 10 Jun 88 11:32 EDT > From: ELIOT@cs.umass.edu > > (I don't count #.(make-hash-table...) because it's so gross.) > >I object to the characterization of doing something through the normal >syntax, instead of inventing a special weird syntax that people have >to learn as a special case, as "gross." Yes, that was a poor choice of words. But I don't think I am the only one who considers "escape" constructs like #. to be a technique of last resort. Still, I think my abstract point holds. QUOTE is a very good way to construct small and simple data structures, but there are many data structures that cannot *reasonably* be constructed with it. So QUOTE can't support a general mechanism for constructing read only data. If Common Lisp is going to have a notion of read-only, (for those implementations capable of it) then it would be best to support a general mechanism for it. Admittedly I don't know exactly how a general mechanism should be defined. A straightforward recursive decent copy won't work on circular data structures.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 14 Jun 88 14:49:39 EDT Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 14 Jun 88 11:33:05 PDT Posted-Date: Tue, 14 Jun 88 11:32:48 PDT Message-Id: <8806141832.AA16045@vaxa.isi.edu> Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51) id AA16045; Tue, 14 Jun 88 11:32:51 PDT To: common-lisp@sail.stanford.edu From: goldman@vaxa.isi.edu Subject: (macro . atom) Date: Tue, 14 Jun 88 11:32:48 PDT Sender: goldman@vaxa.isi.edu Consider the following macro definitions: (defmacro MACW (&whole w) `(- ,(cdr w))) (defmacro MACR (&rest r) `(- ,r )) and uses of them: (a) (MACW . 1) (b) (MACR . 1) I tried these on 3 CL implementations, with the following results: 1) Implementation 1 accepted both forms, binding w to (MACW . 1) in (a) and r to T in (b) 2) Implementation 2 treated case (a) the same as implementation 1, but rejected (b), saying that T was not a list. 3) Implementation 3 rejected both cases, saying that T was not a list. Interestingly, it gladly accepted both forms as arguments to MACROEXPAND-1, binding w and r the same as implementation 1. Question#1 -- what is the allowable behavior of an implementation in the case of (MACR . T)? Are all 3 valid? Question#2 -- what about the case of (MACW . T)? Should my MACW code be portable, or am I just lucky that 2 of these implementations let me get away with it? ---------------------------------------------------------------- Relevant sections of CLtL: On P.54, it states that only certain forms are "meaningful": self-evaluating forms, symbols, and "lists". If (MACW . T) and (MACR . T) are "meaningful", they must be lists. On Pp. 26-27, we have definitions of LIST and DOTTED LIST. (My examples are dotted lists). In the middle of P.27 is a rather odd paragraph. First it seems to say that uses of the term LIST in the book include dotted lists, and the the term "true list" will be used if dotted lists are to be excluded. It then says that if the book specifies that an argument must be a "list", it really means "true list"; that a dotted list is an error. A discussion of Destructuring macro arguments appears on P.146 . It allows dotted lists as or within individual arguments in macro calls -- e.g. (mac (foo . fum)), (mac (3 (foo . fum) 4)), and I read into that an implication that I can expect &rest args (at least embedded ones) to bind to dotted lists or non-NIL atoms. [I'd like to think that there is nothing special about non-embedded &rest args -- that they, too, could bind to dotted lists or non-NIL atoms. But I can't say that anything on P.146 really implies that.] P.146 also allows dotted lists in the lambda list of a macro definition, but states that they are equivalent to something that could be written with &rest. ---------------------------------------------------------------- So, just what is the intent of the use of "list" on pp. 54-59? Are dotted lists portable as macro calls? If so, is &whole the only portable way to accept them? What about as function calls? [there is no &whole for function lambda lists.] Incidentally, I believe I have a justifiable reason to want a dotted list to be acceptable as a macro form. It would be slightly more convenient if I could use a macro lambda list with an &REST in it, rather than resorting to &WHOLE, but that's no big deal. I would like to see the issue clarified so that a) dotted lists are legal as macro calls (but not as function calls if that forces added run-time costs in APPLY or ordinary function calling.) b) &rest parameters in macro lambda lists may bind to dotted lists or non-NIL atoms. This applies to top-level as well as embedded &rest parameters. Neil  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 Jun 88 19:04:18 EDT Received: from G.BBN.COM by SAIL.Stanford.EDU with TCP; 13 Jun 88 15:51:32 PDT Date: 13 Jun 1988 18:50-EDT Sender: NGALL@G.BBN.COM Subject: Re: constant folding/smashing From: NGALL@G.BBN.COM To: common-lisp@SAIL.STANFORD.EDU Message-ID: <[G.BBN.COM]13-Jun-88 18:50:37.NGALL> In-Reply-To: The message of Fri, 10 Jun 88 11:32 EDT from ELIOT@cs.umass.edu Date: Fri, 10 Jun 88 11:32 EDT From: ELIOT@cs.umass.edu What about constant hash-tables? No variety of QUOTE can build a constant hash table because there is no notation for them. (I don't count #.(make-hash-table...) because it's so gross.) Once again, I will state that the problem is not notation. QUOTE cannot cons its argument into RO-space because the argument has ALREADY BEEN CONSED. All QUOTE can do it to cons in RO-space an EQUAL COPY of its argument and return that copy. But there is NO SUCH THING as an EQUAL "COPY" of a hashtable. It doesn't matter that its gross, it just won't work. In general I like the idea of quoted constants being read-only, because it ensures that the semantics of a function at run-time are apparent from its textual representation as code. If constants are not read-only then: (defun foo () '(a b c)) Really means (defun foo () G00047) (setq G00047 '(a b c)) Funny, this is the semantics that most Lisper's have as their initial mental model (and I assume find the most intuitive). It is also the semantics of all (?) CL interpreters. QUOTE MUST have the same behavior in the compiler and the interpreter. To do otherwise is to introduce a compiler/interpreter incompatibility as confusing and error-prone as the SPECIAL variable incompatibility used to be. Agreed? If you want to suggest that the interpreter should be changed to make QUOTE return a RO-EQUAL-copy of its arg when possible*** (as I think JonL may have been suggesting?), then consider what a pain it will cause at the top-level: > (setf foo '(1 2 3)) (1 2 3) > (push 0 foo) >>>>> Error ... Instead, you'll have to do: > (setf foo (list 1 2 3)) (1 2 3) > (push 0 foo) (0 1 2 3) A lot of Lisp textbooks will have to be rewritten! -- Nick *** Actually, the interpreter's handling of self-evaluating forms will have to be changed too.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 Jun 88 17:50:04 EDT Received: from Xerox.COM by SAIL.Stanford.EDU with TCP; 13 Jun 88 14:38:56 PDT Received: from Burger.ms by ArpaGateway.ms ; 13 JUN 88 14:20:47 PDT Sender: "David_Snyder.Wbst208"@Xerox.COM Date: 13 Jun 88 07:22:28 PDT (Monday) Subject: Re: constant folding/smashing From: "David_Snyder.Wbst208"@Xerox.COM To: gls@Think.COM cc: Moon@stony-brook.scrc.symbolics.COM, DLA@jasper.scrc.symbolics.COM, Cyphers@jasper.scrc.symbolics.COM, NGALL@g.bbn.COM, common-lisp@sail.stanford.EDU In-Reply-to: gls%Think:COM:Xerox's message of 10 Jun 88 19:28 Message-ID: <880613-142047-9689@Xerox> Will the substitution preserve EQness?  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 Jun 88 15:59:00 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 13 Jun 88 12:48:29 PDT Received: from EUPHRATES.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 419009; Mon 13-Jun-88 15:47:15 EDT Date: Mon, 13 Jun 88 15:47 EDT From: David A. Moon Subject: constant folding/smashing To: ELIOT@cs.umass.edu cc: common-lisp@SAIL.STANFORD.EDU In-Reply-To: The message of 10 Jun 88 11:32 EDT from ELIOT@cs.umass.edu Message-ID: <19880613194703.9.MOON@EUPHRATES.SCRC.Symbolics.COM> Date: Fri, 10 Jun 88 11:32 EDT From: ELIOT@cs.umass.edu (I don't count #.(make-hash-table...) because it's so gross.) I object to the characterization of doing something through the normal syntax, instead of inventing a special weird syntax that people have to learn as a special case, as "gross."  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 Jun 88 15:05:53 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 13 Jun 88 11:52:41 PDT Received: by labrea.stanford.edu; Mon, 13 Jun 88 11:50:44 PDT Received: from bhopal.lucid.com by edsel id AA02227g; Mon, 13 Jun 88 11:37:35 PDT Received: by bhopal id AA10559g; Mon, 13 Jun 88 11:36:30 PDT Date: Mon, 13 Jun 88 11:36:30 PDT From: Jim McDonald Message-Id: <8806131836.AA10559@bhopal.lucid.com> To: RWK@ai.ai.mit.edu Cc: common-lisp@sail.stanford.edu In-Reply-To: "Robert W. Kerns"'s message of Mon, 13 Jun 88 02:05:15 EDT <396357.880613.RWK@AI.AI.MIT.EDU> Subject: EQUAL While this all sounds very nice, I'm afraid you're engaging in a bit of historical revisionism. After hitting I had second thoughts along those lines, but third thoughts removed them. (Now I'm afraid to hit return again. :-) Originally, LISP didn't have all these nice hairy datatypes. Those of us who were there (Not me!) can tell about what McCarthy wrought, but I know I've seen Lisp's without arrays at all. No fair. That's an argument for my position. I know people have been using EQUAL to compare data more often than to compare code for a very long time. One of the tenants of evolution is that rather small advantages can drive natural selection. If EQUAL and EQUAL' are of comparable utility for comparing data, but EQUAL is much better for code, then EQUAL will prevail, even if 99% of the comparisons are for data. In fact, EQUAL doesn't work on code, plain and simple. To compare code, you must first recognize that it is not computable to compare two functions which contain quoted data, unless that quoted data is EQ. You also have to place constraints on macros to not be pathological (i.e. sick). But EQUAL *does* work on code. E.g., I might have a rewrite system in my compiler that makes all sorts of modifications and then checks to see if the result is EQUAL. If not, it goes around again. Since the code analysis is using CAR, CDR, CONS, LIST, etc. and never copying arrays or other objects, EQUAL is precisely the right test. Textbook arguments and pathological examples miss the historical point I was making. My sense is that the early implementers were pragmatic enough not to fall into the trap of avoiding something useful because it was not (and could never be) perfect. In short, what EQUAL is good for is comparing "old-style" data (that is, data structures like are used in such venerable programs as Macsyma -- and there are some exceptions there, too). I would include "old-style" and most "new-style" code. Another way of phrasing my argument is that "old-style" code and data were so similar as to blur the uses of EQUAL. "New-style" data has evolved more, so discrepencies are emerging between the uses. I do think it would be reasonable to define an extremely limited set of new predicates. I would suggest limiting it to two new ones that do the two pieces of EQUALP -- descend other structures, and merge case in strings and characters. I agree with the focus, but probably not the details. I would strongly discourage any attempt to "solve the problem of comparisons", on the grounds that it will require more hair, additions to the language, and discussion than it could possibly be worth. Agreed! jlm  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 Jun 88 13:17:32 EDT Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 13 Jun 88 10:04:32 PDT Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0) id AA22912; Mon, 13 Jun 88 10:02:01 PDT Received: from lukasiewicz.sun.com by snail.sun.com (4.0/SMI-3.2) id AA06262; Mon, 13 Jun 88 09:58:29 PDT Received: by lukasiewicz.sun.com (4.0/SMI-4.0) id AA07423; Mon, 13 Jun 88 10:04:00 PDT Date: Mon, 13 Jun 88 10:04:00 PDT From: jrose@Sun.COM (John Rose) Message-Id: <8806131704.AA07423@lukasiewicz.sun.com> To: edsel!jlm@labrea.stanford.edu Cc: common-lisp@sail.stanford.edu In-Reply-To: Jim McDonald's message of Fri, 10 Jun 88 18:27:18 PDT <8806110127.AA03445@bhopal.lucid.com> Subject: EQUAL Date: Fri, 10 Jun 88 18:27:18 PDT From: Jim McDonald ... Thus EQUAL is (in some historical sense) defined to make it easy to do pattern matching on code. Since code traditionally becomes read-only, this is more-or-less consistent with collapsing EQUAL structures to be EQ. I claim that the traditional explanation for EQUAL's semantics (that EQUAL means roughly HAVE-THE-SAME-PRINT-REPRESENTATION-P) is actually just an observation based on this more fundamental reason. ... Also, since people in general have some esthetic sensibilities, a fully haired roll-your-own equality predicate seems unlikely. ... jlm Date: Sat, 11 Jun 88 17:32:08 PDT From: Jon L White I like you analysis, and think it explains very well why EQUAL has the peculiar semantics that it now has. How would you feel about extending EQUAL to descend defsturct structures and T-type arrays? it wouldn't mess up its utility for its original purpose, and would satisfy an enormous number of Lisp users. Of course, EQUAL type hashtables would work with this new definition. ... -- JonL -- To add fuel to the fire: Since EQUAL bears an observable relationship to READ and WRITE, there's an obvious way to supply a "fully haired roll-your-own equality predicate". Add, to EQUAL, keyword arguments analogous to WRITE, for controlling these debatable behaviors. E.g., the people who want to compare array substructure would use a call like this: (EQUAL X Y :ARRAY T) Comparison of structures would be controlled by the :STRUCTURE keyword. Hash tables could be handled similarly, especially if hash-table printing is ever made standard. Perhaps case sensitivity in strings could be controlled by :CASE. Something should be done for numbers too. I hope there's no call for the analogous special variables, e.g., *EQUAL-ARRAY*! We might go further, by allowing the argument to :ARRAY or :STRUCTURE to be an equality predicate instead of a boolean. This would allow somewhat better control over, e.g., which types of structure were to be opened up for comparison. (A DEFSTRUCT option controlling equality behavior would be much preferable, for reasons of modularity.) -- John  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 Jun 88 02:44:00 EDT Received: from AI.AI.MIT.EDU by SAIL.Stanford.EDU with TCP; 12 Jun 88 23:31:34 PDT Date: Mon, 13 Jun 88 02:31:18 EDT From: "Robert W. Kerns" Subject: constant folding/smashing To: edsel!jonl@LABREA.STANFORD.EDU cc: common-lisp@SAIL.STANFORD.EDU, goldman@VAXA.ISI.EDU, cperdue@SUN.COM, NGALL@G.BBN.COM In-reply-to: Msg of Thu 9 Jun 88 14:59:16 PDT from Jon L White Message-ID: <396377.880613.RWK@AI.AI.MIT.EDU> Date: Thu, 9 Jun 88 14:59:16 PDT From: Jon L White To: NGALL at g.bbn.com cc: goldman at vaxa.isi.edu, cperdue at sun.com, common-lisp at sail.stanford.edu Re: constant folding/smashing re: My point is that in the form (SETF (SYMBOL-VALUE (QUOTE X)) 1) the quoted object is no more or less "constant" than in the form (SETF (FIRST (QUOTE (A B C))) 1) So why does QUOTE make the components of the list (1 2 3) unmodifiable but not the components of X? Because the semantic model of symbols doesn't consider them to have modifiable components; they are "atomic". In fact, several implementations Wrong reason. (As has been pointed out in other discussion). (SETF (SYMBOL-VALUE 'X) 1) is the same as (SETQ X 1), for X being special. The X in either piece of code is a REFERENCE to a non-constant object, shared between occurrances of read. It is a PUBLIC structure published by INTERN. Modifications to its value cell are modifications to the global variable environment. They're already EQified as much as makes sense. The list structure in '(A B C) is a private structure not obtainable by any other call to READ. EQification makes sense. Where this breaks down, of course, is macros. Symbols, obviously, are always (potentially) a shared resource (if interned). Lists are provably private if they came from READ, but not from macroexpansion. As you point out, EQification is part of the semantics of QUOTE. To clean this up, we have to be more explicit in the semantics of QUOTE. In fact, let me assert that one special form cannot accomplish all the variations of what behaviour you'd like to see. You'd like to be able to establish explicit control over what things are shared & read-only in a datastructure, presumably by providing your own function. QUOTE should follow simple rules (the rules it now follows, I claim, because it discourages self-modifying programs).  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 Jun 88 02:22:14 EDT Received: from AI.AI.MIT.EDU by SAIL.Stanford.EDU with TCP; 12 Jun 88 23:05:19 PDT Date: Mon, 13 Jun 88 02:05:15 EDT From: "Robert W. Kerns" Subject: EQUAL To: edsel!jlm@LABREA.STANFORD.EDU cc: common-lisp@SAIL.STANFORD.EDU In-reply-to: Msg of Fri 10 Jun 88 18:27:18 PDT from Jim McDonald Message-ID: <396357.880613.RWK@AI.AI.MIT.EDU> Date: Fri, 10 Jun 88 18:27:18 PDT From: Jim McDonald Thus EQUAL is (in some historical sense) defined to make it easy to do pattern matching on code. Since code traditionally becomes read-only, this is more-or-less consistent with collapsing EQUAL structures to be EQ. I claim that the traditional explanation for EQUAL's semantics (that EQUAL means roughly HAVE-THE-SAME-PRINT-REPRESENTATION-P) is actually just an observation based on this more fundamental reason. When people try to move beyond manipulation of code, the whole basis for the semantics of EQUAL is removed, so the result is somewhat chaotic. While this all sounds very nice, I'm afraid you're engaging in a bit of historical revisionism. Originally, LISP didn't have all these nice hairy datatypes. Those of us who were there (Not me!) can tell about what McCarthy wrought, but I know I've seen Lisp's without arrays at all. I know people have been using EQUAL to compare data more often than to compare code for a very long time. In fact, EQUAL doesn't work on code, plain and simple. To compare code, you must first recognize that it is not computable to compare two functions which contain quoted data, unless that quoted data is EQ. You also have to place constraints on macros to not be pathological (i.e. sick). To illustrate a couple examples: (defvar *call-registry* (make-hash-table :test 'eq)) (defvar *macro-registry* (make-hash-table :test 'eq)) (defun register-macro-marker (marker) (let ((marker (gethash *macro-registry* marker))) (unless marker (setf marker `',(gensym)) (setf (gethash *macro-registry* marker) marker)) marker)) (defun register-call (marker result) (push result (gethash *call-registry* marker))) (defmacro register (&whole marker) `(register-call ,(register-macro-marker marker) ,(second marker))) (defun confound (flag) (if flag (register '(MARKER)) (register '(MARKER)))) Are the two branches of the IF equivalent? EQUAL says yes. I leave it as an exercise for the reader to count how many ways and on how many levels those two branches differ. [I apologize in advance for any spazzes in the code; I have to type it in by hand; I don't have any way of transfering files to or from arpanetland for testing, and editing directly on ITS doesn't work well for me either]. In short, what EQUAL is good for is comparing "old-style" data (that is, data structures like are used in such venerable programs as Macsyma -- and there are some exceptions there, too). I do think it would be reasonable to define an extremely limited set of new predicates. I would suggest limiting it to two new ones that do the two pieces of EQUALP -- descend other structures, and merge case in strings and characters. I would strongly discourage any attempt to "solve the problem of comparisons", on the grounds that it will require more hair, additions to the language, and discussion than it could possibly be worth.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 Jun 88 01:25:00 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 12 Jun 88 22:12:38 PDT Received: from relay2.cs.net by RELAY.CS.NET id ac01479; 13 Jun 88 1:07 EDT Received: from cs.umass.edu by RELAY.CS.NET id ae19893; 13 Jun 88 1:00 EDT Date: Sun, 12 Jun 88 13:08 EDT From: ELIOT@cs.umass.edu Subject: Backquote Constants To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.EDU" >From: IN%"sandra@cs.utah.EDU" "Sandra J Loosemore" 12-JUN-1988 02:41 > >> From: edsel!jonl@labrea.stanford.edu (Jon L White) >> >> re: What about constant hash-tables? No variety of QUOTE can build >> a constant hash table because there is no notation for them. >> (I don't count #.(make-hash-table...) because it's so gross.) >> >> There is a proposal before X3J13 now (presented by Dave Touretzky) to >> give a printable representation to hashtables. If a sufficiently powerful >> version of it is adopted, then it should be possible to use QUOTE to >> reference a constant hashtable. > >There is already a way to make a constant hashtable with QUOTE. Try: > > (defmacro make-a-constant-hash-table () > `(quote ,(make-hash-table ...))) > >This same trick can also be used to make "constants" out of other kinds >of weird objects, like packages or streams. > >-Sandra >------- At first I thought this was crazy, since this implies that backquote copies data inside a comma and I didn't think backquote was allowed to do this. However, Cltl P.350 says: "...an implementation is free to interpret a backquoted form as any form that,... is EQUAL to the result implied by the above definition." (My caps.) So, you are right, and CltL is (in my opinion) wrong. As CltL says on page 351 "There is no good reason why copy-list should be performed, but it is not prohibited." If there is no good reason why copying should be performed, then it *should* be prohibited. I don't know of any implementation which gratuitously copies extra structure in backquoted forms and I consider the possibility to be grossly unintuitive. In fact, I think some code I wrote a few years ago is probably "in error" because of this very obscure ambiguity. I strongly believe that the intuitive way for backquote to work is to directly incorporate the results of comma evaluation into the result without modification, exactly as if the corresponding set of calls to CONS had been coded directly. Unless there is a good reason for the ambiguity in the definition it must be considered a bad definition. Perhaps the ambiguity in the definition is an attempt to allow for some of the read-only/collapsing optimizations that are being discussed. If so, then as KMP said this is an attempt to combine two kinds of functionality into a single construct. I consider backquote to be a *shorthand* data construction primitive. Anything produced by backquote can, more generally, be produced by a combination of CONS, VECTOR, QUOTE and other functions. If we need a way to construct read-only data structure (it would be nice) then there should be a *general* way to do so, corresponding to the general use of CONS, VECTOR and QUOTE to produce data structures. It would be unfortunate to introduce a new way to manipulate data without making it general. As an aside, the description of the difference between ,@ and ,. seems to be incoherent. The syntax ,. indicates that it is permissible to destroy (i.e. incorporate?) the list produced by the following form. However, the example on p.351 indicates that it is permissible to incorporate the list produced by the ,@ form also. I fail to see how these differ.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 11 Jun 88 21:46:29 EDT Received: from cs.utah.edu by SAIL.Stanford.EDU with TCP; 11 Jun 88 18:35:23 PDT Received: by cs.utah.edu (5.54/utah-2.0-cs) id AA07785; Sat, 11 Jun 88 19:34:03 MDT From: sandra@cs.utah.edu (Sandra J Loosemore) Message-Id: <8806120134.AA07785@cs.utah.edu> Date: Sat, 11 Jun 88 19:34:01 MDT Subject: constant folding/smashing (constant hash tables) To: common-lisp@sail.stanford.edu Cc: edsel!jonl@labrea.stanford.edu, eliot@cs.umass.edu > From: edsel!jonl@labrea.stanford.edu (Jon L White) > Subject: constant folding/smashing > > re: What about constant hash-tables? No variety of QUOTE can build > a constant hash table because there is no notation for them. > (I don't count #.(make-hash-table...) because it's so gross.) > > There is a proposal before X3J13 now (presented by Dave Touretzky) to > give a printable representation to hashtables. If a sufficiently powerful > version of it is adopted, then it should be possible to use QUOTE to > reference a constant hashtable. There is already a way to make a constant hashtable with QUOTE. Try: (defmacro make-a-constant-hash-table () `(quote ,(make-hash-table ...))) This same trick can also be used to make "constants" out of other kinds of weird objects, like packages or streams. -Sandra -------  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 11 Jun 88 21:05:12 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 11 Jun 88 17:55:17 PDT Received: by labrea.stanford.edu; Sat, 11 Jun 88 17:54:10 PDT Received: from bhopal.lucid.com by edsel id AA26900g; Sat, 11 Jun 88 17:48:01 PDT Received: by bhopal id AA06005g; Sat, 11 Jun 88 17:46:49 PDT Date: Sat, 11 Jun 88 17:46:49 PDT From: Jon L White Message-Id: <8806120046.AA06005@bhopal.lucid.com> To: ELIOT@cs.umass.edu Cc: common-lisp@sail.stanford.edu In-Reply-To: ELIOT@cs.umass.edu's message of Fri, 10 Jun 88 11:32 EDT <8806110719.AA23994@edsel.lucid.com> Subject: constant folding/smashing re: What about constant hash-tables? No variety of QUOTE can build a constant hash table because there is no notation for them. (I don't count #.(make-hash-table...) because it's so gross.) Lucid's "Re-Targetable" compiler is table driven; the tables are ordinary CL hashtables. In recent images, they are stored in read-only memory, since all the key entries are symbols, and since they change very rarely (such as when someone is debugging the compiler). A "lazy migration" scheme ensures that they become writeable upon demand. There is a proposal before X3J13 now (presented by Dave Touretzky) to give a printable representation to hashtables. If a sufficiently powerful version of it is adopted, then it should be possible to use QUOTE to reference a constant hashtable. I don't think the techniques that Lucid uses to build read-only tables are exported to the end-user; but it certainly is possible to reference "constant" hashtables using the "gross" #. notation, and have such code be compiled and loaded correctly. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 11 Jun 88 20:50:26 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 11 Jun 88 17:37:55 PDT Received: by labrea.stanford.edu; Sat, 11 Jun 88 17:36:49 PDT Received: from bhopal.lucid.com by edsel id AA26883g; Sat, 11 Jun 88 17:33:22 PDT Received: by bhopal id AA05974g; Sat, 11 Jun 88 17:32:08 PDT Date: Sat, 11 Jun 88 17:32:08 PDT From: Jon L White Message-Id: <8806120032.AA05974@bhopal.lucid.com> To: edsel!jlm@labrea.stanford.edu Cc: common-lisp@sail.stanford.edu In-Reply-To: Jim McDonald's message of Fri, 10 Jun 88 18:27:18 PDT <8806110127.AA03445@bhopal.lucid.com> Subject: EQUAL I like you analysis, and think it explains very well why EQUAL has the peculiar semantics that it now has. How would you feel about extending EQUAL to descend defsturct structures and T-type arrays? it wouldn't mess up its utility for its original purpose, and would satisfy an enormous number of Lisp users. Of course, EQUAL type hashtables would work with this new definition. As we have often said, EQUALP went a little bit too far -- because of ignoring representation type on numbers and character case in strings. I think there should be an EQUALP type hashtable as long as there's an EQUALP function; but a satisfactorily extended EQUAL function might make it less of pressing issue. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 11 Jun 88 02:27:23 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 10 Jun 88 23:16:15 PDT Received: from relay2.cs.net by RELAY.CS.NET id ab13411; 11 Jun 88 2:11 EDT Received: from cs.umass.edu by RELAY.CS.NET id av06082; 11 Jun 88 2:03 EDT Date: Fri, 10 Jun 88 11:32 EDT From: ELIOT@cs.umass.edu Subject: constant folding/smashing To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: in%"common-lisp@sail.stanford.EDU" What about constant hash-tables? No variety of QUOTE can build a constant hash table because there is no notation for them. (I don't count #.(make-hash-table...) because it's so gross.) This suggests that something like the 'purcopy' function is still needed. However, should this be recursive in the case of hash tables? Certainly the KEYS of ANY hash table must be thought of as constants, because otherwise the table can become inconsistent. But I can think of situations both where the values should also be constants (if the table is) and where the valueshould not be constants. Making 'pucopy' non-recursive is fine for large data structures, like arrays, structures, strings etc., but I think most people feel that CONSes in list structure should be handled in one fell swoop. Perhaps a 'pucopy' function should accept a data argument and an arbitrary number of type specifiers, indicating the data types to recurse through. In general I like the idea of quoted constants being read-only, because it ensures that the semantics of a function at run-time are apparent from its textual representation as code. If constants are not read-only then: (defun foo () '(a b c)) Really means (defun foo () G00047) (setq G00047 '(a b c)) On the other hand, I think it would be consistent to define BACKQUOTE so that it always makes a fresh copy of its entire argument. This is reasonable, since BACKQUOTE already has to copy its argument down to the last comma. Die-hards who really want to avoid the final CONSing in a BACKQUOTE could use ,'(...) to insert un-copied structure.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 10 Jun 88 23:48:14 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 10 Jun 88 20:37:03 PDT Received: by labrea.stanford.edu; Fri, 10 Jun 88 20:35:13 PDT Received: from bhopal.lucid.com by edsel id AA23338g; Fri, 10 Jun 88 20:30:31 PDT Received: by bhopal id AA03714g; Fri, 10 Jun 88 20:29:14 PDT Date: Fri, 10 Jun 88 20:29:14 PDT From: Jon L White Message-Id: <8806110329.AA03714@bhopal.lucid.com> To: NGALL@g.bbn.com Cc: common-lisp@sail.stanford.edu In-Reply-To: NGALL@G.BBN.COM's message of 10 Jun 1988 11:03-EDT <[G.BBN.COM]10-Jun-88 11:03:26.NGALL> Subject: constant folding/smashing re: >From what I read in CLtL, the semantic model of symbols DOES consider them to have modifiable components: ... I think you are confusing YOUR semantics of CL (which may be widespread (Moon seems to share your view of SYMBOLs as being componentles)s) with the semantics actually described in CLtL. Lisp has been around longer than Common Lisp. There are many places where CLtL makes a stab at clarifying the generally-understood semantics, and fails. This notion (of CLtL being "in error" at times) is not just a "confusion" that moon and I share, but a serious topic that the X3J13 Cleanup subcommittee is addressing. Lest anyone get the wrong impression from what I've just said, let me add that I find CLtL one of the truly impressive documents in Computer Science. I can hardly praise it highly enough. It just isn't 100% perfect. re: If this "capability of implementation" [read-only constants] is so important, why are so few implementations taking advantage of it? . . . What implementations DO put constants in RO space? Lucid Common Lisp, for one. Because of efficiency questions, you will not actually have the "read-only" constant put into a write-protected area of memory until after a subsequent "DISKSAVE". On Unix hosts, this typically means re-ordering the image so that all the constants and other read-only stuff are in the text segment. Maybe some of the other implementations you tried and failed on do the same thing, and you just didn't look at them after the corresponding "world dump". re: I hope CLtL would clean-up EQUAL to mean "collapsable" rather than subject the poor Lisp novice to yet another slightly-different equality predicate. Thank you for your opinion. I used the word COALESCABLEP rather than "collapsable"; I should hope that whatever notion is acceptable to the X3J13 committee will imply "substitution of one similar, but non-EQ, datum for another" rather than "utter collapse" of a particular structure. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 10 Jun 88 21:48:10 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 10 Jun 88 18:34:33 PDT Received: by labrea.stanford.edu; Fri, 10 Jun 88 18:32:21 PDT Received: from bhopal.lucid.com by edsel id AA22886g; Fri, 10 Jun 88 18:28:36 PDT Received: by bhopal id AA03445g; Fri, 10 Jun 88 18:27:18 PDT Date: Fri, 10 Jun 88 18:27:18 PDT From: Jim McDonald Message-Id: <8806110127.AA03445@bhopal.lucid.com> To: common-lisp@sail.stanford.edu Subject: EQUAL > Look at the definition of ATOM on pg. 73 ("is > not a CONS"); it says nothing about the notion of atominicity. How > sensible is it to view an array as "atomic"? I think most of the confusion with EQUAL may stem from the fact that the syntax of lisp programs is expressed with lists. When modifying programs, writing macros, etc. it is critical to have primitives that are sensitive to the components of your code, which effectively means having primitives that are sensitive to the components of lists. [Thus, to answer the question posed above, when transforming a lisp program, arrays are atomic since they express no syntactic control information.] There is no comparable historical reason for similar access to the contents of strings, arrays, structures, etc. Thus EQUAL is (in some historical sense) defined to make it easy to do pattern matching on code. Since code traditionally becomes read-only, this is more-or-less consistent with collapsing EQUAL structures to be EQ. I claim that the traditional explanation for EQUAL's semantics (that EQUAL means roughly HAVE-THE-SAME-PRINT-REPRESENTATION-P) is actually just an observation based on this more fundamental reason. When people try to move beyond manipulation of code, the whole basis for the semantics of EQUAL is removed, so the result is somewhat chaotic. Overall, I'll argue that you must first decide what you are trying to do (transform code, manipulate databases, build parse trees, etc.) before you can decide what you want of your equality predicates. Since Common Lisp presumably is not dedicated to any particular application (except that code transformations should be supported), I'm pessimistic that people will ever agree on simple semantics. Also, since people in general have some esthetic sensibilities, a fully haired roll-your-own equality predicate seems unlikely. Since code transformation is common to almost all lisp endeavors, EQUAL and friends should first be tested for usefulness in that context. Then, if someone can define another similar class of endeavors, perhaps another set of predicates can be defined to capture the semantics needed there. So far, I have seen no coherent description of generic data transformations, let alone one that would warrant modification of the language. jlm  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 10 Jun 88 19:49:03 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 10 Jun 88 16:39:32 PDT Return-Path: Received: from kali.think.com by Think.COM; Fri, 10 Jun 88 17:34:00 EDT Received: by kali.think.com; Fri, 10 Jun 88 17:33:55 EDT Date: Fri, 10 Jun 88 17:33:55 EDT From: gls@Think.COM Message-Id: <8806102133.AA04956@kali.think.com> To: Moon@stony-brook.scrc.symbolics.com Cc: DLA@jasper.scrc.symbolics.com, Cyphers@jasper.scrc.symbolics.com, NGALL@g.bbn.com, common-lisp@sail.stanford.edu In-Reply-To: David A. Moon's message of Fri, 10 Jun 88 15:24 EDT <19880610192418.8.MOON@EUPHRATES.SCRC.Symbolics.COM> Subject: constant folding/smashing Date: Fri, 10 Jun 88 15:24 EDT From: David A. Moon ... Actually, just about anything in Common Lisp that has anything at all to do with equality seems to be out of whack. For "Common Lisp", try substituting "logic", "the United States", or "the universe". --Guy  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 10 Jun 88 16:41:50 EDT Received: from G.BBN.COM by SAIL.Stanford.EDU with TCP; 10 Jun 88 13:29:19 PDT Date: 10 Jun 1988 16:26-EDT Sender: NGALL@G.BBN.COM Subject: Re: constant folding/smashing From: NGALL@G.BBN.COM To: Moon@SCRC-STONY-BROOK.ARPA Cc: common-lisp@SAIL.STANFORD.EDU Message-ID: <[G.BBN.COM]10-Jun-88 16:26:10.NGALL> In-Reply-To: <19880610182840.2.MOON@EUPHRATES.SCRC.Symbolics.COM> Date: Fri, 10 Jun 88 14:28 EDT From: David A. Moon Date: 10 Jun 1988 11:03-EDT From: NGALL@G.BBN.COM .... And this brings up the second example of the confusion in constant folding that no one has yet addressed: Why are lists and strings (among others) constant folded, but not general vectors, since all of them are composite objects? What makes you think that is true? (I assume you mean "coalesced", that is, two distinct pieces of source text resulting in a single object in the compiled program, rather than "constant folded", which means a pure function with constant arguments replaced by its constant result.) I don't of Yes. I meant "collapsed" (CLtL pg. 78) not "folded". anything that says that Common Lisp must treat quoted general vectors differently from quoted strings. If some implementations do so, that's merely an implementation. I think my statement above is true based on pg. 78 (Collapsing constants that are EQUAL) and pg. 80 (Def of EQUAL): Object X may be collapsed with object Y iff (AND (EQUAL X Y) (NOT (EQ X Y))). This condition can hold for strings, but NOT for general vectors, since any EQUAL general vectors are EQ and hence are already collapsed. [3] (EQ (QUOTE #1=(1 2 3)) (QUOTE #1#)) => T or NIL, wow!!!!! I see no evidence that any interpreter or compiler is permitted to return NIL for the above form. According to the above quoted passages, the following definition for COPY-QUOTE is semantically equivalent to QUOTE: (defvar *copy-quote-flip-flop* nil) (defmacro copy-quote (obj) `(let ((obj-copy (copy ',obj))) (if (and (equal ',obj obj-copy) (setf *copy-quote-flip-flop* (not *copy-quote-flip-flop*))) obj-copy ',obj))) [Where COPY is a function that dispatches off to the appropiate copy function (e.g., COPY-SEQ, COPY-SYMBOL, etc) if there is one, otherwise it returns its arg.] If you agree with this assertion, then you'll agree that an implementation that used the above semantics for QUOTE, would return NIL in example [3]. What you're probably thinking of is (EQ (QUOTE #(1 2 3)) (QUOTE #(1 2 3))), which might be true or false. Assuming that READ is non-structure-sharing, this predicate form MUST return NIL in ALL implementations. The two vectors are not EQUAL so they cannot be collapsed! Agreed? Once you (or anyone else in this somewhat rambling and inconclusive discussion) think you understand the issues above, figure out what you think about these three forms: (EQ (FUNCTION (LAMBDA () 1)) (FUNCTION (LAMBDA () 1))) T or NIL (EQ (FUNCTION (LAMBDA (N) (DO ((I 1 (1+ I)) (A 0 (+ A I))) ((>= I N) A)))) (FUNCTION (LAMBDA (N) (DO ((I 0 (1+ I)) (A 0 (+ A I))) ((>= I N) A))))) T or NIL (EQ (FUNCTION (LAMBDA (N) (DO ((I 1 (1+ I)) (A 0 (+ A I))) ((>= I N) A)))) (FUNCTION (LAMBDA (N) (* N (1- N) 1/2)))) T or NIL (what an optimizer! :-) Based on my interpretation of the description of FUNCTION pgs. 87-89 But I think you're getting away from the point. I think you'll find that in some systems compiled code and its constants become read-only during a system building procedure, but not when you just call the COMPILE or LOAD functions. Nobody says read-onlyness of constants is -required- to be enforced. You're right, nobody did say it. ...you are collapsing two behaviors into one special form. A bad idea in this case.... I hope CLtL would clean-up EQUAL to mean "collapsable" rather than subject the poor Lisp novice to yet another slightly-different equality predicate. The above two statements don't seem to me to be based on a consistent philosophy. You're right, I should have said ...you are collapsing two [unrelated] behaviors into one special form. A bad idea in this case.... I hope CLtL would clean-up EQUAL to mean "collapsable" rather than subject the poor Lisp novice to yet another [closely related] equality predicate. I think the confusion in the discussion demonstrates conclusively that the current semantics of QUOTE is not well defined. -- Nick  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 10 Jun 88 15:39:53 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 10 Jun 88 12:25:48 PDT Received: from EUPHRATES.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 418064; Fri 10-Jun-88 15:24:28 EDT Date: Fri, 10 Jun 88 15:24 EDT From: David A. Moon Subject: Re: constant folding/smashing To: David L. Andre cc: Cyphers@JASPER.SCRC.Symbolics.COM, NGALL@g.bbn.com, common-lisp@SAIL.STANFORD.EDU In-Reply-To: <19880610191103.0.DLA@KOYAANISQATSI.SCRC.Symbolics.COM> Message-ID: <19880610192418.8.MOON@EUPHRATES.SCRC.Symbolics.COM> Date: Fri, 10 Jun 88 15:11 EDT From: David L. Andre Date: Fri, 10 Jun 88 14:28 EDT From: David A. Moon Date: 10 Jun 1988 11:03-EDT From: NGALL@G.BBN.COM I don't of anything that says that Common Lisp must treat quoted general vectors differently from quoted strings. Actually, CLtL (p. 78) is specific that an implementation only collapse objects which are EQUAL. I personally think this is inconsistent and a bug in CLtL. Thanks, I somehow missed seeing that in CLtL. I agree with you that this is inconsistent. Actually, just about anything in Common Lisp that has anything at all to do with equality seems to be out of whack.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 10 Jun 88 14:42:57 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 10 Jun 88 11:29:52 PDT Received: from EUPHRATES.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 418025; Fri 10-Jun-88 14:28:52 EDT Date: Fri, 10 Jun 88 14:28 EDT From: David A. Moon Subject: Re: constant folding/smashing To: NGALL@G.BBN.COM cc: common-lisp@SAIL.STANFORD.EDU In-Reply-To: <[G.BBN.COM]10-Jun-88 11:03:26.NGALL> Message-ID: <19880610182840.2.MOON@EUPHRATES.SCRC.Symbolics.COM> Date: 10 Jun 1988 11:03-EDT From: NGALL@G.BBN.COM .... And this brings up the second example of the confusion in constant folding that no one has yet addressed: Why are lists and strings (among others) constant folded, but not general vectors, since all of them are composite objects? What makes you think that is true? (I assume you mean "coalesced", that is, two distinct pieces of source text resulting in a single object in the compiled program, rather than "constant folded", which means a pure function with constant arguments replaced by its constant result.) I don't of anything that says that Common Lisp must treat quoted general vectors differently from quoted strings. If some implementations do so, that's merely an implementation. [3] (EQ (QUOTE #1=(1 2 3)) (QUOTE #1#)) => T or NIL, wow!!!!! I see no evidence that any interpreter or compiler is permitted to return NIL for the above form. What you're probably thinking of is (EQ (QUOTE #(1 2 3)) (QUOTE #(1 2 3))), which might be true or false. Once you (or anyone else in this somewhat rambling and inconclusive discussion) think you understand the issues above, figure out what you think about these three forms: (EQ (FUNCTION (LAMBDA () 1)) (FUNCTION (LAMBDA () 1))) (EQ (FUNCTION (LAMBDA (N) (DO ((I 1 (1+ I)) (A 0 (+ A I))) ((>= I N) A)))) (FUNCTION (LAMBDA (N) (DO ((I 0 (1+ I)) (A 0 (+ A I))) ((>= I N) A))))) (EQ (FUNCTION (LAMBDA (N) (DO ((I 1 (1+ I)) (A 0 (+ A I))) ((>= I N) A)))) (FUNCTION (LAMBDA (N) (* N (1- N) 1/2)))) Kudos to the Scheme community for elucidating this undecidable issue some years ago. I couldn't get Symbolics CL (which I thought WOULD do it), Vax CL, or KCL to put a "constant" into read-only space. What implementations DO put constants in RO space? Try (set :foo 105) in Symbolics. It will signal a write in read only error. That's one kind of constant. The Symbolics compiler doesn't currently put quoted constants in compiled functions into read-only space, because it puts the constants and the code on the same virtual memory page and there is currently a stupid reason why compiled functions can't normally be put into read-only space. I believe it used to make constants read-only a few years ago. At some point the stupid reason will be fixed and then all constants and compiled code will be read-only (and a certain programmer/technical manager, who I won't name but who will recognize himself, will have to stop writing self-modifying code!). I think you'll find that in some systems compiled code and its constants become read-only during a system building procedure, but not when you just call the COMPILE or LOAD functions. Nobody says read-onlyness of constants is -required- to be enforced. ...you are collapsing two behaviors into one special form. A bad idea in this case.... I hope CLtL would clean-up EQUAL to mean "collapsable" rather than subject the poor Lisp novice to yet another slightly-different equality predicate. The above two statements don't seem to me to be based on a consistent philosophy.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 10 Jun 88 11:23:26 EDT Received: from G.BBN.COM by SAIL.Stanford.EDU with TCP; 10 Jun 88 08:06:47 PDT Date: 10 Jun 1988 11:03-EDT Sender: NGALL@G.BBN.COM Subject: Re: constant folding/smashing From: NGALL@G.BBN.COM To: edsel!jonl@LABREA.STANFORD.EDU Cc: common-lisp@SAIL.STANFORD.EDU Message-ID: <[G.BBN.COM]10-Jun-88 11:03:26.NGALL> In-Reply-To: <8806092159.AA25338@bhopal.lucid.com> Date: Thu, 9 Jun 88 14:59:16 PDT From: Jon L White re: My point is that in the form (SETF (SYMBOL-VALUE (QUOTE X)) 1) the quoted object is no more or less "constant" than in the form (SETF (FIRST (QUOTE (A B C))) 1) So why does QUOTE make the components of the list (1 2 3) unmodifiable but not the components of X? Because the semantic model of symbols doesn't consider them to have modifiable components; they are "atomic". In fact, several implementations I'm familiar do a "spaghetti-stack" lookup for the SYMBOL-VALUE function -- not a structure-component fetch. And there have been serious suggestions for flushing the symbol-plist notion in favor of hashtables, or at least encouraging one to use hashtable entries rather than plist entries. From what I read in CLtL, the semantic model of symbols DOES consider them to have modifiable components: "Symbols have a component called the PROPERTY LIST..." pg. 24 "A Lisp symbol is a data object that has three user-visible components [Print-name, Plist, and Package]" pg. 163 ... In short, I think you have confused the structure of names [in this case, CL symbols] with their use. I think you are confusing YOUR semantics of CL (which may be widespread (Moon seems to share your view of SYMBOLs as being componentles)s) with the semantics actually described in CLtL. I personally find the concept of "atomic" (as opposed to composite) a useless one in CL. I think CLtL agrees; it has virtually eliminated the notion of "atomic". Look at the definition of ATOM on pg. 73 ("is not a CONS"); it says nothing about the notion of atominicity. How sensible is it to view an array as "atomic"? And this brings up the second example of the confusion in constant folding that no one has yet addressed: Why are lists and strings (among others) constant folded, but not general vectors, since all of them are composite objects? I know the answer in CLtL (two non-EQ general vectors are not EQUAL (this is the same reason SYMBOLs aren't folded)); what I want to know is how much sense does this distinction make? For example, according to my understanding of the constant-folding rule: [1] (EQ (QUOTE #1=(gensym)) (QUOTE #1#)) => must be T [2] (EQ (QUOTE #1=#(1 2 3)) (QUOTE #1#)) => must be T [3] (EQ (QUOTE #1=(1 2 3)) (QUOTE #1#)) => T or NIL, wow!!!!! How much sense does the difference in behavior between [2] and [3] make? Now, on the general issue of program "constants". PDP10 MacLisp would "uniquify" constants into a read-only are at load time; other lisps do similar things. I believe this is the intent of the few mumbling words in CLtL about "constants". More importantly, this capability of implementation is so important, and the hacks involved in permitting runtime modification of constants are so un-useful, that CL should probably confront the issue square on. ["un-useful", because the programmer's intent is never more clear when using this hack than when using a more approved way, such as a global parameter explicitly constructed up by techniques like backquote or cons etc.] If this "capability of implementation" is so important, why are so few implementations taking advantage of it? I couldn't get Symbolics CL (which I thought WOULD do it), Vax CL, or KCL to put a "constant" into read-only space. What implementations DO put constants in RO space? ... (defvar *constants-hashtable* (make-hash-table :test 'EQUAL)) (defun quote fexpr (x) (let ((form (car x))) (or (gethash *constants-hashtable* form) (setf (gethash *constants-hashtable* form) (purcopy form))))) should be thought of as minimal definition. As KMP pointed out, you are collapsing two behaviors into one special form. A bad idea in this case. I will have more to say on this in my reply to him. ... [Of course, the hashtable wouldn't really be an EQUAL table, as defined by CLtL, but something more akin to EQUALP. I have seen the term COALESCABLEP used used. It's probably not important just how much "collapsing" goes on.] I hope CLtL would clean-up EQUAL to mean "collapsable" rather than subject the poor Lisp novice to yet another slightly-different equality predicate. -- Nick  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 10 Jun 88 08:05:42 EDT Received: from CUNYVM.CUNY.EDU by SAIL.Stanford.EDU with TCP; 10 Jun 88 04:57:11 PDT Received: from DHVRRZN1.BITNET by CUNYVM.CUNY.EDU (IBM VM SMTP R1.1) with BSMTP id 8778; Fri, 10 Jun 88 07:55:58 EDT Date: Fri, 10 Jun 88 11:07:00 MEZ To: common-lisp@sail.stanford.edu From: ZZZO%DHVRRZN1.BITNET@CUNYVM.CUNY.EDU Comment: CROSSNET mail via SMTP@INTERBIT Date: 10 June 1988, 11:06:16 MEZ From: Wolfgang Zocher (0511) 762-3684 ZZZO at DHVRRZN1 To: COMMON-LISP at SAIL.STANFORD.EDU Please put on the mailing list. WZ  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 9 Jun 88 18:24:39 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 9 Jun 88 15:10:13 PDT Received: by labrea.stanford.edu; Thu, 9 Jun 88 15:09:06 PDT Received: from bhopal.lucid.com by edsel id AA16467g; Thu, 9 Jun 88 15:00:38 PDT Received: by bhopal id AA25338g; Thu, 9 Jun 88 14:59:16 PDT Date: Thu, 9 Jun 88 14:59:16 PDT From: Jon L White Message-Id: <8806092159.AA25338@bhopal.lucid.com> To: NGALL@g.bbn.com Cc: goldman@vaxa.isi.edu, cperdue@sun.com, common-lisp@sail.stanford.edu In-Reply-To: NGALL@G.BBN.COM's message of 8 Jun 1988 13:42-EDT <[G.BBN.COM] 8-Jun-88 13:42:34.NGALL> Subject: constant folding/smashing re: My point is that in the form (SETF (SYMBOL-VALUE (QUOTE X)) 1) the quoted object is no more or less "constant" than in the form (SETF (FIRST (QUOTE (A B C))) 1) So why does QUOTE make the components of the list (1 2 3) unmodifiable but not the components of X? Because the semantic model of symbols doesn't consider them to have modifiable components; they are "atomic". In fact, several implementations I'm familiar do a "spaghetti-stack" lookup for the SYMBOL-VALUE function -- not a structure-component fetch. And there have been serious suggestions for flushing the symbol-plist notion in favor of hashtables, or at least encouraging one to use hashtable entries rather than plist entries. The two parts of a symbol that *are* part of their semantics (as opposed to part of their usage) are the symbol-name and the "identity" (read: address). CL specifically makes it an error to update the symbol name; and very little that a user can do will change the address that a symbol is stored in -- i.e., you are guaranteed that (eq 'foo 'foo) is always true. [Remember why EQL was introduced into the language -- (eq n n) is *not* guaranteed to be true for numbers, so that compilers can play the pdlnum game]. In short, I think you have confused the structure of names [in this case, CL symbols] with their use. Now, on the general issue of program "constants". PDP10 MacLisp would "uniquify" constants into a read-only are at load time; other lisps do similar things. I believe this is the intent of the few mumbling words in CLtL about "constants". More importantly, this capability of implementation is so important, and the hacks involved in permitting runtime modification of constants are so un-useful, that CL should probably confront the issue square on. ["un-useful", because the programmer's intent is never more clear when using this hack than when using a more approved way, such as a global parameter explicitly constructed up by techniques like backquote or cons etc.] Perhaps the single most damaging piece of folklore that has confused the issue of program constants is the PDP10 MacLisp "Pun": (defun quote fexpr (x) (car x)) This programmatic "Pun" *** must not *** be allowed to serve as a definition for program constants. At best, something like (defvar *constants-hashtable* (make-hash-table :test 'EQUAL)) (defun quote fexpr (x) (let ((form (car x))) (or (gethash *constants-hashtable* form) (setf (gethash *constants-hashtable* form) (purcopy form))))) should be thought of as minimal definition. This is "minimal" in that at least this much is required for the interpreter's definition of QUOTE to match that of compiled code semantics. And I must stress that we all believe this implementational style for compiled code to be necessary for reasonable performance. [Of course, the hashtable wouldn't really be an EQUAL table, as defined by CLtL, but something more akin to EQUALP. I have seen the term COALESCABLEP used used. It's probably not important just how much "collapsing" goes on.] A word of caution on PURCOPY: (1) PDP10 MacLisp treated symbols separately so that purcopy'ing one didn't require moving it. [incidentally, purcopy basically means "make me a read-only copy which is equal (or coalescablep) to my argument"]. I have some design notes on what to do for symbols when you can't do the PDP10 MacLisp hack; the issues are not semantic, but merely those of efficient implementaiton of SYMBOL-FUNCTION etc. (2) The "read only" copy needn't be be "write-protected"; of course, it helps if it can be made so. Interlisp-D had a notion of unwriteable strings that the microcode could detect and signal an error if you tried to update them [well, microcode "in theory" -- maybe most implementations simply punted to macrocode]. The point is that "it is an error" to update such objects. There are many ways to implement "read only" objects even if you don't want that to mean "create the object on a write-protected page and let the operating-system give the protection". The buzz words are "Don't confuse semantics with implementational hacks". -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 9 Jun 88 17:51:02 EDT Received: from Xerox.COM by SAIL.Stanford.EDU with TCP; 9 Jun 88 14:39:09 PDT Received: from Burger.ms by ArpaGateway.ms ; 09 JUN 88 14:31:06 PDT Sender: "Leo_Vetter.WBST207V"@Xerox.COM Date: 9 Jun 88 13:25:50 PDT (Thursday) Subject: Remove from Distribution From: "Leo_Vetter.WBST207V"@Xerox.COM To: LispUsers^.X@Xerox.COM, scheme@mc.lcs.mit.EDU, common-lisp@sail.stanford.EDU, info-1100@sumex-aim.stanford.EDU, franz-friends@berkeley.EDU, kcl@cli.COM cc: LV.WBST207V@Xerox.COM Reply-to: "Leo_Vetter.WBST207V"@Xerox.COM Message-ID: <880609-143106-5374@Xerox> Please remove me from all LISP DLs. Thanks, Leo Vetter  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 9 Jun 88 17:43:00 EDT Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 9 Jun 88 14:29:09 PDT Posted-Date: Thu, 09 Jun 88 14:28:50 PDT Message-Id: <8806092128.AA23723@vaxa.isi.edu> Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51) id AA23723; Thu, 9 Jun 88 14:28:59 PDT To: COMMON-LISP@sail.stanford.edu From: goldman@vaxa.isi.edu Subject: Re: constant folding/smashing Cc: KMP@stony-brook.scrc.symbolics.com, miller@acorn.cs.rochester.edu Date: Thu, 09 Jun 88 14:28:50 PDT Sender: goldman@vaxa.isi.edu Kent Pitman's 1.5 bit rule is correct as far as it goes, but doesn't supply enough bits to cover the set of declarations of "constant"ness under discussion. 1) It says nothing about whether (portions of) the constant can be COLLAPSED to EQness with (portions of) other constants. I am starting to believe this may be a moot point, and that NOBODY really wants to authorize an implementation to EQify values just because they have been declared constant. 2) It does not address how much of READ-ONLY datum is read only. It seems to imply that KMP does NOT like the distinction made currently between lists and arrays. But it does not say whether, if a list is "read only" constant, its component lists must be read-only as well. Nor does it imply anything about other (non list or array) datatypes that might appear QUOTEd. Just suppose I want to establish a symbol with a couple special properties that I use as a constant -- (QUOTE #,(let ((s (gensym))) (setf s 0 (get s 'indicator1) 0 (get s 'indicator2) 0))) Suppose further that I do NOT intend to change the value cell of this symbol, or change, add, or remove any of the properties of this constant symbol -- just read them. Should I be able to declare any of this to the lisp implementation, so it can produce better code or allocate structure in read-only memory? Maybe so, but certainly not by differently named variants of QUOTE. So the only reason I can see for inventing any variant special forms, is that there are a very few variants (but more than 1) that cover the overwhelming majority of uses. On the other hand, a syntax along the lines of QUOTE object &rest declarations leaves room for extensibility. A comment on Brad Miller's question: It is still an open question, however, as to when the compiler is allowed to take advantage of read-only objects and treat them as inline. That is, given: (defun foo () (constant '(a b c)) (defun mumble () (foo)) is the compiler allowed to collapse mumble into the equivalent of foo? Seems like a red herring to me. Why would the fact that foo happens to compute a CONSTANT result influence whether or not calls on it are allowed to be INLINEd? I don't think anyone would want foo INLINEd if it were not explicitly declared INLINE. I see nothing in CLtL that could be construed to authorize doing so. This is NOT the issue of constant folding discussed in earlier messages in this series -- they have to do with the folding of SYMBOL values for symbols declared DEFCONSTANT. (This folding is authorized by CLtL on P. 69) Neil  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 9 Jun 88 05:15:17 EDT Received: from lindy.Stanford.EDU by SAIL.Stanford.EDU with TCP; 9 Jun 88 02:03:38 PDT Received: by lindy.Stanford.EDU (4.0/4.7); Thu, 9 Jun 88 02:03:24 PDT Received: by Forsythe.Stanford.EDU; Thu, 9 Jun 88 02:03:22 PDT Received: by AEARN (Mailer X1.24) id 1010; Thu, 09 Jun 88 10:22:36 EDT Date: Thu, 09 Jun 88 09:51:55 EDT From: Hubert Hofbauer Subject: CLOS questions, PCL version To: Pavel Curtis , Common-Lisp@Sail.Stanford.EDU Cc: Gregor.pa@Xerox.COM, CommonLoops-Coordinator.pa@Xerox.COM Sorry to bother you. But i did not yet get any responses from mailings to Gregor.pa and CommonLoops-Coordinator.pa. I have seen your address on a posting to the Scheme mailing list. I need information on the Common Lisp Object System (CLOS) and on the Portable Common LOOPS (PCL) implementation: - documents on the CLOS standard in general - information on PCL, particularly how to define meta classes The PCL version i have is 5/22/87, delivered with DEC VAX-Lisp. Since i am on Bitnet i do not have ftp access to the pcl directories at parcvax. I need somebody who send new versions of the files via mail to me. Please help me, Hubert Hofbauer or if this does not work PS.: If Common-Lisp is a public mailing list, i would like to subscribe. +-----------------------------------------------+-----------------------+ ! Hubert Hofbauer ! K311770@AEARN.BITNET ! ! Research Institute for Symbolic Computation ! RISC ! ! Johannes-Kepler-Universitaet Linz ! JKU Linz ! ! A-4040 Linz ! Austria / Europe ! +-----------------------------------------------+-----------------------+  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Jun 88 17:23:22 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 8 Jun 88 14:08:22 PDT Received: from EUPHRATES.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 416610; Wed 8-Jun-88 17:07:34 EDT Date: Wed, 8 Jun 88 17:07 EDT From: David A. Moon Subject: Re: constant folding/smashing To: NGALL@G.BBN.COM cc: cperdue@SUN.COM, common-lisp@SAIL.STANFORD.EDU In-Reply-To: <[G.BBN.COM] 8-Jun-88 13:42:34.NGALL> Message-ID: <19880608210715.1.MOON@EUPHRATES.SCRC.Symbolics.COM> Date: 8 Jun 1988 13:42-EDT From: NGALL@G.BBN.COM So why does QUOTE make the components of the list (1 2 3) unmodifiable but not the components of X? Try thinking of it this way: Symbols don't -have- components. There are several -associations- from symbols to other objects, accessed by such functions as SYMBOL-VALUE and SYMBOL-PACKAGE. Naturally the mutability of these assocations does not depend on whether the participants in the associations are also used as constants in one or more programs. This is the qualitative difference between a symbol and a cons. Of course this is only a point of view, but I think it properly reflects what Lisp programmers expect. People are sometimes misled into thinking that SYMBOL-PLIST and CDR are both components, because both are implemented by the HRRZ instruction on the pdp-10, but that's thinking in terms of the implementation rather than in terms of the semantics.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Jun 88 17:08:13 EDT Received: from ACORN.CS.ROCHESTER.EDU by SAIL.Stanford.EDU with TCP; 8 Jun 88 13:49:33 PDT Received: from DOUGHNUT.CS.ROCHESTER.EDU by ACORN.CS.ROCHESTER.EDU via CHAOS with CHAOS-MAIL id 42371; Wed 8-Jun-88 16:47:51 EDT Date: Wed, 8 Jun 88 16:49 EDT From: Brad Miller Subject: Re: constant folding/smashing To: Kent M Pitman cc: Common-Lisp@SAIL.Stanford.EDU, cperdue@sun.com, NGALL@g.bbn.com, goldman@vaxa.isi.edu In-Reply-To: <880607180851.3.KMP@PEWEE.SCRC.Symbolics.COM> Message-ID: <19880608204902.2.MILLER@DOUGHNUT.CS.ROCHESTER.EDU> Sender: miller@cs.rochester.edu Reply-To: miller@cs.rochester.edu Organization: University of Rochester, Department of Computer Science Postal-address: 610 CS Building, Comp Sci Dept., U. Rochester, Rochester NY 14627 Phone: 716-275-1118 Date: Tue, 7 Jun 88 18:08 EDT From: Kent M Pitman I don't know what these primitives should be called, exactly, but here are some straw-men for people to discuss: #1: (QUOTE x) might mean X is not evaluated and is also read-only and (IMMEDIATE x) might mean X is not evaluated but is NOT read-only. #2: (QUOTE x) might mean X is not evaluated and NOT read-only (CONSTANT x) might mean X is not evaluated and is also read-only. How about #3: (QUOTE x) means X is not evaluated and is NOT read-only (CONSTANT x) means X *is* evaluated and is read-only. Thus the resulting objects from: (CONSTANT '(A B C)) is a read-only list '(A B C) isn't. (constant (foo x)) evals the function and the result is read-only. (foo x) has a non-read-only result (unless the function foo DECLARED it to be read-only) I don't particularly care for the [] syntax, but only because those have been marked as explicitly reserved to the user and never to be defined by CL. It is still an open question, however, as to when the compiler is allowed to take advantage of read-only objects and treat them as inline. That is, given: (defun foo () (constant '(a b c)) (defun mumble () (foo)) is the compiler allowed to collapse mumble into the equivalent of foo? If so, foo cannot be incrementally recompiled, and debugging mumble gives some non-intuitive results since the function call on foo may represent a logical partition of the problem space. (Thus one gives up some of the advantage of source level debugging...) So, while we have introduced a syntactic construct to allow the user to distinguish between the eval/ro distinction, we still have a foldability distiction that we may want to control on a finer level than the OPTIMIZE switches will allow, and we may not be able to just define it syntactically (though a FOLDABLE or DONT-FOLD construction similar to the QUOTE/CONSTANT might be a step). Here is a side example of this folding problem that declarations may not help (due to quiroz@cs.rochester.edu): (foo (CONSTANT '(NIL)) (CONSTANT (CONS NIL NIL))) Now, are the first and second arguments to foo EQ or not? The point is, that just because two objects are read-only and EQUAL does not mean that we necessarily want to imply that they are EQ, and further that whatever is decided we don't want different implementations doing different things here. It seems to me that the default should be NOT eq, because if the programmer had INTENDED eqness, they should have done something along the lines of: (let ((bar (constant '(nil)))) (foo bar bar)) and now the EQness is explicit and obvious. The point is, there is a distinction between ACCIDENTAL EQness and INTENTIONAL EQness. The compiler and interpreter probably should never[1] take advantage of ACCIDENTAL EQness. If the programmer had intended two objects to be EQ, he should have cons'd them that way. Another question, is defun the rough equivalent of (setf (symbol-function x) ...) or (setf (symbol-function x) (CONSTANT ...)) or <> (setf (CONSTANT (symbol-function x)) ...) or (setf (CONSTANT (symbol-function x)) (CONSTANT ...)) i.e. to say that this symbol's functional value happens to evaluate to this function, or this symbol's functional value happens to evaluate to this constant function, or this symbol's functional value *will always* evaluate to this function/ constant function. In the first two cases, we are allowing the symbol to be associated with new functions later (e.g. incremental compiles), and in the latter two this is prevented. The semantic difference between the second and forth and the first and third is whether the function may self-modify. Currently, my opinion is along the lines of: Yes, we do need to make a distinction as KMP suggests, because these are different things, and the programmer should be able to represent them explicitly. However, compilers should not take advantage of anything that has a cost in terms of debugging or loss of incremental compiling[1]. Both *can* be maintained, of course, if we want to carry around a list of all the references to a function that has been folded, but the performance cost of so doing may be significant. Further this syntactic issue still hasn't addressed a more fundamental problem, namely the necessity of being able to control the compilers behavior when it crosses objects that are accidentally equivalent in some agreed upon sense (e.g. EQUAL). [1]: (unless, of course one is doing optimize safety 0, speed 3, stupidity 3) ---- Brad Miller U. Rochester Comp Sci Dept. miller@cs.rochester.edu {...allegra!rochester!miller}  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Jun 88 17:06:59 EDT Received: from ACORN.CS.ROCHESTER.EDU by SAIL.Stanford.EDU with TCP; 8 Jun 88 13:52:28 PDT Received: from DOUGHNUT.CS.ROCHESTER.EDU by ACORN.CS.ROCHESTER.EDU via CHAOS with CHAOS-MAIL id 42373; Wed 8-Jun-88 16:51:33 EDT Date: Wed, 8 Jun 88 16:52 EDT From: Brad Miller Subject: Re: Call for publishable code! To: Pavel.pa@Xerox.COM cc: LispUsers^.x@Xerox.COM, scheme@mc.lcs.mit.edu, common-lisp@sail.stanford.edu, info-1100@sumex-aim.stanford.edu, franz-friends@berkeley.edu, kcl@cli.com In-Reply-To: <880608-125943-2995@Xerox> Message-ID: <19880608205244.4.MILLER@DOUGHNUT.CS.ROCHESTER.EDU> Sender: miller@cs.rochester.edu Reply-To: miller@cs.rochester.edu Organization: University of Rochester, Department of Computer Science Postal-address: 610 CS Building, Comp Sci Dept., U. Rochester, Rochester NY 14627 Phone: 716-275-1118 Date: Wed, 8 Jun 88 11:49:09 PDT From: Pavel.pa@Xerox.COM You might also try (sending your message to): SLUG@ai.sri.com (Symbolics lisp user group) info-ti-explorer@sumex-aim.stanford.edu Regards, ---- Brad Miller U. Rochester Comp Sci Dept. miller@cs.rochester.edu {...allegra!rochester!miller}  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Jun 88 16:13:24 EDT Received: from Xerox.COM by SAIL.Stanford.EDU with TCP; 8 Jun 88 13:01:16 PDT Received: from Cabernet.ms by ArpaGateway.ms ; 08 JUN 88 12:59:43 PDT Date: Wed, 8 Jun 88 11:49:09 PDT From: Pavel.pa@Xerox.COM Subject: Call for publishable code! To: LispUsers^.x@Xerox.COM, scheme@mc.lcs.mit.edu, common-lisp@sail.stanford.edu, info-1100@sumex-aim.stanford.edu, franz-friends@berkeley.edu, kcl@cli.com Reply-To: Pavel.pa@Xerox.COM Message-ID: <880608-125943-2995@Xerox> I am the editor of the new Algorithms department of the international newsletter/journal Lisp Pointers. The department is intended to cater to the perceived preferences of most Lisp hackers: they'd rather write code than articles. The articles in the department therefore fall into one or more of the following three broad categories: -- Annotated implementations of interesting and relevant algorithms that make particularly good or novel use of the unique features of the Lisp family of programming languages (e.g., closures, continuations, code as data, polymorphism), -- Annotated implementations of algorithms whose subject matter is the Lisp family of languages (e.g., code analysis tools, iteration facilities, generic arithmetic), and -- Discussion of performance issues, benchmarking, or implementation experiences for interesting algorithms written in or about the Lisp family of languages. I am continually looking for ideas for appropriate articles for the department. If you've got a nice hack you're proud of, or a particularly elegant piece of code (you know, the kind that you call in one of your fellow hackers to see) and you'd like to see it written up in the Algorithms department, please send it along. What you give me doesn't have to be polished or even contain any prose; if I agree that it's appropriate for the column, I'll work with you to put together an article around it. Hoping to hear from you, Pavel Curtis Xerox PARC/CSL 3333 Coyote Hill Rd. Palo Alto, CA 94304 (415) 494-4455 Pavel.pa@Xerox.Com  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Jun 88 16:10:14 EDT Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 8 Jun 88 12:57:20 PDT Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0) id AA18694; Wed, 8 Jun 88 12:54:12 PDT Received: from clam.sun.com by snail.sun.com (4.0/SMI-3.2) id AA13089; Wed, 8 Jun 88 12:50:54 PDT Received: by clam.sun.com (3.2/SMI-3.2) id AA11482; Wed, 8 Jun 88 12:56:45 PDT Date: Wed, 8 Jun 88 12:56:45 PDT From: cperdue@Sun.COM (Cris Perdue) Message-Id: <8806081956.AA11482@clam.sun.com> To: NGALL@G.BBN.COM Subject: Re: constant folding/smashing Cc: common-lisp@SAIL.STANFORD.EDU > I don't believe the following form is in error > (SETF (SYMBOL-VALUE (QUOTE X)) 1) > even though X is wrapped by (QUOTE ...) and is therefore being > "written as a constant value in a program." (See above) The reason > this ISN'T an "intolerable situation" is that in the case of a symbol, > EQUAL is the same as EQ, so you don't get UNEXPECTED side-effects. > Agreed. > What WOULD be intolerable would be to follow your rule ("side-effects > on constants are in error") and say that the above form is in error. > That would force people to write such things as > (SETF (SYMBOL-VALUE (INTERN "X")) 1) > I don't think anyone intends to be proposing this. I don't. -Cris  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Jun 88 13:55:24 EDT Received: from G.BBN.COM by SAIL.Stanford.EDU with TCP; 8 Jun 88 10:43:40 PDT Date: 8 Jun 1988 13:42-EDT Sender: NGALL@G.BBN.COM Subject: Re: constant folding/smashing From: NGALL@G.BBN.COM To: cperdue@SUN.COM Cc: common-lisp@SAIL.STANFORD.EDU Message-ID: <[G.BBN.COM] 8-Jun-88 13:42:34.NGALL> In-Reply-To: <8806071724.AA08861@clam.sun.com> Date: Tue, 7 Jun 88 10:24:20 PDT From: cperdue@Sun.COM (Cris Perdue) ... > It is this aspect of `constant'ly returning the same (EQ) object that > is meant in the sentence on pg. 86: "[QUOTE] allows any Lisp object to > be written as a constant value in a program." It is the value of the > (QUOTE ...) form that is held constant, not the object itself. The > same (EQ) object will always be referenced, but that object may be > modified over time (if it is a composite object). The problem with this conclusion is that if the storage for constants is "collapsed" together, it is impossible to know how many constants are changing if you change a constant. A constant in someone else's code, even system code, may be changed by your side effect. This is an intolerable situation, so side-effects on constants are an error. -Cris I don't believe the following form is in error (SETF (SYMBOL-VALUE (QUOTE X)) 1) even though X is wrapped by (QUOTE ...) and is therefore being "written as a constant value in a program." (See above) The reason this ISN'T an "intolerable situation" is that in the case of a symbol, EQUAL is the same as EQ, so you don't get UNEXPECTED side-effects. What WOULD be intolerable would be to follow your rule ("side-effects on constants are in error") and say that the above form is in error. That would force people to write such things as (SETF (SYMBOL-VALUE (INTERN "X")) 1) My point is that in the form (SETF (SYMBOL-VALUE (QUOTE X)) 1) the quoted object is no more or less "constant" than in the form (SETF (FIRST (QUOTE (A B C))) 1) So why does QUOTE make the components of the list (1 2 3) unmodifiable but not the components of X? What causes the UNEXPECTED side effects in the latter form is the folding of EQ but not EQUAL objects into one object. I am currently thinking of a way to use DEFCONSTANT to limit such CONSTANT folding in a CLtL compatible way (i.e., don't constant fold the values of DEFCONSTANT). -- Nick  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Jun 88 06:01:30 EDT Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 8 Jun 88 02:50:04 PDT Received: from maths.bath.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP id aa03406; 8 Jun 88 10:39 BST Received: from xenakis by mordell.maths.bath.AC.UK id aa02893; 8 Jun 88 10:37 BST To: ETSTMOL <@cunyvm.cuny.edu:ETSTMOL@hdetud1.bitnet> CC: common-lisp@sail.stanford.edu In-reply-to: ETSTMOL's message of Tue, 07 Jun 88 09:57:40 MET Date: Wed, 8 Jun 88 10:40:02 BST From: jpff%maths.bath.ac.uk@NSS.Cs.Ucl.AC.UK Sender: jpff%maths.bath.ac.uk@NSS.Cs.Ucl.AC.UK How is progress on 1-lisp and 2-lisp? This question is one I get asked a great deal by beginners and non soaked-in-the-culture types. I read that a document was to be prepared by mid June on this issue. ==John  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Jun 88 18:27:01 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 7 Jun 88 15:08:50 PDT Received: from PEWEE.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 416067; Tue 7-Jun-88 18:09:02 EDT Date: Tue, 7 Jun 88 18:08 EDT From: Kent M Pitman Subject: Re: constant folding/smashing To: Common-Lisp@SAIL.Stanford.EDU cc: miller@acorn.cs.rochester.edu, cperdue@sun.com, NGALL@g.bbn.com, goldman@vaxa.isi.edu References: <8806072027.AA08564@vaxa.isi.edu>, <8806071724.AA08861@clam.sun.com>, <19880601211515.2.MILLER@DOUGHNUT.CS.ROCHESTER.EDU>, <[G.BBN.COM] 1-Jun-88 15:36:21.NGALL> Message-ID: <880607180851.3.KMP@PEWEE.SCRC.Symbolics.COM> Since we're in the process of a CL overhaul, I'm not so concerned with what's allowed as what should be. Whether the (FOO BAR BAZ) is interpretable as read-only or not by a compiler in (DEFUN FOO-BAR-OR-BAZ-P (X) (MEMBER X '(FOO BAR BAZ)) is not very interesting. Indeed, even in (DEFUN FOO-BAR-BAZ () '(FOO BAR BAZ)) I'm happy to have this return a read-only list or a list shared with other programs because even when sharing doesn't occur, I could get screwed by modifying the list. Consider: (DEFUN FOO-BAR-OR-BAZ-P (X) (MEMBER X (FOO-BAR-BAZ))) (DEFUN QUUXIFY (THING) (NCONC THING (LIST 'QUUX))) (QUUXIFY (FOO-BAR-BAZ)) => (FOO BAR BAZ QUUX)) (QUUXIFY (FOO-BAR-BAZ)) => (FOO BAR BAZ QUUX QUUX)) HOWEVER, I am -very- concerned about the following case: (DEFVAR *FOO-LIST* (LIST (MAKE-ARRAY 5) (MAKE-ARRAY 5))) (DEFUN FOO-0 () '#,(NTH 0 *FOO-LIST*)) (DEFUN FOO-1 () '#,(NTH 1 *FOO-LIST*)) I want to be programming in a language that guarantees that if I modify (NTH 0 *FOO-LIST*), then the array returned by FOO-0 will have been modified. Moreover, I want my language of choice to guarantee that FOO-0 and FOO-1 will not return EQ values. In programming terms, I want the following to be true immediately after loading the preceding three forms: (EQ (FOO-0) (NTH 0 *FOO-LIST*)) => T (EQ (FOO-1) (NTH 1 *FOO-LIST*)) => T (EQ (FOO-0) (FOO-1)) => NIL I'm concerned that under CLTL it seems to me just as valid to get: (EQ (FOO-0) (NTH 0 *FOO-LIST*)) => NIL (EQ (FOO-1) (NTH 1 *FOO-LIST*)) => NIL (EQ (FOO-0) (FOO-1)) => T In particular, if *FOO-LIST* is a registry of arrays or structures which is expensive to select from but which might need to be dynamically altered, and my purpose in using #, is to allow me to do that access once and for all at load time, but I may not wish to commit to the unchangingness of those arrays. If QUOTE is going to foist constancy on me, I'm screwed. There are solutions like using closures, but they are not guaranteed to be fast, whereas QUOTE is fast in every dialect. There are clearly two issues involved: - is the object evaluated or not - is the object constant or not Long ago, I made a rule of thumb which I've not yet found to be violated: If you have two boolean quantities to represent, don't try to do it with one bit. What happens when you violate this rule is that you let a user write just 0 or 1 and then you waste endless time arguing over whether they really meant 00, 01, 10, or 11 when instead you should have just let them write 00, 01, 10, or 11 and been done with it. [Friends who read drafts of this message have jokingly dubbed this "KMP's two-bit rule". Whatever you call it, you'll quickly see that it is quite applicable to this problem.] People have legitimate reasons for having quoted constants and quoted non-constants, so should have two primitives to control the orthogonal features of evaluation and object constancy. Then programmers could just say what they want to say and overzealous implementors wouldn't keep trying to second-guess them and keep them from getting work done. I don't know what these primitives should be called, exactly, but here are some straw-men for people to discuss: #1: (QUOTE x) might mean X is not evaluated and is also read-only and (IMMEDIATE x) might mean X is not evaluated but is NOT read-only. #2: (QUOTE x) might mean X is not evaluated and NOT read-only (CONSTANT x) might mean X is not evaluated and is also read-only. [The observant reader will note that this is only 1.5 bits (not 2 bits) of information. You can write either x, (QUOTE x), or (CONSTANT x) but there is nothing that says this is a constant, evaluated expression. I didn't propose that just because no one is asking for it. If there were a strong need, I might have proposed that [...] means like (...) except that it allocates the list in read-only space. Then '[A B C] would be EQUAL to '(A B C) but '[A B C] would designate an unchanging expression and '(A B C) would not. There have been Lisp dialects which took this approach and got useful mileage out of it, but I'm stopping short of proposing we go that route.] Having a facility like this, I could presumably then do either (CONSTANT #,X) or (IMMEDIATE #,X) as appropriate ... or I could even still use (QUOTE #,X) -- if only I knew which of CONSTANT and IMMEDIATE QUOTE meant!  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Jun 88 16:44:17 EDT Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 7 Jun 88 13:26:19 PDT Posted-Date: Tue, 07 Jun 88 13:27:08 PDT Message-Id: <8806072027.AA08564@vaxa.isi.edu> Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51) id AA08564; Tue, 7 Jun 88 13:27:21 PDT To: COMMON-LISP@sail.stanford.edu From: goldman@vaxa.isi.edu Subject: Re: constant folding/smashing Cc: miller@acorn.cs.rochester.edu, cperdue@sun.com, NGALL@g.bbn.com Date: Tue, 07 Jun 88 13:27:08 PDT Sender: goldman@vaxa.isi.edu Thanks for pointing out that paragraph on P.78 that explicitly authorizing "collapsing" EQUAL constants to EQ. That at least provided a recorded justification for the compiler's action. By the way, does anyone know the rationale behind this authorization? Is there a big win in implementation, or is to discourage perceived misuse of EQ-based discriminations by programmers? It seems to me to rule out some sensible programs (and transformations), as well as plenty of bad ones. At any rate, as can be seen from the responses, CLtL still fails to make clear what must be held constant about an object used as a constant in a program (whether declared with DEFCONSTANT or appearing in a QUOTEd form). One hypothesis of INTENT (although it does not necessarily follow from the text) is: Let V1 be a "constant" value. If V1 is an instance of any of the types (listed below) for which "components" are considered in the definition of EQUALity, then it is an ERROR for a program to modify any of those particular components of V1. In particular, they cannot even be changed to an EQUAL "copy" of their value. In other words, the "boundary" of constanthood is described by the definition of EQUAL on P.80 -- it prohibits changing: the car or cdr of a CONS elements of STRINGs or BIT-VECTORs components "(host, device, and so on)" of pathnames Within this boundary, the parts must remain EQ forever. Allocating these parts in read-only memory is therefore permissible. I have two questions about this: 1) is the above clear enough that an implementor knows what is allowed and a programmer knows what he is saying? 2) Is it the right framework for an answer? I believe that the best way to define constanthood for lisp is in terms of the boundary used by SOME equivalence predicate. I think that within that boundary, constants should be constrained to remain constant up to EQness. But it doesn't follow, and I don't advocate, authorizing an implemenation to collapse constants, OR PORTIONS THEREOF (is there an implication that one can collapse selective parts?), that happen to satisfy that equivalence predicate. 3) Is EQUAL what we need? Frankly, I fail to see what is so interesting about EQUAL that makes it the "best" equivalence predicate to use. Why not EQUALP? I like EQUALP better, except for the fact that numbers of different type can be EQUALP. CommonLisp is full of generic sequence operations. But EQUAL is not one of them. It behaves quite differently for lists and vectors, and NEVER considers a list EQUAL to a vector. [This is the source of one's natural surprise in the example pointed out by Nick Gall -- that (setf (elt '#(#\a #\b #\c) 0) #\x) must be legal.] Because of this, a transformation that changes representations between lists and vectors runs into oddball semantic problems wherever EQUAL is used and, given the current semantics, wherever constants need to be transformed. Neil  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Jun 88 14:29:10 EDT Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 7 Jun 88 10:23:31 PDT Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0) id AA25609; Tue, 7 Jun 88 10:22:12 PDT Received: from clam.sun.com by snail.sun.com (4.0/SMI-3.2) id AA08422; Tue, 7 Jun 88 10:18:38 PDT Received: by clam.sun.com (3.2/SMI-3.2) id AA08861; Tue, 7 Jun 88 10:24:20 PDT Date: Tue, 7 Jun 88 10:24:20 PDT From: cperdue@Sun.COM (Cris Perdue) Message-Id: <8806071724.AA08861@clam.sun.com> To: NGALL@G.BBN.COM, goldman@VAXA.ISI.EDU Subject: Re: constant folding/smashing Cc: common-lisp@SAIL.STANFORD.EDU It was an odd sensation to me to read Nick (Gall(?))'s note. To me, everything he said made sense, down to this paragraph: > It is this aspect of `constant'ly returning the same (EQ) object that > is meant in the sentence on pg. 86: "[QUOTE] allows any Lisp object to > be written as a constant value in a program." It is the value of the > (QUOTE ...) form that is held constant, not the object itself. The > same (EQ) object will always be referenced, but that object may be > modified over time (if it is a composite object). The problem with this conclusion is that if the storage for constants is "collapsed" together, it is impossible to know how many constants are changing if you change a constant. A constant in someone else's code, even system code, may be changed by your side effect. This is an intolerable situation, so side-effects on constants are an error. -Cris  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Jun 88 14:28:49 EDT Received: from G.BBN.COM by SAIL.Stanford.EDU with TCP; 7 Jun 88 07:22:16 PDT Date: 7 Jun 1988 10:21-EDT Sender: NGALL@G.BBN.COM Subject: Re: little question From: NGALL@G.BBN.COM To: ETSTMOL%HDETUD1.BITNET@CUNYVM.CUNY.EDU Cc: common-lisp@SAIL.STANFORD.EDU Message-ID: <[G.BBN.COM] 7-Jun-88 10:21:55.NGALL> In-Reply-To: The message of Tue, 07 Jun 88 09:57:40 MET from ETSTMOL%HDETUD1.BITNET@cunyvm.cuny.edu Date: Tue, 07 Jun 88 09:57:40 MET From: ETSTMOL%HDETUD1.BITNET@cunyvm.cuny.edu From: Marcel Mol +31 15 783644 ETSTMOL at HDETUD1 Here is my (little?) question: (... perhaps asked a hundred times :-?) Why does Common Lisp symbols have both a function and a value cell? Why not use one of them and use values and function as in Scheme. Marcel To avoid name clashes. For example, (defun foo (cons) (cons (rest cons) (first cons))) will not work in Scheme, since CONS will not have the correct value (the CONS function). An even worse case is the following: Programmer A writes: (defmacro rev-cons (cons-obj) `(cons (rest ,cons-obj) (first ,cons-obj))) Programmer B writes: (defun zap (cons) (frob (rev-cons cons))) Programmer B is surprised! The real problem is this second example is with the semantics of macros (which Scheme does not "officially" condone (because of the above problem)). But since macros are such an important part of CL and since "sanitizing" is complex, CL skirts the issue by putting functional variables and 'normal' variables is two different namespaces. CL progammers are used to dealing with lots of namespaces: functional, normal variable, package, property-list, etc. -- Nick  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Jun 88 04:12:25 EDT Received: from CUNYVM.CUNY.EDU by SAIL.Stanford.EDU with TCP; 7 Jun 88 00:58:43 PDT Received: from HDETUD1.BITNET by CUNYVM.CUNY.EDU (IBM VM SMTP R1.1) with BSMTP id 1107; Tue, 07 Jun 88 03:58:52 EDT Date: Tue, 07 Jun 88 09:57:40 MET To: common-lisp@sail.stanford.EDU From: ETSTMOL%HDETUD1.BITNET@CUNYVM.CUNY.EDU Comment: CROSSNET mail via SMTP@INTERBIT Date: 7 June 1988, 09:48:35 MET From: Marcel Mol +31 15 783644 ETSTMOL at HDETUD1 To: COMMON-LISP at SAIL.STANFORD Here is my (little?) question: (... perhaps asked a hundred times :-?) Why does Common Lisp symbols have both a function and a value cell? Why not use one of them and use values and function as in Scheme. Marcel  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 6 Jun 88 15:48:25 EDT Received: from NMFECC.ARPA by SAIL.Stanford.EDU with TCP; 6 Jun 88 12:30:14 PDT Received: from tuva.sainet.mfenet by ccc.mfenet with Tell via MfeNet ; Mon, 6 Jun 88 12:30:14 PDT Date: Mon, 6 Jun 88 12:30:14 PDT From: POTHIERS%TUVA.SAINET.MFENET@NMFECC.ARPA Message-Id: <880606123014.20400214@NMFECC.ARPA> To: COMMON-LISP@SAIL.STANFORD.EDU Subject: test Date: Mon, 6-JUN-1988 07:39 MST X-VMS-Mail-To: @COMMON-LISP Please excuse this test.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 1 Jun 88 17:53:55 EDT Received: from ACORN.CS.ROCHESTER.EDU by SAIL.Stanford.EDU with TCP; 1 Jun 88 14:36:30 PDT Received: from DOUGHNUT.CS.ROCHESTER.EDU by ACORN.CS.ROCHESTER.EDU via CHAOS with CHAOS-MAIL id 41778; Wed 1-Jun-88 17:15:12 EDT Date: Wed, 1 Jun 88 17:15 EDT From: Brad Miller Subject: Re: constant folding/smashing To: NGALL@G.BBN.COM cc: goldman@VAXA.ISI.EDU, common-lisp@SAIL.STANFORD.EDU In-Reply-To: <[G.BBN.COM] 1-Jun-88 15:36:21.NGALL> Message-ID: <19880601211515.2.MILLER@DOUGHNUT.CS.ROCHESTER.EDU> Sender: miller@cs.rochester.edu Reply-To: miller@cs.rochester.edu Organization: University of Rochester, Department of Computer Science Postal-address: 610 CS Building, Comp Sci Dept., U. Rochester, Rochester NY 14627 Phone: 716-275-1118 Date: 1 Jun 1988 15:36-EDT From: NGALL@G.BBN.COM I believe there are 3 places in CLtL where "constant objects", "constant values", and "constants in code" are discussed: DEFCONSTANT pgs. 68-69 EQ pg. 78 QUOTE pg. 86 [Any others?] I think we have to be very careful about the semantics of constants and variables. For example, does DEFUN proclaim the functional value of a symbol is a constant? What about (compile 'mumble ...)? I think we must break these constants down into an ontology, and consider each class separately. Variables and Parameters (e.g. from DEFVAR and DEFPARAMETER) are obviously different: Variables are things that may change their values many times during a particular execution, while Parameters are constant during a particular execution. This semantics extends into variables and parameters vis. function calls as well, so we need not limit ourselves to talking about program invocations. But there seem to be some other things as well, though CL (or necessarily any other language) break them out. An Unknown might be defined as an object that changes at most once during a particular execution. (A single assignment variable). Prolog variables are a good example. (I don't necessarily think they should be in common lisp, though they are rather hard to add given there is no way to make new first-class objects.) A Functional constant may be one that rarely changes between executions of a funcion/program and never during execution. THe usual use of DEFUN covers this: if you blow into the debugger and redefine a function, you don't expect invocations of the function below you on the stack to be updated with the new definition. Note that functions that are redefined during execution are considered variables under this ontology. A Declared constant (e.g. objects created by DEFCONSTANT) is one that Never changes in a particular implementation. The compiler is allowed to fold these things safely, since the user will not be expected to incrementally patch them, without recompiling the entire system. Macros, (unfortunately in some sense,) currently have this semantics. A Defined constant is something that never changes BETWEEN implementations. I.e. the value of PI, or other things some STANDARD defines. I separate this from declared constant, because when one reads the symbol PI or E or whatever, one beleives the reference is to this well known object (though the implementation may have an imperfect description) rather than to some constant the programmer has happened to name that. I suppose if one wanted to wax ontological, one could separate two kinds of defined constants: those that have a value as a matter of logical necessity, i.e. their value is part of their definitions (e.g. PI) and those that simply are not known to have changed in human experience, so we can assume they are constant for all practical purposes (an empirical constant, like the speed of light in a vacuum) Now for each of these types (and a finer ontology than this may certainly be necessary) there are the issues of when it is safe or unsafe for the compiler to fold, and when it is just a good or a bad idea for the compiler to fold, based on the information that will be preserved for the debugger, allowing incremental redefinition, etc. Now the question becomes, what sort of object is 'A? A declared constant, a functional constant, or even a parameter? I infer that some people want to treat it as a functional constant, which would make folding undesirable (at least), and others a declared constant where folding would be desireable (or at least safe and logical). We also have to be careful in that the properties of an object may, indeed must be treated separately. A's functional value my be a functional constant, but it's symbol-value may be a variable or parameter. The same can be said of any other properties of the object, except for it's printname, which would seem to be a defined constant (the object that I write as A has a printname of "A" is the way these sorts of atoms are defined by the language). ---- Brad Miller U. Rochester Comp Sci Dept. miller@cs.rochester.edu {...allegra!rochester!miller}  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 1 Jun 88 16:15:42 EDT Received: from G.BBN.COM ([8.2.0.18]) by SAIL.Stanford.EDU with TCP; 1 Jun 88 12:37:28 PDT Date: 1 Jun 1988 15:36-EDT Sender: NGALL@G.BBN.COM Subject: Re: constant folding/smashing From: NGALL@G.BBN.COM To: goldman@VAXA.ISI.EDU Cc: common-lisp@SAIL.STANFORD.EDU Message-ID: <[G.BBN.COM] 1-Jun-88 15:36:21.NGALL> I believe there are 3 places in CLtL where "constant objects", "constant values", and "constants in code" are discussed: DEFCONSTANT pgs. 68-69 EQ pg. 78 QUOTE pg. 86 [Any others?] What do these sections explicitly state about what is actually being held constant and what can still be modified? The DEFCONSTANT section, pgs. 68-69, explicitly allows "constant folding" (i.e., "replac[ing] references to the name of the constant by the value of the constant"). In this case, it is clear the the value-cell of DEFCONSTANT's first argument (a symbol) is held constant. But it does not state that any of the symbol's other `components' are held constant. E.g., Can that symbol's function-cell or plist or home-package be modified? I believe most implementations correctly infer the answer to be "YES". Pgs. 68-69 also do not state whether or not the object contained in the constant's value-cell may have its components modified (assuming it is a composite object)? I.e., Is the value itself held constant? I'm not sure how most implementations have decided this, but I am sure that the DEFCONSTANT section does not authorize it (even implicitly). In the EQ section, pg. 78, "constant collapsing" is explicitly allowed. This is not the same thing as "constant folding" (For a while I thought it was.) Constant folding means replacing a name by its value (an object). Constant collapsing means replacing 2 or more "constants in code to be compiled" that are EQUAL but not EQ with a single one of those objects. What is a "constant in code to be compiled?" An answer to this question is given on pg. 78: "An object is considered to be a constant in code to be compiled if it is a self-evaluating form or is contained in a QUOTE form." This does not seem to allow constant collapsing of the values of DEFCONSTANTs. I think this is an oversight, since pg. 69 allows the compiler to "replace references ... by the value of the constant ... in order to allow further optimizations [e.g., constant collapsing]." So far, we have seen two types of `constant assumption/optimization' explicity permitted: constant folding and constant collapsing. Neither has suggested the optimization/assumption that a composite object may be made `Read-Only'. What about pg. 86, the section on QUOTE. Unfortunately, QUOTE muddies the waters by using such phrases as "constant data object", "constant object", and "constant value". It is my contention though, that these phrases imply nothing more than the longer phrase "constant in code" and do NOT imply that the data object itself is held to be constant. I contend that the QUOTE special form is nothing more than a way of providing an `anonymous DEFCONSTANT', i.e., a form that is guaranteed to return the same (i.e, EQ) value EVERY time. For example, the following DEFUN of FOO using QUOTE (DEFUN FOO (N) (IF (< -1 N (LENGTH (QUOTE (1 2 3)))) (ELT (QUOTE (1 2 3)) N) NIL)) is semantically equivalent to the following DEFUN using an `anonymous DEFCONSTANT' (PROGN (DEFCONSTANT #1=#:ANON-CONST (LIST 1 2 3)) (DEFUN FOO (N) (IF (< -1 N (LENGTH #1#)) (ELT #1# N) NIL))) It is this aspect of `constant'ly returning the same (EQ) object that is meant in the sentence on pg. 86: "[QUOTE] allows any Lisp object to be written as a constant value in a program." It is the value of the (QUOTE ...) form that is held constant, not the object itself. The same (EQ) object will always be referenced, but that object may be modified over time (if it is a composite object). Thus, I believe that the practice of collapsing an object that is a "constant in code to be compiled" with an EQUAL object in Read-Only space is not authorized by CLtL, even implicitly. Moreover, I think that the practice of collapsing an object that is a "constant in code to be compiled" with an EQUAL object in Read-Only space is a bad idea, since it violates the Consistency requirement between compiler and interpreter. When learning/experimenting-with Lisp at Top-Level, people regularly type in forms such as (setf (first '(1 2 3)) 'a) which won't work if quoted objects are collapsed into Read-Only space. Also it is hard to understand why (setf (elt '"abc" 0) #\A) is illegal (setf (elt '#(#\a #\b #c) 0) #\A) is not. (You can't collapse the general array to Read-Only space since for it to be EQUAL it must be EQ! This is why (setf (symbol-plist 'X) '()) doesn't cause a memory violation.) In summary, CLtL explicitly permits two constant optimizations: folding and collapsing. But it says nothing (as far as I have found) about what would permit an object to be put into Read-Only space, i.e., to be made unmodifiable. -- Nick  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 31 May 88 16:07:25 EDT Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 31 May 88 12:51:43 PDT Posted-Date: Tue, 31 May 88 12:52:46 PDT Message-Id: <8805311952.AA09512@vaxa.isi.edu> Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51) id AA09512; Tue, 31 May 88 12:52:50 PDT To: common-lisp@sail.stanford.edu From: goldman@vaxa.isi.edu Subject: constant folding/smashing Date: Tue, 31 May 88 12:52:46 PDT Sender: goldman@vaxa.isi.edu A flurry of messages was generated last week (on another mailing list) by a poor common lisp programmer whose program apparently quit working (the way he expected) due to a change in the way the compiler dealt with quoted lists. The user was relying on two properties of the old compiler: i) he relied on a particular result of destructively modifying elements of a quoted list. ii) he relied on the compiler keeping distinct lexical occurrences of quoted conses as distinct (non-EQ) values. The compiler had been modified to collapse certain EQUAL quoted lists so that they became EQ. One could no longer write (let ((unique-value-one '(nil)) (unique-value-two '(nil))) ...) and use EQ to distinguish two values. The responses correctly suggested that programs which relied on the former compiler treatment could not be expected to be portable(across common lisp implementations or across releases). But it should be noted that the reason for this is NOT that the "semantics of Common Lisp " makes that clear, or that the particular vendor's lisp documentation gave any indication that this programming practice was unsafe. CLtL does not make it at all clear what a program is deemed to be saying when it uses DEFCONSTANT or QUOTE. The decisions made by compiler writers seem to be based on years of lore about how these constructs "should" be used, rather than on any specification of what they mean. For example, it is plausible that if I write (let ((c1 '((a b) (c d)))) ) a compiler may "simplify" (CAAR c1) to 'a. (i.e., if the value of a constant is a list, its CARs/CDRs, arbitrarily deep, are not supposed to be altered.) But, as far as anything I can find WRITTEN DOWN goes, it is just as PLAUSIBLE that if I write (let ((c2 'X)) ) I am declaring the PROPERTY-LIST of the symbol X to be unchanging, although I doubt that anyone has yet employed that assumption in a compiler. As correctly pointed out in one of the responses, the question of what comprises the boundary of "constantness" of constants is distinct from the issue of "constant collapsing". The latter is a question of what EQUIVALENCE predicates can be imposed on lexically distinct constants in a program. Common Lisp provides 4 universal equivalence predicates (EQ, EQL, EQUAL, and EQUALP), as well as some type-specific equivalences (=, char=, string=). The only reference to this issue I could find in CLtL is a mention, under DEFCONSTANT, that an implementation may replace lexically distinct references to a constant with EQL copies of its value (an authorization to actually use a WEAKER equivalence than one might expect!) This certainly leaves many other transformations in limbo as to legitimacy. I believe that it is NOT acceptable for these issues of program meaning to be undefined to the extent they currently are. Following is a cut at a proposal for clarifying these issues: I. The meaning of a constant is based solely on the S-expression representation of a program, not on its textual representation. I doubt this controversial, but it does mean one can't rely on intuitions about looking at the "source code" that appears inside a QUOTE. [It does not matter if a constant is introduced by '(a b #,(foo) c) as opposed to '(a b #,(make-myrecord :f1 1 :f2 2) c) or '(a b #s c) ] II. I would define a new equivalence predicate, SAME-BOUNDARY. SAME-BOUNDARY would be specified for each datatype in the language. For some, it could be defined in terms of existing equivalence predicates (e.g., for integers, it would be EQ.) For other datatypes of the language, certain accessors are specified to define the boundary. E.g., CAR/CDR for CONSes, SYMBOL-PNAME and SYMBOL-PACKAGE for SYMBOLs, all fields for untyped defstructs, no accessors for PACKAGEs... SAME-BOUNDARY would then be recursively defined in the "obvious" way. [Perhaps EQUALP could be clarified to be this, or perhaps its use is already too wide spread do do that. There should also be a version of COPY that yields a SAME-BOUNDARY copy.] IT IS AN ERROR for a program to modify any part of a constant to a value that is not in the same SAME-BOUNDARY equivalence class as its original value. An implemenation may replace a constant at any time with a SAME-BOUNDARY copy; programs may thus rely on "pieces" of constants only up to SAME-BOUNDARY equivalence. An implementation may introduce declarations or proclamations that EXTEND the set of accessors defining the boundary of constanthood. III. Lexically distinct references to a "variable" declared by defconstant may be replaced by SAME-BOUNDARY copies. IV. Lexically distinct occurrences of constant expressions -- (QUOTE x), or self-evaluating expressions -- may be replaced by SAME-BOUNDARY copies. V. Lexically distinct occurrences of constant expressions may NOT be collapsed so that an equivalence predicate P holds between them provided P is required by Common Lisp to be STRONGER than SAME-BOUNDARY over the datatype of the expressions. [E.g., an implementation may collapse distinct integer constants to become EQ because i.) SAME-BOUNDARY is defined as EQL over the integers, and ii.) CL does not require EQ to be stronger than EQL over the integers. ]  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 28 May 88 23:44:42 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 28 May 88 20:31:15 PDT Received: by labrea.stanford.edu; Sat, 28 May 88 20:31:34 PDT Received: from bhopal.lucid.com by edsel id AA29640g; Sat, 28 May 88 20:22:09 PDT Received: by bhopal id AA12846g; Sat, 28 May 88 20:26:21 PDT Date: Sat, 28 May 88 20:26:21 PDT From: Jon L White Message-Id: <8805290326.AA12846@bhopal.lucid.com> To: Moon@stony-brook.scrc.symbolics.com Cc: common-lisp@sail.stanford.edu In-Reply-To: David A. Moon's message of Tue, 24 May 88 17:08 EDT Subject: SIDE-EFFECT-FREE/STATELESS Functions re: As I said in my earlier message, the Symbolics declarations do not attempt to keep track of aliasing. Thus there is no distinction between side-effects that are known to be connected with a particular object, and side-effects in general. Aliasing can be fairly difficult to track in Lisp, and even more so in a language extended with locatives (which allow non-type-specific operations to access aliases). The issue of whether or not "CAR is sensitive to side-effects" doesn't involve aliasing, or keeping track of particular objects. It is related to the issue of knowing whether or not a function's arguments fall into the class of non- modifiable objects. Numeric functions are in that class; and CAR, CDR, & etc. aren't. The relevant part of the message that you quoted in part from is: Date: Mon, 16 May 88 17:55:30 PDT From: Jon L White To: ELIOT@cs.umass.edu Cc: Common-Lisp@sail.stanford.edu Subject: SIDE-EFFECT-FREE/STATELESS Functions . . . By contrast, the arguments to + cannot be modified by any CLtL function, and this is presumably what LT:SIMPLE adds to LT:REDUCIBLE for Symbolics. [Remember my previous note about SETN in Interlisp?]. Unfortunately, there aren't many read-only datatypes in Common Lisp. CAR itself has no internal state, such as for example GET-UNIVERSAL-TIME has; thus no outside events can affect the value of CAR when it is given a known datum. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 24 May 88 21:41:48 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 24 May 88 18:31:06 PDT Received: by labrea.stanford.edu; Tue, 24 May 88 18:31:29 PDT Received: from bhopal.lucid.com by edsel id AA08273g; Tue, 24 May 88 18:17:50 PDT Received: by bhopal id AA07622g; Tue, 24 May 88 18:21:46 PDT Date: Tue, 24 May 88 18:21:46 PDT From: Jim McDonald Message-Id: <8805250121.AA07622@bhopal.lucid.com> To: Moon@stony-brook.scrc.symbolics.com Cc: common-lisp@sail.stanford.edu Subject: replies to hash table comments Date: Tue, 24 May 88 17:31 EDT From: David A. Moon Here's my problem: This is a slippery slope: today it's hash tables, tomorrow it will be random-states, next week it will be CLOS objects, where will it end? Also bear in mind that I hate the #A and #S syntaxes and disable them for output whenever I can. I just don't like seeing huge amounts of output shoved in my face. That leaves me predisposed to oppose proposals like this one. I think one of the major underrated features of lisp is that in general you need not spend any of your programming/debugging efforts writing code to format the objects you're manipulating. When I had to write in Fortan or Pascal, usually the first or second task was to identify the data structures I was going to use, and following that to write formatting code to be used for debugging. Then as the structures changed I would (with growing annoyance) rewrite the formatters. I remember those days with nausea. I also dislike huge amounts of output, but the proper mechanism is, as you suggested, to elide the output on first showing and possibly make it accessible in more detail later. (Otherwise, why not argue against the default format for lists, since some are very long.) More parameters to control the default elision would be a welcome addition to the language/environment. I'd really like to be able to set some global that would, for example, make any call to print and friends immediately terminate after 100 characters or two newlines were produced. Or terminate when column 78 was reached. Or put all the characters in a hidden buffer but only display the first 40 unless that buffer is explicitly visited. Etc. I also would like to be able to tell defstruct in some simple manner that a particular slot is always huge and uninteresting, so print it as #. Ideally, I should be able to toggle this suppression from, say, the inspector without having said anything about it in the defstruct definition. It just doesn't seem that hard to come up with simple solutions for the major offenders that spew unwelcome characters. BTW, until your message it never occurred to me there might not be a simple way to make CLOS objects display their contents by default. I'd call it a misfeature if you can't. jlm  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 24 May 88 18:35:34 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 24 May 88 15:24:01 PDT Received: by labrea.stanford.edu; Tue, 24 May 88 15:24:11 PDT Received: from blacksox.lucid.com by edsel id AA07662g; Tue, 24 May 88 15:14:21 PDT Received: by blacksox id AA00323g; Tue, 24 May 88 15:18:05 pdt Date: Tue, 24 May 88 15:18:05 pdt From: Eric Benson Message-Id: <8805242218.AA00323@blacksox.lucid.com> To: Moon@stony-brook.scrc.symbolics.com Cc: Dave.Touretzky@c.cs.cmu.edu, common-lisp@sail.stanford.edu In-Reply-To: David A. Moon's message of Tue, 24 May 88 17:31 EDT <19880524213100.0.MOON@EUPHRATES.SCRC.Symbolics.COM> Subject: replies to hash table comments Date: Tue, 24 May 88 17:31 EDT From: David A. Moon Here's my problem: This is a slippery slope: today it's hash tables, tomorrow it will be random-states, next week it will be CLOS objects, where will it end? Also bear in mind that I hate the #A and #S syntaxes and disable them for output whenever I can. I just don't like seeing huge amounts of output shoved in my face. That leaves me predisposed to oppose proposals like this one. Random-states have always been required to have a readable printed representation. We're already most of the way down the slope.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 24 May 88 17:45:03 EDT Received: from JASPER.SCRC.Symbolics.COM ([128.81.41.58]) by SAIL.Stanford.EDU with TCP; 24 May 88 14:31:07 PDT Received: from EUPHRATES.SCRC.Symbolics.COM by JASPER.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 191930; Tue 24-May-88 17:30:53 EDT Date: Tue, 24 May 88 17:31 EDT From: David A. Moon Subject: replies to hash table comments To: Dave.Touretzky@C.CS.CMU.EDU cc: common-lisp@SAIL.STANFORD.EDU In-Reply-To: <12398139318.17.TOURETZKY@C.CS.CMU.EDU> Message-ID: <19880524213100.0.MOON@EUPHRATES.SCRC.Symbolics.COM> Date: Fri 13 May 88 23:33:21-EDT From: Dave.Touretzky@C.CS.CMU.EDU To Moon: there are three reasons why DESCRIBE doesn't solve the problems that arise in teaching beginners about hash tables: 1. In some implementations, DESCRIBE does not show the contents of a hash table. CMU Common Lisp currently displays this regrettable (but legal) behavior. I think it would be better to fix the regrettable implementations than to assume that they will always stay that way and therefore we have to change the language to work around their flaws. If we're going to change the language, I think it would be better to change the language to be more specific about what DESCRIBE is for than to introduce new substitutes for DESCRIBE on the assumption that we can never change DESCRIBE. 2. It is a hassle for a beginner to have to type (describe my-table) every time he wants to see what's inside his hash table. Then he should get a better programming environment that allows this command to be executed with less hand motion. Several exist. And if he's passing the hash table as an argument to a function, it would be nice if its contents could be displayed automatically by TRACE or by the debugger simply by setting *PRINT-HASH* to T. Now this is an argument that I find more convincing. On the other hand, I hate environments where TRACE dumps out such large arguments that I can't see what's going on. I suspect your proposal can only fly if there is a length limit and a level limit on printing of hash table contents. Of course what's really needed is a better TRACE that shows only one line worth of information to start, but saves the data and provides a convenient interface for getting more detailed information when it is wanted. Hasn't it been more than ten years since the first time I read a paper describing something like that? It's been so long, I forget. Most Lisp implementors, Symbolics' included, don't seem to have much imagination. This kind of behavior would make hash tables a first class "visible" data structure, as easy to understand as lists and vectors. Surely not, since hash tables have inherently more complicated structure. 3. The proposed #H notation would make it possible to read and write hash tables from files, and to create them interactively with a single expression rather than doing a MAKE-HASH-TABLE and a bunch of SETF's. I don't find this convincing. #H wouldn't change what is possible in either the file case or the interactive case, it would just make it syntactically simpler. Here's my problem: This is a slippery slope: today it's hash tables, tomorrow it will be random-states, next week it will be CLOS objects, where will it end? Also bear in mind that I hate the #A and #S syntaxes and disable them for output whenever I can. I just don't like seeing huge amounts of output shoved in my face. That leaves me predisposed to oppose proposals like this one.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 24 May 88 17:22:54 EDT Received: from JASPER.SCRC.Symbolics.COM ([128.81.41.58]) by SAIL.Stanford.EDU with TCP; 24 May 88 14:08:15 PDT Received: from EUPHRATES.SCRC.Symbolics.COM by JASPER.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 191923; Tue 24-May-88 17:08:02 EDT Date: Tue, 24 May 88 17:08 EDT From: David A. Moon Subject: SIDE-EFFECT-FREE/STATELESS Functions To: Common-Lisp@SAIL.STANFORD.EDU In-Reply-To: <8805170055.AA02396@bhopal.lucid.com> Message-ID: <19880524210810.9.MOON@EUPHRATES.SCRC.Symbolics.COM> Date: Mon, 16 May 88 17:55:30 PDT From: Jon L White .... One more interesting question related to what is STATELESS arises out of noting the distinction drawn between Symbolic's declarations (LT:SIDE-EFFECTS LT:REDUCIBLE) and (LT:SIDE-EFFECTS LT:SIMPLE REDUCIBLE). Is CAR STATELESS? I say yes, even though the Symbolics terminology seems to imply that it is sensitive to side-effects. CAR is certainly sensitive to side-effects, in the sense that a side-effect on its argument can change its result. It's true that CAR doesn't reference any (obvious) free variables. So, I would prefer to say that the argument to CAR can be modified by side-effecting functions; hence a compiler must keep track not only of the properties of the function it is compiling a call to, but also of the potential alterations to the arguments to that function. The same analysis applies to arrays, hash-tables, defstructs and so on, as well as to cons cells. As I said in my earlier message, the Symbolics declarations do not attempt to keep track of aliasing. Thus there is no distinction between side-effects that are known to be connected with a particular object, and side-effects in general. Aliasing can be fairly difficult to track in Lisp, and even more so in a language extended with locatives (which allow non-type-specific operations to access aliases).  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 21 May 88 01:59:24 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 20 May 88 22:40:34 PDT Received: from relay2.cs.net by RELAY.CS.NET id aq05019; 21 May 88 1:11 EDT Received: from cs.umass.edu by RELAY.CS.NET id bg04248; 21 May 88 1:05 EDT Date: Fri, 20 May 88 13:13 EDT From: ELIOT@cs.umass.edu Subject: STATELESS/SIDE-EFFECT-FREE Functions To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.EDU" From: Jon L White re: . . . Should "ERROR" and ... re: . . . if a compiler can check these properties it could also compute them. But currently it would not be allowed to use those computed properties. I agree with you that a compiler (and maybe even interpreter?) should do as much consistency checking as possible. As moon implied in previous mail, an SSC(*) should be able to determine "simpleness" mechanically. But the danger of using that information is that it may not have been the user's _intent_ that this function be marked as "simple" (e.g., he may want to alter it incompatibly at a later time). An explicit proclamation (or whatever) is the right vehicle for conveying that intent. The previous paragraph describes the situation accurately. There seems to be general agreement that an SSC(*) could mechanically determine a number of properties of functions that would help a compiler optimize code. MOON lists a veritable conspiracy of such properties that are used by the Symbolics compiler. Most people agree that by default a compiler should not use these properties without some explicit proclamation (or whatever) indicating that it is OK. (GZ seems to disagree with this.) There does seem to be a reasonable amount of interest in making these properties known to compilers. Using a set of ad-hoc declarations to specify these properties has several problems. It is inevitable that these declarations will be defined for the purpose of enabling specific optimizations. MOON's description of the Symbolics declarations refered to specific optimization techniques several times. The STATELESS/SIDE-EFFECT-FREE proposal is intended to enable constant folding. More importantly there are subtle semantic difficulties with these declarations. The "curious property" of functions which allocate modifyable structures seems like a dangerous trap to me. I have difficulty understanding the meaning and distinctions of the Symbolics declarations. This means they have to be used slowing and carefully, and therefore infrequently, and therefore they are not very useful. Even worse is the kind of bugs that can be caused. An incorrect STATELESS declaration might be ignored in one programing environment and eventually cause bugs only when the code is ported to another environment, perhaps years and generations of programmers later. I consider language features which can cause hidden bugs of this nature dangerous, and generaly think they should be avoided. This is why (integer 0 100) is a better type specifyer that FIXNUM. The only way to safely use these declarations is with a SSC(*) that checks to verify that the function definition agrees with the declaration. But an SSC can compute any of these properties that it can check, so why make the programmer use the congitive overhead required to figure out where, when and which declarations are needed if the compiler could do it automatically? Simply because the compiler cannot assume that that is the intended definition of the functions involved. From this analysis it seems very desirable to have some way to specify that a compiler should compute and use any implementation dependant optimization properties that it can. All of the declarations listed by MOON are examples of things that a compiler might compute from a function definition and use for later optimizations. Doing so automatically would save programmers from having to learn the meaning of all these declarations, and prevent the possible bugs caused by their incorrect use. So, can anyone suggest a good way to specify that a compiler should commpute and use any implementation dependant optimizations properties that it knows about (such as those properties listed by MOON), preferably a mechanism with sufficient flexibility to offer both corse and fine grained control? One more interesting question related to what is STATELESS arises out of noting the distinction drawn between Symbolic's declarations [Translation: One more obscure fact that makes these declarations harder to use correctly. :-) --CRE] (LT:SIDE-EFFECTS LT:REDUCIBLE) and (LT:SIDE-EFFECTS LT:SIMPLE REDUCIBLE). Is CAR STATELESS? I say yes, even though the Symbolics terminology seems to imply that it is sensitive to side-effects. In the example: (*) SSC -- acronym for "Sufficiently Smart Compiler"  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 19 May 88 23:41:09 EDT Received: from AI.AI.MIT.EDU by SAIL.Stanford.EDU with TCP; 19 May 88 18:28:52 PDT Date: Thu, 19 May 88 21:33:03 EDT From: "Robert W. Kerns" Subject: [portable pathname formats] visible hash tables To: edsel!jonl@LABREA.STANFORD.EDU cc: common-lisp@SAIL.STANFORD.EDU, Skef.Wholey@SPICE.CS.CMU.EDU In-reply-to: Msg of Tue 17 May 88 16:22:13 PDT from Jon L White Message-ID: <381420.880519.RWK@AI.AI.MIT.EDU> Date: Tue, 17 May 88 16:22:13 PDT From: Jon L White To: Skef.Wholey at SPICE.CS.CMU.EDU cc: common-lisp at sail.stanford.edu Re: [portable pathname formats] visible hash tables re: Well, just today I heard a user ask a CMU-CL implementor about having Lucid CL on a Sun talk to CMU-CL on an RT. Among other things, these two Lisps share the same network file system, and so passing pathnames back and forth is a sensible thing...) Symbolics has something like"logical pathnames"; I'm not familiar enough with it to comment on whether or not that approach is satisfactory. Are you? I am. Logical pathnames solve a different problem: taking a program which contains pathnames and porting it to a different site with different machines and directory layouts. The problem here is rather different; a problem of naming. What is needed is a syntax that includes an (optional) host name, and a PATHNAME-HOST slot in pathnames. As Symbolics does, and as DEC does with their pathnames with DECNET. (TI and LMI, too). (I don't know what DEC's CL does with this). The syntax of the rest of the pathname is determined by the foreign host. In Symbolics' case, since it needs to understand the syntax (in order to do things like cross-host defaulting, etc.), it knows how to parse each hosts' syntax locally. In DEC's case, they leave the parsing to the remote system and pass it through uninterpreted. (Symbolics does the same when the foreign host is of some type it never heard of, which is pretty rare since it's heard of most things you or I would use, and is not too hard to extend). Logical pathnames are more useful in a networked environment, of course. Symbolics' logical pathnames even allow you to split one logical host over several physical hosts of various types.  Received: from REAGAN.AI.MIT.EDU (CHAOS 13065) by AI.AI.MIT.EDU 19 May 88 18:41:50 EDT Received: from SAIL.STANFORD.EDU by REAGAN.AI.MIT.EDU via INTERNET with SMTP id 113167; 19 May 88 18:03:49 EDT Received: from ACORN.CS.ROCHESTER.EDU by SAIL.Stanford.EDU with TCP; 19 May 88 12:16:37 PDT Received: from DOUGHNUT.CS.ROCHESTER.EDU by ACORN.CS.ROCHESTER.EDU via CHAOS with CHAOS-MAIL id 40396; Thu 19-May-88 15:10:07 EDT Date: Thu, 19 May 88 15:11 EDT From: Brad Miller Subject: Re: Readable Hash-Tables To: ELIOT@cs.umass.edu cc: common-lisp@SAIL.STANFORD.EDU In-Reply-To: <8805191539.AA07394@cayuga.cs.rochester.edu> Message-ID: <19880519191116.1.MILLER@DOUGHNUT.CS.ROCHESTER.EDU> Sender: miller@CS.ROCHESTER.EDU Reply-To: miller@CS.ROCHESTER.EDU Organization: University of Rochester, Department of Computer Science Postal-address: 610 CS Building, Comp Sci Dept., U. Rochester, Rochester NY 14627 Phone: 716-275-1118 Date: Wed, 18 May 88 12:35 EDT From: ELIOT@cs.umass.edu I was aware of this, and it is the principal reason why DESCRIBE *should* be defined in terms of a portable standard. I think Common Lisp should be commited to providing user-level support for its concepts. I consider this as part of the criteria for being complete. By stipulating that DESCRIBE can be written in portable CL and then extending the language to make this true we will have satisfied one of the requirements for making CL complete. More generally I believe that Common Lisp should be powerful enough to implement a portable programming environment. Chris Eliot I certainly concur with this. Perhaps the mythical portable code walker can be justified as part of the standard this way too... BTW: is it still mythical, or has anyone actually *got* one? I'd use it... ---- Brad Miller U. Rochester Comp Sci Dept. miller@cs.rochester.edu {...allegra!rochester!miller}  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 19 May 88 11:28:48 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 19 May 88 08:12:51 PDT Received: from relay2.cs.net by RELAY.CS.NET id bv08365; 19 May 88 8:24 EDT Received: from cs.umass.edu by RELAY.CS.NET id bq18331; 19 May 88 3:53 EDT Date: Wed, 18 May 88 12:35 EDT From: ELIOT@cs.umass.edu Subject: Readable Hash-Tables To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.EDU" From: Barry Margolin Better still for DESCRIBE, at least, would be a portable public domain implementation. Until we define CL functions for examining defstruct structures (e.g. a function that takes a structure name and returns a list of slot accessor functions) it will not be possible to write a portable DESCRIBE that can tell you the contents of a structure. Also, there are no accessors at all for some other types, such as RANDOM-STATE and HASH-TABLE (and this is the one that prompted this discussion). One of the reasons that DESCRIBE is part of the standard is because it is impossible to write a useful version of it using the existing accessors. barmar I was aware of this, and it is the principal reason why DESCRIBE *should* be defined in terms of a portable standard. I think Common Lisp should be commited to providing user-level support for its concepts. I consider this as part of the criteria for being complete. By stipulating that DESCRIBE can be written in portable CL and then extending the language to make this true we will have satisfied one of the requirements for making CL complete. More generally I believe that Common Lisp should be powerful enough to implement a portable programming environment. Chris Eliot  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 19 May 88 10:53:29 EDT Received: from DIAMOND.S4CC.Symbolics.COM ([128.81.51.3]) by SAIL.Stanford.EDU with TCP; 19 May 88 07:38:16 PDT Received: from CHURCH.S4CC.Symbolics.COM by DIAMOND.S4CC.Symbolics.COM via CHAOS with CHAOS-MAIL id 190873; Thu 19-May-88 10:33:26 EDT Date: Thu, 19 May 88 10:33 EDT From: Michael Greenwald Subject: Features To: Gumby@MCC.COM, edsel!jonl@labrea.stanford.edu cc: common-lisp@sail.stanford.edu In-Reply-To: <880518205815.3.GUMBY@BRAHMA.ACA.MCC.COM> Message-ID: <19880519143304.7.GREENWALD@CHURCH.S4CC.Symbolics.COM> Date: Wed, 18 May 88 20:58 CDT From: David Vinayak Wallace Date: Tue, 10 May 88 14:02:42 PDT From: Jon L White X3J13 is considering a proposal to require the setting of *package* to be the KEYWORD package during the scope of reading the forms under a #+ or a #-. This will tend to give the appearance of "namestring" comparison rather than EQ only because, for example, #+LUCID will be read in the feature as :LUCID, and the search on *features* will be for that symbol. The X3J13 proposal would permit reading in feature names like #+MACSYMA:HYPERLINEAR, in which case the member test would be with the symbol MACSYMA:HYPERLINEAR. What do you do if you encounter #+nasa:hyperdrive but you don't have the nasa package defined? The Symbolics' reader allows the use of package qualified symbols for features. If no package is present the symbol is assumed to be in the keyword package. If a symbol is in an undefined package then the feature is considered "not present", so #- is true, and #+ is false.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 19 May 88 03:57:53 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 19 May 88 00:42:54 PDT Received: by labrea.stanford.edu; Thu, 19 May 88 00:43:17 PDT Received: from bhopal.lucid.com by edsel id AA09223g; Thu, 19 May 88 00:11:16 PDT Received: by bhopal id AA11771g; Thu, 19 May 88 00:14:48 PDT Date: Thu, 19 May 88 00:14:48 PDT From: Jon L White Message-Id: <8805190714.AA11771@bhopal.lucid.com> To: Gumby@mcc.com Cc: common-lisp@sail.stanford.edu In-Reply-To: David Vinayak Wallace's message of Wed, 18 May 88 20:58 CDT <880518205815.3.GUMBY@BRAHMA.ACA.MCC.COM> Subject: Features re: What do you do if you encounter #+nasa:hyperdrive but you don't have the nasa package defined? If an alleged feature name "doesn't exist", that means that the feature isn't present [and it can fail to "exist" in several different ways]. This is the behaviour Lucid implements, and I'm sure I saw some network mail a long time ago agreeing to this meaning. But I don't see any statement about this case in the X3J13 CLeanup Committee's issue SHARPSIGN-PLUS-MINUS-PACKAGE. Kent? Larry? -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 19 May 88 02:26:04 EDT Received: from C.CS.CMU.EDU by SAIL.Stanford.EDU with TCP; 18 May 88 21:18:38 PDT Received: ID ; Thu 19 May 88 00:18:06-EDT Date: Thu 19 May 88 00:18:05-EDT From: Dave.Touretzky@C.CS.CMU.EDU Subject: Re: visible hash table nit To: Gumby@MCC.COM cc: common-lisp@SAIL.STANFORD.EDU In-Reply-To: <880518205254.1.GUMBY@BRAHMA.ACA.MCC.COM> Message-ID: <12399458184.18.TOURETZKY@C.CS.CMU.EDU> I think we should stick with #H unless the Common Lisp cleanup committee decides to eliminate the word "hash" from the language. Right now, everyone calls them "hash tables", not "tables", and "hash" is built into the language in lots of places, e.g., GETHASH, MAKE-HASH-TABLE, HASH-TABLE (as a type specifier), :REHASH-SIZE, and so on. So #H is mnemonic; #T would not be for most readers. -- Dave -------  Received: from REAGAN.AI.MIT.EDU (CHAOS 13065) by AI.AI.MIT.EDU 19 May 88 00:17:55 EDT Received: from SAIL.STANFORD.EDU by REAGAN.AI.MIT.EDU via INTERNET with SMTP id 112993; 18 May 88 23:57:32 EDT Received: from MCC.COM by SAIL.Stanford.EDU with TCP; 18 May 88 18:58:30 PDT Received: from BRAHMA.ACA.MCC.COM by MCC.COM with TCP/SMTP; Wed 18 May 88 20:58:25-CDT Date: Wed, 18 May 88 20:58 CDT From: David Vinayak Wallace Subject: Features To: Jon L White cc: common-lisp@sail.stanford.edu In-Reply-To: <8805102102.AA16844@bhopal.lucid.com> Message-ID: <880518205815.3.GUMBY@BRAHMA.ACA.MCC.COM> Date: Tue, 10 May 88 14:02:42 PDT From: Jon L White X3J13 is considering a proposal to require the setting of *package* to be the KEYWORD package during the scope of reading the forms under a #+ or a #-. This will tend to give the appearance of "namestring" comparison rather than EQ only because, for example, #+LUCID will be read in the feature as :LUCID, and the search on *features* will be for that symbol. The X3J13 proposal would permit reading in feature names like #+MACSYMA:HYPERLINEAR, in which case the member test would be with the symbol MACSYMA:HYPERLINEAR. What do you do if you encounter #+nasa:hyperdrive but you don't have the nasa package defined?  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 18 May 88 23:22:38 EDT Received: from MCC.COM by SAIL.Stanford.EDU with TCP; 18 May 88 18:53:06 PDT Received: from BRAHMA.ACA.MCC.COM by MCC.COM with TCP/SMTP; Wed 18 May 88 20:52:59-CDT Date: Wed, 18 May 88 20:52 CDT From: David Vinayak Wallace Subject: visible hash table nit To: common-lisp@sail.stanford.edu Message-ID: <880518205254.1.GUMBY@BRAHMA.ACA.MCC.COM> Could you use #T instead of #H? Right now symbolics uses make-hash-table as an interface to a system which uses an "appropriate" representation for the size of the table (alist or hash-table only, I think.) One could imagine an implementation which build a b-tree or whatever of its data (which would still fit the GETHASH model, but wouldn't be a hash table in the strict sense). Touretzky, I don't know about your pedagogical needs (are you teaching hashing functions too, or are they just a "black box" to your students?) but in general it's better to hide the implementation from the user, and a sort of a generic table representation seems "right." Plus, I use #H for hosts. david  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 18 May 88 14:29:54 EDT Received: from XN.LL.MIT.EDU by SAIL.Stanford.EDU with TCP; 18 May 88 11:11:52 PDT Received: by XN.LL.MIT.EDU; Wed, 18 May 88 08:22:14 EDT Date: Wed, 18 May 88 08:22:14 EDT From: walton@XN.LL.MIT.EDU (Robert Walton) Posted-Date: Wed, 18 May 88 08:22:14 EDT Message-Id: <8805181222.AA24880@XN.LL.MIT.EDU> To: common-lisp@sail.stanford.edu Cc: walton@XN.LL.MIT.EDU, glenn@XN.LL.MIT.EDU, cogen@XN.LL.MIT.EDU Subject: request to change my mailing address Would you replace walton@vlsi.ll.mit.edu (or maybe its ll-vlsi.arpa) by commonlisp-mail@xn.ll.mit.edu which will reach me and others. Also, if you could help add commonlisp-objects-mail@xn.ll.mit.edu to the CLOS mailing list I've heard tell of, and add commonlisp-windows-mail@xn.ll.mit.edu to the CL WINDOWS mailing list I think may exist, I'd be much appreciative. Thanks, Bob Walton  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 18 May 88 03:20:29 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 18 May 88 00:00:27 PDT Received: by labrea.stanford.edu; Wed, 18 May 88 00:00:41 PDT Received: from bhopal.lucid.com by edsel id AA03695g; Tue, 17 May 88 23:51:46 PDT Received: by bhopal id AA07983g; Tue, 17 May 88 23:55:13 PDT Date: Tue, 17 May 88 23:55:13 PDT From: Jon L White Message-Id: <8805180655.AA07983@bhopal.lucid.com> To: barmar@think.com Cc: ELIOT@cs.umass.edu, common-lisp@sail.stanford.edu In-Reply-To: Barry Margolin's message of Tue, 17 May 88 18:13 EDT <19880517221347.5.BARMAR@OCCAM.THINK.COM> Subject: Visible Hash-Tables re: . . . Also, there are no accessors at all for some other types, such as RANDOM-STATE and HASH-TABLE (and this is the one that prompted this discussion). Guy Steele's "Clarifications" of December 6, 1985 added the necessary, missing accessors for hash-tables: HASH-TABLE-TEST, HASH-TABLE-SIZE, HASH-TABLE-REHASH-SIZE, and HASH-TABLE-REHASH-THRESHOLD. Lucid's implementation added them almost immediately, although documentation about their existence is somewhat recent. These "Clarifications" were presented at the meeting which founded X3J13 -- for ANSI standardization of Common Lisp -- and represented a consensus amongst the community back then. There was some subsequent discussion of the points on this mailing list shortly after that meeting. One unfortunate lacuna in the x3j13 "cleanup" committee's work is that there is no explicit statement about the validity of Steele's "Clarifications". In fact, most of the individual "Clarifications" haven't been specifically and individually addressed. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 18 May 88 02:29:16 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 17 May 88 23:00:40 PDT Received: by labrea.stanford.edu; Tue, 17 May 88 23:01:05 PDT Received: from bhopal.lucid.com by edsel id AA03524g; Tue, 17 May 88 22:49:40 PDT Received: by bhopal id AA07807g; Tue, 17 May 88 22:53:07 PDT Date: Tue, 17 May 88 22:53:07 PDT From: Jon L White Message-Id: <8805180553.AA07807@bhopal.lucid.com> To: barmar@think.com Cc: MLY@ai.ai.mit.edu, Dave.Touretzky@c.cs.cmu.edu, common-lisp@sail.stanford.edu In-Reply-To: Barry Margolin's message of Tue, 17 May 88 11:58 EDT <19880517155802.0.BARMAR@OCCAM.THINK.COM> Subject: visible hash tables re: That's not an unprecedented flaw. Arrays have a number of properties that are not represented in their printed representations, such as adjustability, fill pointer, and element type. Not all arrays have these properties; contrast that with all hashtables having the rehash-size and rehash-threshold slots. I think my message did address the question about arrays, in the first paragraph, when enumerating the types that don't have adequate print representations and for which MLY's suggestion might be a solution: ". . . and non-simple ARRAY and ARRAY with specialized element-type not among {'bit', 'string-char', 'T'}." -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 17 May 88 21:12:27 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 17 May 88 16:28:05 PDT Received: by labrea.stanford.edu; Tue, 17 May 88 16:28:32 PDT Received: from bhopal.lucid.com by edsel id AA02356g; Tue, 17 May 88 16:18:48 PDT Received: by bhopal id AA06440g; Tue, 17 May 88 16:22:13 PDT Date: Tue, 17 May 88 16:22:13 PDT From: Jon L White Message-Id: <8805172322.AA06440@bhopal.lucid.com> To: Skef.Wholey@SPICE.CS.CMU.EDU In-Reply-To: Skef.Wholey@SPICE.CS.CMU.EDU's message of Tue, 17 May 88 04:02:15 EDT <8805170836.AA29487@edsel.lucid.com> Cc: common-lisp@sail.stanford.edu Subject: [portable pathname formats] visible hash tables re: Well, just today I heard a user ask a CMU-CL implementor about having Lucid CL on a Sun talk to CMU-CL on an RT. Among other things, these two Lisps share the same network file system, and so passing pathnames back and forth is a sensible thing...) Symbolics has something like"logical pathnames"; I'm not familiar enough with it to comment on whether or not that approach is satisfactory. Are you? Although this issue is a bit off the direction of printing random structure like things, it is still a very important one, especially as multi-vendor networks spring up. See Mar 88 issue of CACM with articles on heterogeneous network/operating systems. -- JonL -- P.S. Glad to see someone else hacking at "3:39 AM"!  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 17 May 88 18:53:41 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 17 May 88 15:14:05 PDT Received: from fafnir.think.com by Think.COM; Tue, 17 May 88 18:12:08 EDT Return-Path: Received: from OCCAM.THINK.COM by fafnir.think.com; Tue, 17 May 88 18:12:05 EDT Date: Tue, 17 May 88 18:13 EDT From: Barry Margolin Subject: RE: Visible Hash-Tables To: ELIOT@cs.umass.edu Cc: common-lisp@sail.stanford.edu In-Reply-To: <8805172053.AA11503@Think.COM> Message-Id: <19880517221347.5.BARMAR@OCCAM.THINK.COM> Date: Tue, 17 May 88 10:05 EDT From: ELIOT@cs.umass.edu Both INSPECT and DESCRIBE are "standard" CLtL functions. The results are not READable, but the original question was for a way to allow students to look inside hash-tables. INSPECT may be too complex for students (I don't use INSPECT) but DESCRIBE should not be. However, CLtL does not specify that either of these functions will show you the content of Hash-Tables. Would it be resonable to specify for each data type what is the minimal information that these functions must show? Better still for DESCRIBE, at least, would be a portable public domain implementation. Until we define CL functions for examining defstruct structures (e.g. a function that takes a structure name and returns a list of slot accessor functions) it will not be possible to write a portable DESCRIBE that can tell you the contents of a structure. Also, there are no accessors at all for some other types, such as RANDOM-STATE and HASH-TABLE (and this is the one that prompted this discussion). One of the reasons that DESCRIBE is part of the standard is because it is impossible to write a useful version of it using the existing accessors. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 17 May 88 16:53:33 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 17 May 88 13:36:03 PDT Received: from PEWEE.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 406207; Tue 17-May-88 16:34:11 EDT Date: Tue, 17 May 88 16:34 EDT From: Kent M Pitman Subject: (aside about) visible hash tables To: rose@Think.COM cc: edsel!jonl@labrea.stanford.edu, MLY@ai.ai.mit.edu, Dave.Touretzky@c.cs.cmu.edu, common-lisp@sail.stanford.edu In-Reply-To: <8805171442.AA02649@brigit.think.com> Message-ID: <880517163400.6.KMP@PEWEE.SCRC.Symbolics.COM> Date: Tue, 17 May 88 10:42:01 EDT From: rose@Think.COM Date: Mon, 16 May 88 23:51:57 PDT From: Jon L White I think you've made a useful observation that there a whole slew of potential (or real) data types in CLtL for which there is no commonly accepted print syntax, and for which the #S syntax could be naturally extended to cover. BYTE-SPECIFIER comes to mind, as well as RANDOM-STATE, PATHNAME, HASH-TABLE, PACKAGE, READTABLE, STREAM, (compiled) FUNCTION, and non-simple ARRAY and ARRAY with specialized element-type not among {'bit', 'string-char','T'}. Having a print function presumes having a dynamically distinguishable type. If BYTE-SPECIFIER is implemented as an integer, you might have a read syntax for it, but you couldn't expect it to print that way. ... Well, you couldn't expect it in all possible universes, but you could in some. The following technique works for at least some implementations and is provided only for color in this discussion. The main thrust of your point is, of course, correct. In Maclisp, we had the problem that people wanted a read macro #/A which read in as 65 for use in programs, but the problem is that it didn't pretty print well. Maclisp only `interned' small fixnums, so I once wrote a facility that generated uninterned small fixnums by adding 1 to a large fixnum (to get a fresh FIXNUM cell) and then bashing a small number back into the `cdr' of the fixnum. Then I filled an array of numbers from 0-127 with small fixnums whose values were 0-127, respectively, but which were not EQ to the normal 0-127. I could then do (DEFUN READ-CHAR (STREAM) (ARRAYCALL T THE-CHARS (TYI STREAM))) (DEFUN CHAR= (CHAR1 CHAR2) (= CHAR1 CHAR2)) (DEFUN CHARACTERP (CHAR) (AND (FIXNUMP CHAR) (< -1 CHAR 128) (EQ (ARRAYCALL T THE-CHARS CHAR) CHAR))) ;Use of EQ is critical (DEFUN CHAR-CODE (CHAR) (+ CHAR 0)) (DEFUN CODE-CHAR (CHAR) (ARRAYCALL T THE-CHARS CHAR)) ...etc. In this way, an integer could be used to represent a character but the fact that the data object was a character was still preserved. This allowed me to extend the pretty printer so that #/A would print as #/A and 65 would print as 65 even though (LET ((X1 #/A) (X2 65)) (AND (EQ (TYPEP X1) 'FIXNUM) (EQ (TYPEP X2) 'FIXNUM) (= X1 X2))) was true. You just had to be sure that CHARACTERP tests always preceded number tests and you were all set... Similarly, one could imagine a particular CL implementation which chose to implement byte pointers as fixnums (and which did not represent fixnums immediately) might have done: (DEFMACRO CACHED-BYTE-SIZE (SIZE POSITION) ;there are -definitely- more time-efficient and GC-efficient ways to do ;this but this gets the abstract idea across just fine. `(GETHASH (LIST SIZE POSITION) *THE-BYTE-SIZES*)) (DEFUN BYTE (SIZE POSITION) (OR (CACHED-BYTE SIZE POSITION) (SETF (CACHED-BYTE SIZE POSITION) (MAKE-UNIQUE-FIXNUM (BYTE-INTERNAL SIZE POSITION))))) (DEFUN BYTE-INTERNAL (SIZE POSITION) ...fool around with LOGIOR, ASH, etc...) (DEFUN MAKE-UNIQUE-FIXNUM (VALUE) ...implementation would vary and would only be possible on systems which didn't represent fixnums immediately...)  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 17 May 88 15:57:50 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 17 May 88 08:58:22 PDT Received: from fafnir.think.com by Think.COM; Tue, 17 May 88 11:56:27 EDT Return-Path: Received: from OCCAM.THINK.COM by fafnir.think.com; Tue, 17 May 88 11:56:24 EDT Date: Tue, 17 May 88 11:58 EDT From: Barry Margolin Subject: visible hash tables To: Jon L White Cc: MLY@ai.ai.mit.edu, Dave.Touretzky@c.cs.cmu.edu, common-lisp@sail.stanford.edu In-Reply-To: <8805170651.AA03483@bhopal.lucid.com> Message-Id: <19880517155802.0.BARMAR@OCCAM.THINK.COM> Date: Mon, 16 May 88 23:51:57 PDT From: Jon L White Incidentally, both you and Touretzky forgot that hash-tables have two additional interesting properties beyond the :type and :size -- the :rehash-size and :rehash-threshold. Hash-tables wouldn't be fully reconstructable from the printed format unless this information were also included. That's not an unprecedented flaw. Arrays have a number of properties that are not represented in their printed representations, such as adjustability, fill pointer, and element type. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 17 May 88 15:29:32 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 17 May 88 12:16:59 PDT Received: from relay2.cs.net by RELAY.CS.NET id ah04568; 17 May 88 13:38 EDT Received: from cs.umass.edu by RELAY.CS.NET id ad05674; 17 May 88 13:24 EDT Date: Tue, 17 May 88 10:05 EDT From: ELIOT@cs.umass.edu Subject: RE: Visible Hash-Tables To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.EDU" Both INSPECT and DESCRIBE are "standard" CLtL functions. The results are not READable, but the original question was for a way to allow students to look inside hash-tables. INSPECT may be too complex for students (I don't use INSPECT) but DESCRIBE should not be. However, CLtL does not specify that either of these functions will show you the content of Hash-Tables. Would it be resonable to specify for each data type what is the minimal information that these functions must show? Better still for DESCRIBE, at least, would be a portable public domain implementation. I think a more detailed specification of DESCRIBE and INSPECT would be useful. I have been disapointed because information was not printed that *obviously* (to me) should have been. A standard could list the components of compound objects that must be printed, without trying to specify the format.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 17 May 88 15:28:11 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 17 May 88 07:45:33 PDT Return-Path: Received: from brigit.think.com by Think.COM; Tue, 17 May 88 10:42:04 EDT Received: by brigit.think.com; Tue, 17 May 88 10:42:01 EDT Date: Tue, 17 May 88 10:42:01 EDT From: rose@Think.COM Message-Id: <8805171442.AA02649@brigit.think.com> To: edsel!jonl@labrea.stanford.edu Cc: MLY@ai.ai.mit.edu, Dave.Touretzky@c.cs.cmu.edu, common-lisp@sail.stanford.edu In-Reply-To: Jon L White's message of Mon, 16 May 88 23:51:57 PDT <8805170651.AA03483@bhopal.lucid.com> Subject: visible hash tables Date: Mon, 16 May 88 23:51:57 PDT From: Jon L White I think you've made a useful observation that there a whole slew of potential (or real) data types in CLtL for which there is no commonly accepted print syntax, and for which the #S syntax could be naturally extended to cover. BYTE-SPECIFIER comes to mind, as well as RANDOM-STATE, PATHNAME, HASH-TABLE, PACKAGE, READTABLE, STREAM, (compiled) FUNCTION, and non-simple ARRAY and ARRAY with specialized element-type not among {'bit', 'string-char','T'}. Having a print function presumes having a dynamically distinguishable type. If BYTE-SPECIFIER is implemented as an integer, you might have a read syntax for it, but you couldn't expect it to print that way. (Actually, the Genera 7 PRESENT function allows an optional type argument for just this purpose.) On the other hand, I may have to argue against this unifying approach in at least one or more of the important cases at hand. Lucid, like Symbolics, already uses the #P"..." approach to pathnames, and probably wouldn't like to go to a more space-wasting format. And for "database"-like types such as packages and streams, using something like #S would be a gross over- simplification; recursive descent throught the slots would indubitably have incestuous circularities. Right. You don't want to print an object's implementation. You want to print something which has a fighting chance of being interpreted by any Common Lisp, using only CLtL functions. Incidentally, both you and Touretzky forgot that hash-tables have two additional interesting properties beyond the :type and :size -- the :rehash-size and :rehash-threshold. Hash-tables wouldn't be fully reconstructable from the printed format unless this information were also included. -- JonL -- A well-designed #H syntax would be open-ended enough to include all sorts of info on the hash table. Since a hash table is created by a call to MAKE-HASH-TABLE, followed by any number of calls to (SETF GETHASH), the form following the #H should be able to contain all the arguments of those calls. The format that appeals to me has one list element per call, each giving the arguments for that call apart from the table itself: #H((:test 'eql :size 10) (:blue #(0 0 10)) (:red #(10 0 0))) Perhaps if the first form is an atom X, it should be taken to mean (:test X); this supports an earlier proposal as a special case. Probably if an implementation puts non-standard keywords into the first list, it should also put in :allow-other-keys t. There's an obvious generalization here to other "container types", especially arrays: Their P.R.'s should recapitulate their creation. By "container type" I mean that the meaning of such an object depends only on its connections to a set of pre-existing objects, which were associated with it in the course of its creation. In particular, its meaning must not depend on objects which refer to it; i.e., there must be no visible "back pointers". By "meaning" I mean that which is preserved by the P.R. It's all pretty loose. -- John  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 17 May 88 04:48:00 EDT Received: from SKEF.SLISP.CS.CMU.EDU ([128.2.218.47]) by SAIL.Stanford.EDU with TCP; 17 May 88 01:01:14 PDT Received: from SKEF.SLISP.CS.CMU.EDU by SKEF.SLISP.CS.CMU.EDU; 17 May 88 04:02:25 EDT To: Jon L White cc: MLY@ai.ai.mit.edu, Dave.Touretzky@c.cs.cmu.edu, common-lisp@sail.stanford.edu Subject: Re: visible hash tables In-reply-to: Your message of Mon, 16 May 88 23:51:57 -0700. <8805170651.AA03483@bhopal.lucid.com> Date: Tue, 17 May 88 04:02:15 EDT From: Skef.Wholey@SPICE.CS.CMU.EDU From: Jon L White [...] there a whole slew of potential (or real) data types in CLtL for which there is no commonly accepted print syntax [...] BYTE-SPECIFIER comes to mind, as well as RANDOM-STATE, PATHNAME, [...] and non-simple ARRAY and ARRAY with specialized element-type [...] Lucid, like Symbolics, already uses the #P"..." approach to pathnames [...] [...] hash-tables have two additional interesting properties beyond the :type and :size -- the :rehash-size and :rehash-threshold. Hash-tables wouldn't be fully reconstructable from the printed format unless this information were also included. Ok, Crazy 3:39 AM Idea: CMU-CL prints pathnames out as #.(pathname "/usr/foo/bar"). I think this was done as a quick hack to satisfy the requirement that pathnames print out readably, and that the writer of that code had never seen the #P syntax. BUT: the idea of using #. in printing could be incorporated to preserve such things as array element type in array printing. Then, if things like Make-Hash-Table were to be modified to take :Initial-Elements keyword args, ala Make-Array, the problem of preserving things like Rehash-Size and Rehash-Threshold could be easily solved in a consistent, centralized way, using the user-visible construction functions rather than a bizzare extension to #S, which would have many weird special cases to document and implement. One can (if one tries) envision a super printer switch, *Print-It-Like-It-Is*, which would cause things to print out in an ugly but information-laden way, preserving all the things that (we think) ought to be preserved. Now, it would be especially neato if *Print-It-Like-It-Is* printed things in a \portable/ way, so that a hash table (or pathname!) printed under Lucid CL could be read by any other CL. #P is obviously not portable. (What use would people have in wanting pathnames to be portable? Well, just today I heard a user ask a CMU-CL implementor about having Lucid CL on a Sun talk to CMU-CL on an RT. Among other things, these two Lisps share the same network file system, and so passing pathnames back and forth is a sensible thing...) --Skef  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 17 May 88 04:13:55 EDT Received: from SKEF.SLISP.CS.CMU.EDU ([128.2.218.47]) by SAIL.Stanford.EDU with TCP; 17 May 88 01:01:14 PDT Received: from SKEF.SLISP.CS.CMU.EDU by SKEF.SLISP.CS.CMU.EDU; 17 May 88 04:02:25 EDT To: Jon L White cc: MLY@ai.ai.mit.edu, Dave.Touretzky@c.cs.cmu.edu, common-lisp@sail.stanford.edu Subject: Re: visible hash tables In-reply-to: Your message of Mon, 16 May 88 23:51:57 -0700. <8805170651.AA03483@bhopal.lucid.com> Date: Tue, 17 May 88 04:02:15 EDT From: Skef.Wholey@SPICE.CS.CMU.EDU From: Jon L White [...] there a whole slew of potential (or real) data types in CLtL for which there is no commonly accepted print syntax [...] BYTE-SPECIFIER comes to mind, as well as RANDOM-STATE, PATHNAME, [...] and non-simple ARRAY and ARRAY with specialized element-type [...] Lucid, like Symbolics, already uses the #P"..." approach to pathnames [...] [...] hash-tables have two additional interesting properties beyond the :type and :size -- the :rehash-size and :rehash-threshold. Hash-tables wouldn't be fully reconstructable from the printed format unless this information were also included. Ok, Crazy 3:39 AM Idea: CMU-CL prints pathnames out as #.(pathname "/usr/foo/bar"). I think this was done as a quick hack to satisfy the requirement that pathnames print out readably, and that the writer of that code had never seen the #P syntax. BUT: the idea of using #. in printing could be incorporated to preserve such things as array element type in array printing. Then, if things like Make-Hash-Table were to be modified to take :Initial-Elements keyword args, ala Make-Array, the problem of preserving things like Rehash-Size and Rehash-Threshold could be easily solved in a consistent, centralized way, using the user-visible construction functions rather than a bizzare extension to #S, which would have many weird special cases to document and implement. One can (if one tries) envision a super printer switch, *Print-It-Like-It-Is*, which would cause things to print out in an ugly but information-laden way, preserving all the things that (we think) ought to be preserved. Now, it would be especially neato if *Print-It-Like-It-Is* printed things in a \portable/ way, so that a hash table (or pathname!) printed under Lucid CL could be read by any other CL. #P is obviously not portable. (What use would people have in wanting pathnames to be portable? Well, just today I heard a user ask a CMU-CL implementor about having Lucid CL on a Sun talk to CMU-CL on an RT. Among other things, these two Lisps share the same network file system, and so passing pathnames back and forth is a sensible thing...) --Skef  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 17 May 88 03:20:23 EDT Received: from C.CS.CMU.EDU by SAIL.Stanford.EDU with TCP; 17 May 88 00:07:54 PDT Received: ID ; Tue 17 May 88 03:07:41-EDT Date: Tue 17 May 88 03:07:40-EDT From: Dave.Touretzky@C.CS.CMU.EDU Subject: Re: visible hash tables To: edsel!jonl@LABREA.STANFORD.EDU cc: MLY@AI.AI.MIT.EDU, common-lisp@SAIL.STANFORD.EDU In-Reply-To: <8805170651.AA03483@bhopal.lucid.com> Message-ID: <12398964767.12.TOURETZKY@C.CS.CMU.EDU> I'm didn't forget that hash tables have other parameters besides :type and :size. I just didn't think it appropriate to include them in the #H notation, in part because they're likely to be implementation-dependent. For that matter, you can't fully reconstruct vectors and arrays from the #() and #A notations either, since they omit properties like whether or not the vector has a fill pointer, whether the array is adjustable or not, and whether the array is one of :element-type T or some more restricted type. -- Dave -------  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 17 May 88 03:10:19 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 16 May 88 23:56:53 PDT Received: by labrea.stanford.edu; Mon, 16 May 88 23:57:19 PDT Received: from bhopal.lucid.com by edsel id AA28941g; Mon, 16 May 88 23:48:33 PDT Received: by bhopal id AA03483g; Mon, 16 May 88 23:51:57 PDT Date: Mon, 16 May 88 23:51:57 PDT From: Jon L White Message-Id: <8805170651.AA03483@bhopal.lucid.com> To: MLY@ai.ai.mit.edu Cc: Dave.Touretzky@c.cs.cmu.edu, common-lisp@sail.stanford.edu In-Reply-To: Richard Mlynarik's message of Fri, 13 May 88 09:14 EDT <19880513131438.3.MLY@JACKIE.AI.MIT.EDU> Subject: visible hash tables I think you've made a useful observation that there a whole slew of potential (or real) data types in CLtL for which there is no commonly accepted print syntax, and for which the #S syntax could be naturally extended to cover. BYTE-SPECIFIER comes to mind, as well as RANDOM-STATE, PATHNAME, HASH-TABLE, PACKAGE, READTABLE, STREAM, (compiled) FUNCTION, and non-simple ARRAY and ARRAY with specialized element-type not among {'bit', 'string-char', 'T'}. On the other hand, I may have to argue against this unifying approach in at least one or more of the important cases at hand. Lucid, like Symbolics, already uses the #P"..." approach to pathnames, and probably wouldn't like to go to a more space-wasting format. And for "database"-like types such as packages and streams, using something like #S would be a gross over- simplification; recursive descent throught the slots would indubitably have incestuous circularities. Incidentally, both you and Touretzky forgot that hash-tables have two additional interesting properties beyond the :type and :size -- the :rehash-size and :rehash-threshold. Hash-tables wouldn't be fully reconstructable from the printed format unless this information were also included. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 16 May 88 23:00:27 EDT Received: from C.CS.CMU.EDU by SAIL.Stanford.EDU with TCP; 16 May 88 18:34:16 PDT Received: ID ; Mon 16 May 88 21:34:01-EDT Date: Mon 16 May 88 21:34:00-EDT From: Dave.Touretzky@C.CS.CMU.EDU Subject: #H syntax To: common-lisp@SAIL.STANFORD.EDU cc: pavel.pa@XEROX.COM, Dave.Touretzky@C.CS.CMU.EDU Message-ID: <12398904023.12.TOURETZKY@C.CS.CMU.EDU> > From: Pavel.pa@Xerox.COM > Would the input > #H(EQUAL (FOO 7) (BAR 8)) > be equivalent to the input > #H(EQUAL (FOO . (7)) (BAR . (8))) > or simply illegal? If the former, I'm left a bit queasy, I think, but I'm > not sure why. If the latter, then why use dot notation? I wanted the syntax of hash table elements in #H to mirror the syntax of a-lists, since hash tables and a-lists are semantically similar and provide similar functionality in Common Lisp. So my proposal is for the former alternative, i.e., (FOO 7) would be treated as (FOO . (7)). I understand Pavel's queasiness on this point. For a while I considered using list syntax instead of dotted pair syntax, because the dots look kind of messy and require two extra characters per table entry. I'm happy to leave the exact choice of syntax up to the cleanup committee. If no one else has objections or suggestions, I will submit a proposal to the cleanup committee using the dot notation and mention the list notation version as a possible alternative. -- Dave -------  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 16 May 88 22:49:02 EDT Received: from C.CS.CMU.EDU by SAIL.Stanford.EDU with TCP; 16 May 88 18:34:16 PDT Received: ID ; Mon 16 May 88 21:34:01-EDT Date: Mon 16 May 88 21:34:00-EDT From: Dave.Touretzky@C.CS.CMU.EDU Subject: #H syntax To: common-lisp@SAIL.STANFORD.EDU cc: pavel.pa@XEROX.COM, Dave.Touretzky@C.CS.CMU.EDU Message-ID: <12398904023.12.TOURETZKY@C.CS.CMU.EDU> > From: Pavel.pa@Xerox.COM > Would the input > #H(EQUAL (FOO 7) (BAR 8)) > be equivalent to the input > #H(EQUAL (FOO . (7)) (BAR . (8))) > or simply illegal? If the former, I'm left a bit queasy, I think, but I'm > not sure why. If the latter, then why use dot notation? I wanted the syntax of hash table elements in #H to mirror the syntax of a-lists, since hash tables and a-lists are semantically similar and provide similar functionality in Common Lisp. So my proposal is for the former alternative, i.e., (FOO 7) would be treated as (FOO . (7)). I understand Pavel's queasiness on this point. For a while I considered using list syntax instead of dotted pair syntax, because the dots look kind of messy and require two extra characters per table entry. I'm happy to leave the exact choice of syntax up to the cleanup committee. If no one else has objections or suggestions, I will submit a proposal to the cleanup committee using the dot notation and mention the list notation version as a possible alternative. -- Dave -------  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 16 May 88 22:47:03 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 16 May 88 18:02:12 PDT Received: by labrea.stanford.edu; Mon, 16 May 88 18:02:37 PDT Received: from bhopal.lucid.com by edsel id AA27337g; Mon, 16 May 88 17:52:07 PDT Received: by bhopal id AA02396g; Mon, 16 May 88 17:55:30 PDT Date: Mon, 16 May 88 17:55:30 PDT From: Jon L White Message-Id: <8805170055.AA02396@bhopal.lucid.com> To: ELIOT@cs.umass.edu Cc: Common-Lisp@sail.stanford.edu In-Reply-To: ELIOT@cs.umass.edu's message of Fri, 13 May 88 16:00 EDT <8805140852.AA16784@edsel.lucid.com> Subject: SIDE-EFFECT-FREE/STATELESS Functions re: . . . Should "ERROR" and "CERROR" be considered side effect free for this purpose? If not then functions like division can't be considered side effect free, since division by zero must signal an error. Hmmm, I think you've hit upon a good question. The only way I can around the problem is to define these kinds of properties of a function based on "correct" arguments, and without regard to asynchronous interrupts. After all, in virtually every implementation, you could interrupt almost any old random function, and cause whatever malevolent side-effects you want. Thus division should be considered "simple", even though there is a legal path through it that calls a function with probable side-effects. re: . . . if a compiler can check these properties it could also compute them. But currently it would not be allowed to use those computed properties. I agree with you that a compiler (and maybe even interpreter?) should do as much consistency checking as possible. As moon implied in previous mail, an SSC(*) should be able to determine "simpleness" mechanically. But the danger of using that information is that it may not have been the user's _intent_ that this function be marked as "simple" (e.g., he may want to alter it incompatibly at a later time). An explicit proclamation (or whatever) is the right vehicle for conveying that intent. One more interesting question related to what is STATELESS arises out of noting the distinction drawn between Symbolic's declarations (LT:SIDE-EFFECTS LT:REDUCIBLE) and (LT:SIDE-EFFECTS LT:SIMPLE REDUCIBLE). Is CAR STATELESS? I say yes, even though the Symbolics terminology seems to imply that it is sensitive to side-effects. In the example: (let ((x (list '1 '2))) (print (CAR (cdr x))) [1] (rplaca (cdr x) '3) [2] (print (CAR (cdr x)))) [3] One might be tempted to say that CAR is sensitive to the side-effect on line [2]; but it certainly isn't sensitive to side-effects the way INTERN is sensitive to the setting of *PACKAGE*. That is, no state other than the argument is needed to produce the result. What is going on here is that two _different_ arguments are being given to CAR at two different times (times [1] and [3]); even though they appear to be EQ at the times of call, they are not EQUAL, and that is the equivalence of importance when talking about list accessors. (EQ but not EQUAL -- quite iconoclastic, no?). So, I would prefer to say that the argument to CAR can be modified by side-effecting functions; hence a compiler must keep track not only of the properties of the function it is compiling a call to, but also of the potential alterations to the arguments to that function. The same analysis applies to arrays, hash-tables, defstructs and so on, as well as to cons cells. By contrast, the arguments to + cannot be modified by any CLtL function, and this is presumably what LT:SIMPLE adds to LT:REDUCIBLE for Symbolics. [Remember my previous note about SETN in Interlisp?]. Unfortunately, there aren't many read-only datatypes in Common Lisp. -- JonL -- (*) SSC -- acronym for "Sufficiently Smart Compiler"  Received: from REAGAN.AI.MIT.EDU (CHAOS 13065) by AI.AI.MIT.EDU 16 May 88 22:45:09 EDT Received: from SAIL.STANFORD.EDU by REAGAN.AI.MIT.EDU via INTERNET with SMTP id 112419; 16 May 88 20:41:34 EDT Received: from Xerox.COM by SAIL.Stanford.EDU with TCP; 16 May 88 17:03:34 PDT Received: from Semillon.ms by ArpaGateway.ms ; 16 MAY 88 17:00:26 PDT Date: Mon, 16 May 88 17:00:17 PDT From: Pavel.pa@Xerox.COM Subject: Re: replies to hash table comments In-reply-to: <12398139318.17.TOURETZKY@C.CS.CMU.EDU> To: Dave.Touretzky@C.CS.CMU.EDU Cc: common-lisp@SAIL.STANFORD.EDU Message-ID: <880516-170026-1599@Xerox> Would the input #H(EQUAL (FOO 7) (BAR 8)) be equivalent to the input #H(EQUAL (FOO . (7)) (BAR . (8))) or simply illegal? If the former, I'm left a bit queasy, I think, but I'm not sure why. If the latter, then why use dot notation? Pavel  Received: from REAGAN.AI.MIT.EDU (CHAOS 13065) by AI.AI.MIT.EDU 16 May 88 22:44:37 EDT Received: from SAIL.STANFORD.EDU by REAGAN.AI.MIT.EDU via INTERNET with SMTP id 112418; 16 May 88 20:41:16 EDT Received: from PECAN.CS.ROCHESTER.EDU ([192.5.53.206]) by SAIL.Stanford.EDU with TCP; 16 May 88 16:19:14 PDT Received: from DOUGHNUT.CS.ROCHESTER.EDU by PECAN.CS.ROCHESTER.EDU via CHAOS with CHAOS-MAIL id 2738; Mon 16-May-88 19:13:54 EDT Date: Mon, 16 May 88 19:13 EDT From: Brad Miller Subject: Re: Constant-Function, and integration-level To: Gail Zacharias cc: common-lisp@SAIL.STANFORD.EDU In-Reply-To: <8805131805.AA17354@spt.entity.com> Message-ID: <19880516231342.7.MILLER@DOUGHNUT.CS.ROCHESTER.EDU> Sender: miller@cs.rochester.edu Reply-To: miller@cs.rochester.edu Organization: University of Rochester, Department of Computer Science Postal-address: 610 CS Building, Comp Sci Dept., U. Rochester, Rochester NY 14627 Phone: 716-275-1118 Date: 13 May 88 18:05:52 EDT (Fri) From: gz@spt.entity.com (Gail Zacharias) Clearly any decent development environment should not 'lock in' functions during development. But that's not a question that a language standard need address, it's something between you and your Lisp vendor... Here we disagree. If any progress has been made in software engineering in the past decade, it is probably to approach agreement that software reuse is very important. When vendor delivers me software, I should be able to simply and easily modify said work to my needs. I'm not going to be able to do that if the implementation of the language defines the loaded code to be static. Of course, by this standard, delivery of binary-only systems is useless. A position I'm prepared to defend. ---- Brad Miller U. Rochester Comp Sci Dept. miller@cs.rochester.edu {...allegra!rochester!miller}  Received: from REAGAN.AI.MIT.EDU (CHAOS 13065) by AI.AI.MIT.EDU 16 May 88 21:13:39 EDT Received: from SAIL.STANFORD.EDU by REAGAN.AI.MIT.EDU via INTERNET with SMTP id 112416; 16 May 88 20:40:52 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 16 May 88 16:02:52 PDT Received: by labrea.stanford.edu; Mon, 16 May 88 16:03:12 PDT Received: from bhopal.lucid.com by edsel id AA26918g; Mon, 16 May 88 15:52:20 PDT Received: by bhopal id AA02023g; Mon, 16 May 88 15:55:43 PDT Date: Mon, 16 May 88 15:55:43 PDT From: Jon L White Message-Id: <8805162255.AA02023@bhopal.lucid.com> To: Moon@stony-brook.scrc.symbolics.com Cc: common-lisp@sail.stanford.edu In-Reply-To: David A. Moon's message of Fri, 13 May 88 21:00 EDT <19880514010013.2.MOON@EUPHRATES.SCRC.Symbolics.COM> Subject: SIDE-EFFECT-FREE/STATELESS Functions re: . . . When defining a function named bar, one declares properties of that function and all future redefinitions of the function [name] by putting a declare inside the function's definition. When calling a function named bar, the declarations attached to the definition that will be called are used. (I inserted the bracketed "[name]" in your comments quoted above, to be consistent with your emmendations of your previous message.) The issue is that the Symbolics' declaration can't be a proclamation because it doesn't apply specifically to a name for the function. It does seem a bit of a departure from CLtL to acquire global compilation directions out of the current binding of a function name rather than using PROCLAIM. I see a reasonable amount of code that calls SETF on symbol-function; how would the symbolics style declaration handle this? the same as if it had been a DEFUN? Perhaps what is needed is something beyond DEFUN that, like DEFVAR, will do implicit proclaims on the name as well as setting initial values; (SETF SYMBOL-FUNCTION) would remain "primitive", like SETQ. re: I don't think I should admit to knowing what you mean by implementation dependent concepts like "binding" and "cell". . . . The term "binding" to mean an assignment of value to an identifier, whether temporary or permanent, has been around the Lisp world for decades. I don't even think it is Lisp-world specific. Also, cells aren't especially "implementation-dependent concepts" -- see the current discussion on the Scheme mailing list about "CELLS" (especially re ML). Even beyond that theoretical scope, there is a common practice in the Lisp comunity to speak of setting a dynamic variable's value as "setting it's value cell"; rarely, if ever, is there any point to making a distinction between the two, regardless of how an implementation handles dynamic variables. One interesting avenue for maintaining consistency between proclamations and "reality" is to signal errors whenever the compiler can determine that a proclamation is being violated. So an attempt to proclaim RANDOM "simple" would generate an error; and a subsequent "non-simple" definition of FOO, where FOO had been proclaimed "simple", should signal an error or warning. Of course, not every compiler and/or interpreter is capable of enough analysis to distinguish "simple" from "non-simple" from "unknown"; this is in the realm of "user-friendly" rather than language semantics. -- JonL --