Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 16 Sep 88 09:07:19 EDT Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 16 Sep 88 05:51:31 PDT Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP id aa04457; 16 Sep 88 13:08 BST Date: Fri, 16 Sep 88 13:41:31 BST Message-Id: <442.8809161241@subnode.aiai.ed.ac.uk> From: Jeff Dalton Subject: Re: (eq #'eq #'eq) To: common-lisp@sail.stanford.edu In-Reply-To: System Files's message of 15 Sep 88 0909 PDT > Date: Thu, 15 Sep 88 07:26 EDT > From: "Steve Bacher (Batchman)" > > Thanks, JonL. I was pleased to hear that it is conceivable for a valid CL > implementation not necessarily to return the same object for > (SYMBOL-FUNCTION foo) all the time. This has ramifications for > autoloading schemes: if the function definition for a symbol FOO is > autoloaded, then the initial contents of the "function cell" of FOO would > contain a FOO-autoloader, or perhaps some kind of null value; therefore > just loading up the function cell twice would not result in the same (EQ) > pointer under such circumstances. Such freedom is probably necessary in > order to support function autoloading on (formerly much-maligned until > recent developments in the business world) "stock hardware". Sigh. I don't really want to beat this issue to death, but I don't think autoloading makes that much difference. You allow that the initial contents might be "some kind of null value". That is very like what will happen if the function is initially undefined. (Indeed, some Lisps make autoloading part of the handling for undefined functions.) Autoloading is very like defining or redefining the function. And that is not much different from doing a SETQ. But suppose (SYMBOL-FUNCTION F) does contain an autoloader. Then either SYMBOL-FUNCTION does the autoloading itself (and returns the real function) or else it returns the autoloader function. Presumably it will do the same thing if called again, and so (eq (symbol-function f) (symbol-function f)) will return true. My point is simply this: it would be nice if FUNCTION of a symbol were simply a way to get the value of the symbol in the function namespace Would you say Scheme can't support function autoloading? -- Jeff  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 16 Sep 88 08:28:53 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 16 Sep 88 05:13:41 PDT Received: from relay2.cs.net by RELAY.CS.NET id ab13370; 16 Sep 88 8:00 EDT Received: from draper.com by RELAY.CS.NET id aa16695; 16 Sep 88 7:49 EDT Date: Fri, 16 Sep 88 07:09 EDT From: "Steve Bacher (Batchman)" Subject: EQness of functions To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: COMMON-LISP,SEB1525 The case of (let ((f #'(lambda ...))) (eq f f)) has no bearing on the issue of whether (eq f #'eq) is valid. #'eq means (function eq), which may or may not result in something being done at run time to evaluate it; f is a variable reference whose value has already "been evaluated" at some prior time. (eq f f) ought to always be true, modulo some kinds of number-optimization.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 15 Sep 88 21:42:16 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 15 Sep 88 18:23:44 PDT Received: from relay2.cs.net by RELAY.CS.NET id am01919; 15 Sep 88 18:08 EDT Received: from draper.com by RELAY.CS.NET id aa11476; 15 Sep 88 17:49 EDT Date: Thu, 15 Sep 88 17:12 EDT From: "Steve Bacher (Batchman)" Subject: Testing for #'eqness To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: COMMON-LISP,SEB1525 Moon's suggestions are a real win. It is much better to test a function passed to another function by means of "is-this-named-eq-p" or "is-this-a-valid-hashing-test-function-p" than by trying to compare it to whatever #'eq ends up as being in the tester function's code. There are ways to screw the system, of course, like creating another compiled function called EQ (check the package???), but who cares. Let 'em screw the system if that's what they really want to do. :-)  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 15 Sep 88 15:59:37 EDT Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 15 Sep 88 12:36:48 PDT Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP id aa06246; 15 Sep 88 19:09 BST Date: Thu, 15 Sep 88 19:42:15 BST Message-Id: <11304.8809151842@subnode.aiai.ed.ac.uk> From: Jeff Dalton Subject: Re: Implementing :TEMPORARY hash tables at the Lisp level? To: "David A. Moon" , Jon L White In-Reply-To: David A. Moon's message of Thu, 15 Sep 88 13:36 EDT Cc: barmar@think.com, SEB1525 <@sail.stanford.edu:SEB1525@draper.com>, common-lisp@sail.stanford.edu, jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK > I know of at least one case in Symbolics Common Lisp where (eq #'foo #'foo) > returns false. However, foo was defined with a non-Common-Lisp construct > (defun-in-flavor). It wouldn't surprise me to learn that there are > implementations where the same thing happens when foo was defined with > FLET, in cases where the surrounding lexical environment structure is > sufficiently complex. As you pointed out, the same thing can happen with > functions defined globally, in the implementation technique used in > Interlisp-10. > > One could see how to add hair to a compiler to avoid these situations, but > it may be infeasible in an interpreter. Modulo certain efficiency considerations, as in Interlisp-10, I do not think there is any particular difficulty in having (eq #'f #'f) return true. Presumably, interpreters do not have any trouble with (let ((f #'(lambda ...))) (eq f f)) ==> t Are there optimization considerations, as there are for numbers and EQ, that argue against having EQ be well-defined to the extent of being able to make comparisons such as (eq x #'eq) [which I think is all that's needed for make-hash-table]?  Received: from REAGAN.AI.MIT.EDU (CHAOS 13065) by AI.AI.MIT.EDU 15 Sep 88 15:47:57 EDT Received: from SAIL.STANFORD.EDU by REAGAN.AI.MIT.EDU via INTERNET with SMTP id 135242; 15 Sep 88 15:42:01 EDT Message-ID: <17c83T@SAIL.Stanford.EDU> Date: 15 Sep 88 0909 PDT From: System Files Subject: (eq #'eq #'eq) Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 15 Sep 88 09:09:45 PDT Received: from relay2.cs.net by RELAY.CS.NET id aa24766; 15 Sep 88 10:45 EDT Received: from draper.com by RELAY.CS.NET id aa09139; 15 Sep 88 10:34 EDT Date: Thu, 15 Sep 88 07:26 EDT From: "Steve Bacher (Batchman)" Subject: (eq #'eq #'eq) To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: COMMON-LISP,SEB1525 Thanks, JonL. I was pleased to hear that it is conceivable for a valid CL implementation not necessarily to return the same object for (SYMBOL-FUNCTION foo) all the time. This has ramifications for autoloading schemes: if the function definition for a symbol FOO is autoloaded, then the initial contents of the "function cell" of FOO would contain a FOO-autoloader, or perhaps some kind of null value; therefore just loading up the function cell twice would not result in the same (EQ) pointer under such circumstances. Such freedom is probably necessary in order to support function autoloading on (formerly much-maligned until recent developments in the business world) "stock hardware".  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 15 Sep 88 14:29:53 EDT Received: from MCC.COM by SAIL.Stanford.EDU with TCP; 15 Sep 88 11:12:29 PDT Received: from CHOMOLUNGMA.ACA.MCC.COM (CHOMOLUNGMA.ACA.MCC.COM.#Chaos) by MCC.#Chaos with Chaos/SMTP; Thu 15 Sep 88 08:25:10-CDT Date: Thu, 15 Sep 88 08:24 CDT From: William D. Gooch Subject: Profiling lisp To: Conal.Elliott%PROOF.ERGO.CS.CMU.EDU@MCC.COM cc: common-lisp%sail.stanford.edu@MCC.COM, Kenneth.Cline%PROOF.ERGO.CS.CMU.EDU@MCC.COM In-Reply-To: <26018.590274139@PROOF.ERGO.CS.CMU.EDU> Message-ID: <19880915132456.7.GOOCH@CHOMOLUNGMA.ACA.MCC.COM> Date: Wed, 14 Sep 88 17:02:19 EDT From: Conal.Elliott@PROOF.ERGO.CS.CMU.EDU Does anyone have ideas, or preferably code, to profile Lisp code, i.e., to find out how much time is being spent where? We are using Lucid Common Lisp 2.1.1. I'll post a summary of my results. Thanks! - Conal I don't think this will help you, but: Symbolics has put an excellent set of metering tools in their latest release (Genera 7.2).  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 15 Sep 88 14:01:06 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 15 Sep 88 10:40:44 PDT Received: from EUPHRATES.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 459766; Thu 15-Sep-88 13:37:06 EDT Date: Thu, 15 Sep 88 13:36 EDT From: David A. Moon Subject: Implementing :TEMPORARY hash tables at the Lisp level? To: Jon L White cc: barmar@Think.COM, SEB1525@draper.com, common-lisp@sail.stanford.edu, jeff@aiai.edinburgh.ac.uk In-Reply-To: <8809150049.AA07298@bhopal> Message-ID: <19880915173625.6.MOON@EUPHRATES.SCRC.Symbolics.COM> Date: Wed, 14 Sep 88 17:49:57 PDT From: Jon L White My first thought would be like yours -- that #' in the absence of lexical overrides return a unique pointer for as long as the function remains the same. Still, we would have to hear from the vendors for which this would be an incompatible change. I know of at least one case in Symbolics Common Lisp where (eq #'foo #'foo) returns false. However, foo was defined with a non-Common-Lisp construct (defun-in-flavor). It wouldn't surprise me to learn that there are implementations where the same thing happens when foo was defined with FLET, in cases where the surrounding lexical environment structure is sufficiently complex. As you pointed out, the same thing can happen with functions defined globally, in the implementation technique used in Interlisp-10. One could see how to add hair to a compiler to avoid these situations, but it may be infeasible in an interpreter. I remember a discussion among the Scheme folks on these issues a few years ago, which I think came to the conclusion that EQ cannot be well-defined on closures. Two closures that look different, but can be proved equivalent by an optimizing compiler, might end up EQ, and two closures of the same function in what the user imagines to be the same environment might end up distinct due to an optimizing compiler (stack allocation) or a non-optimizing interpreter or compiler. However, no one said that MAKE-HASH-TABLE's association from the :TEST argument to the type of hashing has to be done with EQ. One approach is to get the function's name and then look up the name in a table. Another is to embed the type of hashing in the test function's definition, using a declaration that causes the compiler to attach data to the compiled code. Both of these rely on the fact that, at least for the builtin hash functions, the type of hashing depends only on the function and not on the environment in which it is enclosed. It wouldn't be outlandish to let this fall into the realm of EQL -- just at Interlisp used EQP -- and extend EQL to cover "function" objects as well as numbers and characters. I would resist this, as our hardware implementation of EQL would not be capable of this extension. Aside from that somewhat parochial viewpoint, if equivalence of closures is something different from EQ, I have trouble figuring out what it would be defined as that would have any meaning that was both portable and effectively computable.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 14 Sep 88 22:11:10 EDT Received: from lucid.com by SAIL.Stanford.EDU with TCP; 14 Sep 88 18:53:37 PDT Received: from bhopal ([192.9.200.13]) by heavens-gate.lucid.com id AA00834g; Wed, 14 Sep 88 17:51:10 PST Received: by bhopal id AA07576g; Wed, 14 Sep 88 18:50:35 PDT Date: Wed, 14 Sep 88 18:50:35 PDT From: Jon L White Message-Id: <8809150150.AA07576@bhopal> To: DDYER@RIVERSIDE.SCRC.Symbolics.COM Cc: Greenwald@STONY-BROOK.SCRC.Symbolics.COM, Gregor.pa@Xerox.COM, goldman@vaxa.isi.edu, COMMON-LISP@sail.stanford.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk In-Reply-To: DDYER@RIVERSIDE.SCRC.Symbolics.COM's message of Wed, 7 Sep 88 11:52 PDT <19880907185230.5.DDYER@PURPLE.SWW.Symbolics.COM> Subject: Hash Tables and GC re: Just to throw a little light into this discussion: On Symbolics systems there is a list of forms to be evaluated before any gc flip (ephemeral or dynamic). It's possible to implement whatever kind of weak pointers strategy you want by explicitly clearing whatever pointers are "weak" before the flip occurs. The list is called SI:GC-EVERY-FLIP-LIST Hmmmmm. As barmar points out, this could't work _in general_ for weak pointers unless you also restore the non-GC'd entries that you deleted. PDP10 MacLisp provided a different variant of this -- the infamous GC hook [sigh, there were so many "hooks" in MacLisp!]. Just _after_ a GC finishs, but before any more consing is done, the user's "hook" function is run. At this unique interval in time, it is possible to ask of a random address/pointer "Were you just GC'd"; [in fact, this capability is independent of whether it is a copying, or collecting or refcnt'ing GC]. Then using NIL type arrays, pointers could be kept around for inspection after the GC; the "NIL type" array simply means that the GC doesn't mark or descend the entries (just like XPOINTER type arrays in Interlisp-D]. GJS used this hook to good advantage in MicroPlanner and early Scheme implementations. In effect, I think he implemnted :temporary type hash tables. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 14 Sep 88 21:13:36 EDT Received: from lucid.com by SAIL.Stanford.EDU with TCP; 14 Sep 88 17:53:25 PDT Received: from bhopal ([192.9.200.13]) by heavens-gate.lucid.com id AA00781g; Wed, 14 Sep 88 16:50:32 PST Received: by bhopal id AA07298g; Wed, 14 Sep 88 17:49:57 PDT Date: Wed, 14 Sep 88 17:49:57 PDT From: Jon L White Message-Id: <8809150049.AA07298@bhopal> To: barmar@Think.COM Cc: SEB1525@draper.com, common-lisp@sail.stanford.edu, jeff@aiai.edinburgh.ac.uk In-Reply-To: Barry Margolin's message of Wed, 7 Sep 88 12:07 EDT <19880907160730.3.BARMAR@OCCAM.THINK.COM> Subject: Implementing :TEMPORARY hash tables at the Lisp level? [I've read ahead to look at other comments on this issue, and will try to coordinate my comments on several such messages.] First, I think someone already pointed out that CASE is not the proper common lisp construct to use since: (case x ((#'eq #'equal) ...)) is simply equivalent to: (case x (((function eq) (function equal)) ...)) and one definitely doesn't intend to compare the value of x with some "internal" list (function eq)! [Query: should an implementation give you a warning msg when finding such a situation in CASE?] re: The internal implementation of a Common Lisp need not be written using portable constructs. Right. In fact, Interlisp did "cons" up a new value each time you called the equivalent of SYMBOL-FUNCTION, because the function cell did _not_ contain a Lisp object, but something more hardware and/or firmware specific. Of course, access and update of that cell is via a functional interface, which "mediates" between the expected type of value and that actually stored in memory. Thus in that implmentation: (eq #'eq #'eq) would be guaranteed not to work the way this discussion has been assuming it to work. Consequently, Interlisp had the function EQP -- somewhat a forerunner of the Common Lisp EQL -- which would tell you when two different "compiled code pointers" were in fact pointing to the same piece of compiled code, but would simply be EQ on most other cases. [I don't know how XAIS/ENVOS's Common Lisp product handles this matter; probably something less tied to the tricks "firmware".] re: I suspect that in most CL implementations, #' always returns the same thing for symbols that do not have a lexical function binding, so the above code would work. Sigh, I wish you were right. I know of at least one implmenetation where (function ) simply acts like (quote ); although this "always returns the same thing", it definitely isn't what you expect [i.e., it would not be FUNCTIONP under the revised x3j13 sense.] I think it would be a good idea for an X3J13 "Cleanup" to address this. My first thought would be like yours -- that #' in the absence of lexical overrides return a unique pointer for as long as the function remains the same. Still, we would have to hear from the vendors for which this would be an incompatible change. It wouldn't be outlandish to let this fall into the realm of EQL -- just at Interlisp used EQP -- and extend EQL to cover "function" objects as well as numbers and characters. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 14 Sep 88 17:27:32 EDT Received: from PROOF.ERGO.CS.CMU.EDU by SAIL.Stanford.EDU with TCP; 14 Sep 88 14:04:31 PDT Received: from PROOF.ERGO.CS.CMU.EDU by PROOF.ERGO.CS.CMU.EDU; 14 Sep 88 17:02:25 EDT To: common-lisp@sail.stanford.edu cc: Kenneth.Cline@PROOF.ERGO.CS.CMU.EDU Subject: Profiling lisp Date: Wed, 14 Sep 88 17:02:19 EDT Message-ID: <26018.590274139@PROOF.ERGO.CS.CMU.EDU> From: Conal.Elliott@PROOF.ERGO.CS.CMU.EDU Does anyone have ideas, or preferably code, to profile Lisp code, i.e., to find out how much time is being spent where? We are using Lucid Common Lisp 2.1.1. I'll post a summary of my results. Thanks! - Conal  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 Sep 88 09:39:49 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 13 Sep 88 06:23:28 PDT Received: from relay2.cs.net by RELAY.CS.NET id af06011; 13 Sep 88 8:20 EDT Received: from draper.com by RELAY.CS.NET id aa23004; 13 Sep 88 8:13 EDT Date: Tue, 13 Sep 88 07:40 EDT From: "Steve Bacher (Batchman)" Subject: MAKE-HASH-TABLE :TEST arg To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: COMMON-LISP,SEB1525 Please don't CC to me. I am getting 2 copies of all your flames due to being on common-lisp. Thanks. - "Steve Bacher"  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 12 Sep 88 19:10:01 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 12 Sep 88 15:56:00 PDT Return-Path: Received: from sauron.think.com by Think.COM; Mon, 12 Sep 88 18:53:14 EDT Received: from OCCAM.THINK.COM by sauron.think.com; Mon, 12 Sep 88 18:53:54 EDT Date: Mon, 12 Sep 88 18:54 EDT From: Barry Margolin Subject: MAKE-HASH-TABLE :TEST arg To: David A. Moon Cc: "Steve Bacher (Batchman)" , common-lisp@sail.stanford.edu In-Reply-To: <19880912194542.1.MOON@EUPHRATES.SCRC.Symbolics.COM> Message-Id: <19880912225417.5.BARMAR@OCCAM.THINK.COM> Date: Mon, 12 Sep 88 15:45 EDT From: David A. Moon Date: Mon, 12 Sep 88 11:05 EDT From: Barry Margolin I suppose you COULD use SXHASH for all hash tables, since EQ objects are necessarily EQUAL Not if the following program is valid Common Lisp. I couldn't find anything in CLtL that speaks to this. Should this be run through the cleanup committee? (setq ht (make-hash-table :test #'eq)) (setq a (cons 1 2)) (setf (gethash a ht) 'win) (setf (cdr a) 3) (gethash a ht 'lose) => win t If SXHASH was used, the last form would evaluate to lose nil unless by chance (= (sxhash '(1 . 2)) (sxhash '(1 . 3))) was true or by chance the structure of the hash table was such that the difference between the two sxhash values did not matter. Similar examples can be constructed using strings and bit-vectors in place of conses. I would propose that modifications to components of the key do not affect EQ and EQL hash tables, and thus are allowed, but are not allowed for EQUAL hash tables when the modification is to a component that is examined by the EQUAL function. You're right. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 12 Sep 88 17:05:10 EDT Received: from lucid.com by SAIL.Stanford.EDU with TCP; 12 Sep 88 13:47:23 PDT Received: from edsel ([192.9.200.1]) by heavens-gate.lucid.com id AA00469g; Mon, 12 Sep 88 12:39:26 PST Site: Received: from blacksox.lucid.com by edsel id AA00955g; Mon, 12 Sep 88 13:32:38 PDT Received: by blacksox id AA00162g; Mon, 12 Sep 88 13:35:18 pdt Date: Mon, 12 Sep 88 13:35:18 pdt From: Eric Benson Message-Id: <8809122035.AA00162@blacksox.lucid.com> To: Moon@STONY-BROOK.SCRC.Symbolics.COM Cc: barmar@Think.COM, SEB1525@draper.com, common-lisp@SAIL.STANFORD.EDU In-Reply-To: David A. Moon's message of Mon, 12 Sep 88 15:45 EDT <19880912194542.1.MOON@EUPHRATES.SCRC.Symbolics.COM> Subject: MAKE-HASH-TABLE :TEST arg Date: Mon, 12 Sep 88 15:45 EDT From: David A. Moon I would propose that modifications to components of the key do not affect EQ and EQL hash tables, and thus are allowed, but are not allowed for EQUAL hash tables when the modification is to a component that is examined by the EQUAL function. This makes sense, since EQ and EQL hash tables use the identity of the object as the key, while EQUAL hash tables use the structure of the object as the key. Component modification changes the structure of an object, while the identity of an object cannot be changed in Common Lisp. On p.168 of CLtL the following comment is found under SYMBOL-NAME: "It is an extremely bad idea to modify a string being used as the print name of a symbol. Such a modification may tremendously confuse the function READ and the package system." This should be generalized to apply to any object which is used as a key in an EQUAL hash table.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 12 Sep 88 16:04:19 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 12 Sep 88 12:49:16 PDT Received: from EUPHRATES.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 457773; Mon 12-Sep-88 15:45:03 EDT Date: Mon, 12 Sep 88 15:44 EDT From: David A. Moon Subject: MAKE-HASH-TABLE :TEST arg To: Barry Margolin cc: "Steve Bacher (Batchman)" , common-lisp@SAIL.STANFORD.EDU In-Reply-To: <19880912150515.9.BARMAR@OCCAM.THINK.COM> Message-ID: <19880912194413.0.MOON@EUPHRATES.SCRC.Symbolics.COM> Date: Mon, 12 Sep 88 11:05 EDT From: Barry Margolin I suppose you COULD use SXHASH for all hash tables, since EQ objects are necessarily EQUAL Not if the following program is valid Common Lisp. I couldn't find anything in CLtL that speaks to this. Should this be run through the cleanup committee? (setq ht (make-hash-table :test #'eq)) (setq a (cons 1 2)) (setf (gethash a ht) 'win) (setf (cdr a) 3) (gethash a ht 'lose) => win t If SXHASH was used, the last form would evaluate to lose nil unless by chance (= (sxhash '(1 . 2)) (sxhash '(1 . 3))) was true. Similar examples can be constructed using strings and bit-vectors in place of conses. I would propose that modifications to components of the key do not affect EQ and EQL hash tables, and thus are allowed, but are not allowed for EQUAL hash tables when the modification is to a component that is examined by the EQUAL function.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 12 Sep 88 16:02:28 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 12 Sep 88 12:48:02 PDT Received: from EUPHRATES.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via INTERNET with SMTP id 457774; 12 Sep 88 15:46:35 EDT Date: Mon, 12 Sep 88 15:45 EDT From: David A. Moon Subject: MAKE-HASH-TABLE :TEST arg To: Barry Margolin cc: "Steve Bacher (Batchman)" , common-lisp@SAIL.STANFORD.EDU In-Reply-To: <19880912150515.9.BARMAR@OCCAM.THINK.COM> Supersedes: <19880912194413.0.MOON@EUPHRATES.SCRC.Symbolics.COM> Comments: sent original version with equality where I meant equivalence Message-ID: <19880912194542.1.MOON@EUPHRATES.SCRC.Symbolics.COM> Date: Mon, 12 Sep 88 11:05 EDT From: Barry Margolin I suppose you COULD use SXHASH for all hash tables, since EQ objects are necessarily EQUAL Not if the following program is valid Common Lisp. I couldn't find anything in CLtL that speaks to this. Should this be run through the cleanup committee? (setq ht (make-hash-table :test #'eq)) (setq a (cons 1 2)) (setf (gethash a ht) 'win) (setf (cdr a) 3) (gethash a ht 'lose) => win t If SXHASH was used, the last form would evaluate to lose nil unless by chance (= (sxhash '(1 . 2)) (sxhash '(1 . 3))) was true or by chance the structure of the hash table was such that the difference between the two sxhash values did not matter. Similar examples can be constructed using strings and bit-vectors in place of conses. I would propose that modifications to components of the key do not affect EQ and EQL hash tables, and thus are allowed, but are not allowed for EQUAL hash tables when the modification is to a component that is examined by the EQUAL function.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 12 Sep 88 15:08:54 EDT Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 12 Sep 88 11:46:36 PDT Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0) id AA12250; Mon, 12 Sep 88 11:41:17 PDT Received: from lukasiewicz.sun.com by snail.sun.com (4.0/SMI-4.0) id AA18046; Mon, 12 Sep 88 11:44:09 PDT Received: by lukasiewicz.sun.com (4.0/SMI-4.0) id AA11669; Mon, 12 Sep 88 10:37:32 PDT Date: Mon, 12 Sep 88 10:37:32 PDT From: jrose@Sun.COM (John Rose) Message-Id: <8809121737.AA11669@lukasiewicz.sun.com> To: DLA@JASPER.SCRC.Symbolics.COM Cc: Gregor.pa@Xerox.COM, goldman@vaxa.isi.edu, COMMON-LISP@sail.stanford.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk In-Reply-To: David L. Andre's message of Sun, 11 Sep 88 13:12 EDT <19880911171244.3.DLA@KOYAANISQATSI.SCRC.Symbolics.COM> Subject: Hash Tables and GC Date: Sun, 11 Sep 88 13:12 EDT From: David L. Andre Date: Tue, 6 Sep 88 19:50 PDT From: Gregor.pa@Xerox.COM As I understand it, finalization is a mechanism for recording a function which the garbage collector should call on an object when it is about to be GC'd. I find it surprising that no one has talked about finalization during this discussion. This may not be facility we want to add to Common Lisp, but as near as I can tell, weak pointers and finalization are the primitives you need to build these kind of hash tables. In addition, finalization is a useful mechanism to have direct access to. ... the function has to be called on an object which is in oldspace but it cannot migrate the object to copyspace before examining it. ... I understand how to implement this feature, but I don't see how to do it in an implemention-independent fashion in a copying garbage collector. This is significant since most garbage collectors on the market today are copying garbage collectors. I also don't understand how to make it safe enough to be a language feature. There is a single answer to both those questions: Don't treat the object any differently under after the finalization function has run. This means that unfinalized objects get moved to copyspace, and so take two GC cycles to free. (This is an acceptable cost, to my mind: You just pay double for finalizable memory.) Here's how it would work from the client's point of view: Finalizable objects have a single bit of client-alterable state FINALIZABLE-P. When the GC is about to collect an object with this bit turned on, it instead preserves the object in a central place. After the GC has finished running, all such objects get their FINALIZABLE-P bits turned off, and they are then passed to their various finalization functions. Those functions, in turn are free to manipulate the FINALIZABLE-P bit; if after finalization the bit is turned off, and no references remain, the next GC will treat the object like any other piece of garbage. Note that this model does not refer to exact nature of the underlying GC technology. It simply assumes there is a simple way to implement the FINALIZABLE-P bit. Note that if another GC happens while a finalization function is running, even though the object's FINALIZABLE-P bit is turned off, the object is retained, since it is referenced from the stack. It is not obvious to me when weak pointers to objects undergoing finalization should be cleared. I can think of cases supporting either choice, of clearing the pointers during the first GC, or during the second. I lean towards clearing them during the first GC, when the objects are being placed on the FINALIZATIONS list. Here's how you could implement this in a copying GC: In addition to a FINALIZABLE-P bit, there is in fact a hidden slot called FINALIZEABLE-CHAIN in the layout of finalizable objects. (The bit can maiybe be stored somewhere in the slot, instead of a tag.) This slot forms a linked list FINALIZABLE-LIST of all objects needing finalization. When the client turns the FINALIZABLE-P bit off, the system is free to remove the object from the linked list when convenient. When the client turns the bit on, the system must ensure that they are once again on the list. At GC time, oldspace is scanned as usual, but FINALIZABLE-LIST is not used as a root reference, nor is the FINALIZABLE-CHAIN slot used to propagate referencing. Just before oldspace is flushed, however, FINALIZABLE-LIST is now used as a root reference. Any objects which are moved to copyspace at this time are objects needing finalization. Such objects are unlinked from the FINALIZABLE-LIST (which by now is in newspace) but are placed on another list called FINALIZATIONS. It is this list that is traversed after the GC, to call the finalization functions. Note that these functions are called after the GC has finished reconstructing the heap in copyspace. In fact, there is no need to call them immediately after the GC; the list could be processed at any opportune moment, perhaps in a low-priority background process. Some provision must be made to retain the FINALIZATIONS list across GCs occurring during the actual process of finalization. The simplest thing to do is leave their FINALIZABLE-P bit turned on, so intervening GCs just re-collect the FINALIZATIONS list from scratch. By the way, a clean way to introduce finalization into CLOS would be to have a finalizable superclass, which contained the hidden FINALIZABLE-CHAIN slot, and supported an accessor for the FINALIZABLE-P bit. The generic function FINALIZE would be called to finalize such objects, and subclasses could specialize it. This design implies that some kinds of objects (e.g., cons cells) are not finalizable; that's fine with me. I use finalization, in C++, mainly to deallocate memory when I'm done with it. Lisp takes care of that task, but there are other resources which both C++ and Lisp finalization help manage, notably operating system channels for open streams. (Other examples: Temporary files or disk blocks, and resources in coprocessors or servers.) Therefore, finalization typically applies to an object which serves as a container for the non-Lisp resources, and it doesn't disturb me that such objects are a limited subset of all possible Lisp objects. -- John  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 12 Sep 88 11:21:47 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 12 Sep 88 08:07:08 PDT Return-Path: Received: from sauron.think.com by Think.COM; Mon, 12 Sep 88 11:04:51 EDT Received: from OCCAM.THINK.COM by sauron.think.com; Mon, 12 Sep 88 11:04:54 EDT Date: Mon, 12 Sep 88 11:05 EDT From: Barry Margolin Subject: MAKE-HASH-TABLE :TEST arg To: "Steve Bacher (Batchman)" Cc: common-lisp@sail.stanford.edu In-Reply-To: <8809121223.AA00923@Think.COM> Message-Id: <19880912150515.9.BARMAR@OCCAM.THINK.COM> Date: Mon, 12 Sep 88 07:18 EDT From: "Steve Bacher (Batchman)" From: CCFVX3::SEB1525 "Steve Bacher (Batchman)" 12-SEP-1988 07:15 To: IN%"jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.UK",SEB1525 Subj: RE: Re: Comparing functions Er, my point was that MAKE-HASH-TABLE doesn't absolutely need to do that test. Why can't a valid implementation of MAKE-HASH-TABLE just blindly FUNCALL the TEST argument? If you can explain to me what different frobulations it needs to set up based on the TEST argument, I will be convinced. Otherwise, I remain..... Various aspects of the behavior of a hash table are dependent upon the TEST argument. An EQUAL hash table need not be rehashed after a copying GC. The hash function is generally dependent upon the test function; for an EQUAL hash table it would be SXHASH, while for an EQ hash table it would probably be a simple hash on the address. I suppose you COULD use SXHASH for all hash tables, since EQ objects are necessarily EQUAL, and you COULD rehash ALL hash tables. Or you could implement hash tables without actually hashing (e.g. implement them as alists). But if performance is an issue (which it generally is when you use a hash table), you'll probably want to do things dependent on the test function. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 12 Sep 88 08:39:23 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 12 Sep 88 05:22:18 PDT Received: from relay2.cs.net by RELAY.CS.NET id aa23444; 12 Sep 88 8:11 EDT Received: from draper.com by RELAY.CS.NET id ac14648; 12 Sep 88 8:06 EDT Date: Mon, 12 Sep 88 07:18 EDT From: "Steve Bacher (Batchman)" Subject: MAKE-HASH-TABLE :TEST arg To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: COMMON-LISP From: CCFVX3::SEB1525 "Steve Bacher (Batchman)" 12-SEP-1988 07:15 To: IN%"jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.UK",SEB1525 Subj: RE: Re: Comparing functions Er, my point was that MAKE-HASH-TABLE doesn't absolutely need to do that test. Why can't a valid implementation of MAKE-HASH-TABLE just blindly FUNCALL the TEST argument? If you can explain to me what different frobulations it needs to set up based on the TEST argument, I will be convinced. Otherwise, I remain.....  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 12 Sep 88 08:39:18 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 12 Sep 88 05:22:27 PDT Received: from relay2.cs.net by RELAY.CS.NET id aa23495; 12 Sep 88 8:17 EDT Received: from draper.com by RELAY.CS.NET id ae14648; 12 Sep 88 8:06 EDT Date: Mon, 12 Sep 88 07:21 EDT From: "Steve Bacher (Batchman)" Subject: Comparing functions To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: COMMON-LISP,SEB1525 Yes, I knew the case code wouldn't work as written. It was intended tobe an absurd example, being (in my opinion) impossible to write correctly in CL.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 11 Sep 88 13:28:50 EDT Received: from JASPER.SCRC.Symbolics.COM ([128.81.41.58]) by SAIL.Stanford.EDU with TCP; 11 Sep 88 10:14:53 PDT Received: from KOYAANISQATSI.SCRC.Symbolics.COM by JASPER.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 215657; Sun 11-Sep-88 13:13:55 EDT Date: Sun, 11 Sep 88 13:12 EDT From: David L. Andre Subject: Re: Hash Tables and GC To: Gregor.pa@Xerox.COM cc: goldman@vaxa.isi.edu, COMMON-LISP@sail.stanford.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk In-Reply-To: <19880907025057.5.GREGOR@PORTNOY.parc.xerox.com> Message-ID: <19880911171244.3.DLA@KOYAANISQATSI.SCRC.Symbolics.COM> Date: Tue, 6 Sep 88 19:50 PDT From: Gregor.pa@Xerox.COM As I understand it, finalization is a mechanism for recording a function which the garbage collector should call on an object when it is about to be GC'd. I find it surprising that no one has talked about finalization during this discussion. This may not be facility we want to add to Common Lisp, but as near as I can tell, weak pointers and finalization are the primitives you need to build these kind of hash tables. In addition, finalization is a useful mechanism to have direct access to. Finalization is certainly useful, but I'm not sure how any implementation of a copying GC could implement it. This is because the function has to be called on an object which is in oldspace but it cannot migrate the object to copyspace before examining it. In a GC with hardware assistance, you have to bypass the transport hardware to do this, which means you have to specially write the function using implementation-dependent primitives. (Note that "conventional processors" may use "hardware assistance" such as read and write traps.) In all GCs, you have to ensure that the finalization function does not cause a pointer to oldspace to be stored into anyplace in memory. This itself is a fairly severe restriction; it is certainly not the same as "side-effect-free", but it is close. I understand how to implement this feature, but I don't see how to do it in an implemention-independent fashion in a copying garbage collector. This is significant since most garbage collectors on the market today are copying garbage collectors. I also don't understand how to make it safe enough to be a language feature.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 11 Sep 88 13:24:21 EDT Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 11 Sep 88 10:04:01 PDT Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP id aa02927; 11 Sep 88 17:30 BST Date: Sun, 11 Sep 88 18:01:03 BST Message-Id: <2933.8809111701@subnode.aiai.ed.ac.uk> From: Jeff Dalton Subject: Re: Comparing functions To: "Steve Bacher (Batchman)" , common-lisp@sail.stanford.edu In-Reply-To: Steve Bacher (Batchman)'s message of Fri, 9 Sep 88 17:13 EDT > In looking at the definition for make-hash-table, I contend that a valid > implementation has no need for function-comparing primitives. That is expected since function comparing primitives that determine "do these compute the same function" are impossible. > It does say that the :test argument "must be one of the threee values > #'eq, #'eql, or #'equal, or one of the three symbols eq, eql, or equal". I am assuming you agree that MAKE-HASH-TABLE does need some way to determine whether the :TEST argument is EQ, #'EQ, EQL, #'EQL, EQUAL or #'EQUAL, because it does, of course, need some way to do this. > So if temporary hash tables need to test the :test argument, which they do, > they can't rely on MAKE-HASH-TABLE already having established the need for > the requisite primitive. Yes they can. They do not need any other test than whatever means MAKE-HASH-TABLE uses to determine whether to make an EQ table or an EQL or EQUAL one. -- Jeff  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 10 Sep 88 00:02:58 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 9 Sep 88 20:44:14 PDT Received: from relay2.cs.net by RELAY.CS.NET id aa26552; 9 Sep 88 19:09 EDT Received: from draper.com by RELAY.CS.NET id ab03033; 9 Sep 88 18:53 EDT Date: Fri, 9 Sep 88 17:13 EDT From: "Steve Bacher (Batchman)" Subject: Comparing functions To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: COMMON-LISP,SEB1525 In looking at the definition for make-hash-table, I contend that a valid implementation has no need for function-comparing primitives. It does say that the :test argument "must be one of the threee values #'eq, #'eql, or #'equal, or one of the three symbols eq, eql, or equal". However, as I understand it, "must be" is equivalent to "It is an error if not...", which means that the implementation doesn't have to do anything if the :test argument happens to be something else. Presumably, the compiler can source-level-optimize calls to MAKE-HASH-TABLE (as long as the :test argument is a constant) to enforce this, and in fact can convert such calls to lower-level things (e.g. MAKE-HASH-TABLE-WITH-EQ-TEST and the like, or what have you). So if temporary hash tables need to test the :test argument, which they do, they can't rely on MAKE-HASH-TABLE already having established the need for the requisite primitive.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Sep 88 11:13:45 EDT Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 8 Sep 88 08:00:25 PDT Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP id aa05090; 8 Sep 88 15:19 BST Date: Thu, 8 Sep 88 15:50:07 BST Message-Id: <18347.8809081450@aiai.ed.ac.uk> From: Jeff Dalton Subject: Re: Comparing functions To: "Steve Bacher (Batchman)" , common-lisp@sail.stanford.edu In-Reply-To: Steve Bacher (Batchman)'s message of Thu, 8 Sep 88 07:47 EDT > From: CCFVX3::SEB1525 "Steve Bacher (Batchman)" 8-SEP-1988 07:30 > To: IN%"jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.UK",SEB1525 > Subj: RE: Re: Implementing :TEMPORARY hash tables at the Lisp level? > > Well, as was already pointed out, an implementation may be creating new > objects every time #' is done, and it may not be trivial to optimize this > on the part of the compiler. There's gotta be a better way... I think it *is* trivial to optimize #'F when F is a symbol. Simply return the value of F in the function namespace: this function should already exist and should not have to be copied or remade. Comparison between different results of #'(LAMBDA ...), however, will always be problematic because we want to allow certain optimizations which will depend on what side-effects occur in the lambda-expression and because it is not possible to compare arbitrary functions in general. -- Jeff  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Sep 88 08:56:54 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 8 Sep 88 05:42:50 PDT Received: from relay2.cs.net by RELAY.CS.NET id ab25423; 8 Sep 88 8:22 EDT Received: from draper.com by RELAY.CS.NET id ae21239; 8 Sep 88 8:02 EDT Date: Thu, 8 Sep 88 07:47 EDT From: "Steve Bacher (Batchman)" Subject: Comparing functions To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.edu" From: CCFVX3::SEB1525 "Steve Bacher (Batchman)" 8-SEP-1988 07:30 To: IN%"jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.UK",SEB1525 Subj: RE: Re: Implementing :TEMPORARY hash tables at the Lisp level? Well, as was already pointed out, an implementation may be creating new objects every time #' is done, and it may not be trivial to optimize this on the part of the compiler. There's gotta be a better way...  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Sep 88 17:27:34 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 7 Sep 88 14:11:18 PDT Received: from SWALLOW.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 455802; Wed 7-Sep-88 17:07:17 EDT Date: Wed, 7 Sep 88 17:06 EDT From: Michael Greenwald Subject: weak pointers vs temporary hash tables To: barmar@Think.COM, common-lisp@sail.stanford.edu In-Reply-To: <19880907200516.0.BARMAR@OCCAM.THINK.COM> Message-ID: <19880907210643.8.GREENWALD@SWALLOW.SCRC.Symbolics.COM> Date: Wed, 7 Sep 88 16:05 EDT From: Barry Margolin This discussion we've been having keeps going between temporary hash tables and weak pointers, and the implication of the latter discussion seemed to be that weak pointers are all you need for temporary hash tables. I'm not sure this is so. Weak pointers + finalization. For temporary hash tables, special measures need to be taken when a weak key is GCed. You can't just set the key slot of the table entry to NIL. First of all, it would be nice to also nullify the value slot of an entry whose key is GCed, so that the value can be GCed. This could be done by high-level code outside the GC, though. A more significant problem is that most hash table mechanisms need to be able to distinguish never-used table entries from deleted table entries. Also, just setting the key field to NIL is no good, because NIL is a valid key. The mechanism for invalidating weak pointers to garbage must therefore be cognizant of the high-level structure containing the weak pointer. That's what finalization is for. The finalization function really has to be per pointer. Maybe that means that an explicit form is needed to dereference a weak-pointer (this would be invisible to users of temporary hash tables but visible to clients of the subprimitives). This would probably need to be done anyway, since when you pass an object referenced through a weak pointer to another function, you probably want to pass the strong pointer. In any case, I don't see why this is a problem. When you are about to free an object in a temporary table, you call the finalization function on it. The finalization function for this particular weak-pointer is probably a closure that is closed over the table, and fixes up the key-field - i.e. it is cognizant of the high-level structure containing the weak pointer. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Sep 88 17:15:22 EDT Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 7 Sep 88 14:00:49 PDT Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP id aa07948; 7 Sep 88 21:25 BST Date: Wed, 7 Sep 88 21:54:04 BST Message-Id: <21717.8809072054@subnode.aiai.ed.ac.uk> From: Jeff Dalton Subject: Re: Implementing :TEMPORARY hash tables at the Lisp level? To: Barry Margolin Cc: common-lisp@sail.stanford.edu > Date: Wed, 7 Sep 88 18:26:30 BST > From: Jeff Dalton > > Functions can be compared with EQ, EQL, and EQUAL, > > Function objects can, but not the results of invocations of the FUNCTION > special form. On p.89, CLtL says, "a perfectly valid implementation > might simply cause every distinct evaluation of a FUNCTION form to > produce a new closure object not EQ to any other." Well, (FUNCTION F) where there is no local function binding of F is supposedly equivalent to (SYMBOL-FUNCTION 'F); and this is what I had in mind when comparing with #'EQ. So a question is: can SYMBOL-FUNCTION return a new object each time? If so, I think this should be changed since it is clearly pointless. And, if (let ((f #'(lambda () 1))) (eq f f)) => t [and it had better], then (flet ((f () 1)) (eq #'f #'f)) should => t [though I agree that CLtL does not say it will or should => T]. > The precise behavior > of the FUNCTION special form in this regard will frequently depend on > whether the code is compiled or interpreted and whether the argument is > a global function name, a local function name, or a lambda expression. > > For example, in Symbolics Common Lisp the function > > (defun fn-eq-test (a) > (flet ((internal () (cons a a))) > (eq #'internal #'internal))) > > returns NIL when interpreted, but T when compiled. The interpreter > definition of FUNCTION simply makes a new lexical closure, while the > compiler collapses equivalent lexical closures. Because of the LET analogy above, I do not see any need to have FUNCTION make a new closure when its argument is a symbol. When the argument is a LAMBDA-expression, then "is it really the same" becomes more difficult, and I can see an interpreter (or compiler) taking a shortcut. That is: FLET should be the one taking the shortcut for symbols, not FUNCTION. I suppose this would be harder to describe, though. -- Jeff  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Sep 88 16:41:08 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 7 Sep 88 13:22:37 PDT Received: from SWALLOW.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 455750; Wed 7-Sep-88 16:18:27 EDT Date: Wed, 7 Sep 88 16:17 EDT From: Michael Greenwald Subject: Re: Hash Tables and GC To: DDYER@RIVERSIDE.SCRC.Symbolics.COM, Greenwald@STONY-BROOK.SCRC.Symbolics.COM, Gregor.pa@Xerox.COM, goldman@vaxa.isi.edu cc: COMMON-LISP@sail.stanford.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk In-Reply-To: <19880907200206.8.DDYER@PURPLE.SWW.Symbolics.COM> Message-ID: <19880907201756.7.GREENWALD@SWALLOW.SCRC.Symbolics.COM> Date: Wed, 7 Sep 88 13:02 PDT From: DDYER@RIVERSIDE.SCRC.Symbolics.COM Date: Wed, 7 Sep 88 15:49 EDT From: Michael Greenwald Date: Wed, 7 Sep 88 11:52 PDT From: DDYER@RIVERSIDE.SCRC.Symbolics.COM Just to throw a little light into this discussion: On Symbolics systems there is a list of forms to be evaluated before any gc flip (ephemeral or dynamic). It's possible to implement whatever kind of weak pointers strategy you want by explicitly clearing whatever pointers are "weak" before the flip occurs. The list is called SI:GC-EVERY-FLIP-LIST How does this tell you whether there *are* any non-weak pointers to the object in question? The main point of the desire for weak pointers is to free storage being held by the pointers. weak-pointers also allow you to hold on to a pointer that may be useful if and only if someone else is also interested in the object. If "strong" pointers exist to the object then you definitely want to keep a weak pointer to it. If not, you could have just cleared the pointer at any point and it would have been GC'd in the next flip. SI:GC-EVERY-FLIP-LIST can't tell you that removing a pointer will definitely free storage, but it does let you remove pointers that you don't need and that you know will probably free storage. For example, I've used it to empty the free pool of a resource, and I've used it to "clean" a cache of all obsolete items.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Sep 88 16:25:33 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 7 Sep 88 13:10:43 PDT Return-Path: Received: from sauron.think.com by Think.COM; Wed, 7 Sep 88 16:11:39 EDT Received: from OCCAM.THINK.COM by sauron.think.com; Wed, 7 Sep 88 16:08:48 EDT Date: Wed, 7 Sep 88 16:05 EDT From: Barry Margolin Subject: weak pointers vs temporary hash tables To: common-lisp@sail.stanford.edu Message-Id: <19880907200516.0.BARMAR@OCCAM.THINK.COM> This discussion we've been having keeps going between temporary hash tables and weak pointers, and the implication of the latter discussion seemed to be that weak pointers are all you need for temporary hash tables. I'm not sure this is so. For temporary hash tables, special measures need to be taken when a weak key is GCed. You can't just set the key slot of the table entry to NIL. First of all, it would be nice to also nullify the value slot of an entry whose key is GCed, so that the value can be GCed. This could be done by high-level code outside the GC, though. A more significant problem is that most hash table mechanisms need to be able to distinguish never-used table entries from deleted table entries. Also, just setting the key field to NIL is no good, because NIL is a valid key. The mechanism for invalidating weak pointers to garbage must therefore be cognizant of the high-level structure containing the weak pointer. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Sep 88 16:23:19 EDT Received: from WHITE.SWW.Symbolics.COM ([128.81.57.24]) by SAIL.Stanford.EDU with TCP; 7 Sep 88 13:06:41 PDT Received: from PURPLE.SWW.Symbolics.COM by WHITE.SWW.Symbolics.COM via CHAOS with CHAOS-MAIL id 206738; Wed 7-Sep-88 13:01:32 PDT Date: Wed, 7 Sep 88 13:02 PDT From: DDYER@RIVERSIDE.SCRC.Symbolics.COM Subject: Re: Hash Tables and GC To: Michael Greenwald , Gregor.pa@Xerox.COM, goldman@vaxa.isi.edu cc: COMMON-LISP@sail.stanford.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk Fcc: W:>ddyer>mail.sent.newest In-Reply-To: <19880907194934.3.GREENWALD@SWALLOW.SCRC.Symbolics.COM> Message-ID: <19880907200206.8.DDYER@PURPLE.SWW.Symbolics.COM> Date: Wed, 7 Sep 88 15:49 EDT From: Michael Greenwald Date: Wed, 7 Sep 88 11:52 PDT From: DDYER@RIVERSIDE.SCRC.Symbolics.COM Just to throw a little light into this discussion: On Symbolics systems there is a list of forms to be evaluated before any gc flip (ephemeral or dynamic). It's possible to implement whatever kind of weak pointers strategy you want by explicitly clearing whatever pointers are "weak" before the flip occurs. The list is called SI:GC-EVERY-FLIP-LIST How does this tell you whether there *are* any non-weak pointers to the object in question? The main point of the desire for weak pointers is to free storage being held by the pointers. SI:GC-EVERY-FLIP-LIST can't tell you that removing a pointer will definitely free storage, but it does let you remove pointers that you don't need and that you know will probably free storage. For example, I've used it to empty the free pool of a resource, and I've used it to "clean" a cache of all obsolete items.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Sep 88 16:20:54 EDT Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 7 Sep 88 13:02:10 PDT Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP id aa07379; 7 Sep 88 20:23 BST Date: Wed, 7 Sep 88 20:51:39 BST Message-Id: <21582.8809071951@subnode.aiai.ed.ac.uk> From: Jeff Dalton Subject: Re: Hash Tables and GC To: Michael Greenwald , Gregor.pa@xerox.com, goldman@vaxa.isi.edu In-Reply-To: Michael Greenwald's message of Wed, 7 Sep 88 13:07 EDT Cc: COMMON-LISP@sail.stanford.edu > Date: Tue, 6 Sep 88 19:50 PDT > From: Gregor.pa@Xerox.COM > > This may not be facility we want to add to Common > Lisp, but as near as I can tell, weak pointers and finalization are the > primitives you need to build these kind of hash tables. > > In addition, finalization is a useful mechanism to have direct access > to. > > Yes. It's not just useful in hash tables, and it allows multiple > weak-pointers to the same object. [...] I'm not sure if there is an > advantage in having multiple weak-pointers to the same object, but > still, weak-pointers and finalization provide a lot more flexibility > than simply implementing temporary hash tables. Can weak pointers can be implemented using temp-entry tables? I think something like the following might work: (let ((table (make-hash-table :test #'eq :temporary t)) (inverse (make-hash-table :test #'eq :temporary t))) (defun make-weak-pointer (object) (let ((wp (gethash object table nil))) (when (null wp) (setq wp (list "weak pointer")) (setf (gethash object table) wp) (setf (gethash wp inverse) object)) wp)) (defun deref (wp) (gethash wp inverse nil)) ) Unfortunately, these weak pointers can't be collected while there are still references to the corresponding objects. This suggests that we may want tables from which entries can be removed when there is no other reference to the value [or the key?]. Then, if there were no reference to the weak pointer, the entries in both TABLE and INVERSE could be removed. Or we could have tables that hashed both ways. Oh, well. Perhaps we *should* look to lower-level primitives. The reasons against that approach, though, seem to be the following: (1) Weak tables are as good as weak pointers for many purposes. (2) Weak tables are sufficiently useful in their own right that they should be provided even if lower-level primitives are also available. (3) Weak pointers + finalization are insufficient for implementing weak tables because one also needs EQ-hashing that is efficient and yet doesn't break when used with a GC that moves objects. [I would be pleased to find that I am wrong on this point.] [OK, maybe something like this: (defun make-weak-table () (make-hash-table)) (defun weak-gethash (object table) (gethash (unique-weak-pointer object) table)) But when the weak pointer becomes invalid, the table entry must still remain. Enter finalization?] (4) While it seems possible that weak tables might be accepted as as addition to Common Lisp, it seems less likely that finalization would be. -- Jeff  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Sep 88 16:09:50 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 7 Sep 88 12:54:30 PDT Return-Path: Received: from sauron.think.com by Think.COM; Wed, 7 Sep 88 15:54:21 EDT Received: from OCCAM.THINK.COM by sauron.think.com; Wed, 7 Sep 88 15:51:30 EDT Date: Wed, 7 Sep 88 15:47 EDT From: Barry Margolin Subject: Re: Hash Tables and GC To: DDYER@riverside.scrc.symbolics.com Cc: Michael Greenwald , Gregor.pa@xerox.com, goldman@vaxa.isi.edu, COMMON-LISP@sail.stanford.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk In-Reply-To: <19880907185230.5.DDYER@PURPLE.SWW.Symbolics.COM> Message-Id: <19880907194758.9.BARMAR@OCCAM.THINK.COM> Date: Wed, 7 Sep 88 11:52 PDT From: DDYER@riverside.scrc.symbolics.com Just to throw a little light into this discussion: On Symbolics systems there is a list of forms to be evaluated before any gc flip (ephemeral or dynamic). It's possible to implement whatever kind of weak pointers strategy you want by explicitly clearing whatever pointers are "weak" before the flip occurs. The list is called SI:GC-EVERY-FLIP-LIST I don't think this works. After the flip finishes you will then need to restore the weak pointers that pointed to objects that also had strong pointers pointing to them. How do you do this? barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Sep 88 16:06:19 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 7 Sep 88 12:52:47 PDT Received: from SWALLOW.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 455709; Wed 7-Sep-88 15:50:05 EDT Date: Wed, 7 Sep 88 15:49 EDT From: Michael Greenwald Subject: Re: Hash Tables and GC To: DDYER@RIVERSIDE.SCRC.Symbolics.COM, Greenwald@STONY-BROOK.SCRC.Symbolics.COM, Gregor.pa@Xerox.COM, goldman@vaxa.isi.edu cc: COMMON-LISP@sail.stanford.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk In-Reply-To: <19880907185230.5.DDYER@PURPLE.SWW.Symbolics.COM> Message-ID: <19880907194934.3.GREENWALD@SWALLOW.SCRC.Symbolics.COM> Date: Wed, 7 Sep 88 11:52 PDT From: DDYER@RIVERSIDE.SCRC.Symbolics.COM Just to throw a little light into this discussion: On Symbolics systems there is a list of forms to be evaluated before any gc flip (ephemeral or dynamic). It's possible to implement whatever kind of weak pointers strategy you want by explicitly clearing whatever pointers are "weak" before the flip occurs. The list is called SI:GC-EVERY-FLIP-LIST How does this tell you whether there *are* any non-weak pointers to the object in question?  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Sep 88 15:38:15 EDT Received: from WHITE.SWW.Symbolics.COM ([128.81.57.24]) by SAIL.Stanford.EDU with TCP; 7 Sep 88 12:22:44 PDT Received: from PURPLE.SWW.Symbolics.COM by WHITE.SWW.Symbolics.COM via CHAOS with CHAOS-MAIL id 206707; Wed 7-Sep-88 11:51:58 PDT Date: Wed, 7 Sep 88 11:52 PDT From: DDYER@RIVERSIDE.SCRC.Symbolics.COM Subject: Re: Hash Tables and GC To: Michael Greenwald , Gregor.pa@Xerox.COM, goldman@vaxa.isi.edu cc: COMMON-LISP@sail.stanford.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk Fcc: W:>ddyer>mail.sent.newest In-Reply-To: <19880907170749.7.GREENWALD@SWALLOW.SCRC.Symbolics.COM> Message-ID: <19880907185230.5.DDYER@PURPLE.SWW.Symbolics.COM> Just to throw a little light into this discussion: On Symbolics systems there is a list of forms to be evaluated before any gc flip (ephemeral or dynamic). It's possible to implement whatever kind of weak pointers strategy you want by explicitly clearing whatever pointers are "weak" before the flip occurs. The list is called SI:GC-EVERY-FLIP-LIST  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Sep 88 15:14:51 EDT Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 7 Sep 88 11:56:53 PDT Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP id aa06905; 7 Sep 88 19:20 BST Date: Wed, 7 Sep 88 19:49:10 BST Message-Id: <21507.8809071849@subnode.aiai.ed.ac.uk> From: Jeff Dalton Subject: Re: Hash Tables and GC To: COMMON-LISP@sail.stanford.edu, goldman@vaxa.isi.edu Cc: jeff <@NSS.Cs.Ucl.AC.UK:jeff@aiai.edinburgh.ac.uk> > Also, the think the proposal should explicitly state that > IT IS AN ERROR to apply MAPHASH or HASH-TABLE-COUNT to > a TEMPORARY hash table. (Alternatively, the proposal could state what > useful behavior can be relied on for these functions with > temporary hash tables. For instance, they could map over / count all > the non-garbage entries as well as whatever garbage entries had > not yet been collected. But would that be useful?) This question is tied to that of whether temporary tables should be a variety of hash table or a tables of a new type. If they are hash tables, I think it should be possible to apply MAPHASH and HASH-TABLE- COUNT (with the understanding that some entries might vanish without an explicit REMHASH). It would be too great an inconsistency to disallow these operations. Moreover, if we feel the operations *are* useful, that would be an additional reason to make temporary tables be hash tables. (This is the "they would be so like hash tables that they might as well *be* hash tables" argument.) However, suppose temporary tables are not hash tables. Then we might omit operations like MAPHASH and HASH-TABLE-COUNT, for simplicity, but also because removability would then follow automatically: there would be no way to determine that *any* entries had been removed unless there was some independent reference to the keys, and so entries without such an independent reference could be removed. There would be no need to mention garbage collection in the description of the tables. [BTW, this suggests that the keyword argument to MAKE-HASH-TABLE might be :MAPPABLE rather than :TEMPORARY. Tables that were not mappable could have entries secretly removed. Of course, another choice would be to have :PERMANENT, defaulting to T, instead of :TEMPORARY, defaulting to NIL.] The reason I have not advocated this approach is that I suspect that mapping over temporary tables is useful. For example, a table where the values are meant only to be "true" would be a "weak set", presence in the table indicating membership in the set. It makes sense to ask what objects are (still) in the set. Moreover, implementation of such tables tend to provide mapping operations. T, which has weak sets but not the general tables, provides a WALK-WEAK-SET to map over the set as well as WEAK-SET->LIST to give a list of the members. Pop11, which has tables with temporary entries, also provides a mapping operation. -- Jeff  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Sep 88 14:44:48 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 7 Sep 88 11:30:28 PDT Return-Path: Received: from sauron.think.com by Think.COM; Wed, 7 Sep 88 14:31:10 EDT Received: from OCCAM.THINK.COM by sauron.think.com; Wed, 7 Sep 88 14:28:01 EDT Date: Wed, 7 Sep 88 14:24 EDT From: Barry Margolin Subject: Re: Implementing :TEMPORARY hash tables at the Lisp level? To: Jeff Dalton Cc: "Steve Bacher (Batchman)" , SEB1525%draper.com@NSS.Cs.Ucl.AC.UK, common-lisp@sail.stanford.edu In-Reply-To: <21061.8809071726@subnode.aiai.ed.ac.uk> Message-Id: <19880907182427.4.BARMAR@OCCAM.THINK.COM> Date: Wed, 7 Sep 88 18:26:30 BST From: Jeff Dalton Functions can be compared with EQ, EQL, and EQUAL, Function objects can, but not the results of invocations of the FUNCTION special form. On p.89, CLtL says, "a perfectly valid implementation might simply cause every distinct evaluation of a FUNCTION form to produce a new closure object not EQ to any other." The precise behavior of the FUNCTION special form in this regard will frequently depend on whether the code is compiled or interpreted and whether the argument is a global function name, a local function name, or a lambda expression. For example, in Symbolics Common Lisp the function (defun fn-eq-test (a) (flet ((internal () (cons a a))) (eq #'internal #'internal))) returns NIL when interpreted, but T when compiled. The interpreter definition of FUNCTION simply makes a new lexical closure, while the compiler collapses equivalent lexical closures. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Sep 88 14:39:57 EDT Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 7 Sep 88 11:24:16 PDT Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP id aa06508; 7 Sep 88 18:31 BST Date: Wed, 7 Sep 88 19:00:12 BST Message-Id: <21247.8809071800@subnode.aiai.ed.ac.uk> From: Jeff Dalton Subject: Re: Hash Tables and GC To: COMMON-LISP@sail.stanford.edu, goldman@vaxa.isi.edu Cc: jeff <@NSS.Cs.Ucl.AC.UK:jeff@aiai.edinburgh.ac.uk> > Add a keyword parameter :TEMPORARY to MAKE-HASH-TABLE. If this > argument is specified and not NIL, and if :TEST is #'EQ or #'EQL, > entries in the table may be removed by the GC if the key (i.e., > an object EQ or EQL to the key) IS ACCESSIBLE ONLY THROUGH THE > TABLE. Entries in EQUAL tables are never so removed, nor are > numbers in EQL tables. [Explanation: in these cases, it is > generally possible to construct new objects that are respectively > EQUAL or EQL to the key.] > > Numbers and Characters could never be removed from EQL tables, because > they ARE always accessible in other ways. But what is the rationale for > PROHIBITING the removal of an entry from an EQUAL hash table if its > key is in fact accessible ONLY through the table? E.g., defstruct > instances and symbols can be legitimately used as keys in an EQUAL hash > table, so an implementation that removed them from EQ hash tables > would be able to remove them from EQUAL tables as well. You are quite correct; I neglected to include characters with numbers as objects that could not be removed from EQL tables and also to consider the cases where EQUAL was equivalent to EQL (for EQUAL hash tables). The latter point is important because it makes EQUAL tables less of a special case. Thank you for bringing it up. > Note that > all discussions of this topic have considered an implementation correct > even if it NEVER removed entries, and I don't recall anyone implying > that an implementation that did remove entries was required to remove > ALL removable entries. I agree. Moreover, there will be times when removable entries have not yet been removed even if they will be removed eventually. Or, consider lists in EQUAL tables. I would not expect list-key entries to be removed even though some might be removable in principle when they contain EQ-unique objects accessable only through the table entry. -- Jeff  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Sep 88 14:10:00 EDT Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 7 Sep 88 10:52:55 PDT Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP id aa06322; 7 Sep 88 17:57 BST Date: Wed, 7 Sep 88 18:26:30 BST Message-Id: <21061.8809071726@subnode.aiai.ed.ac.uk> From: Jeff Dalton Subject: Re: Implementing :TEMPORARY hash tables at the Lisp level? To: "Steve Bacher (Batchman)" , SEB1525%draper.com@NSS.Cs.Ucl.AC.UK, common-lisp@sail.stanford.edu In-Reply-To: Steve Bacher (Batchman)'s message of Wed, 7 Sep 88 07:52 EDT > Just a question. If one were to implement :TEMPORARY hash tables as > described - i.e. testing to see if the test were #'EQ or #'EQL - well, > just how does one code such a test in CL? Presumably you'd have code like > > (case test > ((#'eq #'eql) (make-em-collectible)) > ((#'equal) (dont-make-em-collectible)) > (otherwise (make-em-whatever-you-want))) > > But... there is no way of testing equality of functions, lexical closures, > or what have you, in CL. So how can this possibly be implemented? This problem already exists for hash tables: something must see whether the :TEST argument is EQ, EQL, or EQUAL. I suspect this involves code like the following: (cond ((or (eq test #'eq) (eq test 'eq)) ...eq hash table...) ((or (eq test #'eql) (eq test 'eql)) ...eql hash table...) ((eq (eq test #'equal) (eq test 'equal)) ...equal hash table...) (t ...whatever...)) Functions can be compared with EQ, EQL, and EQUAL, but the meaning is not "do they compute the same (mathematical) function". Code like the following will not work: (make-hash-table :test #'(lambda (a b) (eq a b))) -- Jeff  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Sep 88 13:26:25 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 7 Sep 88 10:12:48 PDT Received: from SWALLOW.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 455541; Wed 7-Sep-88 13:08:22 EDT Date: Wed, 7 Sep 88 13:07 EDT From: Michael Greenwald Subject: Re: Hash Tables and GC To: Gregor.pa@Xerox.COM, goldman@vaxa.isi.edu cc: COMMON-LISP@sail.stanford.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk In-Reply-To: <19880907025057.5.GREGOR@PORTNOY.parc.xerox.com> Message-ID: <19880907170749.7.GREENWALD@SWALLOW.SCRC.Symbolics.COM> Date: Tue, 6 Sep 88 19:50 PDT From: Gregor.pa@Xerox.COM As I understand it, finalization is a mechanism for recording a function which the garbage collector should call on an object when it is about to be GC'd. I find it surprising that no one has talked about finalization during this discussion. I guess my previous mail did not get through. I'll recap. We had an uninstalled version of finalization (not the name we used, but "finalization" is better) and weak pointers in the SWIFT system. SWIFT wasn't written in LISP, but it is still applicable (CLU is another GC'd language, which you can consider sort of Lisp with syntax, strong typing, and compile time type checking, for the purpose of this conversation). There are only two points about finalization that I feel should be brought up. First, we found it useful to allow the finalization funarg to return a value indicating whether or not to *really* GC the object. The finalization funarg was called on every GC pass when the only pointers to an object were weak pointers. If it returned FALSE, then the object survived the GC, TRUE then the storage was reclaimed. Second, given a finalization funarg, it is possible to lie to the GC (keep, or create, another reference to the object). Therefore, the GC reclaimed weak-pointer objects by clearing the pointer to the object in the weak pointer, so that if there *really* are no other references to the object it would be reclaimed on the next pass. We had a non-compacting, mark and sweep, parallel ("real time") GC, FYI, since someone asked about this before. This may not be facility we want to add to Common Lisp, but as near as I can tell, weak pointers and finalization are the primitives you need to build these kind of hash tables. In addition, finalization is a useful mechanism to have direct access to. Yes. It's not just useful in hash tables, and it allows multiple weak-pointers to the same object. It was mainly useful for unlinking and caching. (SWIFT ran in a single address space, so if you wanted to flush some application completely from the world, you had to make sure that you didn't leave a pointer to some data structure squirreled away somewhere in the bowels of the operating system. Weak pointers (it was actually more like "weak objects" (or "GCable objects")) solved this problem.) In a lisp application where each process gets its own address space that is killed when the process is killed, I'm not sure if there is an advantage in having multiple weak-pointers to the same object, but still, weak-pointers and finalization provide a lot more flexibility than simply implementing temporary hash tables.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Sep 88 12:27:23 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 7 Sep 88 09:13:07 PDT Return-Path: Received: from sauron.think.com by Think.COM; Wed, 7 Sep 88 12:13:56 EDT Received: from OCCAM.THINK.COM by sauron.think.com; Wed, 7 Sep 88 12:11:01 EDT Date: Wed, 7 Sep 88 12:07 EDT From: Barry Margolin Subject: Implementing :TEMPORARY hash tables at the Lisp level? To: "Steve Bacher (Batchman)" Cc: common-lisp@sail.stanford.edu In-Reply-To: <8809071217.AA06853@Think.COM> Message-Id: <19880907160730.3.BARMAR@OCCAM.THINK.COM> Date: Wed, 7 Sep 88 07:52 EDT From: "Steve Bacher (Batchman)" Just a question. If one were to implement :TEMPORARY hash tables as described - i.e. testing to see if the test were #'EQ or #'EQL - well, just how does one code such a test in CL? Presumably you'd have code like (case test ((#'eq #'eql) (make-em-collectible)) ((#'equal) (dont-make-em-collectible)) (otherwise (make-em-whatever-you-want))) But... there is no way of testing equality of functions, lexical closures, or what have you, in CL. So how can this possibly be implemented? The internal implementation of a Common Lisp need not be written using portable constructs. I suspect that in most CL implementations, #' always returns the same thing for symbols that do not have a lexical function binding, so the above code would work. If not, then the hash table implementation will have to use some implementation-dependent functions to extract the function object from a closure and compare it against the function bindings of EQ, EQL, and EQUAL. In fact, current implementations of MAKE-HASH-TABLE must already have something like this, since the hash function of a hash table must be dependent on the :TEST argument. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Sep 88 08:28:05 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 7 Sep 88 05:15:09 PDT Received: from relay2.cs.net by RELAY.CS.NET id aa06150; 7 Sep 88 8:14 EDT Received: from draper.com by RELAY.CS.NET id ab13145; 7 Sep 88 7:59 EDT Date: Wed, 7 Sep 88 07:52 EDT From: "Steve Bacher (Batchman)" Subject: Implementing :TEMPORARY hash tables at the Lisp level? To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.edu",SEB1525 Just a question. If one were to implement :TEMPORARY hash tables as described - i.e. testing to see if the test were #'EQ or #'EQL - well, just how does one code such a test in CL? Presumably you'd have code like (case test ((#'eq #'eql) (make-em-collectible)) ((#'equal) (dont-make-em-collectible)) (otherwise (make-em-whatever-you-want))) But... there is no way of testing equality of functions, lexical closures, or what have you, in CL. So how can this possibly be implemented?  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 6 Sep 88 23:05:43 EDT Received: from Xerox.COM by SAIL.Stanford.EDU with TCP; 6 Sep 88 19:53:04 PDT Received: from Semillon.ms by ArpaGateway.ms ; 06 SEP 88 19:51:12 PDT Date: Tue, 6 Sep 88 19:50 PDT From: Gregor.pa@Xerox.COM Subject: Re: Hash Tables and GC To: goldman@vaxa.isi.edu cc: COMMON-LISP@sail.stanford.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk Fcc: BD:>Gregor>mail>outgoing-mail-4.text.newest In-Reply-To: <8809070108.AA13965@vaxa.isi.edu> Message-ID: <19880907025057.5.GREGOR@PORTNOY.parc.xerox.com> Line-fold: no As I understand it, finalization is a mechanism for recording a function which the garbage collector should call on an object when it is about to be GC'd. I find it surprising that no one has talked about finalization during this discussion. This may not be facility we want to add to Common Lisp, but as near as I can tell, weak pointers and finalization are the primitives you need to build these kind of hash tables. In addition, finalization is a useful mechanism to have direct access to. -------  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 6 Sep 88 21:21:57 EDT Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 6 Sep 88 18:08:07 PDT Posted-Date: Tue, 06 Sep 88 17:08:03 PST Message-Id: <8809070108.AA13965@vaxa.isi.edu> Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51) id AA13965; Tue, 6 Sep 88 18:08:06 PDT To: COMMON-LISP@sail.stanford.edu From: goldman@vaxa.isi.edu Subject: Hash Tables and GC Cc: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk Date: Tue, 06 Sep 88 17:08:03 PST Sender: goldman@vaxa.isi.edu Add a keyword parameter :TEMPORARY to MAKE-HASH-TABLE. If this argument is specified and not NIL, and if :TEST is #'EQ or #'EQL, entries in the table may be removed by the GC if the key (i.e., an object EQ or EQL to the key) IS ACCESSIBLE ONLY THROUGH THE TABLE. Entries in EQUAL tables are never so removed, nor are numbers in EQL tables. [Explanation: in these cases, it is generally possible to construct new objects that are respectively EQUAL or EQL to the key.] Numbers and Characters could never be removed from EQL tables, because they ARE always accessible in other ways. But what is the rationale for PROHIBITING the removal of an entry from an EQUAL hash table if its key is in fact accessible ONLY through the table? E.g., defstruct instances and symbols can be legitimately used as keys in an EQUAL hash table, so an implementation that removed them from EQ hash tables would be able to remove them from EQUAL tables as well. Note that all discussions of this topic have considered an implementation correct even if it NEVER removed entries, and I don't recall anyone implying that an implementation that did remove entries was required to remove ALL removable entries. Also, the think the proposal should explicitly state that IT IS AN ERROR to apply MAPHASH or HASH-TABLE-COUNT to a TEMPORARY hash table. (Alternatively, the proposal could state what useful behavior can be relied on for these functions with temporary hash tables. For instance, they could map over / count all the non-garbage entries as well as whatever gargage entries had not yet been collected. But would that be useful?) Neil  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 4 Sep 88 16:33:54 EDT Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 4 Sep 88 13:17:25 PDT Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP id aa04434; 4 Sep 88 20:43 BST Date: Sun, 4 Sep 88 21:10:24 BST Message-Id: <13560.8809042010@subnode.aiai.ed.ac.uk> From: Jeff Dalton Subject: Re: hash tables and GC To: Rob.MacLachlan@wb1.cs.cmu.edu, Sandra J Loosemore In-Reply-To: Rob.MacLachlan@edu.cmu.cs.wb1's message of Thu, 01 Sep 88 15:07:46 EDT Cc: common-lisp@sail.stanford.edu > There is also the rather similar "weak pointer" notion, which I believe is > implemented in T. Yes, T does have weak pointers. They were also in RnRS for some n (as object-hash and object-unhash). I had thought that weak pointers might be sufficient, but then could not see any nice way to use them to implement what I really wanted. > The GC-able hash-table notion unnecessarily complicates the semantics by > rolling in hash-table semantics when the real issue is with GC. You're right, to some extent. But hash tables are the way Common Lisp provides efficient table-like mappings from keys to values. You might use something like a-lists instead, but only if a linear search is fast enough. You might implement a new facility of your own, but only if you wanted it to be significantly different from hash tables. My feeling is that a new kind of table-like mapping from keys to values that didn't prevent keys from being collected would be so much like hash tables that they might as well be hash tables. Or, we could look at it the other way around. A hash table is a mapping from keys to values. Why should a key be uncollectable just because it was given a value in a mapping? When the key is no longer referenced (except in the mapping), why must it's entry remain? Well, in some cases you may want it to remain, but I suspect that those cases are actually in the minority. Perhaps a better proposal would be to change hash tables to always have all entries be "temporary". But then we have a problem with backwards compatibility. > Usually the association capacity of hashtables is unnecessary: instead > of weak-hashing from A to B, allocate another slot in A to hold the weak > pointer to B. Weak pointers are more general. You can put them in lists, etc., not just in hash tables. But: (1) What if you can't add a slot to A? (2) What if only a small number of objects of the same type as A need the slot? (3) What if what you need is a weak pointer to A, not to B? That is what I actually want form the tables. I want the keys to be collectable. (But, since a hash table is a mapping from keys to values, values will be collectable when no longer needed for may key.) To implement tables with weak pointers to the keys, you need access to an EQ hash function and you need it to be an efficient hash that works even when objects might be moved. I suspect that would be very difficult. By having the tables built in, you do not need to provide the hash function. Then, once you have the tables, you can easily implement weak pointers and put them in lists, etc. -- Jeff  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 4 Sep 88 16:10:39 EDT Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 4 Sep 88 12:28:34 PDT Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP id aa04316; 4 Sep 88 19:45 BST Date: Sun, 4 Sep 88 20:12:49 BST Message-Id: <13499.8809041912@subnode.aiai.ed.ac.uk> From: Jeff Dalton Subject: Re: hash tables and GC To: Sandra J Loosemore , sandra@cs.utah.edu, common-lisp@sail.stanford.edu In-Reply-To: Sandra J Loosemore's message of Thu, 1 Sep 88 09:29:10 MDT > Specifically, I was thinking it would be nice to be > able to attach a property list to arbitrary objects, and not just to > symbols. (Two objects that are EQ would have the same property list.) > > As far as what it would allow you to do, this functionality is actually > pretty close to what is being proposed with the GC'able hash tables, and > I think it has some advantages. First, it would allow more freedom of > implementation; off the top of my head, I can think of at least two > approaches to doing it. And, it avoids some of the strangenesses that > would result from forcing GC'able hash tables into the same mold as > ordinary hash tables (like not allowing EQUAL as the :TEST, and MAPHASH > finding different sets of objects in the hash table depending on when > the last GC was). As you may recall, my original message took the idea from "temporary properties" in Pop11. So, the notion of "property" is OK with me. But, I'm not so happy with property *list*, which implies (1) linear search, (2) the existence of an actual list, and (3) a format for the list (an alternating sequence of property names and property values). -- Jeff  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 3 Sep 88 15:09:50 EDT Received: from Xerox.COM by SAIL.Stanford.EDU with TCP; 3 Sep 88 11:47:35 PDT Received: from Burger.ms by ArpaGateway.ms ; 03 SEP 88 11:46:29 PDT Sender: "Larry_Masinter.PARC"@Xerox.COM Date: 3 Sep 88 11:46:07 PDT (Saturday) Subject: Re: hash tables and GC From: "Larry_Masinter.PARC"@Xerox.COM To: common-lisp@sail.stanford.EDU In-Reply-to: smh's message of 29 Aug 88 23:07 Message-ID: <880903-114629-8359@Xerox> I recall that in the early-70s, Interlisp-10 only had EQ hash tables and would GC hash keys if the hash table was the only pointer. However, Peter Deutsch had an application (a theorem prover, I think) which used hash tables as the only pointers to his data structures and then used MAPHASH to retrieve them. So we changed the GC not to collect hash keys; I'm not sure when, but I'd guess around 1975. We thought about having both kinds of hash tables, but didn't implement it. My point is that the proposal isn't a novel feature (or issue) for Lisp implementations. It would be most useful to describe the proposal in terms of the semantics from the point of view of Lisp programs rather than the implementation of the garbage collector, especially since CLtL and the spec make almost no reference to the GC at all. The only semantic difference between :TEMPORARY and non-:TEMPORARY hash tables is that MAPHASH on :TEMPORARY hash tables may find fewer entries. For me, the questions remaining are: 0. Is :TEMPORARY T a good indicator? The table isn't really temporary, just the entires. Perhaps :MAPHASH T or :MAPHASH NIL? 1. How to describe the behavior of MAPHASH on such a table; are the results "undefined"? Didn't we already have this discussion on the Common-Lisp mailing list a while ago? Or was it about DO-ALL-SYMBOLS and packages...?  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 2 Sep 88 02:53:30 EDT Received: from lucid.com by SAIL.Stanford.EDU with TCP; 1 Sep 88 23:39:19 PDT Received: from bhopal ([192.9.200.13]) by heavens-gate id AA05817g; Thu, 1 Sep 88 22:36:48 PST Received: by bhopal id AA04580g; Thu, 1 Sep 88 23:36:06 PDT Date: Thu, 1 Sep 88 23:36:06 PDT From: Jon L White Message-Id: <8809020636.AA04580@bhopal> To: barmar@Think.COM Cc: DLA@jasper.scrc.symbolics.com, smh@ems.media.mit.edu, common-lisp@sail.stanford.edu In-Reply-To: Barry Margolin's message of Wed, 31 Aug 88 21:47 EDT <19880901014745.2.BARMAR@OCCAM.THINK.COM> Subject: hash tables and GC re: By the way, here is how I think weak tables could be implemented in a mark-sweep GC (are there any of those around any more?): During the mark phase, don't recurse through the keys of any weak tables. Before the sweep phase, make another pass, deleting any weak table entries whose keys are not marked. In fact, PDP10 MacLisp's OBARRAY (the hash-table for interned symbols) was implemented in the obvious way so that "truly worthless atoms" could be garbage collected, even though they were entered in the table. [There was a mode switch -- (SSTATUS GCTWA t-or-nil) -- to turn this capability on or off, since it did cost a marginal amount more of time]. The explicit step that is needed but not directly mentioned in your wording of the algorithm is that "value" links must be recursed through during the mark phase (for MacLisp, this meant descending the value-cell and plist attributes of interned symbols, without marking the symbol itself). That is, value links for entries that will not be deleted *may* contain the only pointers to other keys which protect those keys from undesired removal. In many reference counting garbage collectors, it is possible to ask "Is the reference count of this object equal to 1?" [and in the Deutsch/Bobrow variations, you can at least ask this question at scavenge time, even though you may not be able to ask it an just any old time]. If the answer to this question is Yes for a key in a "weak" table, then it must be that the one pointer to it is the table entry itself; hence it may be deleted. In VAX/NIL, we had devised a scheme for a sort of "weak pointer" table even though the garbage collector was to be a copying one. [It was mostly in conjunction with an emulation of the MAKNUM function of PDP10 MacLisp, which didn't do copying.] But alas, as the GC was last on the implementation agenda . . . well, suffice it to say that we didn't ever find out what the performance implication of that scheme would be. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 1 Sep 88 15:23:30 EDT Received: from FRED.SLISP.CS.CMU.EDU by SAIL.Stanford.EDU with TCP; 1 Sep 88 12:09:51 PDT Received: from FRED.SLISP.CS.CMU.EDU by FRED.SLISP.CS.CMU.EDU; 1 Sep 88 15:08:02 EDT To: sandra@cs.utah.edu (Sandra J Loosemore) cc: common-lisp@sail.stanford.edu Subject: Re: hash tables and GC In-reply-to: Your message of Thu, 01 Sep 88 09:29:10 -0600. <8809011529.AA00519@cs.utah.edu> Date: Thu, 01 Sep 88 15:07:46 EDT From: Rob.MacLachlan@WB1.CS.CMU.EDU There is also the rather similar "weak pointer" notion, which I believe is implemented in T. The operations on a weak pointer are something like: MAKE-WEAK-POINTER Object => Weak-Pointer INDIRECT-WEAK-POINTER Weak-Pointer => Object or NIL Having a weak pointer to an object allows you to keep track of it, but doesn't prevent GC. Although I haven't ever used either weak pointers or GC'able hash-tables, I think weak pointers are superior as a language feature, since they are more primitive and potentially more efficient. The GC-able hash-table notion unnecessarily complicates the semantics by rolling in hash-table semantics when the real issue is with GC. Usually the association capacity of hashtables is unnecessary: instead of weak-hashing from A to B, allocate another slot in A to hold the weak pointer to B. The implementation issues are basically the same as for GC-able hash-tables, but weak pointers seem to have a sight edge. They can be implemented by allocating weak pointers in a special area, but given abundant tag bits, immediate representations are also conceivable. Rob  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 1 Sep 88 12:38:57 EDT Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 1 Sep 88 09:24:53 PDT Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0) id AA01353; Thu, 1 Sep 88 09:21:50 PDT Received: from clam.sun.com by snail.sun.com (4.0/SMI-4.0) id AA19954; Thu, 1 Sep 88 09:24:39 PDT Received: by clam.sun.com (3.2/SMI-3.2) id AA13220; Thu, 1 Sep 88 09:25:04 PDT Date: Thu, 1 Sep 88 09:25:04 PDT From: cperdue@Sun.COM (Cris Perdue) Message-Id: <8809011625.AA13220@clam.sun.com> To: common-lisp@sail.stanford.edu, sandra@cs.utah.edu Subject: Re: hash tables and GC I've wished for the ability to put properties on arbitrary objects via hash tables without making the objects with properties non-collectable. I've written code that maps values such as strings to objects (a lot like a package does!). The purpose was for all equivalent values to map to a single object, so that any value in an equivalence class could share a set of properties with its equivalent values. I have wished that this mapping would not permanently hold onto the *objects*. If the object has no properties and no references except through the table it could be reclaimed. On the other hand, I'm not sure these are the most pressing issues around. -Cris  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 1 Sep 88 11:42:55 EDT Received: from cs.utah.edu by SAIL.Stanford.EDU with TCP; 1 Sep 88 08:30:23 PDT Received: by cs.utah.edu (5.54/utah-2.0-cs) id AA00519; Thu, 1 Sep 88 09:29:10 MDT Date: Thu, 1 Sep 88 09:29:10 MDT From: sandra@cs.utah.edu (Sandra J Loosemore) Message-Id: <8809011529.AA00519@cs.utah.edu> Subject: Re: hash tables and GC Newsgroups: fa.common-lisp To: common-lisp@sail.stanford.edu I suppose I should throw in my $.02 worth on this issue. A couple of weeks ago I was hacking on a piece of code where I thought that my job would be made much easier if I could attach some extra information to arbitrary objects. Specifically, I was thinking it would be nice to be able to attach a property list to arbitrary objects, and not just to symbols. (Two objects that are EQ would have the same property list.) As far as what it would allow you to do, this functionality is actually pretty close to what is being proposed with the GC'able hash tables, and I think it has some advantages. First, it would allow more freedom of implementation; off the top of my head, I can think of at least two approaches to doing it. And, it avoids some of the strangenesses that would result from forcing GC'able hash tables into the same mold as ordinary hash tables (like not allowing EQUAL as the :TEST, and MAPHASH finding different sets of objects in the hash table depending on when the last GC was). Anybody else think this is worth pursuing? -Sandra  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 31 Aug 88 23:02:45 EDT Received: from JASPER.SCRC.Symbolics.COM ([128.81.41.58]) by SAIL.Stanford.EDU with TCP; 31 Aug 88 19:50:40 PDT Received: from KOYAANISQATSI.SCRC.Symbolics.COM by JASPER.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 213821; Wed 31-Aug-88 22:49:45 EDT Date: Wed, 31 Aug 88 22:49 EDT From: David L. Andre Subject: Re: hash tables and GC To: barmar@Think.COM cc: smh@ems.media.mit.edu, common-lisp@sail.stanford.edu In-Reply-To: <19880901014745.2.BARMAR@OCCAM.THINK.COM> Message-ID: <19880901024922.3.DLA@KOYAANISQATSI.SCRC.Symbolics.COM> Date: Wed, 31 Aug 88 21:47 EDT From: Barry Margolin There's actually an even more trivial solution: don't implement them if you don't want to! Of course. The difference between weak tables and ordinary tables is that the implementation is ALLOWED to GC entries in weak tables. However, just as Common Lisp never actually says that an implementation MUST have a GC, it can't REQUIRE an implementation to GC entries in a weak table. So, if your GC is not easily extended to support weak tables, you can simply ignore the :WEAK (or whatever) option. The only invalid way to implement weak tables is to implement them in such a way that they GC entries that they shouldn't; remembering too much should never bother a valid CL program (unless it runs out of memory, but that's outside the language spec). (Hmm, this argument would justify a Lisp implementation that used only a reference-count GC, but I expect that there would be far fewer weak tables than circular structures, so the argument doesn't really scale up.) By the way, I assume that David meant that only key fields of tables should be skipped. Otherwise you could end up with keys whose values have been GCed. I can think of applications for weak-key, weak-value, and weak-key-and-value hash tables. Certainly weak-key is the most generally useful. By the way, here is how I think weak tables could be implemented in a mark-sweep GC (are there any of those around any more?): During the mark phase, don't recurse through the keys of any weak tables. Before the sweep phase, make another pass, deleting any weak table entries whose keys are not marked. The added passes of both the copying and mark/sweep GCs would be sped up significantly if the implementation maintained a list of all weak tables (or it could cons up such a list during the first pass), so that it wouldn't have to make a full pass through memory to find them. Sounds reasonable given 10 seconds of thought.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 31 Aug 88 22:03:41 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 31 Aug 88 18:49:35 PDT Return-Path: Received: from sauron.think.com by Think.COM; Wed, 31 Aug 88 21:43:52 EDT Received: from OCCAM.THINK.COM by sauron.think.com; Wed, 31 Aug 88 21:47:33 EDT Date: Wed, 31 Aug 88 21:47 EDT From: Barry Margolin Subject: Re: hash tables and GC To: David L. Andre Cc: smh@ems.media.mit.edu, common-lisp@sail.stanford.edu In-Reply-To: <19880901010347.3.DLA@KOYAANISQATSI.SCRC.Symbolics.COM> Message-Id: <19880901014745.2.BARMAR@OCCAM.THINK.COM> Date: Wed, 31 Aug 88 21:03 EDT From: David L. Andre Well, we haven't done it for standard architectures, but it would seem to be straightforward to add the feature to any copying garbage collector. Simplisticly, all you have to do is modify the scavenger to make two passes: The first pass skips any references from weak tables, and the second pass replaces oldspace references to the deleted objects with a null marker. The overhead of the second pass can typically be minimized by always creating such tables in a special part of address space, so the second pass has little overhead. There are many other possible optimizations. My point is, it has nothing to do with hardware support; it's at the next higher level. Hardware support at best will just give you a better scavenger to build this on. There's actually an even more trivial solution: don't implement them if you don't want to! The difference between weak tables and ordinary tables is that the implementation is ALLOWED to GC entries in weak tables. However, just as Common Lisp never actually says that an implementation MUST have a GC, it can't REQUIRE an implementation to GC entries in a weak table. So, if your GC is not easily extended to support weak tables, you can simply ignore the :WEAK (or whatever) option. The only invalid way to implement weak tables is to implement them in such a way that they GC entries that they shouldn't; remembering too much should never bother a valid CL program (unless it runs out of memory, but that's outside the language spec). (Hmm, this argument would justify a Lisp implementation that used only a reference-count GC, but I expect that there would be far fewer weak tables than circular structures, so the argument doesn't really scale up.) By the way, I assume that David meant that only key fields of tables should be skipped. Otherwise you could end up with keys whose values have been GCed. By the way, here is how I think weak tables could be implemented in a mark-sweep GC (are there any of those around any more?): During the mark phase, don't recurse through the keys of any weak tables. Before the sweep phase, make another pass, deleting any weak table entries whose keys are not marked. The added passes of both the copying and mark/sweep GCs would be sped up significantly if the implementation maintained a list of all weak tables (or it could cons up such a list during the first pass), so that it wouldn't have to make a full pass through memory to find them. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 31 Aug 88 21:20:07 EDT Received: from JASPER.SCRC.Symbolics.COM ([128.81.41.58]) by SAIL.Stanford.EDU with TCP; 31 Aug 88 18:06:10 PDT Received: from KOYAANISQATSI.SCRC.Symbolics.COM by JASPER.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 213799; Wed 31-Aug-88 21:05:29 EDT Date: Wed, 31 Aug 88 21:03 EDT From: David L. Andre Subject: Re: hash tables and GC To: smh@EMS.MEDIA.MIT.EDU cc: common-lisp@sail.stanford.edu In-Reply-To: <8808300403.AA03125@EMS.MEDIA.MIT.EDU> Message-ID: <19880901010347.3.DLA@KOYAANISQATSI.SCRC.Symbolics.COM> Date: Tue, 30 Aug 88 00:03:57 EDT From: smh@EMS.MEDIA.MIT.EDU (Steven Haflich) From: David L. Andre Subject: Re: hash tables and GC 0. Can such tables be implemented? Proof by existence: We have had such tables prototyped internally at Symbolics for a year or so, but have not had the resources to qualify them for release to customers. They can be quite efficient, and of course can significantly improve the efficiency of some kinds of programs. But perhaps this isn't exactly the right question for such a late date in the CL standards process. Rather: Can such tables be implemented with reasonable performance in *all* existing CL implementations, without breaking the GC strategies upon which they depend? I myself have no idea which way this question would fall, but unless it could confidently be answered in the affirmative I feel X3J13 would have to exclude these `weak-pointer' tables from the standard. The *real* problem is that it would be incumbent on the *proposer* to prove practicality. This would not be an easy proof. Well, we haven't done it for standard architectures, but it would seem to be straightforward to add the feature to any copying garbage collector. Simplisticly, all you have to do is modify the scavenger to make two passes: The first pass skips any references from weak tables, and the second pass replaces oldspace references to the deleted objects with a null marker. The overhead of the second pass can typically be minimized by always creating such tables in a special part of address space, so the second pass has little overhead. There are many other possible optimizations. My point is, it has nothing to do with hardware support; it's at the next higher level. Hardware support at best will just give you a better scavenger to build this on.  Received: from SAIL.Stanford.EDU (TCP 4425400302) by AI.AI.MIT.EDU 31 Aug 88 01:27:16 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 30 Aug 88 22:14:38 PDT Received: from SWALLOW.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 452687; Wed 31-Aug-88 01:13:35 EDT Date: Wed, 31 Aug 88 01:13 EDT From: Michael Greenwald Subject: RE: Read and "illegal" characters To: SEB1525@draper.com, common-lisp@SAIL.STANFORD.EDU In-Reply-To: The message of 30 Aug 88 16:37 EDT from "Steve Bacher (Batchman)" Message-ID: <19880831051323.5.GREENWALD@SWALLOW.SCRC.Symbolics.COM> Date: Tue, 30 Aug 88 16:37 EDT From: "Steve Bacher (Batchman)" Yes, (a) is what I meant - the syntactic property of the character, not the attribute used in scanning atom names. Then I believe that you are in luck. To recap: There are no standard characters that are syntactically "illegal", therefore no characters that *must* behave differently between single and multiple escapes. There is no CL sanctified way to set the syntax of a character, only to copy the syntax. Further, I believe it is legal for you, as a language implementor, to define the syntax of a character. So you are free to ensure that in your implementation, no characters have an "illegal syntactic type". Instead, define characters you want to outlaw as "constituents" with just the "illegal" attribute. There is now no way to create the problem characters. As I said before, this finesses the practical problem, but does not solve the academic problem. My personal hope is that the distinction between single and multiple-escapes is unintentional. The 2 paragraphs on pg 338 seems to support this: "As a rule, a @i(single escape) character never stands for itself but always serves to cause the following character to be treated as a simple alphabetic character. A @i(single escape) character can be included in a token only if preceded by another @i(single escape) character. A @i(multiple escape) character also never stands for itself. The characters between a pair of @i(multiple escape) characteres are all treated as simple alphabetic characrters, except that @i(single escape) and @i(multiple escape) characters must nevertheless be preceded by a @i(single escape) character to be included." Perhaps the cleanup committee has dealt with this issue already. I don't know.  Received: from SAIL.Stanford.EDU (TCP 4425400302) by AI.AI.MIT.EDU 30 Aug 88 19:48:05 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 30 Aug 88 16:36:45 PDT Received: from relay2.cs.net by RELAY.CS.NET id aa05497; 30 Aug 88 19:03 EDT Received: from draper.com by RELAY.CS.NET id ab15253; 30 Aug 88 18:50 EDT Date: Tue, 30 Aug 88 16:37 EDT From: "Steve Bacher (Batchman)" Subject: RE: Read and "illegal" characters To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.edu",SEB1525 Yes, (a) is what I meant - the syntactic property of the character, not the attribute used in scanning atom names.  Received: from REAGAN.AI.MIT.EDU (CHAOS 13065) by AI.AI.MIT.EDU 30 Aug 88 17:52:21 EDT Received: from SAIL.STANFORD.EDU by REAGAN.AI.MIT.EDU via INTERNET with SMTP id 131989; 30 Aug 88 17:08:47 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 30 Aug 88 09:51:32 PDT Received: from SWALLOW.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 452311; Tue 30-Aug-88 12:47:10 EDT Date: Tue, 30 Aug 88 12:46 EDT From: Michael Greenwald Subject: READ and "illegal" characters To: SEB1525@draper.com, common-lisp@SAIL.STANFORD.EDU In-Reply-To: The message of 25 Aug 88 13:36 EDT from "Steve Bacher (Batchman)" Message-ID: <19880830164657.2.GREENWALD@SWALLOW.SCRC.Symbolics.COM> Date: Thu, 25 Aug 88 13:36 EDT From: "Steve Bacher (Batchman)" Taking the description of the CL reader at face value, I infer that an "illegal" character may occur in a symbol name if it is preceded by a backslash ("single escape"), but not if it occurs inside a pair of vertical bars ("multiple escape"). This seems strange. Is it merely an oversight, or is it intentional? There appear to be two types of "illegal" characters - (a) a character with an "illegal" syntax type, or (b) a constituent character with an "illegal" attribute. Only illegal characters of type (b) are specified in the manual. Since it is impossible for a programmer to explicitly specify the syntactic type of a character (you can only copy it by set-syntax-from-char), it is up to the implementors to allow, or disallow an "illegal" syntactic type (type (a) illegal characters) in their implementation. Step 9 on page 337 specifically says that the reader performs "one of the following actions" according to the character's >syntactic< type. If you want multiple escapes to behave identically to single escapes, you can choose to make no characters with "illegal" syntactic type. (Make them all whitespace, or constituent with an "illegal" attribute) This finesses the question of whether CLtL means to treat single and multiple-escapes differently. But it does mean that the question isn't >significant<. Notice, though, that portability of printed representation isn't an issue here, because none of the standard characters have an "illegal" syntax type. This is a potentially significant problem, because it mandates that the printer must slashify "illegal" characters by preceding each one individually with a backslash rather than being able to just surround the entire name with vertical bars. For some implementations (i.e. mine), it is easier to embar the entire name, once it is determined that funny characters are present somewhere in the name. Is it intended that all characters not listed in the table as consituent, macro, etc. are "illegal"? Or might an implementation be able to treat them all as constituent characters? I believe the latter must be correct, (the implementor can choose the syntactic type of all non-standard characters), otherwise it would be impossible to read in symbols in (for example) Japanese.  Received: from REAGAN.AI.MIT.EDU (CHAOS 13065) by AI.AI.MIT.EDU 30 Aug 88 16:42:59 EDT Received: from SAIL.STANFORD.EDU by REAGAN.AI.MIT.EDU via INTERNET with SMTP id 131845; 30 Aug 88 04:41:11 EDT Received: from EMS.MEDIA.MIT.EDU (EMS.MIT.EDU) by SAIL.Stanford.EDU with TCP; 29 Aug 88 21:04:40 PDT Received: by EMS.MEDIA.MIT.EDU (5.54/4.8) id AA03125; Tue, 30 Aug 88 00:03:57 EDT Date: Tue, 30 Aug 88 00:03:57 EDT From: smh@EMS.MEDIA.MIT.EDU (Steven Haflich) Message-Id: <8808300403.AA03125@EMS.MEDIA.MIT.EDU> To: common-lisp@sail.stanford.edu Subject: Re: hash tables and GC From: David L. Andre Subject: Re: hash tables and GC 0. Can such tables be implemented? Proof by existence: We have had such tables prototyped internally at Symbolics for a year or so, but have not had the resources to qualify them for release to customers. They can be quite efficient, and of course can significantly improve the efficiency of some kinds of programs. But perhaps this isn't exactly the right question for such a late date in the CL standards process. Rather: Can such tables be implemented with reasonable performance in *all* existing CL implementations, without breaking the GC strategies upon which they depend? I myself have no idea which way this question would fall, but unless it could confidently be answered in the affirmative I feel X3J13 would have to exclude these `weak-pointer' tables from the standard. The *real* problem is that it would be incumbent on the *proposer* to prove practicality. This would not be an easy proof.  Received: from REAGAN.AI.MIT.EDU (CHAOS 13065) by AI.AI.MIT.EDU 30 Aug 88 13:04:51 EDT Received: from SAIL.STANFORD.EDU by REAGAN.AI.MIT.EDU via INTERNET with SMTP id 131846; 30 Aug 88 04:41:25 EDT Received: from EMS.MEDIA.MIT.EDU (EMS.MIT.EDU) by SAIL.Stanford.EDU with TCP; 29 Aug 88 21:04:40 PDT Received: by EMS.MEDIA.MIT.EDU (5.54/4.8) id AA03125; Tue, 30 Aug 88 00:03:57 EDT Date: Tue, 30 Aug 88 00:03:57 EDT From: smh@EMS.MEDIA.MIT.EDU (Steven Haflich) Message-Id: <8808300403.AA03125@EMS.MEDIA.MIT.EDU> To: common-lisp@sail.stanford.edu Subject: Re: hash tables and GC From: David L. Andre Subject: Re: hash tables and GC 0. Can such tables be implemented? Proof by existence: We have had such tables prototyped internally at Symbolics for a year or so, but have not had the resources to qualify them for release to customers. They can be quite efficient, and of course can significantly improve the efficiency of some kinds of programs. But perhaps this isn't exactly the right question for such a late date in the CL standards process. Rather: Can such tables be implemented with reasonable performance in *all* existing CL implementations, without breaking the GC strategies upon which they depend? I myself have no idea which way this question would fall, but unless it could confidently be answered in the affirmative I feel X3J13 would have to exclude these `weak-pointer' tables from the standard. The *real* problem is that it would be incumbent on the *proposer* to prove practicality. This would not be an easy proof.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 29 Aug 88 12:23:10 EDT Received: from JASPER.SCRC.Symbolics.COM ([128.81.41.58]) by SAIL.Stanford.EDU with TCP; 29 Aug 88 09:08:51 PDT Received: from KOYAANISQATSI.SCRC.Symbolics.COM by JASPER.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 213034; Mon 29-Aug-88 12:08:03 EDT Date: Mon, 29 Aug 88 12:06 EDT From: David L. Andre Subject: Re: hash tables and GC To: jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK cc: barmar@THINK.COM, common-lisp@sail.stanford.edu, DLA@JASPER.SCRC.Symbolics.COM In-Reply-To: <2583.8808272025@subnode.aiai.ed.ac.uk> Message-ID: <19880829160631.8.DLA@KOYAANISQATSI.SCRC.Symbolics.COM> Date: Sat, 27 Aug 88 21:25:34 BST From: Jeff Dalton ... It's probably best to have a concrete proposal, so I'll make one: Add a keyword parameter :TEMPORARY to MAKE-HASH-TABLE. If this argument is specified and not NIL, and if :TEST is #'EQ or #'EQL, entries in the table may be removed by the GC if the key (i.e., an object EQ or EQL to the key) is accessible only through the table(*). Entries in EQUAL tables are never so removed, nor are numbers in EQL tables. [Explanation: in these cases, it is generally possible to construct new objects that are respectively EQUAL or EQL to the key.] (*) Actually, I think this should be "accessible only through such tables", because something might be in more than one. Current practice: Pop11 has a similar capability as "temporary properties". (For this purpose, we can think of Pop as Lisp with a different syntax.) T has "weak sets". T also has OBJECT-HASH and OBJECT-UNHASH, which use "weak pointers". If (OBJECT-HASH object) => i, then (OBJECT-UNHASH i) => object if the object is still accessible and false if it is not. i is an integer. R2RS Scheme also has OBJECT-HASH and OBJECT-UNHASH, but they were not "essential" and have since been removed. Issues: 0. Can such tables be implemented? Proof by existence: We have had such tables prototyped internally at Symbolics for a year or so, but have not had the resources to qualify them for release to customers. They can be quite efficient, and of course can significantly improve the efficiency of some kinds of programs.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 27 Aug 88 22:33:12 EDT Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 27 Aug 88 19:12:12 PDT Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP id aa04124; 27 Aug 88 21:03 BST Date: Sat, 27 Aug 88 21:25:34 BST Message-Id: <2583.8808272025@subnode.aiai.ed.ac.uk> From: Jeff Dalton Subject: Re: hash tables and GC To: barmar@think.com Cc: common-lisp@sail.stanford.edu Now that mail on this topic has quieted down, I would like to try to summarize. My original message suggested that something like Pop11's "temporary properties" would be useful in Common Lisp, and said that temporary properties were similar to hash tables except that being in one did not prevent GC. This left imprecise such things as the meaning of "in". What I had in mind was this: Consider an EQ hash table. I can keep track of some property of objects by entering the objects as keys in a hash table. There is, however, an unfortunate side effect: the keys cannot be garbage collected until the table is. I suspect this greatly restricts the cases in which hash tables can be used. For example, one way to associate new information with an object would be to use CLOS to define a subclass of the object's class. The subclass would have one additional slot, and you could call CHANGE-CLASS to add that slot to a given object. In this case, the association would not affect the collectibility of the object. However, there may be times when you would rather not make the new information be part of the object (or when you can't because the object isn't of a kind that can have its class changed). It might seem that you could use a hash table. But since objects have indefinite lifetimes, the hash table has to stay around more or less forever, and then the objects have to stay around forever too. [Suppose you implement SYMBOL-PLIST using a hash table instead of a slot that's part of each symbol. This seems reasonable until you notice that then no symbol with a plist -- interned or not -- could ever be collected.] It's probably best to have a concrete proposal, so I'll make one: Add a keyword parameter :TEMPORARY to MAKE-HASH-TABLE. If this argument is specified and not NIL, and if :TEST is #'EQ or #'EQL, entries in the table may be removed by the GC if the key (i.e., an object EQ or EQL to the key) is accessible only through the table(*). Entries in EQUAL tables are never so removed, nor are numbers in EQL tables. [Explanation: in these cases, it is generally possible to construct new objects that are respectively EQUAL or EQL to the key.] (*) Actually, I think this should be "accessible only through such tables", because something might be in more than one. Current practice: Pop11 has a similar capability as "temporary properties". (For this purpose, we can think of Pop as Lisp with a different syntax.) T has "weak sets". T also has OBJECT-HASH and OBJECT-UNHASH, which use "weak pointers". If (OBJECT-HASH object) => i, then (OBJECT-UNHASH i) => object if the object is still accessible and false if it is not. i is an integer. R2RS Scheme also has OBJECT-HASH and OBJECT-UNHASH, but they were not "essential" and have since been removed. Issues: 0. Can such tables be implemented? It seems possible that some GC methods might have difficulty, but no one has mentioned anything that makes temporary entries impossible (or even impractical). Note that since CL does not require any GC at all, it probably cannot require that entries ever actually vanish (even if there is a GC). 1. Tables or sets? For some applications, all that's required is a "set" of objects that might be used (or reused) if they still exist. This is equivalent to a table where the value for a key is always T or NIL but is simpler and requires less storage. Moreover, temporary table entries can be implemented, given such "weak sets", by occasionally going through the table and removing entries whose keys are not still in the set. Minimalists may therefore prefer sets; pragmatists will tend to favor tables because they're more generally useful. 2. Hash tables or a new kind of table? There is some reason to say that adding a new feature to hash tables is not the best solution. In particular, there are problems with EQL and EQUAL tables. However, a new kind of table would most likely be so similar to a hash table that it might as well *be* a hash table. This dilemma could be considered an argument for sets instead of tables. Specific alternatives: * Instead of a keyword argument to MAKE-HASH-TABLE, have a separate constructor, MAKE-PROPERTY-TABLE, say. This implies that, instead of property-table being a subtype of hash-table, hash- and property- tables would both be subtypes of a type table. However, it is difficult to come up with a good name for these things, and I find this relationship between the two types of table less natural than adding a new dimension to hash tables. * Have a keyword argument to MAKE-ARRAY. [This was suggested by Christopher Eliot , who also suggested the keyword :GC-PROTECTING.] Membership in an array is, of course, by EQ, thus avoiding questions about EQL and EQUAL. Such arrays would be a kind of "weak set". I do not think such arrays would be very useful as-is because they would require a linear search for membership. 3. What about EQL and EQUAL hash tables? It does not make much sense to have temporary entries in EQUAL hash tables. Suppose an entry could be removed if there were no accessible objects EQUAL to the key. This is not a condition that it is practical to test. Nor is it sufficient: it is often possible to create new EQUAL objects, and so the entry should remain unless it is not possible to create new EQUAL objects. EQL tables share this problem, because it is always possible to create a new EQL number. Nonetheless, any entry that was not a number could be subject to collection as in EQ tables. Well, what about numbers in EQ tables? What about numbers that are represented directly rather than given storage of their own? Such problems already exist for EQ hash tables and are not (I think) made noticeably worse by the addition of temporary entries. (Suppose you have a number. How do you know *that number* is in an EQ hash table?) 4. Pointers to the value. In several messages, it was suggested (or assumed) that a table entry would not be removed unless both the key and its associated value could be collected. Against this notion, I would cite the following: (1) The key and value are not symmetric (hash tables are mappings from keys to values) and so it is reasonable to treat them differently. (2) Tables in which only the key need be inaccessible are more useful -- often the value will be something like T or NIL that will have a lifetime at least as long as the table's. 5. The implications of MAPHASH. > Date: Fri, 22 Jul 88 15:19 EDT > From: Barry Margolin > > Date: Fri, 22 Jul 88 18:23:53 BST > From: Jeff Dalton > > Even if you do a MAPHASH, there is no way for you to tell K should be > in the table (or even that it exists) unless you have independent > access to it. So, the possibility of MAPHASH would still allow K > and V to be removed. Of course, you could gather various statistics > with MAPHASH that would change if K were removed (e.g., the number of > keys would decrease), but I think that's OK. > > That's not quite correct. You could remember some property of the > key, or a value that you expect to find, without retaining independent > access to the key itself. [...] > > (defun gethash-by-pname (string table &optional default) > (maphash #'(lambda (key val) > (when (and (symbolp key) > (string-equal (symbol-name key) string)) > (return-from gethash-by-pname (values val t))) > table) > (values default nil)) > > The general point is that MAPHASH allows you to find entries that have > properties other than the one defined by the table's equality predicate. OK, but assuming some key K has pname S and you have no pointer to K other then the entry in the hash table, all your program can know is that some key has (well, had) pname S, not that K was in the table. To know that K (up to EQ) is in the table, you have to have a pointer to K. Jeff Dalton, JANET: J.Dalton@uk.ac.ed AI Applications Institute, ARPA: J.Dalton%uk.ac.ed@nss.cs.ucl.ac.uk Edinburgh University. UUCP: ...!ukc!ed.ac.uk!J.Dalton  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 27 Aug 88 22:29:31 EDT Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 27 Aug 88 19:16:35 PDT Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP id aa04194; 27 Aug 88 21:21 BST Date: Sat, 27 Aug 88 21:44:19 BST Message-Id: <2624.8808272044@subnode.aiai.ed.ac.uk> From: Jeff Dalton Subject: Standard total ordering To: common-lisp@sail.stanford.edu In Prolog, there is a standard total ordering for terms (i.e., all data). This is often quite useful. For example, it is faster to search an ordered list for membership than to search an unordered one. Note that the order is essentially arbitrary: what matters is that any terms may be consistently compared. (OK, what really matters is all the properties of a total order.) To what extent is it possible to do something like this for Lisp? In a Lisp where objects never move (or never change order relative to each other), the object's address could be used. This assumes we are ordering objects as distinguished by EQ. Is there some point in ordering for EQUAL objects instead? Jeff Dalton, JANET: J.Dalton@uk.ac.ed AI Applications Institute, ARPA: J.Dalton%uk.ac.ed@nss.cs.ucl.ac.uk Edinburgh University. UUCP: ...!ukc!ed.ac.uk!J.Dalton  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 26 Aug 88 11:14:35 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 26 Aug 88 07:59:16 PDT Return-Path: Received: from sauron.think.com by Think.COM; Fri, 26 Aug 88 10:55:26 EDT Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 26 Aug 88 10:57:31 EDT Date: Fri, 26 Aug 88 10:57 EDT From: Barry Margolin Subject: negative values for the :COUNT keyord argument To: David A. Moon Cc: Dave.Touretzky@cs.cmu.edu, common-lisp@sail.stanford.edu In-Reply-To: <19880826001409.0.MOON@EUPHRATES.SCRC.Symbolics.COM> Message-Id: <19880826145742.3.BARMAR@OCCAM.THINK.COM> Date: Thu, 25 Aug 88 20:14 EDT From: David A. Moon Date: Sun, 21 Aug 88 03:45:56 EDT From: Dave.Touretzky@B.GP.CS.CMU.EDU The June 3, 1987 version of KCL treats a negative value as how many spaces to tack on to the end of the string. It appears to handle lists correctly, but not vectors: > (remove #\a "Banana: :count -10) "Banana " Does this mean that in KCL (remove #\n "Banana: :count 3) returns a string that is one character too short? I.e. is it dead-reckoning the length of the returned string, instead of counting the number of items that actually will be removed? I assume you meant :COUNT 4 (since there are 3 a's in "banana"). In any case, it seems to do the right thing when :COUNT is positive. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 26 Aug 88 01:53:37 EDT Received: from DST.BOLTZ.CS.CMU.EDU by SAIL.Stanford.EDU with TCP; 25 Aug 88 22:42:17 PDT Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU; 26 Aug 88 01:39:52 EDT To: common-lisp@sail.stanford.edu Reply-To: Dave.Touretzky@cs.cmu.edu Subject: proposals regarding :COUNT keyword Date: Fri, 26 Aug 88 01:39:35 EDT Message-ID: <9440.588577175@DST.BOLTZ.CS.CMU.EDU> From: Dave.Touretzky@B.GP.CS.CMU.EDU I approve of KMP's revision of my original proposal, and appreciate the time he took to extend it and rewrite it in proper format. In answer to Moon's question: no, KCL isn't dead-reckoning the length of the list for positive values of :COUNT. It only messes up for negative values. Using the June 3, 1987 release of KCL I got the following behavior: (remove #\a "Banana" :count 3) ==> "Bnn" ;Correct. (remove #\a "Banana" :count 4) ==> "Bnn" ;Correct. (remove #\a "Banana" :count -3) ==> "Banana " ;It's padding! (remove #\a "Banana" :count -4) ==> "Bannana " ;More padding. -- Dave  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 25 Aug 88 20:27:06 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 25 Aug 88 17:15:27 PDT Received: from EUPHRATES.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 450862; Thu 25-Aug-88 20:14:00 EDT Date: Thu, 25 Aug 88 20:14 EDT From: David A. Moon Subject: negative values for the :COUNT keyord argument To: Dave.Touretzky@cs.cmu.edu cc: common-lisp@SAIL.STANFORD.EDU In-Reply-To: <5787.588152756@DST.BOLTZ.CS.CMU.EDU> Message-ID: <19880826001409.0.MOON@EUPHRATES.SCRC.Symbolics.COM> Date: Sun, 21 Aug 88 03:45:56 EDT From: Dave.Touretzky@B.GP.CS.CMU.EDU The June 3, 1987 version of KCL treats a negative value as how many spaces to tack on to the end of the string. It appears to handle lists correctly, but not vectors: > (remove #\a "Banana: :count -10) "Banana " Does this mean that in KCL (remove #\n "Banana: :count 3) returns a string that is one character too short? I.e. is it dead-reckoning the length of the returned string, instead of counting the number of items that actually will be removed?  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 25 Aug 88 17:13:20 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 25 Aug 88 13:56:16 PDT Received: from relay2.cs.net by RELAY.CS.NET id aa06487; 25 Aug 88 16:11 EDT Received: from draper.com by RELAY.CS.NET id aa06669; 25 Aug 88 15:59 EDT Date: Thu, 25 Aug 88 13:36 EDT From: "Steve Bacher (Batchman)" Subject: READ and "illegal" characters To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.edu",SEB1525 Taking the description of the CL reader at face value, I infer that an "illegal" character may occur in a symbol name if it is preceded by a backslash ("single escape"), but not if it occurs inside a pair of vertical bars ("multiple escape"). This seems strange. Is it merely an oversight, or is it intentional? This is a potentially significant problem, because it mandates that the printer must slashify "illegal" characters by preceding each one individually with a backslash rather than being able to just surround the entire name with vertical bars. For some implementations (i.e. mine), it is easier to embar the entire name, once it is determined that funny characters are present somewhere in the name. Is it intended that all characters not listed in the table as consituent, macro, etc. are "illegal"? Or might an implementation be able to treat them all as constituent characters?  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 24 Aug 88 15:34:47 EDT Received: from xenurus.gould.com by SAIL.Stanford.EDU with TCP; 24 Aug 88 12:15:11 PDT Received: from vger (vger.Urbana.Gould.COM) by xenurus.gould.com (5.54/) Date: Wed, 24 Aug 88 14:03:18 CDT From: notes%vger@xenurus.gould.com (DCS note file system) Received: by vger (5.54/) Message-Id: <8808241903.AA14769@vger> To: COMMON-LISP@sail.stanford.edu Due to a recent spat of trouble with our internet link we may have bounced some mail back to you. Please be advised we are alive and well and our link is up and running again. If you have turned us off in you mailing list please add us again. Thanks for your attention to this matter. Bruce Zimmerman bzimmerman@xenurus.gould.com OLD ADDR gswd.vms.arpa systems admin Urbana CSD, Gould inc. 1101 E. University ave. Urbana, Illinois. 217 384 8500  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 24 Aug 88 15:34:42 EDT Received: from xenurus.gould.com by SAIL.Stanford.EDU with TCP; 24 Aug 88 12:14:06 PDT Received: from vger (vger.Urbana.Gould.COM) by xenurus.gould.com (5.54/) Date: Wed, 24 Aug 88 14:03:18 CDT From: notes%vger@xenurus.gould.com (DCS note file system) Received: by vger (5.54/) Message-Id: <8808241903.AA14769@vger> To: COMMON-LISP@sail.stanford.edu Due to a recent spat of trouble with our internet link we may have bounced some mail back to you. Please be advised we are alive and well and our link is up and running again. If you have turned us off in you mailing list please add us again. Thanks for your attention to this matter. Bruce Zimmerman bzimmerman@xenurus.gould.com OLD ADDR gswd.vms.arpa systems admin Urbana CSD, Gould inc. 1101 E. University ave. Urbana, Illinois. 217 384 8500  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 22 Aug 88 13:48:53 EDT Received: from xenurus.gould.com by SAIL.Stanford.EDU with TCP; 22 Aug 88 10:34:02 PDT Received: from vger (vger.Urbana.Gould.COM) by xenurus.gould.com (5.54/) Date: Mon, 22 Aug 88 12:27:03 CDT From: zimmerm%vger@xenurus.gould.com (Bruce A. Zimmerman) Received: by vger (5.54/) Message-Id: <8808221727.AA09134@vger> To: AIList@sri.com, COMMON-LISP@sail.stanford.edu, INFO-AMIGA@red.rutgers.edu.arpa.NOTFOUND, NL-KR@cs.rochester.edu, NeWs-makers@brillig.umd.edu, bind-request@ucbarpa.berkeley.edu, gouldbugs@brl.arpa, laser-lovers@brillig.umd.edu, xport@athena.mid.edu.NOTFOUND Due to a recent spat of trouble with our internet link we may have bounced some mail back to you. Please be advised we are alive and well and our link is up and running again. If you have turned us off in you mailing list please add us again. Thanks for your attention to this matter. Bruce Zimmerman bzimmerman@xenurus.gould.com OLD ADDR gswd.vms systems admin Urbana CSD, Gould inc. 1101 E. University ave. Urbana, Illinois. 217 384 8500  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 21 Aug 88 15:49:23 EDT Received: from SEF1.SLISP.CS.CMU.EDU by SAIL.Stanford.EDU with TCP; 21 Aug 88 12:38:38 PDT Received: from SEF1.SLISP.CS.CMU.EDU by SEF1.SLISP.CS.CMU.EDU; 21 Aug 88 15:37:02 EDT To: Dave.Touretzky@cs.cmu.edu cc: common-lisp@sail.stanford.edu Subject: Re: negative values for the :COUNT keyord argument In-reply-to: Your message of Sun, 21 Aug 88 03:45:56 -0400. <5787.588152756@DST.BOLTZ.CS.CMU.EDU> Date: Sun, 21 Aug 88 15:36:55 EDT From: Scott.Fahlman@B.GP.CS.CMU.EDU I cannot find anything in the manual that restricts the range of the :COUNT keyword to non-negative integers, but I'm sure that's what the legal range would have been if we had been more systematic about specifying these things. As it is, a very strict reading of the language in CLtL probably would imply that a negative count is treated as "remove nothing", though some might argue that logically this should add a few random occurrences of what otherwise would have been removed. I think it's best in such cases to assume that "is an error" is the proper interpretation. If you feel that "is an error" is not the right choice here, a proposal to the X3J13 cleanup committee would be in order. -- Scott  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 21 Aug 88 03:59:53 EDT Received: from DST.BOLTZ.CS.CMU.EDU ([128.2.220.61]) by SAIL.Stanford.EDU with TCP; 21 Aug 88 00:47:34 PDT Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU; 21 Aug 88 03:46:04 EDT To: common-lisp@sail.stanford.edu Reply-To: Dave.Touretzky@cs.cmu.edu Subject: negative values for the :COUNT keyord argument Date: Sun, 21 Aug 88 03:45:56 EDT Message-ID: <5787.588152756@DST.BOLTZ.CS.CMU.EDU> From: Dave.Touretzky@B.GP.CS.CMU.EDU According to the way I read CLtL (pages 247 and 253), a negative value for the :COUNT keyword, e.g., to REMOVE, is legal and should behave the same as zero: (remove #\a "Banana" :count -10) ==> "Banana" Apparently, not everyone shares this view. CMU Common Lisp treats negative values like NIL: * (remove #\a "Banana" :count -10) "Bnn" The June 3, 1987 version of KCL treats a negative value as how many spaces to tack on to the end of the string. It appears to handle lists correctly, but not vectors: > (remove #\a "Banana: :count -10) "Banana " > (remove 'a '(b a n a n a) :count -10 (B A N A N A) > (remove 'a '#(b a n a n a) :count -2) (B A N A N A NIL NIL) I don't see anything in the manual to indicate that it "is an error" to supply negative values for the :COUNT keyword. Anybody want to rule on what the legal behavior is in this case? -- Dave  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 16 Aug 88 15:54:59 EDT Received: from cs.utah.edu by SAIL.Stanford.EDU with TCP; 16 Aug 88 12:39:03 PDT Received: by cs.utah.edu (5.54/utah-2.0-cs) id AA26479; Tue, 16 Aug 88 13:37:41 MDT Received: by cons.utah.edu (5.54/utah-2.0-leaf) id AA22021; Tue, 16 Aug 88 13:37:35 MDT Date: Tue, 16 Aug 88 13:37:35 MDT From: kessler%cons@cs.utah.edu (Robert R. Kessler) Message-Id: <8808161937.AA22021@cons.utah.edu> To: common-lisp@sail.stanford.edu, scheme@mc.lcs.mit.edu, fp@cs.yale.edu Cc: dswise@iuvax.cs.indiana.edu Subject: A Quick Note on the Last L&FP Conference One of the rumblings that I heard at the conference was that a number of people didn't receive their copies of the Advance Program mailing from ACM. Thus, it made it more difficult to register. If any of you are members of SIGPLAN, SIGART, or SIGACT and you did not receive a copy of the program some time in May, would you please send David Wise a message (dswise@iuvax.cs.indiana.edu). He is trying to collect actual data on the hits and misses of the mailing. Please send him your name, mailing address at which you receive ACM materials, and your ACM number if you have it. Thanks. Bob.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 11 Aug 88 19:48:22 EDT Received: from Xerox.COM by SAIL.Stanford.EDU with TCP; 11 Aug 88 14:44:23 PDT Received: from Semillon.ms by ArpaGateway.ms ; 11 AUG 88 14:38:15 PDT Date: Thu, 11 Aug 88 14:33 PDT From: Gregor.pa@Xerox.COM Subject: CLOS workshop To: Common-Lisp@Sail.Stanford.edu, CommonLoops.pa@Xerox.COM, X3J13@Sail.Stanford.edu Fcc: BD:>Gregor>mail>outgoing-mail-3.text.newest Message-ID: <19880811213330.2.GREGOR@PORTNOY.parc.xerox.com> Line-fold: no This is the second announcement of the CLOS workshop to be held at PARC October 3rd and 4th. This is a reminder to help us with our planning by letting us know soon if you are planning to attend. My apologies to people who receive multiple copies of this message. To clarify the position paper requirement, the workshop is not limited exclusively to those who have extensive experience writing CLOS code. Anyone planning CLOS implementations, extensions, environments or CLOS based application development is encouraged to attend. A position paper can simply be a description of the kinds of issues you feel should the CLOS community should address at the workshop. Workshop for CLOS Users and Implementors October 3rd and 4th Xerox PARC Palo Alto, California We have been excited by the extent to which CLOS is already being used, and the ways in which it is being extended. The purpose of this workshop is to provide an opportunity for the members of the CLOS community to get together and share their experience. To provide a good start for the interchange, we are requesting that participants supply a short position paper (1-3 pages) describing work related to CLOS. Some topics of interest are: Applications Programming Techniques Implementation Programming Environment Tools Extensions of CLOS Techniques for Converting to CLOS Meta Object Techniques and Theory Critiques We will try to support demonstrations or videotapes of applications, programming environments, implementations or other relevant systems. If you are planning to attend, please let us know by August 15th. This will help us with planning and allow us to arrange a discount rate at a local hotel. Position papers should reach us by September 9th so that we can organize a program and arrange for duplication of the papers. Position papers, notice to attend, and other correspondence should be sent to: Gregor Kiczales 3333 Coyote Hill Rd. Palo Alto, CA 94304 or by Internet mail to: Gregor.pa@Xerox.com -------  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 11 Aug 88 18:36:41 EDT Received: from Xerox.COM by SAIL.Stanford.EDU with TCP; 11 Aug 88 14:44:23 PDT Received: from Semillon.ms by ArpaGateway.ms ; 11 AUG 88 14:38:15 PDT Date: Thu, 11 Aug 88 14:33 PDT From: Gregor.pa@Xerox.COM Subject: CLOS workshop To: Common-Lisp@Sail.Stanford.edu, CommonLoops.pa@Xerox.COM, X3J13@Sail.Stanford.edu Fcc: BD:>Gregor>mail>outgoing-mail-3.text.newest Message-ID: <19880811213330.2.GREGOR@PORTNOY.parc.xerox.com> Line-fold: no This is the second announcement of the CLOS workshop to be held at PARC October 3rd and 4th. This is a reminder to help us with our planning by letting us know soon if you are planning to attend. My apologies to people who receive multiple copies of this message. To clarify the position paper requirement, the workshop is not limited exclusively to those who have extensive experience writing CLOS code. Anyone planning CLOS implementations, extensions, environments or CLOS based application development is encouraged to attend. A position paper can simply be a description of the kinds of issues you feel should the CLOS community should address at the workshop. Workshop for CLOS Users and Implementors October 3rd and 4th Xerox PARC Palo Alto, California We have been excited by the extent to which CLOS is already being used, and the ways in which it is being extended. The purpose of this workshop is to provide an opportunity for the members of the CLOS community to get together and share their experience. To provide a good start for the interchange, we are requesting that participants supply a short position paper (1-3 pages) describing work related to CLOS. Some topics of interest are: Applications Programming Techniques Implementation Programming Environment Tools Extensions of CLOS Techniques for Converting to CLOS Meta Object Techniques and Theory Critiques We will try to support demonstrations or videotapes of applications, programming environments, implementations or other relevant systems. If you are planning to attend, please let us know by August 15th. This will help us with planning and allow us to arrange a discount rate at a local hotel. Position papers should reach us by September 9th so that we can organize a program and arrange for duplication of the papers. Position papers, notice to attend, and other correspondence should be sent to: Gregor Kiczales 3333 Coyote Hill Rd. Palo Alto, CA 94304 or by Internet mail to: Gregor.pa@Xerox.com -------  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 9 Aug 88 13:01:29 EDT Received: from Boa-Constrictor.Stanford.EDU by SAIL.Stanford.EDU with TCP; 9 Aug 88 09:43:17 PDT Received: by Boa-Constrictor.Stanford.EDU.stanford.edu (4.0/SMI-DDN) id AA08892; Tue, 9 Aug 88 09:37:43 PDT Date: Tue, 9 Aug 88 09:37:43 PDT From: binford@Boa-Constrictor.stanford.edu (Tom Binford) Message-Id: <8808091637.AA08892@Boa-Constrictor.Stanford.EDU.stanford.edu> To: common-lisp@sail Subject: request Please include me on the mailing list. Tom Binford  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 6 Aug 88 06:04:03 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 6 Aug 88 02:44:31 PDT Received: from relay2.cs.net by RELAY.CS.NET id an13806; 6 Aug 88 5:16 EDT Received: from cs.umass.edu by RELAY.CS.NET id cq14721; 6 Aug 88 4:56 EDT Date: Fri, 5 Aug 88 11:01 EDT From: ELIOT@cs.umass.edu Subject: [Re: Hashables and GC] To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.EDU" From: IN%"goldman@vaxa.isi.EDU" 4-AUG-1988 17:57 To: ELIOT@cs.umass.EDU Subj: [Re: Hash Tables and GC] Not only does the GC have to prove that the reference count for BOTH key and VALUE is one, but the GC also has to prove that there are no other objects, x, such that: ( x KEY) There is no particular concern about whether other pointers to the VALUE exist; only pointers to members of the KEY's equivalence class. Agreed, but this has nothin gto do with my main point. Look at the problem not as one of GC, but as one of "when is it safe to remove an entry from a hash table?" [once it has been removed that may make the value garbage (reduce its reference count to 0)]. It is certainly SAFE to remove a set of entries Ei= [Ki Vi] if, once the Ei are removed, there is no way to construct a reference to an object equivalent to any Ki. Everything you say is precisely correct. It is a consequence of what you say that requires more emphasis. Consider computationally implementing your phrase "there is no way to construct a reference to an object equivalent to any Ki." For EQ hash tables this is somewhat straightforward because of: for-all x, y if (EQ x y) then (x = y) i.e. there is only one object EQ to any given object. Hence the size of the set of objects that can be constructed which are equivalent (EQ) to Ki is one. Now consider any hash table other than an EQ hash table. In this case the size (cardinality) of the set of objects that can be constructed which are equivalent (#'TEST) to Ki is (potentially) infinite, except when the Ki are some type of object for which EQUAL and EQ are the same (most atomic types) in which case it is still one. Now whatever unspecified process determines that it is safe to remove the keys and values must prove that there is no reference to any element of this potentially infinite set. This is clearly impractical except in some erratic and implementation specific special cases. What I am saying is that this feature is basically meaningless whenever the test is not (effectively) EQ. I don't think Common Lisp should have features which are never really going to work in any implementation. On the other hand, when restricted to EQ and EQL hash tables (excluding numbers/characters) I think this is a reasonable feature. It must be specified what happens when a Key is an interned but GCTWA symbol. In fact I think this feature could reasonably be driven down a level, into MAKE-ARRAY. Consider this proposal, upon which the kind of hash-tables you want could be implemented. PROPOSAL: Add to MAKE-ARRAY the keywords :GC-PROTECTING (default T) and :KEY (default #'IDENTITY). If GC-PROTECTING is NIL and (the KEY of) any element in the array cannot otherwise be referenced then the GC is allowed to replace the entire array element with NIL. ===== The :key argument makes it easy to construct hash tables of the type you want. The lack of a :test argument avoids the problems I am bothered by. Arrays are a more basic data structure than hash tables, so this might have more uses. (The :GC-PROTECTING keyword can be inherited by make-hash-table too.) Something like this was proposed while I was implementing the editor for NIL. It would allow the editor to cache data structures after buffers are killed or large regions deleted, without entirely preventing the GC from reclaiming the memory. This cacheing was particularly important because of a negative temporal displacement in the implementation of the garbage collector. Christopher Eliot University of Massachusetts at Amherst If there are references to KEYS from inside VALUES, some schemes may fail to remove entries that are safe to remove, but this is just like reference count GCers that fail to reclaim certain circular structures even though they are garbage. You lose space, but don't get incorrect results. Even EQ hash tables have problems, in any implementation with immediate representations for objects. For example the key 57236 (a fixnum) may not be interned and therefor there is no way to tell how many copies of it exist. Considering the paragraph of CLTL beginning on pg 77 and continuing to the top of pg 78, entries in EQ hash tables having integers or characters as the KEY can serve NO PORTABLE purpose except for usage through MAPHASH and/or HASH-TABLE-COUNT. Neil  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 4 Aug 88 18:11:56 EDT Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 4 Aug 88 14:55:31 PDT Posted-Date: Thu, 04 Aug 88 14:55:07 PDT Message-Id: <8808042155.AA03929@vaxa.isi.edu> Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51) id AA03929; Thu, 4 Aug 88 14:55:16 PDT To: ELIOT@cs.umass.edu From: goldman@vaxa.isi.edu Subject: [Re: Hash Tables and GC] Cc: common-lisp@sail.stanford.edu In-Reply-To: ELIOT@cs.umass.edu's message of 2795519880 Date: Thu, 04 Aug 88 14:55:07 PDT Sender: goldman@vaxa.isi.edu Not only does the GC have to prove that the reference count for BOTH key and VALUE is one, but the GC also has to prove that there are no other objects, x, such that: ( x KEY) There is no particular concern about whether other pointers to the VALUE exist; only pointers to members of the KEY's equivalence class. Look at the problem not as one of GC, but as one of "when is it safe to remove an entry from a hash table?" [once it has been removed that may make the value garbage (reduce its reference count to 0)]. It is certainly SAFE to remove a set of entries Ei= [Ki Vi] if, once the Ei are removed, there is no way to construct a reference to an object equivalent to any Ki. If there are references to KEYS from inside VALUES, some schemes may fail to remove entries that are safe to remove, but this is just like reference count GCers that fail to reclaim certain circular structures even though they are garbage. You lose space, but don't get incorrect results. Even EQ hash tables have problems, in any implementation with immediate representations for objects. For example the key 57236 (a fixnum) may not be interned and therefor there is no way to tell how many copies of it exist. Considering the paragraph of CLTL beginning on pg 77 and continuing to the top of pg 78, entries in EQ hash tables having integers or characters as the KEY can serve NO PORTABLE purpose except for usage through MAPHASH and/or HASH-TABLE-COUNT. Neil  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 4 Aug 88 04:08:36 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 4 Aug 88 00:55:45 PDT Received: from relay2.cs.net by RELAY.CS.NET id ac15973; 4 Aug 88 3:44 EDT Received: from cs.umass.edu by RELAY.CS.NET id aa27618; 4 Aug 88 3:26 EDT Date: Tue, 2 Aug 88 09:18 EDT From: ELIOT@cs.umass.edu Subject: Hash Tables and GC To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: in%"common-lisp@sail.stanford.EDU" I just got back from vacation and read the discussion of has tables. One point seems not to have been discussed - "Weak" links in hash tables would be almost impossible to implement except for EQ hash tables. Not only does the GC have to prove that the reference count for both key and value is one, but the GC also has to prove that there are no other objects, x, such that: ( x KEY) For EQ hash tables this condition is true, a priori, but for any other hash table it is not. Consider an EQL hash table with BIGNUM keys. A program could somehow effectively copy a bignum that is being used as a hash table key and then lose the original. For EQUAL hash tables it is even worse. Suppose (A . B) is a key. At any time a program might apply CONS to A and B to re-create the key. For example, suppose I am using a hash table to represent a graph. If A and B are nodes, then the graph-links can be implemented using a hash table like this: (defun BEFORE-P (A B) (gethash (cons a b) *link-table*)) Even EQ hash tables have problems, in any implementation with immediate representations for objects. For example the key 57236 (a fixnum) may not be interned and therefor there is no way to tell how many copies of it exist. Because of these problems I would suggest that this feature be restricted to EQ and EQL hash tables, and that numbers of all types should be considered accessible keys.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 3 Aug 88 19:57:24 EDT Received: from SPICE.CS.CMU.EDU by SAIL.Stanford.EDU with TCP; 3 Aug 88 16:44:43 PDT Received: from SPICE.CS.CMU.EDU by SPICE.CS.CMU.EDU; 3 Aug 88 19:40:43 EDT (Message inbox: 32) To: Common-Lisp@sail.stanford.edu Subject: Removal request Date: Wed, 03 Aug 88 19:40:35 EDT Message-ID: <7820.586654835@SPICE.CS.CMU.EDU> From: Rick.Busdiecker@SPICE.CS.CMU.EDU Please remove me from the Common-Lisp mailing list and send me a message confirming that you have done so. Thank you. Rick  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 22 Jul 88 20:31:23 EDT Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 22 Jul 88 17:17:42 PDT Posted-Date: Fri, 22 Jul 88 17:17:59 PDT Message-Id: <8807230018.AA26438@vaxa.isi.edu> Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51) id AA26438; Fri, 22 Jul 88 17:18:07 PDT To: COMMON-LISP@sail.stanford.edu From: goldman@vaxa.isi.edu Subject: Re: hash tables and GC Date: Fri, 22 Jul 88 17:17:59 PDT Sender: goldman@vaxa.isi.edu I may be missing something, but this doesn't look like very complex semantic issue to me. [Implementation is another matter.] The conditions under which a hash table key is accessible ONLY via maphash were, I believe correctly, spelled out in my earlier message. If those conditions are met, and the program in fact does not do maphash's on the array, AND (as I neglected to notice earlier) the program does NOT apply HASH-TABLE-COUNT to the array, then it is SAFE to remove the entry for the key from the hash table. [SAFE == the program cannot possibly tell that it has happened.] As was correctly pointed out, if hash table EQUALity is defined, then the safety conditions mentioned are no longer sufficient. In general, I think if a programmer authorizes (whether through declarations, or extra arguments to a function like MAKE-HASH-TABLE), some potentially unsafe optimization by the implementation (such as the garbage collector removing hash table entries), it is VERY desirable to identify sufficient conditions (such as no uses of maphash and no hash-table-count] under which the optimization is SAFE and declare that "it is an error", if the program requesting the optimization violates those conditions. Of course, these SUFFICIENT conditions may not be NECESSARY, so some programmers, like those at CORAL, may be astute enough to write programs that violate the sufficiency conditions but are nevertheless portable. More power to them. (Or maybe they can state weaker sufficiency conditions?) But if I were just presented with some procedural description of an optimization I can request and NO guidance on when it is safe (just a line that says USE WITH CAUTION), I would be loathe to try using it at all. Neil  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 22 Jul 88 15:46:55 EDT Received: from EDDIE.MIT.EDU by SAIL.Stanford.EDU with TCP; 22 Jul 88 12:32:44 PDT Received: by EDDIE.MIT.EDU with UUCP with smail2.5 with sendmail-5.45/4.7 id ; Fri, 22 Jul 88 15:31:46 EDT Received: by spt.entity.com (smail2.5); 22 Jul 88 14:41:34 EDT (Fri) To: jrose@Sun.COM Cc: common-lisp@sail.stanford.edu In-Reply-To: John Rose's message of Fri, 22 Jul 88 10:00:21 PDT <8807221700.AA04638@lukasiewicz.sun.com> Subject: hash tables and GC Message-Id: <8807221441.AA13220@spt.entity.com> Date: 22 Jul 88 14:41:34 EDT (Fri) From: gz@spt.entity.com (Gail Zacharias) I think you might have misunderstood. These things are a new data type, which doesn't replace any existing lisp data type. You can't get one without explicitly asking for it, which you presumably only do if you want the special behavior it provides. Given that, there's no problem with mapping over them. In fact doing so is necessary in the primary application we have for them (keeping track of marks in the editor). The issue about presenting them as hash tables is simply a question of whether they should be viewed as providing a mapping between pairs of objects like hash tables do, or simply storing a set of objects like lists do.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 22 Jul 88 15:39:11 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 12:21:04 PDT Return-Path: Received: from sauron.think.com by Think.COM; Fri, 22 Jul 88 15:21:57 EDT Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 22 Jul 88 15:18:20 EDT Date: Fri, 22 Jul 88 15:19 EDT From: Barry Margolin Subject: Re: hash tables and GC To: Jeff Dalton Cc: goldman@vaxa.isi.edu, jeff <@NSS.Cs.Ucl.AC.UK:jeff@aiai.edinburgh.ac.uk>, common-lisp@sail.stanford.edu In-Reply-To: <23883.8807221723@aiai.ed.ac.uk> Message-Id: <19880722191930.6.BARMAR@OCCAM.THINK.COM> Date: Fri, 22 Jul 88 18:23:53 BST From: Jeff Dalton Even if you do a MAPHASH, there is no way for you to tell K should be in the table (or even that it exists) unless you have independent access to it. So, the possibility of MAPHASH would still allow K and V to be removed. Of course, you could gather various statistics with MAPHASH that would change if K were removed (e.g., the number of keys would decrease), but I think that's OK. That's not quite correct. You could remember some property of the key, or a value that you expect to find, without retaining independent access to the key itself. For example, (defun reverse-gethash (value table) (let ((keys nil)) (maphash #'(lambda (key val) (when (eq val value) (push key keys))) table) keys)) In the above example I'm presuming that the GCing we are talking about would delete entries if there were no other references to the key, and ignores other references to the value. Here's something that doesn't depend on this: (defun gethash-by-pname (string table &optional default) (maphash #'(lambda (key val) (when (and (symbolp key) (string-equal (symbol-name key) string)) (return-from gethash-by-pname (values val t))) table) (values default nil)) The general point is that MAPHASH allows you to find entries that have properties other than the one defined by the table's equality predicate. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 22 Jul 88 15:06:43 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:50:01 PDT Return-Path: Received: from sauron.think.com by Think.COM; Fri, 22 Jul 88 14:50:49 EDT Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 22 Jul 88 14:47:11 EDT Date: Fri, 22 Jul 88 14:48 EDT From: Barry Margolin Subject: hash tables and GC To: John Rose Cc: gz@spt.entity.com, goldman@vaxa.isi.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk, common-lisp@sail.stanford.edu In-Reply-To: <8807221700.AA04638@lukasiewicz.sun.com> Message-Id: <19880722184820.1.BARMAR@OCCAM.THINK.COM> Date: Fri, 22 Jul 88 10:00:21 PDT From: jrose@sun.com (John Rose) Date: 22 Jul 88 10:13:34 EDT (Fri) From: gz@spt.entity.com (Gail Zacharias) This isn't much different from do-all-symbols in a lisp which does gctwa. I believe only the simplest symbols should be GC-ed; if a symbol is interned and has a nontrivial plist (say), GC-ing it will change the visible behavior of the program, since if a program re-creates it (via INTERN or READ), it will be missing its plist. That's the definition of GCTWA (which stands for GC Truly Worthless Atoms -- an atom is truly worthless if it is unbound, its function cell is unbound, its property list is NIL, and the only reference to it is in a package structure). Such a GC is transparent as long as you don't use DO-SYMBOLS or its variants and don't look at the second value of INTERN and FIND-SYMBOL. Similarly, if hash table keys are being used to store information, as well as merely access it, they shouldn't be GC-ed. Putting weak links to keys in hash tables would make the EQUAL semantics I proposed impossible, since an isomorphism test depends strongly on MAPHASH. (Or, before EQUAL is applied to test for isomorphism, normalize the two tables by performing a full GC! :@) Weak pointers are probably more useful than EQUAL isomorphism tests, but a reliable MAPHASH also seems indispensible. Sounds to me like weakly-linked keys want to be another option to MAKE-HASH-TABLE. He never said that this would be replacing hash tables; in fact, he said it probably would NOT use the hash table interfaces. A CL-compatible hash table can't drop elements into the bit-bucket during GC. This feature would have to be an extension that would be invoked explicitly when it is wanted. The definition of EQUAL on GC-able hash tables might have to be different from that for ordinary hash tables. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 22 Jul 88 14:53:46 EDT Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:34:31 PDT Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP id aa06246; 22 Jul 88 18:56 BST From: Jeff Dalton Date: Fri, 22 Jul 88 18:52:15 BST Message-Id: <23915.8807221752@aiai.ed.ac.uk> To: gz%spt.entity.com@NSS.Cs.Ucl.AC.UK, jrose@sun.com Subject: Re: hash tables and GC Cc: common-lisp@sail.stanford.edu, jeff <@NSS.Cs.Ucl.AC.UK:jeff@aiai.edinburgh.ac.uk> > Date: Fri, 22 Jul 88 10:00:21 PDT > From: John Rose > Sometimes that's "OK", sometimes not. For example, if a hash table is > being used as a relational database (with a primary key indexed by the > hash table), you probably don't want tuples therein to be GC-able. True. There are cases where the "independent reference" is in the user's head. Some value has been associated with a string key, say, and it should remain in case the user types it again. So, I'm not whether "weak retention" makes sense for EQUAL tables; but perhaps it does nonetheless. > Therefore, it's wise not to present them as hash tables. I don't mind calling them something else. > Similarly, if hash table keys are being used to store information, > as well as merely access it, they shouldn't be GC-ed. The question is whether you have any way of getting that key object. If nothing has a pointer to X, there's no way to know X exists much less that it's in some table. (I'm thinking EQ here.) > Putting weak links to keys in hash tables would make the EQUAL semantics > I proposed impossible, since an isomorphism test depends strongly > on MAPHASH. (Or, before EQUAL is applied to test for isomorphism, > normalize the two tables by performing a full GC! :@) I'm willing to have "EQUAL uncertainty" for "weak tables" if it's decided that EQUAL traverses such things at all. > Weak pointers are probably more useful than EQUAL isomorphism tests, > but a reliable MAPHASH also seems indispensible. Sounds to me > like weakly-linked keys want to be another option to > MAKE-HASH-TABLE. Just so. I did not want all tables to be that way, just for it to possible to have some that were. Cheers, Jeff Jeff Dalton, JANET: J.Dalton@uk.ac.ed AI Applications Institute, ARPA: J.Dalton%uk.ac.ed@nss.cs.ucl.ac.uk Edinburgh University. UUCP: ...!ukc!ed.ac.uk!J.Dalton  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 22 Jul 88 14:51:29 EDT Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:33:18 PDT Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP id aa06079; 22 Jul 88 18:27 BST From: Jeff Dalton Date: Fri, 22 Jul 88 18:23:53 BST Message-Id: <23883.8807221723@aiai.ed.ac.uk> To: goldman@vaxa.isi.edu, jeff <@NSS.Cs.Ucl.AC.UK:jeff@aiai.edinburgh.ac.uk> Subject: Re: hash tables and GC Cc: common-lisp@sail.stanford.edu > From: goldman@edu.isi.vaxa > Subject: hash tables and GC > Date: Thu, 21 Jul 88 09:33:27 PDT > > Apropos of hash tables, one feature of Pop(Log) that I sometimes want > > to have is "temporary properties". They are essentially hash tables > > such that being in them does not prevent being garbage collected. > I'm not sure just what you mean by "being in" a hash table. I have > commonly seen the following case -- is it what you have in mind? > > I have an EQ hash table H. My program will never apply the MAPHASH accessor > to H. Therefore, the fact that H is accessible to my program does NOT > imply that any of the keys or values are accessible. If the pair [K V] > is in the table, then if K is independently accessible, V is also > accessible. But if K is not independently accessible, it is garbage, and > so is V unless V is independently accessible. Yes, that's what I had in mind, except for one thing: Even if you do a MAPHASH, there is no way for you to tell K should be in the table (or even that it exists) unless you have independent access to it. So, the possibility of MAPHASH would still allow K and V to be removed. Of course, you could gather various statistics with MAPHASH that would change if K were removed (e.g., the number of keys would decrease), but I think that's OK. Indeed, T had something called "populations" (now called "weak sets") that did not prevent GC of their elements and that supported an operation call walk-population. They are somewhat less useful that what I have in mind, though, because all you can ask is whether something's in the population or not (i.e., whether it's a K -- there's no associated V). -- Jeff  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 22 Jul 88 13:23:36 EDT Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 10:00:50 PDT Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0) id AA04035; Fri, 22 Jul 88 09:58:03 PDT Received: from lukasiewicz.sun.com by snail.sun.com (4.0/SMI-4.0) id AA12710; Fri, 22 Jul 88 09:58:40 PDT Received: by lukasiewicz.sun.com (4.0/SMI-4.0) id AA04638; Fri, 22 Jul 88 10:00:21 PDT Date: Fri, 22 Jul 88 10:00:21 PDT From: jrose@Sun.COM (John Rose) Message-Id: <8807221700.AA04638@lukasiewicz.sun.com> To: gz@spt.entity.com Cc: goldman@vaxa.isi.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk, common-lisp@sail.stanford.edu In-Reply-To: Gail Zacharias's message of 22 Jul 88 10:13:34 EDT (Fri) <8807221013.AA12619@spt.entity.com> Subject: hash tables and GC Date: 22 Jul 88 10:13:34 EDT (Fri) From: gz@spt.entity.com (Gail Zacharias) Coral will have something like that in the next (major) release, although they probably will not be presented as hash tables. Letting you map over them is actually ok, although you have to be aware that just because you put something in one once doesn't mean it'll still be there when you map over it later. Sometimes that's "OK", sometimes not. For example, if a hash table is being used as a relational database (with a primary key indexed by the hash table), you probably don't want tuples therein to be GC-able. Therefore, it's wise not to present them as hash tables. This isn't much different from do-all-symbols in a lisp which does gctwa. I believe only the simplest symbols should be GC-ed; if a symbol is interned and has a nontrivial plist (say), GC-ing it will change the visible behavior of the program, since if a program re-creates it (via INTERN or READ), it will be missing its plist. Similarly, if hash table keys are being used to store information, as well as merely access it, they shouldn't be GC-ed. Putting weak links to keys in hash tables would make the EQUAL semantics I proposed impossible, since an isomorphism test depends strongly on MAPHASH. (Or, before EQUAL is applied to test for isomorphism, normalize the two tables by performing a full GC! :@) Weak pointers are probably more useful than EQUAL isomorphism tests, but a reliable MAPHASH also seems indispensible. Sounds to me like weakly-linked keys want to be another option to MAKE-HASH-TABLE. -- John  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 22 Jul 88 10:49:59 EDT Received: from EDDIE.MIT.EDU by SAIL.Stanford.EDU with TCP; 22 Jul 88 07:32:17 PDT Received: by EDDIE.MIT.EDU with UUCP with smail2.5 with sendmail-5.45/4.7 id ; Fri, 22 Jul 88 10:30:26 EDT Received: by spt.entity.com (smail2.5); 22 Jul 88 10:13:34 EDT (Fri) To: goldman@vaxa.isi.edu Cc: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk, common-lisp@sail.stanford.edu In-Reply-To: goldman@vaxa.isi.edu's message of Thu, 21 Jul 88 09:33:27 PDT <8807211633.AA27307@vaxa.isi.edu> Subject: hash tables and GC Message-Id: <8807221013.AA12619@spt.entity.com> Date: 22 Jul 88 10:13:34 EDT (Fri) From: gz@spt.entity.com (Gail Zacharias) Coral will have something like that in the next (major) release, although they probably will not be presented as hash tables. Letting you map over them is actually ok, although you have to be aware that just because you put something in one once doesn't mean it'll still be there when you map over it later. This isn't much different from do-all-symbols in a lisp which does gctwa.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 22 Jul 88 08:00:53 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 22 Jul 88 04:47:21 PDT Received: by labrea.stanford.edu; Fri, 22 Jul 88 04:46:05 PDT Received: from bhopal.lucid.com by edsel id AA06715g; Fri, 22 Jul 88 04:41:55 PDT Received: by bhopal id AA04252g; Fri, 22 Jul 88 04:42:47 PDT Date: Fri, 22 Jul 88 04:42:47 PDT From: Jon L White Message-Id: <8807221142.AA04252@bhopal.lucid.com> To: darrelj@sm.unisys.com Cc: goldman@vaxa.isi.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk, common-lisp@sail.stanford.edu In-Reply-To: darrelj@sm.unisys.com's message of 21 Jul 88 11:36 PDT (Thursday) <8807211842.AA02583@rdcf.sm.unisys.com> Subject: hash tables and GC re: Interlisp-10 does this for all hash tables, although certain cases of keys involving "permanent" objects like SMALLP numbers are never automatically removed. It also looks like pretty complicated code to implement it. At first blush, it seems like it would be much harder to do in some incremental GC scheme as it requires scanning all such hash tables before recycling objects they contain. Interlisp-D has one case where such "weak links" were removed (or, at least so was the plan -- I'm not sure if it was ever implemented). The clever trick was that the incremental Reference Counting garbage collector could be counted upon to tell you a likely candidate: if an entry for the key in a hash-table has refcnt of 1, then (modulo stack reconcilation) it is removeable; because the count of 1 means that that table entry points to it and no one else does. A "background" process could go around scavenging over hash-tables, removing inaccessible entries when it found them (there is no particular need to remove them "instantly", or even at normal GC time). But on a broader view, yes, I think Jeff's request is not only reasonable but very desirable. And I think your assesssment of the problems is correct -- it will be rather tedious non-portable coding to make it work. At one time, a bunch of us working of Vax/NIL devised a scheme for such tables [partly to implement the backwards-compatiblity feature of MacLisp called MAKNUM]; it required a "hook" in the Stop-and-Copy garbage collector. But then, the GC for Vax/NIL never got done. The best-laid plans of mice and men go oftimes a-garbage-collecting. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 21 Jul 88 14:49:17 EDT Received: from rdcf.sm.unisys.com (SM.UNISYS.COM) by SAIL.Stanford.EDU with TCP; 21 Jul 88 11:37:57 PDT Received: by rdcf.sm.unisys.com (sdcrdcf) (5.51/Domain/jpb/2.9.1.4) id AA02583; Thu, 21 Jul 88 11:42:27 PDT Message-Id: <8807211842.AA02583@rdcf.sm.unisys.com> Received: from XAVIER by sdcrdcf with PUP; Thu, 21 Jul 88 11:42 PDT From: darrelj@sm.unisys.com Date: 21 Jul 88 11:36 PDT (Thursday) Subject: Re: hash tables and GC In-Reply-To: goldman@vaxa.isi.edu's message of Thu, 21 Jul 88 09:33:27 PDT To: goldman@vaxa.isi.edu Cc: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk, common-lisp@sail.stanford.edu To: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk From: goldman@vaxa.isi.edu Subject: hash tables and GC Cc: common-lisp@sail.stanford.edu Date: Thu, 21 Jul 88 09:33:27 PDT Sender: goldman@vaxa.isi.edu Do any implementations have "non-mappable" hash tables and a Garbage Collector that takes this into account? Neil Interlisp-10 does this for all hash tables, although certain cases of keys involving "permanent" objects like SMALLP numbers are never automatically removed. It also looks like pretty complicated code to implement it. At first blush, it seems like it would be much harder to do in some incremental GC scheme as it requires scanning all such hash tables before recycling objects they contain.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 21 Jul 88 12:48:18 EDT Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 21 Jul 88 09:33:45 PDT Posted-Date: Thu, 21 Jul 88 09:33:27 PDT Message-Id: <8807211633.AA27307@vaxa.isi.edu> Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51) id AA27307; Thu, 21 Jul 88 09:33:30 PDT To: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk From: goldman@vaxa.isi.edu Subject: hash tables and GC Cc: common-lisp@sail.stanford.edu Date: Thu, 21 Jul 88 09:33:27 PDT Sender: goldman@vaxa.isi.edu Apropos of hash tables, one feature of Pop(Log) that I sometimes want to have is "temporary properties". They are essentially hash tables such that being in them does not prevent being garbage collected. An object might have a property (in this table) and nonetheless be collectable. Is there some problem with such tables that makes them not a good idea? They certainly seem to be something users can't write for themselves. I'm not sure just what you mean by "being in" a hash table. I have commonly seen the following case -- is it what you have in mind? I have an EQ hash table H. My program will never apply the MAPHASH accessor to H. Therefore, the fact that H is accessible to my program does NOT imply that any of the keys or values are accessible. If the pair [K V] is in the table, then if K is independently accessible, V is also accessible. But if K is not independently accessible, it is garbage, and so is V unless V is independently accessible. Do any implementations have "non-mappable" hash tables and a Garbage Collector that takes this into account? [The condition that the hash table equivalence be EQ was only stated to make the explanation simple to follow intuitively. If we think of the key K as an exemplar of some equivalence class, and regard the phrase "K is independently accessible" as meaning "some element of the equivalence class containing K is independently accessible", then the rationale holds regardless of the table's equivalence predicate, and can, in fact, be conservatively followed for EQL and EQUAL hash tables. Neil  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 20 Jul 88 14:00:31 EDT Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 20 Jul 88 10:48:11 PDT Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP id aa06458; 20 Jul 88 18:41 BST From: Jeff Dalton Date: Wed, 20 Jul 88 18:36:30 BST Message-Id: <8470.8807201736@subnode.aiai.ed.ac.uk> To: Greenwald@scrc-stony-brook.arpa, jonl <@labrea.stanford.edu:jonl@edsel.uucp> Subject: hash tables Cc: common-lisp@sail.stanford.edu, goldman@vaxa.isi.edu, jrose@sun.com > Date: Tue, 19 Jul 88 00:05:31 PDT > From: Jon L White > In fact, I have heard some C programmers praise Common Lisp for it's inclusion > of hash-tables. They complain and complain about having to reinvent the > wheel (hash-tables) over and over again. Apropos of hash tables, one feature of Pop(Log) that I sometimes want to have is "temporary properties". They are essentially hash tables such that being in them does not prevent being garbage collected. An object might have a property (in this table) and nonetheless be collectable. Is there some problem with such tables that makes them not a good idea? They certainly seem to be something users can't write for themselves. -- Jeff  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 20 Jul 88 12:07:41 EDT Received: from cs.utah.edu by SAIL.Stanford.EDU with TCP; 20 Jul 88 08:52:57 PDT Received: by cs.utah.edu (5.54/utah-2.0-cs) id AA17258; Wed, 20 Jul 88 09:50:39 MDT Received: by cons.utah.edu (5.54/utah-2.0-leaf) id AA03528; Wed, 20 Jul 88 09:50:19 MDT Date: Wed, 20 Jul 88 09:50:19 MDT From: kessler%cons@cs.utah.edu (Robert R. Kessler) Message-Id: <8807201550.AA03528@cons.utah.edu> To: common-lisp@sail.stanford.edu, scheme@mc.lcs.mit.edu, fp@cs.yale.edu Cc: chaillou@inria.inria.fr, cork@rice.edu, kessler%cons@cs.utah.edu Subject: L&FP Transportation For those of you arriving at the Salt Lake International Airport and wanting transportation to Snowbird, here is the information. Canyon Transportation has van service between the airport and Snowbird. The charge is $10 per person, unless you are the only person in the van, in which case the charge will be $20. They are planning to be at the airport between 10 am and 10 pm on Saturday the 23rd and the same hours on Sunday the 24th. Look for ground transportation after you claim your baggage and you should find them. They may be stationed inside the airport near the baggage claim, or outside at the curb. If you need to make special arrangements with them, particularily, outside of the 10am to 10pm hours, you may call them at the following number: (800)255-1841 You can also take a taxi, but that will cost around $40. Bob.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 20 Jul 88 04:57:28 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 20 Jul 88 01:43:28 PDT Received: by labrea.stanford.edu; Wed, 20 Jul 88 01:42:20 PDT Received: from bhopal.lucid.com by edsel id AA04700g; Wed, 20 Jul 88 01:35:52 PDT Received: by bhopal id AA02976g; Wed, 20 Jul 88 01:36:34 PDT Date: Wed, 20 Jul 88 01:36:34 PDT From: Jon L White Message-Id: <8807200836.AA02976@bhopal.lucid.com> To: Greenwald@stony-brook.scrc.symbolics.com, Moon@stony-brook.scrc.symbolics.com Cc: common-lisp@sail.stanford.edu In-Reply-To: Michael Greenwald's message of Tue, 19 Jul 88 17:33 EDT <19880719213338.0.GREENWALD@SWALLOW.SCRC.Symbolics.COM> Subject: Contagion on numerical comparisons re: [Jonl: the CL numeric comparisons should be transitive functions.] [Moon: this violates CLtL; shouldn't we have a cleanup issue for it?] I'll point out that in March 1987 JonL proposed the same thing, and Moon suggested that the proposal be written up and submitted to the X3J13 committee. From this exchange can I conclude that nothing *was* submitted? I'd guess that this suggestion is probably futile unless someone actively volunteers to write up, and submit, the new floating point contagion rule for comparisons. This "proposal" has been on my list of items "to be submitted". A hardcopy of this list was passed-out to cl-cleanup committee members who were actually present at the March 1988 meeting in Palo Alto, and commentary was invited. The relevant paragraph was: ``Specify that the numerical comparison functions (CLtL, p196) are transitive operations; thus the phrase "required coercions" can't be interpreted to mean "float contagion" (probably "rational contagion" is needed for comparisons, whereas "float contagion" is needed for the other operations). Although this contradicts the statement on p194, third paragraph, but the mathematics is much better.'' Only a handful of persons actually gave me feedback on priorities for this list, and the numeric-comparison transitivity issue didn't rate very high in anyone's book. Note that your(plural) examples were all malice-aforethought cases on numerical-equality; but numeric inequalities are involved also, and are probably even more important [because doing an EQL comparison between a float and a rational that can't be exactly represented by a float is probably a conceptual bug; but doing a < or <= comparison is still meaningful, modulo "fence-posts"]. For a world with 24-bit mantissas (e.g., ieee "single-floats") float-contagion on comparisons will lead to the following absurdity: (setq i #x2000000) ==> 33554432 (setq fx (float i)) ==> 3.3554432E7 Now (<= fx (+ i 1)) ==> T (< (+ i 1) (+ i 2)) ==> T (<= (+ i 2) fx) ==> T which is summarized by: fx <= i+1 < i+2 <= fx Or, put bluntly, fx < fx, an absurdity. Maybe it will be impossible to get complete consensus on this issue, as some dyed-in-the-wool FORTRANer's may insist that compatibililty with the 1950's behaviour is preferable to transitivity. But at Lucid, some time ago, we finally decided to bite the bullet, knowing that the fix will hardly break any reasonable programs, and not fixing it will break some obscure programs. I plan to submit a select subset of my "to be submitted" list as proposals to the x3j13 cleanup committe sometime well before mid-September. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 20 Jul 88 04:25:13 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 20 Jul 88 01:07:45 PDT Received: by labrea.stanford.edu; Wed, 20 Jul 88 01:06:40 PDT Received: from bhopal.lucid.com by edsel id AA04469g; Wed, 20 Jul 88 00:54:51 PDT Received: by bhopal id AA02880g; Wed, 20 Jul 88 00:55:34 PDT Date: Wed, 20 Jul 88 00:55:34 PDT From: Jon L White Message-Id: <8807200755.AA02880@bhopal.lucid.com> To: jrose@sun.com Cc: goldman@vaxa.isi.edu, common-lisp@sail.stanford.edu In-Reply-To: John Rose's message of Tue, 19 Jul 88 13:30:51 PDT <8807192030.AA23049@lukasiewicz.sun.com> Subject: EQUAL, and hash tables, and value/object distinctions re: My contribution, I hope, is to point out that hash tables do in fact have components quite analogous to array or structure components, that these components are the hash table's values, accessed using its keys, and finally that this implies certain things about the way hash table isomorphism is computed. Ah, I see your point now. Put this way, it looks much different. Thanks. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 19 Jul 88 17:49:58 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 19 Jul 88 14:37:48 PDT Received: from SWALLOW.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 435438; Tue 19-Jul-88 17:33:55 EDT Date: Tue, 19 Jul 88 17:33 EDT From: Michael Greenwald Subject: EQUAL, and hash tables, and value/object distinctions To: Moon@STONY-BROOK.SCRC.Symbolics.COM, edsel!jonl@labrea.stanford.edu cc: Greenwald@STONY-BROOK.SCRC.Symbolics.COM, jrose@sun.com, goldman@vaxa.isi.edu, common-lisp@SAIL.STANFORD.EDU In-Reply-To: <19880719152249.9.MOON@EUPHRATES.SCRC.Symbolics.COM> Message-ID: <19880719213338.0.GREENWALD@SWALLOW.SCRC.Symbolics.COM> Date: Tue, 19 Jul 88 11:22 EDT From: David A. Moon Date: Tue, 19 Jul 88 00:05:31 PDT From: Jon L White ....numerical equality and inequalities are not information losing, and should in fact be transitive relations. About one year ago, I pointed out this difficulty to Guy Steele with some well- chosen examples; and he was quite shocked -- indeed it was his intention that "=" be a true equivalence predicate. I agree that = should be transitive even when floating-point numbers are involved. I.e. (= (/ 10.0 single-float-epsilon) (1+ (floor (/ 10.0 single-float-epsilon)))) should be NIL, since (= (/ 10.0 single-float-epsilon) (floor (/ 10.0 single-float-epsilon))) is certainly T and (= (floor (/ 10.0 single-float-epsilon)) (1+ (floor (/ 10.0 single-float-epsilon)))) is certainly NIL. To understand this example better, it helps to realize that (= (/ 10.0 single-float-epsilon) (+ (/ 10.0 single-float-epsilon) 1.0)) is true in all implementations. Without using the epsilon case: (= 1234d20 (FLOOR 1234d20)) => T (= 1234d20 (1+ (FLOOR 1234d20))) => T but obviously (= (FLOOR 1234d20) (1+ (FLOOR 1234d20))) => NIL Or, one of my favorite screw cases along these lines: (LET ((A 1234d10)) (<= A (1+ (FLOOR A)) (COERCE A 'SINGLE-FLOAT) (FLOOR A))) Since CLtL p.194 expressly forbids this, requiring the first form above to return T, shouldn't somebody submit an X3J13 Cleanup subcommittee proposal before it's too late? I'll point out that in March 1987 JonL proposed the same thing, and Moon suggested that the proposal be written up and submitted to the X3J13 committee. From this exchange can I conclude that nothing *was* submitted? I'd guess that this suggestion is probably futile unless someone actively volunteers to write up, and submit, the new floating point contagion rule for comparisons. Lucid's 3.0 release performs "appropriate contagion" in the case of numerical comparisons, in order to preserve transitivity. I'm a little surprised that Lucid would change their implementation incompatibly with both CLtL and previous Lucid implementations without first getting some concensus that the current definition of Common Lisp is wrong and in fact will change. I know Symbolics specifically decided not to "fix this bug" unilaterally when we noticed it some time ago, considering that compatibility was more important. Chacun a son gout.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 19 Jul 88 16:44:09 EDT Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 19 Jul 88 13:31:11 PDT Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0) id AA18904; Tue, 19 Jul 88 13:28:45 PDT Received: from lukasiewicz.sun.com by snail.sun.com (4.0/SMI-4.0) id AA29153; Tue, 19 Jul 88 13:29:10 PDT Received: by lukasiewicz.sun.com (4.0/SMI-4.0) id AA23049; Tue, 19 Jul 88 13:30:51 PDT Date: Tue, 19 Jul 88 13:30:51 PDT From: jrose@Sun.COM (John Rose) Message-Id: <8807192030.AA23049@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 Mon, 18 Jul 88 23:38:35 PDT <8807190638.AA05670@bhopal.lucid.com> Subject: EQUAL, and hash tables, and value/object distinctions Date: Mon, 18 Jul 88 23:38:35 PDT From: Jon L White [have been out of town for some time, and under other time constraints, so apologies in advance for replying to "old mail"] re: 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. That's a lot of very strong words for what must be considered an opinion on how EQUAL could be extended to the case of hash-tables. The difficulty is that EQUAL has, until now, been a very low-level simple-minded component-wise equivalence test. What you are proposing is something that looks much more grandiose than even EQUALP. I think you missed my point. Let me try saying it with fewer strong words. EQUAL currently recurs on the components of CONS cells, and a few other types. There are proposals in the air to add to the set of types whose components EQUAL compares recursively. These types include arrays and structures. I personally find these proposals rather aggressive or "grandiose", as perhaps you do too. However, __if__ it makes overall sense to treat the components of arrays and structures this way, I believe it also makes sense to treat hash table components in the same way, using a suitable definition of "component". My contribution, I hope, is to point out that hash tables do in fact have components quite analogous to array or structure components, that these components are the hash table's values, accessed using its keys, and finally that this implies certain things about the way hash table isomorphism is computed. -- John  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 19 Jul 88 16:10:32 EDT Received: from cayuga.cs.rochester.edu (CS.ROCHESTER.EDU) by SAIL.Stanford.EDU with TCP; 19 Jul 88 12:56:32 PDT Received: by cayuga.cs.rochester.edu (5.52/j) id AA07817; Tue, 19 Jul 88 15:55:40 EDT Received: from loopback by lesath.cs.rochester.edu (3.2/j) id AA03377; Tue, 19 Jul 88 15:55:30 EDT Message-Id: <8807191955.AA03377@lesath.cs.rochester.edu> To: common-lisp@sail.stanford.edu Subject: Question about readtable null arguments Date: Tue, 19 Jul 88 15:55:20 -0400 From: quiroz@cs.rochester.edu I just noticed a certain ambiguity (What else is new? :-) in CLtL that I would like to get clarified. In 22.1.5, p 361, the definitions of `copy-readtable' and of `set-syntax-from-char' establish a convention that a NIL readtable argument that is used as source for a copy, refers to the "standard Common Lisp readtable". (This is slightly irregular, as in other contexts an omitted argument is the same as a null argument, but I digress.) No such guarantee is given for other readtable arguments that happen to be simultaneously optional and from-. There are (at least) two other functions where this convention would be useful: get-[dispatch-]macro-character both take an optional readtable from which they copy some information. Both default to *readtable*. But nothing is said about explicitly giving them NIL. In spite of not giving an explicit guarantee (OR DID I MISS IT?), Steele seems to believe that the same convention applies. In p 378, he uses (get-macro-character #\) nil) with the comment "...Giving } the same definition as the standard definition of the character ) has...", which makes me think he expects the "NIL means standard" convention to apply. I checked three implementations. Two of them (Symbolics and Xerox) seem to take the benign interpretation, making Steele's example of p 378 work. KCl, on the other hand, sent me to the debugger: >(get-macro-character #\) nil) Error: NIL is not of type READTABLE. Error signalled by GET-MACRO-CHARACTER. Broken at GET-MACRO-CHARACTER. Type :H for Help. >> So, I'd appreciate hearing from the Lisp community, especially from implementors: 1- Is there in CLtL an explicit statement of the convention that optional readtable arguments, in from- usage, supplied with an explicit NIL, should mean the standard readtable? 2- If not, is it nonetheless common to take that interpretation? In your version of Common Lisp, (get-macro-character #\) nil) 2.a. Produces the macro function (perhaps nil) associated with ) in the standard readtable. 2.b. Errors out. 2.c. Does something else (like checking the current readtable). 3- If your implementation takes the benign approach, what standard functions have been implemented to show this behavior? (I guess the get-... ones are the only ones, I'd like to know if I missed another.) I will summarize the responses. Thanks, Cesar Quiroz PS. I have patches (trivial) to make KCl behave nicely to the example in p. 378. If you are interested, I can send them to you, or post them if there is any interest.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 19 Jul 88 12:27:56 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 19 Jul 88 08:25:59 PDT Received: from EUPHRATES.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 435124; Tue 19-Jul-88 11:23:22 EDT Date: Tue, 19 Jul 88 11:22 EDT From: David A. Moon Subject: EQUAL, and hash tables, and value/object distinctions To: Jon L White cc: Greenwald@STONY-BROOK.SCRC.Symbolics.COM, jrose@sun.com, goldman@vaxa.isi.edu, common-lisp@SAIL.STANFORD.EDU In-Reply-To: <8807190705.AA05728@bhopal.lucid.com> Message-ID: <19880719152249.9.MOON@EUPHRATES.SCRC.Symbolics.COM> Date: Tue, 19 Jul 88 00:05:31 PDT From: Jon L White ....numerical equality and inequalities are not information losing, and should in fact be transitive relations. About one year ago, I pointed out this difficulty to Guy Steele with some well- chosen examples; and he was quite shocked -- indeed it was his intention that "=" be a true equivalence predicate. I agree that = should be transitive even when floating-point numbers are involved. I.e. (= (/ 10.0 single-float-epsilon) (1+ (floor (/ 10.0 single-float-epsilon)))) should be NIL, since (= (/ 10.0 single-float-epsilon) (floor (/ 10.0 single-float-epsilon))) is certainly T and (= (floor (/ 10.0 single-float-epsilon)) (1+ (floor (/ 10.0 single-float-epsilon)))) is certainly NIL. To understand this example better, it helps to realize that (= (/ 10.0 single-float-epsilon) (+ (/ 10.0 single-float-epsilon) 1.0)) is true in all implementations. Since CLtL p.194 expressly forbids this, requiring the first form above to return T, shouldn't somebody submit an X3J13 Cleanup subcommittee proposal before it's too late? Lucid's 3.0 release performs "appropriate contagion" in the case of numerical comparisons, in order to preserve transitivity. I'm a little surprised that Lucid would change their implementation incompatibly with both CLtL and previous Lucid implementations without first getting some concensus that the current definition of Common Lisp is wrong and in fact will change. I know Symbolics specifically decided not to "fix this bug" unilaterally when we noticed it some time ago, considering that compatibility was more important. Chacun a son gout.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 19 Jul 88 04:21:14 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 19 Jul 88 01:01:54 PDT Received: by labrea.stanford.edu; Tue, 19 Jul 88 01:00:50 PDT Received: from bhopal.lucid.com by edsel id AA20315g; Mon, 18 Jul 88 23:37:58 PDT Received: by bhopal id AA05670g; Mon, 18 Jul 88 23:38:35 PDT Date: Mon, 18 Jul 88 23:38:35 PDT From: Jon L White Message-Id: <8807190638.AA05670@bhopal.lucid.com> To: jrose@sun.com Cc: goldman@vaxa.isi.edu, common-lisp@sail.stanford.edu In-Reply-To: John Rose's message of Thu, 30 Jun 88 12:40:54 PDT <8806301940.AA01804@lukasiewicz.sun.com> Subject: EQUAL, and hash tables, and value/object distinctions [have been out of town for some time, and under other time constraints, so apologies in advance for replying to "old mail"] re: 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. That's a lot of very strong words for what must be considered an opinion on how EQUAL could be extended to the case of hash-tables. The difficulty is that EQUAL has, until now, been a very low-level simple-minded component-wise equivalence test. What you are proposing is something that looks much more grandiose than even EQUALP. While I might see some partial utility in these relations that equated more things (e.g., 3/2 and 1.5 are EQUALP), and those that refined EQUAL (e.g., "graph-isomorphism" equates fewer things than EQUAL), I don't see why EQUAL should bear the burden of being anything more than a "simple-minded component-wise equivalence test." re: Date: Wed, 29 Jun 88 18:57:09 PDT From: Jon L White . . . 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 There is no :HASH-FN argument to make-hash-table in CL; and I presume you mean the :TEST argument when you say :EQUALITY-PREDICATE? The last time on this mailing list that I suggested having user-suppled equivalence predicates for hash-tables, there was: (1) a lot of argumentation over what to call the replacement for SXHASH [a ":test" argument isn't enough, if you give an equivalence relation for which the system-supplied SXHASH function isn't "good enough" in the sense I spoke about before] (2) comments from Symbolics folks that they had discussed these ideas internally, and rejected them because of the potential for confusion over the SXHASH correlation issue. You might try asking Dave Moon what the issues were, if you are really interested. It may be that the close link between methods on EQUAL and methods on SXHASH is one reason that CLOS doesn't say much about EQUAL. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 19 Jul 88 04:21:10 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 19 Jul 88 01:02:39 PDT Received: by labrea.stanford.edu; Tue, 19 Jul 88 01:01:35 PDT Received: from bhopal.lucid.com by edsel id AA20478g; Tue, 19 Jul 88 00:04:54 PDT Received: by bhopal id AA05728g; Tue, 19 Jul 88 00:05:31 PDT Date: Tue, 19 Jul 88 00:05:31 PDT From: Jon L White Message-Id: <8807190705.AA05728@bhopal.lucid.com> To: Greenwald@stony-brook.scrc.symbolics.com Cc: jrose@sun.com, 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 re: 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. You must be referring to the bug in CLtL, p194: "When rational and floating-point numbers are compared or combined by a numerical function, the rule of floating-point contagion is followed: ..." I believe that this should read: "When rational and floating-point numbers are combined by a numerical function, the rule of floating-point contagion is followed: ..." Float conversion is an inherently information-losing process; this is, of course, fine for situations where there will most likely be information loss anyway ,due to rounding and/or truncation [such as in "combination by a numerical function"]. But numerical equality and inequalities are not information losing, and should in fact be transitive relations. About one year ago, I pointed out this difficulty to Guy Steele with some well- chosen examples; and he was quite shocked -- indeed it was his intention that "=" be a true equivalence predicate. Lucid's 3.0 release performs "appropriate contagion" in the case of numerical comparisons, in order to preserve transitivity. re: 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. Efficient hash tables are! ["so complicated that one can't construct them ...]. Both Lucid and Symbolics hide a lot of implementation-dependent knowledge deep within the bowels of CL hash-tables; even if the average Lisp programmer were "smart enough" to defend his ego on hash-tables, he probably wouldn't have reasonable access to all the system internals that the vendor wizards do. In fact, I have heard some C programmers praise Common Lisp for it's inclusion of hash-tables. They complain and complain about having to reinvent the wheel (hash-tables) over and over again. re: Date: Thu, 30 Jun 88 12:40:54 PDT From: jrose@Sun.COM (John Rose) . . . 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. This point that you [Greenwald] are making seems not to be generally appreciated. The fact that many many experts pored over the Common Lisp design, and still thought that numerical equality as defined by "=" was an equivalence relation shows how easy it is to miss closure on transitivity. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 19 Jul 88 00:03:37 EDT Received: from ICS.UCI.EDU by SAIL.Stanford.EDU with TCP; 18 Jul 88 20:49:23 PDT Received: from cip.ics.uci.edu by ICS.UCI.EDU id aa05147; 18 Jul 88 20:46 PDT Received: from cip2.ics.uci.edu by CIP.ICS.UCI.EDU id aa01852; 18 Jul 88 20:44 PDT To: Common-Lisp%sail.stanford.edu@ICS.UCI.EDU Subject: arithmeticprecision Reply-to: Bernd Nordhausen Date: Mon, 18 Jul 88 20:44:36 -0700 From: Bernd Nordhausen Message-ID: <8807182044.aa01852@CIP.ICS.UCI.EDU> Is there an easy way in Common Lisp (especially in KCL) to specify the precision of arithmetic functions (=, +, -, etc.) ? In other words how can I make (= 300.0000001 300.00) return T without having to write a new = funnction? Bernd  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 18 Jul 88 19:10:53 EDT Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 18 Jul 88 15:53:43 PDT Received: from maths.bath.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP id aa06197; 18 Jul 88 21:00 BST Received: from xenakis by mordell.maths.bath.AC.UK id aa27384; 18 Jul 88 21:24 BST To: drl%vuse.vanderbilt.edu@NSS.Cs.Ucl.AC.UK CC: Common-Lisp@sail.stanford.edu In-reply-to: "David R. Linn"'s message of Fri, 15 Jul 88 21:59:50 CDT <8807160259.AA00247@backup.vuse.vanderbilt.edu> Subject: (Not Necessarily Common) LISP Implementation Date: Mon, 18 Jul 88 21:24:34 BST From: jpff%maths.bath.ac.uk@NSS.Cs.Ucl.AC.UK Sender: jpff%maths.bath.ac.uk@NSS.Cs.Ucl.AC.UK I tried to reply to your original message with commnets on POPLOG and the BALM system at Utah, but these where systems without an interpreter. In my opinion a system such as you describe would not be LISP as it loses all the advantages of program development. Having said that I have an experimental system which compiles LISP into C, and that is linked with a fixed library. The target is a fixed languages rather than a LISP system. Is that what you mean? Another possible interpretation: we wrote a LISp system which was constructed by compiling LISP into ALGOL-60, the final thing looking like LISP, but with no compiler. ==John  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 16 Jul 88 21:36:57 EDT Received: from ucbarpa.Berkeley.EDU by SAIL.Stanford.EDU with TCP; 16 Jul 88 18:18:52 PDT Received: by ucbarpa.Berkeley.EDU (5.59/1.28) id AA18764; Sat, 16 Jul 88 18:18:00 PDT Received: from akbar by franz (3.2/3.14) id AA04867; Sat, 16 Jul 88 18:07:42 PDT Received: by akbar (3.2/3.14) id AA11821; Sat, 16 Jul 88 18:07:46 PDT From: franz!akbar!layer@ucbarpa.Berkeley.EDU (Kevin Layer) Return-Path: Message-Id: <8807170107.AA11821@akbar> To: franz!su-ai.stanford.edu!common-lisp Subject: Franz Inc. makes available Allegro CL/GNU Emacs Interface Date: Sat, 16 Jul 88 18:07:45 PDT Introduction ------------ Franz Inc. is offering to the Lisp community version 1.2 of their interface between Allegro Common Lisp (previously known as "Extended Common Lisp") and GNU Emacs. This interface will also work between GNU Emacs and Franz Lisp Opus 43 (the current release from Franz Inc.) or Franz Lisp Opus 38 (the last public domain version). The goal of this interface is to offer the Lisp programmer a tightly integrated Lisp environment. The interface can be broken down into three parts: * Lisp editing modes for Common and Franz Lisp, * Inferior modes for Common and Franz Lisp subprocesses, and * TCP Common Lisp modes for socket communication with Common Lisp. The first two are available for both Common and Franz Lisp, but the third feature, which enables the tight coupling of the environments, is only available for Allegro CL. It uses multiprocessing in Allegro CL and UNIX domain socket to communicate information between the GNU Emacs and Allegro CL worlds. The features of the interface are: * enhanced subprocess modes, including - file name completion - an input ring to allow fetching of previously typed input * macroexpansion of forms in a Lisp source file * `find-tag' for Lisp functions (the Allegro CL world is queried for the location of Lisp functions) * who-calls: find all callers of a Lisp function * Arglist, `describe' and function documentation are available in Lisp source buffers (again, the information comes dynamically from Allegro CL) * automatic indentation of forms entered to an inferior Lisp The interface is written entirely in GNU Emacs Lisp, with the exception of a replacement for the standard `open-network-stream' in src/process.c. Some of the advanced features use UNIX domain sockets and also use features specific to the implementation of Allegro CL (multiprocessing). The interface is fully documented on-line. Ownership --------- The Lisp/GNU Emacs interface is the property of Franz Incorporated. The Emacs Lisp source code is distributed and the following notice is present in all source files for which it applies: ;; ;; copyright (C) 1987, 1988 Franz Inc, Berkeley, Ca. ;; ;; The software, data and information contained herein are the property ;; of Franz, Inc. ;; ;; This file (or any derivation of it) may be distributed without ;; further permission from Franz Inc. as long as: ;; ;; * it is not part of a product for sale, ;; * no charge is made for the distribution, other than a tape ;; fee, and ;; * all copyright notices and this notice are preserved. ;; ;; If you have any comments or questions on this interface, please feel ;; free to contact Franz Inc. at ;; Franz Inc. ;; Attn: Kevin Layer ;; 1995 University Ave ;; Suite 275 ;; Berkeley, CA 94704 ;; (415) 548-3600 ;; or ;; emacs-info%franz.uucp@Berkeley.EDU ;; ucbvax!franz!emacs-info Some files contain GNU Emacs derived code, and those files contain the GNU Emacs standard copyright notice. Obtaining the Software ---------------------- To obtain version 1.2 of this interface either: 1) copy it from ucbarpa.berkeley.edu or ucbvax.berkeley.edu via FTP (login `ftp', password your login name) from the directory pub/fi/gnudist-1.2-tar.Z, or 2) send a check (sorry, no PO's accepted) in the amount of $50 for a US address and $75 for a foreign address to Franz Inc. to the following address: Franz Inc. Attn: Emacs/LISP Interface Request 1995 University Ave Suite 275 Berkeley, CA 94704 Please specify the media (`tar' format only) which is one of: * 1/2", 1600 bpi, 9-track * 1/4", cartridge tape--specify the machine type (ie, TEK, SUN) Future Work ----------- Improvements to this interface will be made in the future, so to facilitate the exchange of information about this and user's experiences, questions and suggestions a mailing list will be created as a forum for discussion on topics relating to this interface. If you would like to be on this mailing list (local redistribution is encouraged), please drop me a note. If you have trouble with one of the addresses below, try one of: layer@Berkeley.EDU -or- ucbvax!layer ---------------------------------------------------------------------------- D. Kevin Layer Franz Inc. layer%franz.uucp@Berkeley.EDU 1995 University Avenue, Suite 275 ucbvax!franz!layer Berkeley, CA 94704 (415) 548-3600, FAX: (415) 548-8253  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 15 Jul 88 23:16:36 EDT Received: from uunet.UU.NET by SAIL.Stanford.EDU with TCP; 15 Jul 88 20:01:41 PDT Received: from [129.59.100.1] by uunet.UU.NET (5.59/1.14) id AA09377; Fri, 15 Jul 88 23:00:37 EDT Received: from backup.vuse.vanderbilt.edu by vuse.vanderbilt.edu (3.2/SMI-3.2) id AA00651; Fri, 15 Jul 88 21:59:33 CDT Received: by backup.vuse.vanderbilt.edu (4.0/SMI-4.0) id AA00247; Fri, 15 Jul 88 21:59:50 CDT Date: Fri, 15 Jul 88 21:59:50 CDT From: drl@vuse.vanderbilt.edu (David R. Linn) Message-Id: <8807160259.AA00247@backup.vuse.vanderbilt.edu> To: Common-Lisp@SAIL.Stanford.EDU Subject: (Not Necessarily Common) LISP Implementation (Hopefully)Gentle Readers, I recently requested information from the readers of the AIList mailing list about implementations of LISP that do not rely (in some way) on a LISP interpreter and now wish to request the same of those readers of the Common LISP mailing list as well. I realize that this question is not really about Common LISP but I also realize the depth and breadth of the LISP experience of the readers of this list. From the initial repsonses to my question, I understand that I probably did not phrase my question in the best possible way. When I refer to a LISP interpreter, I refer not to the evaluator alone but to the program that includes the evaluator, memory manager, reader, printer and other such; perhaps I should call this a LISP "environmental support program". ("Virtual machine" came to mind but was discarded as another multiply-interpretable phrase.) To attempt to find a Common LISP connection in all of this, let me recast my question my question in terms of compiling LISP (which I understand was a central concern of the Common LISP movement): Does anyone have any experience with an implementation of LISP which uses a C/Fortran compiler/link-with-external-runtime-library scheme instead of interpret-or-compile-and-run-within-the-environmental-support- program? Please reply directly to me and I will summarize anything of interest to the list David David Linn, System Manager/Postmaster |INET: Vanderbilt University School of Engineering| drl@vuse.vanderbilt.edu Post Office Box 1824, Station B |Phone: Nashville, TN, USA 37235 | [USA] 615-322-7924  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 15 Jul 88 16:58:19 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 15 Jul 88 13:41:56 PDT Received: by labrea.stanford.edu; Fri, 15 Jul 88 13:40:52 PDT Received: from blacksox.lucid.com by edsel id AA07108g; Fri, 15 Jul 88 13:37:57 PDT Received: by blacksox id AA01410g; Fri, 15 Jul 88 13:34:01 pdt Date: Fri, 15 Jul 88 13:34:01 pdt From: Eric Benson Message-Id: <8807152034.AA01410@blacksox.lucid.com> To: fritzson@prc.unisys.com Cc: Common-Lisp@sail.stanford.edu In-Reply-To: fritzson@PRC.Unisys.COM's message of Fri, 15 Jul 88 16:01:08 EDT <8807152001.AA10285@caesar.PRC.Unisys.COM> Subject: overloading defstruct accessors Date: Fri, 15 Jul 88 16:01:08 EDT From: fritzson@PRC.Unisys.COM The following example can be viewed as an attempt to overload the accessor function "get-a" by making it access the "get-a" fields of both a "foo" structure and a "bar" structure. ------- (defstruct (foo (:conc-name ())) get-a) (defstruct (bar (:conc-name ()) (:include foo)) get-b) (setq afoo (make-foo :get-a 1)) (setq abar (make-bar :get-a 2 :get-b 3)) ------- One could argue that the second defstruct redefines the accessor function "get-a" so that it will only work on bar-s. On the other hand, it is relatively easy to implement this so that "get-a" will work both on foos and bars. Xerox Common Lisp (Lyric release) objects to (get-a afoo) by complaining that "afoo is not a bar". Franz Allegro Common Lisp allows it. I haven't tried any other lisps. Lucid Common Lisp originally (in Release 1.0) had the behavior you describe in Xerox Common Lisp. This was changed in later releases so that the GET-A defined by FOO is not replaced by the GET-A defined by BAR. There is no structure slot access type checking in Franz Allegro Common Lisp or MIT-derived Lisp Machines, other than making sure the argument is an array whose length is greater than the index of the slot being accessed. Is there a consensus on what an implementation of Common Lisp should do with this? My personal opinion is that it is a bug for BAR to define GET-A such that only objects of type BAR are allowed. It is easy to overlook this problem, as I did until someone discovered it. It is too bad (but probably not offically wrong) that many implementations of DEFSTRUCT don't do any type checking. I think this is a legacy of DEFSTRUCT's origin as "just a way to give mnemonic names to array slots." For example, in Zetalisp the default was for DEFSTRUCTs to be unnamed, rather like :TYPE VECTOR in CL. -Rich Fritzson ARPA: fritzson@prc.unisys.com UUCP: {sdcrdcf,psuvax1,cbmvax}!burdvax!fritzson P.S. Please, no complaints about the stylistic appropriateness of using (:conc-name nil) in this way. This was written by someone who should be using CLOS.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 15 Jul 88 16:56:48 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 15 Jul 88 13:41:26 PDT Received: by labrea.stanford.edu; Fri, 15 Jul 88 13:40:27 PDT Received: from rainbow-warrior.lucid.com by edsel id AA07098g; Fri, 15 Jul 88 13:37:11 PDT Received: by rainbow-warrior id AA03925g; Fri, 15 Jul 88 13:37:32 PDT Date: Fri, 15 Jul 88 13:37:32 PDT From: Patrick Dussud Message-Id: <8807152037.AA03925@rainbow-warrior.lucid.com> To: fritzson@prc.unisys.com Cc: Common-Lisp@sail.stanford.edu In-Reply-To: fritzson@PRC.Unisys.COM's message of Fri, 15 Jul 88 16:01:08 EDT <8807152001.AA10285@caesar.PRC.Unisys.COM> Subject: overloading defstruct accessors Date: Fri, 15 Jul 88 16:01:08 EDT From: fritzson@PRC.Unisys.COM The following example can be viewed as an attempt to overload the accessor function "get-a" by making it access the "get-a" fields of both a "foo" structure and a "bar" structure. ------- (defstruct (foo (:conc-name ())) get-a) (defstruct (bar (:conc-name ()) (:include foo)) get-b) (setq afoo (make-foo :get-a 1)) (setq abar (make-bar :get-a 2 :get-b 3)) ------- CLtL is pretty clear about this, the structure accessors defined for foo should apply to instances of bar. The definition of bar should not obliterate the definition of the accessor for the foo structure. Patrick.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 15 Jul 88 16:19:53 EDT Received: from burdvax.PRC.Unisys.COM (PRC-GW.PRC.UNISYS.COM) by SAIL.Stanford.EDU with TCP; 15 Jul 88 13:02:28 PDT Received: from caesar.PRC.Unisys.COM by burdvax.PRC.Unisys.COM (5.59/Domain/jpb/2.9) id AA24404; Fri, 15 Jul 88 16:01:27 EDT Received: from hamlet.PRC.Unisys.COM by caesar.PRC.Unisys.COM (3.2/Domain/jpb/2.9) id AA10285; Fri, 15 Jul 88 16:01:11 EDT Message-Id: <8807152001.AA10285@caesar.PRC.Unisys.COM> Received: by hamlet.PRC.Unisys.COM (3.2/Domain/jpb/2.9) id AA08031; Fri, 15 Jul 88 16:01:08 EDT Date: Fri, 15 Jul 88 16:01:08 EDT From: fritzson@PRC.Unisys.COM To: Common-Lisp@Sail.Stanford.edu Subject: overloading defstruct accessors The following example can be viewed as an attempt to overload the accessor function "get-a" by making it access the "get-a" fields of both a "foo" structure and a "bar" structure. ------- (defstruct (foo (:conc-name ())) get-a) (defstruct (bar (:conc-name ()) (:include foo)) get-b) (setq afoo (make-foo :get-a 1)) (setq abar (make-bar :get-a 2 :get-b 3)) ------- One could argue that the second defstruct redefines the accessor function "get-a" so that it will only work on bar-s. On the other hand, it is relatively easy to implement this so that "get-a" will work both on foos and bars. Xerox Common Lisp (Lyric release) objects to (get-a afoo) by complaining that "afoo is not a bar". Franz Allegro Common Lisp allows it. I haven't tried any other lisps. Is there a consensus on what an implementation of Common Lisp should do with this? -Rich Fritzson ARPA: fritzson@prc.unisys.com UUCP: {sdcrdcf,psuvax1,cbmvax}!burdvax!fritzson P.S. Please, no complaints about the stylistic appropriateness of using (:conc-name nil) in this way. This was written by someone who should be using CLOS.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 12 Jul 88 13:11:30 EDT Received: from cs.utah.edu by SAIL.Stanford.EDU with TCP; 12 Jul 88 09:42:21 PDT Received: by cs.utah.edu (5.54/utah-2.0-cs) id AA10136; Tue, 12 Jul 88 10:42:01 MDT Received: by cons.utah.edu (5.54/utah-2.0-leaf) id AA26236; Tue, 12 Jul 88 10:41:49 MDT Date: Tue, 12 Jul 88 10:41:49 MDT From: kessler%cons@cs.utah.edu (Robert R. Kessler) Message-Id: <8807121641.AA26236@cons.utah.edu> To: common-lisp@sail.stanford.edu, fp@cs.yale.edu, scheme@mc.lcs.mit.edu Subject: L&FP Registration -- FINAL CALL This is the final call for registration for the conference. ACM is accepting registration by EMAIL, so please send your information to them (meetings@acmvm.bitnet). Note, if you plan on using a credit card, please include the name on the card, the type of card, the number, and the expiration date. Also, please include the following information. NOTE -- the final deadline for advance registration is this FRIDAY, JULY 15. Also, you will have to make your own reservations at Snowbird by calling Snowbird Central Reservations at (800)453-3000 or (801)532-1700. It looks like it will be a great conference. We are looking forward to seeing you there. 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, expiration date, 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 11 Jul 88 15:22:01 EDT Received: from Xerox.COM by SAIL.Stanford.EDU with TCP; 11 Jul 88 11:11:23 PDT Received: from Cabernet.ms by ArpaGateway.ms ; 11 JUL 88 11:06:55 PDT Date: Mon, 11 Jul 88 11:02 PDT From: Gregor.pa@Xerox.COM Reply-To: Gregor@GRAPEVINE.parc.xerox.com Subject: CLOS Workshop To: Common-Lisp@Sail.Stanford.edu, common-lisp-object-system@sail.stanford.edu, CL-Object-Oriented-Programming@Sail.Stanford.edu, CommonLoops.pa@Xerox.COM Fcc: BD:>Gregor>mail>outgoing-mail-2.text.newest Message-ID: <19880711180221.8.GREGOR@PORTNOY.parc.xerox.com> Line-fold: no Workshop for CLOS Users and Implementors October 3rd and 4th Xerox PARC Palo Alto, California We have been excited by the extent to which CLOS is already being used, and the ways in which it is being extended. The purpose of this workshop is to provide an opportunity for the members of the CLOS community to get together and share their experience. To provide a good start for the interchange, we are requesting that participants supply a short position paper (1-3 pages) describing work related to CLOS. Some topics of interest are: Applications Programming Techniques Implementation Programming Environment Tools Extensions of CLOS Techniques for Converting to CLOS Meta Object Techniques and Theory Critiques We will try to support demonstrations or videotapes of applications, programming environments, implementations or other relevant systems. If you are planning to attend, please let us know by August 15th. This will help us with planning and allow us to arrange a discount rate at a local hotel. Position papers should reach us by September 9th so that we can organize a program and arrange for duplication of the papers. Position papers, notice to attend, and other correspondence should be sent to: Gregor Kiczales 3333 Coyote Hill Rd. Palo Alto, CA 94304 or by Internet mail to: Gregor.pa@Xerox.com -------  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Jul 88 16:32:22 EDT Received: from NMFECC.ARPA by SAIL.Stanford.EDU with TCP; 8 Jul 88 13:16:10 PDT Received: from tuva.sainet.mfenet by ccc.mfenet with Tell via MfeNet ; Fri, 8 Jul 88 13:13:16 PDT Date: Fri, 8 Jul 88 13:13:16 PDT From: POTHIERS%TUVA.SAINET.MFENET@NMFECC.ARPA Message-Id: <880708131316.2020021f@NMFECC.ARPA> To: COMMON-LISP@SAIL.STANFORD.EDU Subject: error handling Date: Thu, 7-JUL-1988 13:50 MST X-VMS-Mail-To: @COMMON-LISP Can anyone tell me a good (portable) way to handle error handlers in common lisp? Steve Pothier SAIC 5151 East Broadway, Suite 900 Tucson, AZ 85711-3796 602-748-7400 pothiers%tuva.sainet@nmfecc.arpa  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 6 Jul 88 19:25:40 EDT Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 6 Jul 88 16:12:04 PDT Posted-Date: Wed, 06 Jul 88 16:11:58 PDT Message-Id: <8807062312.AA13550@vaxa.isi.edu> Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51) id AA13550; Wed, 6 Jul 88 16:12:07 PDT To: edsel!jonl@labrea.stanford.edu From: goldman@vaxa.isi.edu Subject: [Re: EQUAL] Cc: common-lisp@sail.stanford.edu In-Reply-To: edsel!jonl@labrea.stanford.edu's message of 2792627829 Date: Wed, 06 Jul 88 16:11:58 PDT Sender: goldman@vaxa.isi.edu My original response to part of JonL's suggestion regarding CLOS and EQUAL: 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? JonL's comment on that: 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. But because EQUAL is defined to recur to components of certain compound objects, saying that it is an error to call EQUAL on objects of type C implies that it would be an error to call it on compound objects (say, lists) containing Cs. It seems wrong to me NOT to be able to choose to represent something with a CLOS object if you want to use it in a list, or array, or struct, that is going to tested with EQUAL. I would feel far better if EQ, EQL, EQUAL, and EQUALP (the built-in equivalence predicates) were well defined (no errors) over the entire universe of lisp objects. This does not imply that one couldn't make EQUAL a generic function; only that it would "be an error" to write EQUAL methods that destroyed the properties of EQUAL that make it a universal equivalence predicate. [Like, I'd be very suspicous of any method with different specializers for the two arguments.] Neil  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 6 Jul 88 17:00:54 EDT Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 6 Jul 88 13:44:22 PDT Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0) id AA09648; Wed, 6 Jul 88 13:42:20 PDT Received: from lukasiewicz.sun.com by snail.sun.com (4.0/SMI-3.2) id AA26636; Wed, 6 Jul 88 13:37:43 PDT Received: by lukasiewicz.sun.com (4.0/SMI-4.0) id AA24466; Wed, 6 Jul 88 13:44:31 PDT Date: Wed, 6 Jul 88 13:44:31 PDT From: jrose@Sun.COM (John Rose) Message-Id: <8807062044.AA24466@lukasiewicz.sun.com> To: goldman@vaxa.isi.edu Cc: common-lisp@sail.stanford.edu In-Reply-To: goldman@vaxa.isi.edu's message of Tue, 05 Jul 88 17:49:37 PDT <8807060049.AA21993@vaxa.isi.edu> Subject: EQUAL, and hash tables, and value/object distinctions Posted-Date: Tue, 05 Jul 88 17:49:37 PDT From: goldman@vaxa.isi.edu Date: Tue, 05 Jul 88 17:49:37 PDT Sender: goldman@vaxa.isi.edu Proposal: EQUAL should check for isomorphism of hash tables. I think that's fine; the issue is what properties define, and thus derive from, two hash tables being isomorphic. 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. I definitely do not like that definition. I don't think that two hash tables with different equality predicates should be considered EQUAL unless they are both EMPTY. Rationale: A hash table is best though of as a mapping from (a subset of) the EQUIVALENCE CLASSES of an equivalence predicate to associated values. Good rationale. OK, the "hash"-ness is abstracted away when thinking about hash table semantics, and the equivalence class structure should remain, abstracting away from the specific keys. So a hash table is "really" a finite map over a set of equivalence classes. The fact the CommonLisp's functions for dealing with hash tables (GETHASH, MAPHASH) deal with an equivalence class through an exemplary member of the class should not lead us astray.... ... There's one sticky problem when we concentrate on equivalence classes rather than exemplars: Equivalence classes are defined via equivalence predicates, which in Lisp are algorithms. So, if user-defined hash tables are ever supported, we need to carefully design a notion of "same equivalence predicate". Equivalence of algorithms is undecidable, and so we need a narrower notion predicate equivalence. (That's why I was trying to ignore the predicates altogether; it finesses this problem.) This isn't an issue yet, of course. EQ can distinguish #'EQ, #'EQL, and #EQUAL. Incidentally, what should happen to user-defined hash tables when their predicates or hash functions are redefined? There is a CLOS hook MAKE-INSTANCES-OBSOLETE which could be used to re-construct all instances of the affected table type. Neil -- John  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 5 Jul 88 21:05:55 EDT Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 5 Jul 88 17:49:08 PDT Posted-Date: Tue, 05 Jul 88 17:49:37 PDT Message-Id: <8807060049.AA21993@vaxa.isi.edu> Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51) id AA21993; Tue, 5 Jul 88 17:49:39 PDT To: common-lisp@sail.stanford.edu From: goldman@vaxa.isi.edu Subject: re: EQUAL, and hash tables, and value/object distinctions Date: Tue, 05 Jul 88 17:49:37 PDT Sender: goldman@vaxa.isi.edu Proposal: EQUAL should check for isomorphism of hash tables. I think that's fine; the issue is what properties define, and thus derive from, two hash tables being isomorphic. 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. I definitely do not like that definition. I don't think that two hash tables with different equality predicates should be considered EQUAL unless they are both EMPTY. Rationale: A hash table is best though of as a mapping from (a subset of) the EQUIVALENCE CLASSES of an equivalence predicate to associated values. The fact the CommonLisp's functions for dealing with hash tables (GETHASH, MAPHASH) deal with an equivalence class through an exemplary member of the class should not lead us astray. The suggested semantics, as I read it, makes the issue of whether two hash tables are EQUAL dependent on which exemplars happen to be stored. For example, suppose HEQ and HEQUAL are hash tables, with equivalence predicates EQ and EQUAL, respectively. Further suppose (EQUAL xxx '(a b c)) and (EQUAL yyy '(a b c)) , but (NOT (EQ xxx yyy)) if I do (setf (gethash xxx HEQ) 1 (gethash yyy HEQUAL) 1) then, by my reading of the above definition, (NOT (EQUAL HEQ HEQUAL)) because the key yyy, in HEQUAL, is not a key in HEQ. But if I do (setf (gethash xxx HEQ) 1 (gethash xxx HEQUAL) 1) then they are EQUAL. I claim that the choice between two different exemplars of an E equivalence class should be transparent for a hash table with equivalence predicate E. I would define EQUALity of hash tables H1 and H2 in the following manner: either H1 and H2 are both empty, or the suggested mutual inclusion definition, with the added requirment that H1 and H2 have the same equivalence predicate. Note that this does not imply that MAPHASH applied to the two tables will generate the same sequence of key/value pairs -- the ordering used by maphash is an implementation detail, and could even change from one invocation to another on the same, unaltered, hash table. Also, "it is an error" to destructively modify a value that has been used as a key for a hashtable of equivalence E (or obtained via a MAPHASH over such a hashtable) in a manner that changes the E-class to which it belongs. I.e., the following is an incorrect program: (setf h (make-hash-table :test 'equal) xxx '(a b c)) (setf (gethash xxx h) 1) (setf (second xxx) nil) Neil