Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 14 May 88 03:41:53 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 14 May 88 00:14:59 PDT Received: from relay2.cs.net by RELAY.CS.NET id ab08204; 14 May 88 1:50 EDT Received: from cs.umass.edu by RELAY.CS.NET id bt03216; 14 May 88 1:39 EDT Date: Fri, 13 May 88 16:00 EDT From: ELIOT@cs.umass.edu Subject: SIDE-EFFECT-FREE/STATELESS Functions To: Common-Lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"Common-Lisp@sail.stanford.edu" From: IN%"edsel!jonl@labrea.stanford.EDU" "Jon L White" 13-MAY-1988 06:32 Subj: SIDE-EFFECT-FREE/STATELESS Functions The discussion on "constant functions" seems to me to have reached a dead end. Agreed. But I do maintain that the 'inline' declaration would be significantly more useful if the single word "desirable" is changed to "allowable" in specifying its effect. This would create a more appropriate division of responsibility between the compiler and the programmer. No Common Lisp implementation or program would have to be modified to implement this refinement of the standard. In the future compilers would be encouraged to make a reasonable context dependand decision about open coding. Would it be desirable to have two new declarations: SIDE-EFFECT-FREE and STATELESS? I am in favor of such declarations. Presumably one would want a compiler to try to verify these properties. Should "ERROR" and "CERROR" be considered side effect free for this purpose? If not then functions like division can't be considered side effect free, since division by zero must signal an error. Of course, if a compiler can check these properties it could also compute them. But currently it would not be allowed to use those computed properties.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 14 May 88 01:04:04 EDT Received: from C.CS.CMU.EDU by SAIL.Stanford.EDU with TCP; 13 May 88 20:33:31 PDT Received: ID ; Fri 13 May 88 23:33:21-EDT Date: Fri 13 May 88 23:33:21-EDT From: Dave.Touretzky@C.CS.CMU.EDU Subject: replies to hash table comments To: common-lisp@SAIL.STANFORD.EDU Message-ID: <12398139318.17.TOURETZKY@C.CS.CMU.EDU> To JonL: Yes, *PRINT-HASH* would be a switch analogous to *PRINT-ARRAY*. If T, then the contents of the hash table would be displayed. If NIL, then the current # notation would be used. The initial value of the switch would be implementation-dependent. To Mlynarik: I'm not thrilled with the idea of generalizing #S to objects other than defstructs, but I guess that's a matter of personal taste. By the way, Symbolics writes pathnames as #P"/usr/dst/foo.bar". To Moon: there are three reasons why DESCRIBE doesn't solve the problems that arise in teaching beginners about hash tables: 1. In some implementations, DESCRIBE does not show the contents of a hash table. CMU Common Lisp currently displays this regrettable (but legal) behavior. 2. It is a hassle for a beginner to have to type (describe my-table) every time he wants to see what's inside his hash table. And if he's passing the hash table as an argument to a function, it would be nice if its contents could be displayed automatically by TRACE or by the debugger simply by setting *PRINT-HASH* to T. This kind of behavior would make hash tables a first class "visible" data structure, as easy to understand as lists and vectors. 3. The proposed #H notation would make it possible to read and write hash tables from files, and to create them interactively with a single expression rather than doing a MAKE-HASH-TABLE and a bunch of SETF's. To recap, the proposal was that if *PRINT-HASH* was T, then hash tables would be displayed as #nH(type (key1 . value1) (key2 . value2) ...) where "n" was the size of the table and "type" was one of EQ, EQL, or EQUAL. When reading a #H expression it should be possible to omit the numeric argument, in which case the system will pick some reasonable size based on the number of key/value pairs supplied. It should also be possible to omit the type, in which case EQL is assumed. So #H((FOO . 37) (BAR . 42)) might print as #20H(EQL (FOO . 37) (BAR . 42)). -- Dave -------  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 May 88 21:20:02 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 13 May 88 18:01:17 PDT Received: from EUPHRATES.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 404503; Fri 13-May-88 21:00:12 EDT Date: Fri, 13 May 88 21:00 EDT From: David A. Moon Subject: SIDE-EFFECT-FREE/STATELESS Functions To: Jon L White cc: common-lisp@SAIL.STANFORD.EDU In-Reply-To: <8805132146.AA28645@bhopal.lucid.com> Message-ID: <19880514010013.2.MOON@EUPHRATES.SCRC.Symbolics.COM> Date: Fri, 13 May 88 14:46:52 PDT From: Jon L White Could you clarify how you are using "function" below? sometimes it seems to apply to the symbol naming the routine being defined, and other times it applies only to the compiled function object: It refers to the function object in all cases. I omitted the word "name" in one place, and I've added it in brackets below. Date: Fri, 13 May 88 12:30 EDT From: David A. Moon The LT:SIDE-EFFECTS and LT:REPLICABILITY declarations license the compiler to assume that the current definition and all future redefinitions of the declared function [name] will have the declared properties. The reason these declarations exist is solely for that constraint on future redefinitions, since this is information that the compiler could easily deduce for itself by analyzing the function body. These declarations are placed in the body of a function and declare properties of the function being defined; these properties are available in all scopes where the name of the function is lexically available. "Future redefinitions" must mean "future rebindings of some symbol-function cell", right? I don't think I should admit to knowing what you mean by implementation dependent concepts like "binding" and "cell". If the function was defined by DEFUN, redefinition means evaluating a DEFUN for the same name. Also, it appears as though the declaration can only appear in the body of the code to which it applies; thus you couldn't tell the compiler that BAR is reducible in the following way? There was no function name field in the declaration syntax I showed. The declarations apply to functions, not to function names, sorry about the confusion. I don't know what it would mean to locally declare a function to be free of side-effects; I think that's a property of the function, not of a caller of the function. (defun foo (x) (declare ( bar)) (prog (...) A (bar x) ;compiler might flush this call (when (< (random 5) 3) (return (bar 10))))) ;compiler could constant-fold this one As I read your message, the only way the Symbolics compiler could obtain information about 'bar', for use while compileing 'foo', is if 'foo' and 'bar' are being defined in the same lexical scope and the declare is inside the definition of 'bar'. If this isn't right, then maybe you could give some examples. I suspect I did not understand this comment. When defining a function named bar, one declares properties of that function and all future redefinitions of the function by putting a declare inside the function's definition. When calling a function named bar, the declarations attached to the definition that will be called are used.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 May 88 18:48:48 EDT Received: from EDDIE.MIT.EDU by SAIL.Stanford.EDU with TCP; 13 May 88 15:33:18 PDT Received: by EDDIE.MIT.EDU with UUCP with smail2.5 with sendmail-5.45/4.7 id ; Fri, 13 May 88 18:32:26 EDT Received: by spt.entity.com (smail2.5); 13 May 88 18:05:52 EDT (Fri) To: miller@cs.rochester.edu Cc: common-lisp@SAIL.STANFORD.EDU In-Reply-To: Brad Miller's message of Fri, 13 May 88 15:33 EDT <19880513193300.4.MILLER@DOUGHNUT.CS.ROCHESTER.EDU> Subject: Constant-Function, and integration-level Message-Id: <8805131805.AA17354@spt.entity.com> Date: 13 May 88 18:05:52 EDT (Fri) From: gz@spt.entity.com (Gail Zacharias) Clearly any decent development environment should not 'lock in' functions during development. But that's not a question that a language standard need address, it's something between you and your Lisp vendor... The language issue is, when you've finished developing your program, using whatever tools your implementation provides for that purpose, what properties must that program have in order to be a correct Common Lisp program and hence work in any other correct Common Lisp implementation. In this particular case, the question is, can your program assume that redefining a DEFUN'ed function at runtime will affect all calls to that function: (1) Yes, unless it's been declared CONSTANT-FUNCTION or (2) No, unless it's been declared NOTINLINE I'm arguing that (2) is more useful. With (1), all portable programs which wish to take advantage of implementations which might do significant optimizations on constant functions would have to be accompanied by huge sets of constant-function proclamations (yes, i know this can be a program that you have to run before compiling, which maps through all symbols. It's still awkward).  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 May 88 18:07:54 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 13 May 88 14:52:59 PDT Received: by labrea.stanford.edu; Fri, 13 May 88 14:52:30 PDT Received: from bhopal.lucid.com by edsel id AA13315g; Fri, 13 May 88 14:43:42 PDT Received: by bhopal id AA28645g; Fri, 13 May 88 14:46:52 PDT Date: Fri, 13 May 88 14:46:52 PDT From: Jon L White Message-Id: <8805132146.AA28645@bhopal.lucid.com> To: Moon@stony-brook.scrc.symbolics.com Cc: common-lisp@sail.stanford.edu In-Reply-To: David A. Moon's message of Fri, 13 May 88 12:30 EDT <19880513163043.4.MOON@EUPHRATES.SCRC.Symbolics.COM> Subject: SIDE-EFFECT-FREE/STATELESS Functions Could you clarify how you are using "function" below? sometimes it seems to apply to the symbol naming the routine being defined, and other times it applies only to the compiled function object: Date: Fri, 13 May 88 12:30 EDT From: David A. Moon Subject: SIDE-EFFECT-FREE/STATELESS Functions In-Reply-To: <8805130856.AA25592@bhopal.lucid.com> The LT:SIDE-EFFECTS and LT:REPLICABILITY declarations license the compiler to assume that the current definition and all future redefinitions of the declared function will have the declared properties. The reason these declarations exist is solely for that constraint on future redefinitions, since this is information that the compiler could easily deduce for itself by analyzing the function body. These declarations are placed in the body of a function and declare properties of the function being defined; these properties are available in all scopes where the name of the function is lexically available. "Future redefinitions" must mean "future rebindings of some symbol-function cell", right? Also, it appears as though the declaration can only appear in the body of the code to which it applies; thus you couldn't tell the compiler that BAR is reducible in the following way? (defun foo (x) (declare ( bar)) (prog (...) A (bar x) ;compiler might flush this call (when (< (random 5) 3) (return (bar 10))))) ;compiler could constant-fold this one As I read your message, the only way the Symbolics compiler could obtain information about 'bar', for use while compileing 'foo', is if 'foo' and 'bar' are being defined in the same lexical scope and the declare is inside the definition of 'bar'. If this isn't right, then maybe you could give some examples. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 May 88 16:19:27 EDT Received: from PECAN.CS.ROCHESTER.EDU ([192.5.53.206]) by SAIL.Stanford.EDU with TCP; 13 May 88 12:48:45 PDT Received: from DOUGHNUT.CS.ROCHESTER.EDU by PECAN.CS.ROCHESTER.EDU via CHAOS with CHAOS-MAIL id 2708; Fri 13-May-88 15:42:17 EDT Date: Fri, 13 May 88 15:42 EDT From: Brad Miller Subject: Re: Constant-Function To: Jon L White cc: common-lisp@sail.stanford.edu In-Reply-To: <8805130436.AA24689@bhopal.lucid.com> Message-ID: <19880513194208.5.MILLER@DOUGHNUT.CS.ROCHESTER.EDU> Sender: miller@cs.rochester.edu Reply-To: miller@cs.rochester.edu Organization: University of Rochester, Department of Computer Science Postal-address: 610 CS Building, Comp Sci Dept., U. Rochester, Rochester NY 14627 Phone: 716-275-1118 Date: Thu, 12 May 88 21:36:45 PDT From: Jon L White The very question as to whether such a declaration would be at all useful, as well as the degree of its utility, depends on how an implementation does function-to-function interfaces. Few people in the common lisp community have been desirous of imposing particular Lisp-system implementation techniques into the portable standard; thus it's not surprising that few are interested in standardizing on implementation specific tricks. [...] Perhaps "block compilation" is a better line of pursuit since it has some implications for "modularity" as well as potential for code efficienty. I am getting the sneaking suspicion that what these various proposals boil down to is the desire for super-compilation, a subject that has been much on my mind lately. A simple example would be: (defun foo (bar) (mapcar #'bletch bar)) where we know that bletch is purely functional, that is, it's output is soley determined by it's arguments, and has no internal state. We could then compile (third (foo mumble)) into (bletch (third mumble)) which simply takes advantage of our "understanding" of properties of foo and bletch. This sort of thing seems to be an active research topic, and I don't think it should have a bearing on a CL standard at this time. For a reference: see "The Concept of a Supercompiler", Turchin, Valentin F. in ACM Transaciont on Programming Languages and Systems, July 1986, V8 N3. ---- Brad Miller U. Rochester Comp Sci Dept. miller@cs.rochester.edu {...allegra!rochester!miller}  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 May 88 15:51:27 EDT Received: from ACORN.CS.ROCHESTER.EDU by SAIL.Stanford.EDU with TCP; 13 May 88 12:38:22 PDT Received: from DOUGHNUT.CS.ROCHESTER.EDU by ACORN.CS.ROCHESTER.EDU via CHAOS with CHAOS-MAIL id 39735; Fri 13-May-88 15:32:58 EDT Date: Fri, 13 May 88 15:33 EDT From: Brad Miller Subject: Re: Constant-Function, and integration-level To: Gail Zacharias cc: common-lisp@SAIL.STANFORD.EDU In-Reply-To: <8805130053.AA14552@spt.entity.com> Message-ID: <19880513193300.4.MILLER@DOUGHNUT.CS.ROCHESTER.EDU> Sender: miller@cs.rochester.edu Reply-To: miller@cs.rochester.edu Organization: University of Rochester, Department of Computer Science Postal-address: 610 CS Building, Comp Sci Dept., U. Rochester, Rochester NY 14627 Phone: 716-275-1118 Date: 13 May 88 00:53:49 EDT (Fri) From: gz@spt.entity.com (Gail Zacharias) I don't really understand the rest of your message. The point I was trying to make is that since most DEFUN'ed functions are constant, it's not very useful to have to have a constant-function declaration for every DEFUN in your program. Rather, that should be the default (i.e. implementations should be allowed to assume it), so that correct portable programs *must* explicitly mark the exceptions. NOTINLINE works fine for that purpose. I disagree entirely, that INLINE should be the default. Consider: o If I change a function, then I must recompile all functions that call it, and hence all functions that call *them*, on into the night, on the off chance the compiler may have open coded it. o Debugging becomes harder. One no longer has a function invocation to use as a handle for, say TRACE. STEP doesn't work as expected either, particularly if the compiler is allowed to constant fold whenever it wants to. I'm not arguing that this facility doesn't have it's place, I just don't think it should be the default action. Most of us are more concerned with maintainability than raw speed. ---- Brad Miller U. Rochester Comp Sci Dept. miller@cs.rochester.edu {...allegra!rochester!miller}  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 May 88 14:43:28 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 13 May 88 11:25:19 PDT Return-Path: Received: from kulla.think.com by Think.COM; Fri, 13 May 88 14:23:13 EDT Received: by kulla.think.com; Fri, 13 May 88 14:23:09 EDT Date: Fri, 13 May 88 14:23:09 EDT From: barmar@Think.COM Message-Id: <8805131823.AA00371@kulla.think.com> To: edsel!jonl@labrea.stanford.edu Cc: common-lisp@sail.stanford.edu In-Reply-To: Jon L White's message of Fri, 13 May 88 01:56:30 PDT <8805130856.AA25592@bhopal.lucid.com> Subject: SIDE-EFFECT-FREE/STATELESS Functions Date: Fri, 13 May 88 01:56:30 PDT From: Jon L White In a more general sense, a user would want to be able to tell the compiler that a certain named function has no internal state and that: (1) it has no side effects, and (2) its value is completely determined by its arguments. Thus RANDOM is not side-effect-free, since it updates *random-state*; and while FIND-SYMBOL is side-effect-free, it is not stateless since it is sensitive to the setting of the global variable *package* as well as to the entries in the package database. AREF is both side-effect-free and stateless. Be careful here. Lisp has various ideas of equality, so whether a "value is completely determined by its arguments" has to be qualified by the type of equality you are talking about. For example (eq (aref some-array 3) (progn (some-function some-array) (aref some-array 3))) is NOT guaranteed to return T, even though AREF is being given EQL arguments in both cases. I think you partially addressed this in the later portion of your message, but I was uncomfortable with this AREF example you gave. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 May 88 12:49:37 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 13 May 88 09:32:27 PDT Received: from EUPHRATES.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 404140; Fri 13-May-88 12:30:52 EDT Date: Fri, 13 May 88 12:30 EDT From: David A. Moon Subject: SIDE-EFFECT-FREE/STATELESS Functions To: Jon L White cc: common-lisp@SAIL.STANFORD.EDU In-Reply-To: <8805130856.AA25592@bhopal.lucid.com> Message-ID: <19880513163043.4.MOON@EUPHRATES.SCRC.Symbolics.COM> Here is the declaration that Symbolics currently uses (and has used for some years) to provide this information to the compiler. We keep it rather simple and do not try to break down side-effects into disjoint categories; in other words, we assume that any location can be aliased with any other location. This message does not constitute any kind of commitment not to change the way this is done in the future. The LT:SIDE-EFFECTS and LT:REPLICABILITY declarations license the compiler to assume that the current definition and all future redefinitions of the declared function will have the declared properties. The reason these declarations exist is solely for that constraint on future redefinitions, since this is information that the compiler could easily deduce for itself by analyzing the function body. These declarations are placed in the body of a function and declare properties of the function being defined; these properties are available in all scopes where the name of the function is lexically available. (DECLARE LT:(SIDE-EFFECTS SIMPLE)) means the function neither causes nor is affected by side-effects. There aren't many examples of this (usually one uses SIMPLE REDUCIBLE, see below); in Symbolics Common Lisp, CHAR-CODE is an example, because the only side-effect that affects its value is rebooting the machine (codes are assigned dynamically but once assigned do not change for the duration of a session). (DECLARE LT:(SIDE-EFFECTS READER)) means the function is affected by side-effects but does not cause them. CONS is an example (allocation of storage is not considered a side-effect because it doesn't affect the result of any other function other than performance metering functions.) (DECLARE LT:(SIDE-EFFECTS WRITER)) means the function may cause side-effects and may be affected by them. This is the default. (DECLARE LT:(SIDE-EFFECTS REDUCIBLE)) means the function is affected by side-effects but does not cause them, and furthermore that the function is subject to constant-folding. CAR is an example. (DECLARE LT:(SIDE-EFFECTS SIMPLE REDUCIBLE)) means the function neither causes nor is affected by side-effects, and furthermore that the function is subject to constant-folding. + is an example. LT:REPLICABILITY is much more implementation dependent but I'll mention it here for completeness. (DECLARE LT:(REPLICABILITY MANY-TIMES)) means it's worth computing the function any number of times rather than binding a variable to it. (DECLARE LT:(REPLICABILITY TWO-TIMES)) means it's worth computing the function twice rather than binding a variable to it, but if a common sub-expression calling this function occurs more than twice, it should be bound to a variable.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 May 88 12:48:54 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 13 May 88 09:33:21 PDT Received: from EUPHRATES.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 404144; Fri 13-May-88 12:33:13 EDT Date: Fri, 13 May 88 12:33 EDT From: David A. Moon Subject: visible hash tables To: Dave.Touretzky@C.CS.CMU.EDU cc: common-lisp@SAIL.STANFORD.EDU In-Reply-To: <12397896527.20.TOURETZKY@C.CS.CMU.EDU> Message-ID: <19880513163315.5.MOON@EUPHRATES.SCRC.Symbolics.COM> Date: Fri 13 May 88 01:19:39-EDT From: Dave.Touretzky@C.CS.CMU.EDU In teaching beginning to intermediate level Lispers to use hash tables, I find my job would be a lot easier if they could see inside the things, just as they can see inside structures and vectors. So what about a convention for printing hash tables? I'd be interested to hear why DESCRIBE isn't good enough for this.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 May 88 11:58:55 EDT Received: from paris.Berkeley.EDU ([128.32.150.46]) by SAIL.Stanford.EDU with TCP; 13 May 88 08:41:26 PDT Received: by paris.Berkeley.EDU (5.57/1.25) id AA28975; Fri, 13 May 88 08:38:34 PDT From: larus%paris.Berkeley.EDU@ginger.Berkeley.EDU (James Larus) Message-Id: <8805131538.AA28975@paris.Berkeley.EDU> To: Jon L White Cc: common-lisp@sail.stanford.edu Subject: Re: SIDE-EFFECT-FREE/STATELESS Functions In-Reply-To: Your message of Fri, 13 May 88 01:56:30 PDT. <8805130856.AA25592@bhopal.lucid.com> Reply-To: larus@ginger.Berkeley.EDU Date: Fri, 13 May 88 08:38:29 PDT Dave Gifford and his graduate students at MIT have been working on "effects" systems for language that parallel type systems, but describe the effect of functions on the state of objects. Their ideas can probably clarify the debate and help make the side-effect-free declarations less ad-hoc. There are two Tech Reports and a few papers that I am aware of: @TECHREPORT{gifford:fx87, AUTHOR = "David K. Gifford and Pierre Jouvelot and John M. Lucassen and Mark A. Sheldon", TITLE = "{FX-87} Reference Manual", INSTITUTION = MITLCS, YEAR = 1987, NUMBER = "MIT/LCS/TR-407", MONTH = Sep} @TECHREPORT{lucassen:types, AUTHOR = "John M. Lucassen", TITLE = "Types and Effects: Towards the Integration of Functional and Imperative Programming", INSTITUTION = MITLCS, YEAR = 1987, NUMBER = "MIT/LCS/TR-408", MONTH = Aug} @INPROCEEDINGS{gifford:integrating, AUTHOR = "David K. Gifford and John M. Lucassen", TITLE = "Integrating Functional and Imperative Programming", PAGES = "28-38", BOOKTITLE = LISPC86, YEAR = 1986, MONTH = Aug} @INPROCEEDINGS{lucassen:polymorphic, AUTHOR = "John M. Lucassen and David K. Gifford", TITLE = "Polymorphic Effect Systems", BOOKTITLE = POPL15, YEAR = 1988, PAGES = "47-57", ADDRESS = "San Diego, California", MONTH = Jan} /Jim  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 May 88 11:58:17 EDT Received: from REAGAN.AI.MIT.EDU by SAIL.Stanford.EDU with TCP; 13 May 88 08:34:31 PDT Received: from JACKIE.AI.MIT.EDU by REAGAN.AI.MIT.EDU via CHAOS with CHAOS-MAIL id 111814; Fri 13-May-88 11:34:02 EDT Date: Fri, 13 May 88 09:14 EDT From: Richard Mlynarik Subject: visible hash tables To: common-lisp@SAIL.STANFORD.EDU In-Reply-To: <12397896527.20.TOURETZKY@C.CS.CMU.EDU> Message-ID: <19880513131438.3.MLY@JACKIE.AI.MIT.EDU> I have always thought that an extension to the #S macro is the correct way to do this sort of thing. Might I instead suggest #S(hash-table :test #'eq :initial-contents #) Such an extension would also allow one to present *PRINT-ESCAPE* pathnames along the lines of #S(pathname "FOO.EDU:>File-Server>barfmail.lisp") Similarly #S(byte-specifier 69 259) #S(random-state ...) and so forth. In CLOSsage, I guess the way to do this would be have the reader call a generic function whose methods are defined on either a class instance or, somewhat less flexibly, `on' the prototype instance of a class. (defmethod construct-instance-from-cruft-read-by-\#S ((class (eql (find-class 'pathname))) &rest initargs) (apply (lambda (name) (pathname name)) initargs)) (defmethod construct-instance-from-cruft-read-by-\#S ((class structure-class) &rest initargs) (apply (secret-internal-constructor class) initargs)) I believe that this sort of approach was implemented in NIL at some stage. RMS' lisp machine code had a similar feature. [Then again, one could always print "#.(let ((table (make-hash-table :test #'eql))) (dolist (x '((key1 . val1) ...)) (setf (gethash table (car x)) (cdr x)))))" Yum!]  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 May 88 05:30:13 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 13 May 88 02:18:05 PDT Received: by labrea.stanford.edu; Fri, 13 May 88 02:05:37 PDT Received: from bhopal.lucid.com by edsel id AA11285g; Fri, 13 May 88 01:53:22 PDT Received: by bhopal id AA25592g; Fri, 13 May 88 01:56:30 PDT Date: Fri, 13 May 88 01:56:30 PDT From: Jon L White Message-Id: <8805130856.AA25592@bhopal.lucid.com> To: common-lisp@sail.stanford.edu Subject: SIDE-EFFECT-FREE/STATELESS Functions The discussion on "constant functions" seems to me to have reached a dead end. But one good thing to come from it is the discovery that CL provides no declaration that enables "constant folding", a very useful optimization in quite a number of compilers. In a more general sense, a user would want to be able to tell the compiler that a certain named function has no internal state and that: (1) it has no side effects, and (2) its value is completely determined by its arguments. Thus RANDOM is not side-effect-free, since it updates *random-state*; and while FIND-SYMBOL is side-effect-free, it is not stateless since it is sensitive to the setting of the global variable *package* as well as to the entries in the package database. AREF is both side-effect-free and stateless. A compiler can perform the following optimization on a stateless and side-effect-free function: (A) Calls with arguments that are compile-time constant may be "folded" into the literal data object evaluable at compile time; (B) Common subexpressions that are calls to such a function may be "reduced" [in the sense described by barmar and Soley]; (C) A call to such a function, whose return value is not consumed by subsequent program parts, can be eliminated [this is also true if the function is merely side-effect-free]; (D) Calls to such a function might be commutable with other program segments ["communting" arguments in function calls is an optimization that some compilers will try to do], since the call itself to such a function doesn't have interactions with other program parts. Would it be desirable to have two new declarations: SIDE-EFFECT-FREE and STATELESS? Is there already a terminology somewhere in use for these properties? Oddly enough, functions which return a feshly-allocated pointer to some updatable storage are not stateless, even though they are side-effect-free -- CONS, APPEND, and MAKE-ARRAY are examples -- because the value of this kind of function is essentially an address; and that address is sensitive to the internal pointer to the "free list". Consider the following: (let ((l '(1 2))) (setq a (copy-list l)) (setq b (copy-list l))) If COPY-LIST were stateless, then a and b should be identical; but the existence of RPLACA means they can't be identical in a fundamental sense. Note that the critical argument in this paragraph depends on the word "updatable". For example, * is a stateless function; and in (let ((x (factorial 100)) (y (factorial 200))) (setq a (* x y)) ;surely a bignum (setq b (* x y))) ;surely another bignum, of same value a and b will hold identical results. True, they will likely be distinguishable by EQ, but there is _no_ update function such that an update to a would not be seen as an update to b also. The EQL comparison is the relevant one for "identicalness", rather than EQ, even though a and b are both pointers to freshly-allocated storage. Long ago, PDP10 Interlisp provided a primitive language function called SETN that would do just this -- it would bash the bits of a stored number object -- but happily CL has nothing like this; if it did, then generic multiplication would not be a stateless function. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 May 88 04:03:06 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 13 May 88 00:51:01 PDT Received: by labrea.stanford.edu; Fri, 13 May 88 00:38:32 PDT Received: from bhopal.lucid.com by edsel id AA11011g; Fri, 13 May 88 00:41:53 PDT Received: by bhopal id AA25462g; Fri, 13 May 88 00:45:03 PDT Date: Fri, 13 May 88 00:45:03 PDT From: Jon L White Message-Id: <8805130745.AA25462@bhopal.lucid.com> To: Dave.Touretzky@c.cs.cmu.edu Cc: common-lisp@sail.stanford.edu In-Reply-To: Dave.Touretzky@C.CS.CMU.EDU's message of Fri 13 May 88 01:19:39-EDT <12397896527.20.TOURETZKY@C.CS.CMU.EDU> Subject: visible hash tables re: The basic notation is: #nH(type (key1 . value1) (key2 . value2) ...) where "n" is the size of the hash table and "type" is the type, such as EQL. The ordering of the dotted pairs is arbitrary. Comments? I like it. So is *PRINT-HASH* the hash-table equivalent of *PRINT-ARRAY* and *PRINT-STRUCTURE*? -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 May 88 04:02:56 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 13 May 88 00:50:46 PDT Received: by labrea.stanford.edu; Fri, 13 May 88 00:38:14 PDT Received: from bhopal.lucid.com by edsel id AA11001g; Fri, 13 May 88 00:40:58 PDT Received: by bhopal id AA25455g; Fri, 13 May 88 00:44:06 PDT Date: Fri, 13 May 88 00:44:06 PDT From: Jon L White Message-Id: <8805130744.AA25455@bhopal.lucid.com> To: Dave.Touretzky@c.cs.cmu.edu Cc: common-lisp@sail.stanford.edu In-Reply-To: Dave.Touretzky@C.CS.CMU.EDU's message of Fri 13 May 88 01:19:39-EDT <12397896527.20.TOURETZKY@C.CS.CMU.EDU> Subject: visible hash tables re: The basic notation is: #nH(type (key1 . value1) (key2 . value2) ...) where "n" is the size of the hash table and "type" is the type, such as EQL. The ordering of the dotted pairs is arbitrary. Comments? I like it. But where is the hash-table equivalent of *PRINT-ARRAY* and *PRINT-STRUCTURE*? -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 May 88 01:34:13 EDT Received: from C.CS.CMU.EDU by SAIL.Stanford.EDU with TCP; 12 May 88 22:19:53 PDT Received: ID ; Fri 13 May 88 01:19:40-EDT Date: Fri 13 May 88 01:19:39-EDT From: Dave.Touretzky@C.CS.CMU.EDU Subject: visible hash tables To: common-lisp@SAIL.STANFORD.EDU Message-ID: <12397896527.20.TOURETZKY@C.CS.CMU.EDU> It bothers me that hash tables cannot be made "visible" data structures, i.e., there is no pretty printer switch you can set to see what's inside them. Compare this with: Vectors: contents displayed in #() notation if *PRINT-ARRAY* is T. Arrays: contents displayed in #nA() notation if *PRINT-ARRAY* is T. Structures: normally displayed in #S notation. As previously discussed, there should be a simple way to select #<> notation for structures, e.g., if a flag named *PRINT-STRUCTURE* is NIL. In teaching beginning to intermediate level Lispers to use hash tables, I find my job would be a lot easier if they could see inside the things, just as they can see inside structures and vectors. So what about a convention for printing hash tables? Here is a suggestion: (setq a (make-hash-table)) ;make a hash table (setf (gethash 'foo a) 37) ;put some stuff in it (setf (gethash 'bar a) 42) ;put some more stuff in it (setf *print-hash* t) ;turn on the magic printer flag a ==> #65H(EQL (FOO . 37) (BAR . 42)) The basic notation is: #nH(type (key1 . value1) (key2 . value2) ...) where "n" is the size of the hash table and "type" is the type, such as EQL. The ordering of the dotted pairs is arbitrary. Comments? -- Dave -------  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 May 88 01:14:17 EDT Received: from EDDIE.MIT.EDU by SAIL.Stanford.EDU with TCP; 12 May 88 21:59:34 PDT Received: by EDDIE.MIT.EDU with UUCP with smail2.5 with sendmail-5.45/4.7 id ; Fri, 13 May 88 00:59:13 EDT Received: by spt.entity.com (smail2.5); 13 May 88 00:53:49 EDT (Fri) To: common-lisp@SAIL.STANFORD.EDU In-Reply-To: ELIOT@cs.umass.edu's message of Wed, 11 May 88 14:55 EDT <8805120732.AA10050@EDDIE.MIT.EDU> Subject: Constant-Function, and integration-level Message-Id: <8805130053.AA14552@spt.entity.com> Date: 13 May 88 00:53:49 EDT (Fri) From: gz@spt.entity.com (Gail Zacharias) Date: Wed, 11 May 88 14:55 EDT From: ELIOT@cs.umass.edu From: Gail Zacharias Regarding inlining, I think it is perfectly valid for a compiler to inline explicit constant references to compiled functions (i.e. references of the form '#) since there is nothing in common lisp that would allow you to tell the difference. TRACE is a Common Lisp function that allows you to see the difference. No. Common Lisp doesn't provide a way to trace disembodied functions. I don't really understand the rest of your message. The point I was trying to make is that since most DEFUN'ed functions are constant, it's not very useful to have to have a constant-function declaration for every DEFUN in your program. Rather, that should be the default (i.e. implementations should be allowed to assume it), so that correct portable programs *must* explicitly mark the exceptions. NOTINLINE works fine for that purpose. Regarding Rob MacLachlan's integration-level, I agree that the concept is useful, but I disagree that it's something a program should be requesting for itself - it's something a user is requesting for the program. Put another way, the integration level should not be sitting inside the program sources, but rather be an argument to compile-file (or defsystem or an option on the compile menu, or however it is the user usually goes about requesting a compilation in his system). Since a correct program should work the same regardless of the integration level it was compiled with, and since the tradeoffs will be different for different implementations, there is no useful criterion that a portable program can use to select its 'preferred' integration-level.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 May 88 01:10:42 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 12 May 88 21:46:57 PDT Received: by labrea.stanford.edu; Thu, 12 May 88 21:33:54 PDT Received: from bhopal.lucid.com by edsel id AA10381g; Thu, 12 May 88 21:33:37 PDT Received: by bhopal id AA24689g; Thu, 12 May 88 21:36:45 PDT Date: Thu, 12 May 88 21:36:45 PDT From: Jon L White Message-Id: <8805130436.AA24689@bhopal.lucid.com> To: ELIOT@cs.umass.edu Cc: common-lisp@sail.stanford.edu In-Reply-To: ELIOT@cs.umass.edu's message of Wed, 11 May 88 16:22 EDT <8805120817.AA05875@edsel.lucid.com> Subject: Constant-Function re: Consider (again) this code: . . . (fix-base-system 'lisp) (fix-base-system 'kee) (fix-base-system 'umass-utilities) This tells the compiler that I am not going to redefine "CONS" and "CAR" and "CDR" and the other 500 functions. The compiler can do constant folding and open coding or whatever is valid and appropriate for calls to those functions. But I want the compiler to assume that my functions are full of bugs (too true, too often) and calls to those functions should be tracable/redefineable/debugable. . . . Is there some combination of FTYPE/INLINE that provides a portable substitute for the above? ... The very question as to whether such a declaration would be at all useful, as well as the degree of its utility, depends on how an implementation does function-to-function interfaces. Few people in the common lisp community have been desirous of imposing particular Lisp-system implementation techniques into the portable standard; thus it's not surprising that few are interested in standardizing on implementation specific tricks. On the other hand, what is useful about the "constant-foldable" declaration is that the transformation (sqrt 2.0) ==> 1.414... is independent of how any Lisp system (or compiler) is built [except to the degree that you view this as a "compiler optimization".] User-level macros can do the same thing, but probably less thoroughly than the compiler. It only depends upon knowing some simple properties about the function SQRT. Also, the type system in Common Lisp isn't purely a "compiler efficiency" hack; although I'm not aware of a really good "type inferencing" CL compiler, this declarational information can be used in the sense of "strong typing". Thus its justification is not merely that fixnum declarations can make compiled code run faster. [But I admit that there are so many systems wanting at least some type declarations for efficiency that a few lone "hold outs" against them probably couldn't prevent their appearance in CL]. Perhaps "block compilation" is a better line of pursuit since it has some implications for "modularity" as well as potential for code efficienty. Note that lots of somewhat-incompatible redefinitions of functions don't invalidate FTYPE, or INLINE, or "constant-foldable" assumptions; but they would invalidate the definition you have given (again!) for "constant function", i.e. that it merely means "I won't redefine this function at runtime". [This is the point you said didn't make sense to you; I'm sorry I don't know how to put it in any plainer words]. Thus even in an implementation whose compiler could profit from such information, the declaration seems like overkill because it is too easy to violate its contract without violating any useful requirement. It needs to be more specific (thus I would call it "vague" for not being that specific). Note also that there is a proposal to the x3j13 "cleanup" committee to make it an error to redefine any function named in the Lisp package; this would cover your case (fix-base-system 'lisp). But the proposal is not particlarly for the purpose of enabling potential compiler tricks; rather (I think) it is for the purpose of facilitating reasonable standards for code sharing. I.e., how can you absorb my portable code that uses lisp:append if you have redefined it to do something totally different. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 12 May 88 04:00:58 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 12 May 88 00:37:15 PDT Received: from relay2.cs.net by RELAY.CS.NET id aa06273; 12 May 88 3:12 EDT Received: from cs.umass.edu by RELAY.CS.NET id bu13734; 12 May 88 3:03 EDT Date: Wed, 11 May 88 16:22 EDT From: ELIOT@cs.umass.edu Subject: Constant-Function To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.EDU" From: IN%"edsel!jonl@labrea.stanford.EDU" "Jon L White" 11-MAY-1988 00:58 re: I think there should be some way to closely associate global declaration-type stuff with a function's definition. . . . Of course, the world will not come to an end because people have to use a separate proclaim. I just think it would be nicer to put everything about a function definition into a single form. This is a very good point. Perhaps the bottleneck is that CL can't agree to semantics for *any* declaration (except for SPECIAL); some compiler's basically throw all declarations away (except for SPECIAL). re: Another solution is to define a macro encapsulaing the DEFUN and PROCLAIM. . . . I also don't have a good name for such a macro. 'Defconfun' is rather bletcherous. 'define' would do, but Sussman's students would start schemeing against me. Part of the problem I've been having with the "constant function" declaration is it's vagueness. Its perfectly clear to me :-) In your original message you characterized it as "won't redefine the function at runtime"; Meaning that the definition available at compile time will be the same as the definition in force when the function call is executed. The principle, but not exhaustive, consequences of this are that the compiler can depend upon the FTYPE being fixed, and it is permitted (but not required or even requested) to open code the function call. but as subsequent dialogue shows, there is very little feeling that that implies anything worthwhile beyond what the existing declarations (like ftype, speed/safety etc) provide. "Never redefine, at all, ever" is just too stringent to be useful. It "is an error" to change the definition of a function that has been declared to be a 'constant-function' unless you recompile/reload all calls to that function that have been compiled while that declaration was in force. At best you may not get the new behavior. At worst you might execute code with sufficiently invalid assumptions that the lisp will crash. Further, my assumption that "Never redefine" characterizes the meaning you intended seems to have caused confusion, as evidenced by replies by others; in particular, some (perhaps yourself?) are primarily concerned with the stability of the argument spectrum, so that a compiler *might* be licensed to use a different function-to-function protocol. Maybe I'm confused here too, in which case I'll just drop this line of reasoning; but isn't argument spectra information is already specifiable via the ftype declaration? I tried to suggest that maybe you wanted to cover the case that is currently not covered by any CL declaration -- that of "constant folding" (barmar called it "reducible"; but his example failed to fold the constant form -- it only coalesced common subexpressions). Such "constant folding" at compile time is a critical component of Lucid's optimizing compiler; but the data- base of what is "foldable" isn't user-accessible. There is currently no CL declaration that covers this case. Accepting barmar's terminology, I see a reasonable place for a REDUCIBLE declaration; would you? I think that INLINE combined with algebraic simplification is equivalent to constant folding. What I object to is that 'inline' can cause bloating if the simplifier isn't good enough. It really is the phrase "it is desirable to open-code" that bothers. If that said "It is allowed to open-code..." and "the compiler should make a reasonable heuristic decision based upon the amount of object code that is likely to be produced." I want to tell the compiler what is legal and have it do the right thing. That isn't my reading of the current definition of 'inline'. Consider (again) this code: (defun fix-base-system (pkg) (do-all-external-symbols (sym pkg) (when (fboundp sym) (proclaim (list 'constant-function sym)))))) (fix-base-system 'lisp) (fix-base-system 'kee) (fix-base-system 'umass-utilities) This tells the compiler that I am not going to redefine "CONS" and "CAR" and "CDR" and the other 500 functions. The compiler can do constant folding and open coding or whatever is valid and appropriate for calls to those functions. But I want the compiler to assume that my functions are full of bugs (too true, too often) and calls to those functions should be tracable/redefineable/debugable. Is there some combination of FTYPE/INLINE that provides a portable substitute for the above? It must not cause code-bloating in any legitimate interpretation of the Common Lisp standard, and should not require typing 500 declarations. Furthermore, it should not cause conflicts because of upwards compatible extensions to Common Lisp functions (such as extra keyword args).  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 12 May 88 04:00:07 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 12 May 88 00:37:44 PDT Received: from relay2.cs.net by RELAY.CS.NET id ab06273; 12 May 88 3:12 EDT Received: from cs.umass.edu by RELAY.CS.NET id bv13734; 12 May 88 3:04 EDT Date: Wed, 11 May 88 16:22 EDT From: ELIOT@cs.umass.edu Subject: Constant-Function To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.EDU" From: IN%"edsel!jonl@labrea.stanford.EDU" "Jon L White" 11-MAY-1988 05:47 re: Knowing the FTYPE of sqrt does not allow a compiler to substitute 2.23 for (sqrt 5). You might redefine SQRT as SIN without violating the FTYPE. Right. So your intention for "constant function" really was more along the line of "constant foldable" (or "reducible"), just as I guessed in my first message? No. This is a special case of constant function. The general definition of constant-function is that it promises never to (incompatibly) redefine the function. Constant folding can occur by two processes. (1) The compiler can open-code SQRT (above) or FOO (below) and algebraically simplify the result. In this case we are assuming the simplifying did very well and reduced the code to a constant. (2) The compiler somehow knows that the function is reducible, and proceeds to evaluate the form (in the compilation environment) and substitute the result. In fact, "constant function" by this definition doesn't even imply a constant argument sepectrum. Imagine a function (defun foo (x y) ...) which is "folded" as follows: (foo 2 3) --> 5; then at runtime the user redefines it as (defun foo (x y &optional z) ...) in such a way that (foo 2 3) = (foo 2 3 nil) = 5. No violation of compiler optimizations. This doesn't make any sense to me. This redefinition "is an error" but you will probably get away with it. The fact that in this one example we have not depended upon the fixed FTYPE aspect of a 'constant-function' does not make it legitimate to overgeneralize and assume that in no example is the FTYPE crucial. re: Some Symbolics users use ' in place of #' to get around this bug. (!) I think it exists exactly because the 'constant-function' declaration is missing, . . . Well, Hornig did mention, and others concurred, that the much more common case is to want this assumption; and having to place extra declarations around all the common cases would be a pain. In itself this isn't important, but it leads to the general question of what constant-function is intended for. The relevant buzzwords are "layered systems" and "block-compilation". Initially a function definitoin must be considered somewhat tentative. Perhaps the semantics aren't quite right. Perhaps there is a bug in the definition. In any case it is important that redefinition and tracing work correctly. Eventually this prototype phase ends, and the function definition can be fixed with constant-function. Subsequently the compiler can use knowledge about the arguments, body and even compiled code for the constant-function. ("Snapping uuolinks" as Maclisp called it is effectively an optimization at the compiled code level.) If you believe this model of software development then Hornig's point is wrong. You do not need "extra declarations arount all the common cases" because you (generally) use a single PROCLAIM for every function in the base layer of your system. (Hence the motivation to associate the declaration with the DEFUN.) Happily the Common Lisp declaration system also provides fine-grained control of this form of block compilation.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 12 May 88 03:33:06 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 12 May 88 00:13:44 PDT Received: from relay2.cs.net by RELAY.CS.NET id aj06210; 12 May 88 3:04 EDT Received: from cs.umass.edu by RELAY.CS.NET id bk13734; 12 May 88 2:57 EDT Date: Wed, 11 May 88 14:55 EDT From: ELIOT@cs.umass.edu Subject: Constant-Function To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.EDU" From: Gail Zacharias I believe the point of a CONSTANT-FUNCTION declaration would be to allow references to the function cell of a symbol to be replaced with its compile-time contents (or moral equivalent thereof). I.e. to tell the compiler that it can replace (FOO ...) with (FUNCALL '# ...). Constant-Function allows much more general and useful optimizations than this. Regarding inlining, I think it is perfectly valid for a compiler to inline explicit constant references to compiled functions (i.e. references of the form '#) since there is nothing in common lisp that would allow you to tell the difference. TRACE is a Common Lisp function that allows you to see the difference. Having said all that, I don't think a CONSTANT-FUNCTION declaration would be very useful. Unlike variables, most functions in most programs are constant (once debugging is done), and you don't really want to maintain huge sets of CONSTANT-FUNCTION declarations all over the place (that you have to keep turning off when you need to debug). How does the compiler know that debugging is done, without a constant-function declaration? Should a compiler just *assume* that every function is debugged? What good are debugging tools then? .... I don't really see any need here for language extensions, since requesting block compilation is sort of an environmental issue that I don't think needs to be standardized; and for the exceptions, NOTINLINE will do fine since any implementation that 'snaps links' on functions declared NOTINLINE is asking to lose anyway given current usage. I don't believe there is such a clear separation between language and environment issues. Furthermore I don't believe that "environment issues" should be rigidly excluded from a language. We don't want to impose requirements on the environment that would make Lisp less portable. Certainly block compilation could be addressed as an environment issue. But your proposal actually makes it clear that this cannot be completely handled as an environment issue. You want to split things up so that requests for block compilation are made through the environment, but exceptions to this are handled within the language? Wouldn't it be better to do things one way or the other, rather than both at once?  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 11 May 88 11:30:06 EDT Received: from XX.LCS.MIT.EDU by SAIL.Stanford.EDU with TCP; 11 May 88 08:14:38 PDT Date: Wed, 11 May 1988 11:11 EDT Message-ID: From: SOLEY@XX.LCS.MIT.EDU To: Jon L White Cc: common-lisp@SAIL.STANFORD.EDU, ELIOT@CS.UMASS.EDU Subject: Constant-Function In-reply-to: Msg of 10 May 1988 22:20-EDT from Jon L White Date: Tuesday, 10 May 1988 22:20-EDT From: Jon L White To: ELIOT at cs.umass.edu cc: common-lisp at sail.stanford.edu Re: Constant-Function re: Knowing the FTYPE of sqrt does not allow a compiler to substitute 2.23 for (sqrt 5). You might redefine SQRT as SIN without violating the FTYPE. Right. So your intention for "constant function" really was more along the line of "constant foldable" (or "reducible"), just as I guessed in my first message? I think there are *three* kinds of compiler optimizations we're talking about, not the two that have been bandied about. Given the function (defun bar (x) (+ x 1)) the form (foo (bar 7) (bar 7)) might be compiled in several ways: * INLINE compilation would be (foo (+ 7 1) (+ 7 1)). Yes, a later constant folding stage would do more. But *this* is what INLINE means. * CONSTANT FOLDING, as JonL point out, would be (foo 8 8). Note that in the general case this potentially requires executing random user function definitions from within the compiler. * But REDUCIBLE is what Barmar said; avoid re-executing the function at run time if the arguments are the same (yes, this is the same as common subexp elim). In other words, a source-to-source transform might yield (let ((gensym (bar 7))) (foo gensym gensym)). Note that this does *not* require executing user code. I'm sure that this is what Multics PL/1 does (though my old 1976 Multics PL/I manual doesn't mention it). These transforms obviously have different effects on code size and runtime behavior (particularly in a non-functional language). I agree with the comment that we need to provide the compiler with information about *the function* rather than how we think the compiler should *treat* the function at compile time. -- Richard Soley  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 10 May 88 22:48:36 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 10 May 88 19:25:26 PDT Received: by labrea.stanford.edu; Tue, 10 May 88 19:25:33 PDT Received: from bhopal.lucid.com by edsel id AA29717g; Tue, 10 May 88 19:17:10 PDT Received: by bhopal id AA18005g; Tue, 10 May 88 19:20:10 PDT Date: Tue, 10 May 88 19:20:10 PDT From: Jon L White Message-Id: <8805110220.AA18005@bhopal.lucid.com> To: ELIOT@cs.umass.edu Cc: common-lisp@sail.stanford.edu In-Reply-To: ELIOT@cs.umass.edu's message of Tue, 10 May 88 15:44 EDT <8805102203.AA28707@edsel.lucid.com> Subject: Constant-Function re: Knowing the FTYPE of sqrt does not allow a compiler to substitute 2.23 for (sqrt 5). You might redefine SQRT as SIN without violating the FTYPE. Right. So your intention for "constant function" really was more along the line of "constant foldable" (or "reducible"), just as I guessed in my first message? In fact, "constant function" by this definition doesn't even imply a constant argument sepectrum. Imagine a function (defun foo (x y) ...) which is "folded" as follows: (foo 2 3) --> 5; then at runtime the user redefines it as (defun foo (x y &optional z) ...) in such a way that (foo 2 3) = (foo 2 3 nil) = 5. No violation of compiler optimizations. re: Some Symbolics users use ' in place of #' to get around this bug. (!) I think it exists exactly because the 'constant-function' declaration is missing, . . . Well, Hornig did mention, and others concurred, that the much more common case is to want this assumption; and having to place extra declarations around all the common cases would be a pain. -- JonL --  Received: from REAGAN.AI.MIT.EDU (CHAOS 13065) by AI.AI.MIT.EDU 10 May 88 18:51:20 EDT Received: from SAIL.STANFORD.EDU by REAGAN.AI.MIT.EDU via INTERNET with SMTP id 110960; 10 May 88 18:43:42 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 10 May 88 14:18:51 PDT Received: from relay2.cs.net by RELAY.CS.NET id an15217; 10 May 88 17:15 EDT Received: from cs.umass.edu by RELAY.CS.NET id ai02249; 10 May 88 16:51 EDT Date: Tue, 10 May 88 15:44 EDT From: ELIOT@cs.umass.edu Subject: Constant-Function To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.EDU" From: IN%"edsel!jonl@labrea.stanford.EDU" "Jon L White" 10-MAY-1988 re: Basically, a compiler can't make *any* assumptions at all about a function it is compiling a call to without assuming "constant-function" also. This is as true of FTYPE and INLINE declarations as it would be for the more limiting items you mention like number of required arguments, etc. This is not true. If there has been an FTYPE declaration, the compiler may make assumptions about the types of arguments and values of a function, but certainly not about the implementation. I fail to see your point, since the compiler will also have to assume that the function won't be redefined incompatibly. I hate to keep harping on a point, but the first two lines I sent out on this topic say just about all there is to be said: Isn't it the case that *any* proclaim about a function is equivalent to saying that that aspect of the function is "constant"? Knowing the FTYPE of sqrt does not allow a compiler to substitute 2.23 for (sqrt 5). You might redefine SQRT as SIN without violating the FTYPE. Declaring SQRT a 'constant-function' does make this legitimate (as would 'inline'.) Thus FTYPE declarations absolutely *do not* imply 'Constant-Function' declarations. Comments by Zacharis and Hornig also confirm that CONSTANT-FUNCTION as a declaration gives you nothing beyond what is already implicit in the collection of INLINE, FTYPE etc.; and CONSTANT-FUNCTION by itself cannot substitute for any one of them individually. I particularly like Hornig's explanation that unless the user explicitly declares a name NOTINLINE, the symbolics compiler will make whatever assumptions of constantness it feels like. You may not even know which aspect is relevant. Some Symbolics users use ' in place of #' to get around this bug. (!) I think it exists exactly because the 'constant-function' declaration is missing, so there has not been a good global way to make it happen legitimately. I certainly hope I never see a compiler that feels it can open-code a random DEFUN without some sort of legitimizing declaration. That's what zl:defsubst, 'inline' and 'constant-function' are for. 'Inline' is a mistake. It specifies "that it is desirable for the compiler to open-code calls to the specified functions" (CLtL 159). This is a kludge. It expresses the fact that the functions are 'constant-functions' but then it goes too far and tries to tell the compiler what to do with that knowledge. 'Constant-Function' is clean. It says exactly what you mean, declaratively, without trying to interfere with the compiler's decision about how to use the information. The compiler is in a much better position to decide whether it is "desirable" to open-code a function. It can look at the speed/space optimization settings, the body of the function and predicted code simplifications after the substitution. 'Constant-Function' should be thought of as a primitive for declaring where the current boundary of a layered system lies. I might put these forms into my INIT file: (defun fix-base-system (pkg) (do-all-external-symbols (sym pkg) (when (fboundp sym) (proclaim (list 'constant-function sym)))))) (fix-base-system 'lisp) (fix-base-system 'kee) (fix-base-system 'umass-utilities) It doesn't make sense to do wholesale proclamations like this using 'inline'. To me FORMAT is a 'constant-function' but it is not "desirable for the compiler to open-code calls to" FORMAT. Many other functions should be considered part of the fixed base that I am building a system on, without being "desirable" subjects for open-coding. I think that a compiler should avoid doing anything that affects tracability/redefinability until a function has been declared a 'constant-function'. After that it may be desirable to declare some 'constant functions' as 'inline' to encourage open-coding in situations where the compiler's normal decision is wrong or not trusted.  Received: from REAGAN.AI.MIT.EDU (CHAOS 13065) by AI.AI.MIT.EDU 10 May 88 18:51:07 EDT Received: from SAIL.STANFORD.EDU by REAGAN.AI.MIT.EDU via INTERNET with SMTP id 110959; 10 May 88 18:41:43 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 10 May 88 13:33:38 PDT Received: by labrea.stanford.edu; Tue, 10 May 88 13:33:47 PDT Received: from bhopal.lucid.com by edsel id AA28279g; Tue, 10 May 88 13:26:26 PDT Received: by bhopal id AA16644g; Tue, 10 May 88 13:29:25 PDT Date: Tue, 10 May 88 13:29:25 PDT From: Jon L White Message-Id: <8805102029.AA16644@bhopal.lucid.com> To: ELIOT@cs.umass.edu Cc: common-lisp@sail.stanford.edu In-Reply-To: ELIOT@cs.umass.edu's message of Sun, 8 May 88 12:51 EDT <8805100526.AA25256@edsel.lucid.com> Subject: [Reducible declaration? and] Constant-Function re: I think there should be some way to closely associate global declaration-type stuff with a function's definition. . . . Of course, the world will not come to an end because people have to use a separate proclaim. I just think it would be nicer to put everything about a function definition into a single form. This is a very good point. Perhaps the bottleneck is that CL can't agree to semantics for *any* declaration (except for SPECIAL); some compiler's basically throw all declarations away (except for SPECIAL). re: Another solution is to define a macro encapsulaing the DEFUN and PROCLAIM. . . . I also don't have a good name for such a macro. 'Defconfun' is rather bletcherous. 'define' would do, but Sussman's students would start schemeing against me. Part of the problem I've been having with the "constant function" declaration is it's vagueness. In your original message you characterized it as "won't redefine the function at runtime"; but as subsequent dialogue shows, there is very little feeling that that implies anything worthwhile beyond what the existing declarations (like ftype, speed/safety etc) provide. "Never redefine, at all, ever" is just too stringent to be useful. Further, my assumption that "Never redefine" characterizes the meaning you intended seems to have caused confusion, as evidenced by replies by others; in particular, some (perhaps yourself?) are primarily concerned with the stability of the argument spectrum, so that a compiler *might* be licensed to use a different function-to-function protocol. Maybe I'm confused here too, in which case I'll just drop this line of reasoning; but isn't argument spectra information is already specifiable via the ftype declaration? I tried to suggest that maybe you wanted to cover the case that is currently not covered by any CL declaration -- that of "constant folding" (barmar called it "reducible"; but his example failed to fold the constant form -- it only coalesced common subexpressions). Such "constant folding" at compile time is a critical component of Lucid's optimizing compiler; but the data- base of what is "foldable" isn't user-accessible. There is currently no CL declaration that covers this case. Accepting barmar's terminology, I see a reasonable place for a REDUCIBLE declaration; would you? -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 10 May 88 17:27:16 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 10 May 88 14:08:45 PDT Received: by labrea.stanford.edu; Tue, 10 May 88 14:08:55 PDT Received: from bhopal.lucid.com by edsel id AA28337g; Tue, 10 May 88 13:59:43 PDT Received: by bhopal id AA16844g; Tue, 10 May 88 14:02:42 PDT Date: Tue, 10 May 88 14:02:42 PDT From: Jon L White Message-Id: <8805102102.AA16844@bhopal.lucid.com> To: mcvax!harlqn.co.uk!andrew@uunet.uu.net Cc: common-lisp@sail.stanford.edu In-Reply-To: Andrew Watson's message of Mon, 9 May 88 15:45:46 BST <8805091445.AA12859@jung.harlqn.uucp> Subject: Features re: *features* . . . It is unclear to me from this whether an implementation should compare the features as the symbols themselves or as their printnames. Lucid does the latter, which seems more reasonable given the potential for confusion involving packages. They also put their features in the keyword package, which is good defensive programming. Lucid Common Lisp uses MEMBER as the test of *features* entry; and for symbols, this becomes an EQ check, rather than "same-printname-p"; it also implements the x3j13 proposal described in the next paragraph. X3J13 is considering a proposal to require the setting of *package* to be the KEYWORD package during the scope of reading the forms under a #+ or a #-. This will tend to give the appearance of "namestring" comparison rather than EQ only because, for example, #+LUCID will be read in the feature as :LUCID, and the search on *features* will be for that symbol. The X3J13 proposal would permit reading in feature names like #+MACSYMA:HYPERLINEAR, in which case the member test would be with the symbol MACSYMA:HYPERLINEAR. Since *features* is an ordinary special variable (no contradiction in terms, I hope! I only mean to say that it is "bindable" and not restricted to being a "global" parameter), then nothing prevents you from pushing all kinds of garbage on it. Say, 3.14159. But no consensus exists yet as to how the #+ and #- syntax might interface to non-symbol entries. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 10 May 88 07:41:50 EDT Date: 09 May 88 2234 PDT From: System Files Subject: [not about] Constant Functions Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 9 May 88 22:32:56 PDT Received: by labrea.stanford.edu; Mon, 9 May 88 22:33:04 PDT Received: from bhopal.lucid.com by edsel id AA25236g; Mon, 9 May 88 22:22:41 PDT Received: by bhopal id AA14330g; Mon, 9 May 88 22:25:38 PDT Date: Mon, 9 May 88 22:25:38 PDT From: Jon L White Message-Id: <8805100525.AA14330@bhopal.lucid.com> To: Moon@stony-brook.scrc.symbolics.com Cc: barmar@think.com, ELIOT@cs.umass.edu, common-lisp@sail.stanford.edu In-Reply-To: David A. Moon's message of Mon, 9 May 88 21:25 EDT <19880510012540.8.MOON@EUPHRATES.SCRC.Symbolics.COM> Subject: [not about] Constant Functions re: Extended the way implied by barmar, it's also a declaration; see CLtL p158. I should just not answer this, but read table 4-1 and then resend your message. You did read the phrase of my message "Extended the way implied by barmar ..." didn't you? And you did notice his confession that this extension isn't part of Common Lisp? -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 10 May 88 07:40:35 EDT Date: 09 May 88 1420 PDT From: System Files Subject: Constant Functions Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 9 May 88 14:20:09 PDT Received: by labrea.stanford.edu; Mon, 9 May 88 14:20:14 PDT Received: from bhopal.lucid.com by edsel id AA23164g; Mon, 9 May 88 13:57:53 PDT Received: by bhopal id AA12572g; Mon, 9 May 88 14:00:48 PDT Date: Mon, 9 May 88 14:00:48 PDT From: Jon L White Message-Id: <8805092100.AA12572@bhopal.lucid.com> To: barmar@think.com Cc: ELIOT@cs.umass.edu, common-lisp@sail.stanford.edu In-Reply-To: Barry Margolin's message of Sun, 8 May 88 00:07:09 EDT <8805080407.AA26147@fafnir.think.com> Subject: Constant Functions re: Basically, a compiler can't make *any* assumptions at all about a function it is compiling a call to without assuming "constant-function" also. This is as true of FTYPE and INLINE declarations as it would be for the more limiting items you mention like number of required arguments, etc. This is not true. If there has been an FTYPE declaration, the compiler may make assumptions about the types of arguments and values of a function, but certainly not about the implementation. I fail to see your point, since the compiler will also have to assume that the function won't be redefined incompatibly. I hate to keep harping on a point, but the first two lines I sent out on this topic say just about all there is to be said: Isn't it the case that *any* proclaim about a function is equivalent to saying that that aspect of the function is "constant"? Comments by Zacharis and Hornig also confirm that CONSTANT-FUNCTION as a declaration gives you nothing beyond what is already implicit in the collection of INLINE, FTYPE etc.; and CONSTANT-FUNCTION by itself cannot substitute for any one of them individually. I particularly like Hornig's explanation that unless the user explicitly declares a name NOTINLINE, the symbolics compiler will make whatever assumptions of constantness it feels like. You may not even know which aspect is relevant. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 10 May 88 04:08:34 EDT Received: from MCC.COM by SAIL.Stanford.EDU with TCP; 10 May 88 00:54:25 PDT Received: from BRAHMA.ACA.MCC.COM by MCC.COM with TCP/SMTP; Tue 10 May 88 02:53:29-CDT Date: Tue, 10 May 88 02:53 CDT From: David Vinayak Wallace Subject: Features To: Andrew Watson cc: common-lisp@sail.stanford.edu In-Reply-To: <8805091445.AA12859@jung.harlqn.uucp> Message-ID: <880510025324.6.GUMBY@BRAHMA.ACA.MCC.COM> Date: Mon, 9 May 88 15:45:46 BST From: Andrew Watson I'm answering these in the opposite order to that in which you asked them: And *features* (p448): "The value of the variable *features* should be a list of symbols that name 'features' provided by the implementation." It'd be nice to mark feaures on this list with honest-to-god symbols, to reduce name collision. On the other hand you want to be able to check this list at runtime, (perhaps to see whether or not to load something) as well as at compile-time. Presumably the relevent package won't be available until the feature itself has been loaded. (i.e. if MACLISP had had packages, it wouldn't have made sense to do (COND ((NOT (STAUS FEATURE FORMAT:FORMAT)) (LOAD '(FORMAT)))) since the FORMAT package probably wouldn't yet have been loaded.) So features are really strings in one namespace; since the Book says they should be symbols there are really only four portable packages into which one may safely intern them. You might as well use keyword; it's the safest bet. One reason that forcing them to be symbols is not a bad idea is that it encourages people to use names which are easy to type, though this isn't really that important. Steele (p358) on the 'feature' in the #+ read-time conditionalization facility: "The feature should be the printed representation of a symbol or list. If feature is a symbol, then it is true if and only if it is a member of the list that is the value of the global variable *features*." This is the other good reason to make them symbols; hopefully INTERN is at least as fast as string-equal; plus you'll only have to do it once per #-/+. Hence the reader macro can do (MEMBER (INTERN (READ-SYMBOL BLAH) *THE-KEYWORD-PACKAGE*) *FEATURES*) rather than (MEMBER ... :KEY #'STRING-EQUAL). It is unclear to me from this whether an implementation should compare the features as the symbols themselves or as their printnames. So it seems best to assume (I assume that you're implementing this feature for Harlequin) that *features* will contain only keywords and that you can intern what follows #+/- in KEYWORD and search the list with EQ. Note that some lisps don't behave this way, so you'll have to defend agains them. Reading a package qualifier and throwing it away would probably be OK. I hope the CL cleanup committee takes care of this. Now, what reader syntax should you use to access the *bugs* list?  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 10 May 88 02:30:56 EDT Received: from uunet.UU.NET by SAIL.Stanford.EDU with TCP; 9 May 88 23:16:09 PDT Received: from mcvax.UUCP by uunet.UU.NET (5.54/1.14) with UUCP id AA23108; Tue, 10 May 88 00:21:52 EDT Received: by mcvax.cwi.nl; Tue, 10 May 88 04:42:15 +0200 (MET) Received: from cl.cam.ac.uk by kestrel.Ukc.AC.UK via Janet (UKC CAMEL FTP) id aa01520; 9 May 88 20:35 BST Via: harlqn; 9 May 88 18:43 BST (UK.AC.Cam.Cl.gnnt) Received: from jung.harlqn.uucp (jung) by harlqn.uucp; Mon, 9 May 88 15:46:18 BST Received: by jung.harlqn.uucp (3.2/SMI-3.2) id AA12859; Mon, 9 May 88 15:45:46 BST Date: Mon, 9 May 88 15:45:46 BST From: Andrew Watson Message-Id: <8805091445.AA12859@jung.harlqn.uucp> To: common-lisp@sail.stanford.edu Subject: Features Steele (p358) on the 'feature' in the #+ read-time conditionalization facility: "The feature should be the printed representation of a symbol or list. If feature is a symbol, then it is true if and only if it is a member of the list that is the value of the global variable *features*." And *features* (p448): "The value of the variable *features* should be a list of symbols that name 'features' provided by the implementation." It is unclear to me from this whether an implementation should compare the features as the symbols themselves or as their printnames. Lucid does the latter, which seems more reasonable given the potential for confusion involving packages. They also put their features in the keyword package, which is good defensive programming. Though a small point, this is rather important for portable code. Comments anyone? Regards, Andrew. +-----------------------------------------------------------------------------+ | Andrew Watson, andrew@uk.co.harlqn | | Harlequin Ltd, Tel: +44 223 872522 | | Cambridge, UK Fax: +44 223 872519 | +-----------------------------------------------------------------------------+  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 10 May 88 01:49:57 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 9 May 88 22:16:20 PDT Received: from relay2.cs.net by RELAY.CS.NET id aj02908; 10 May 88 1:11 EDT Received: from cs.umass.edu by RELAY.CS.NET id bg03727; 10 May 88 1:06 EDT Date: Sun, 8 May 88 12:51 EDT From: ELIOT@cs.umass.edu Subject: Constant-Function To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.EDU" From: IN%"edsel!jonl@labrea.stanford.EDU" "Jon L White" 6-MAY-1988 Isn't it the case that *any* proclaim about a function is equivalent to saying that that aspect of the function is "constant"? Yes, I think this is true. What you are looking for is a way to say that "constant folding" is ok; of course, the function must be defined and usable in the compilation environment for this to work. Generally speaking, "constant folding" is ok as long as the function is side-effect free; so maybe that is the declaration you want? No. I think my proposal is more general than that. At any point when I am writing a large program I know that 50-90% of the functions are "mature" and very unlikely to be changed, except perhaps for optimizations. I want a way to tell that to the compiler. re: The declaration (CONSTANT-FUNCTION foo) . . . With SPACE=0, SPEED=3 this should be equivalent to an INLINE declaration. I don't think so, ... This is based upon a strict reading of CLtL P.160 about Declare Optimize. "The value 0 means that the quality is TOTALLY unimportant." I think a common-sense clause might be added to this description. Clearly we don't want compilers to use up exponentially large amounts of space when given a (declare (optimize (space 0))) I see 'inline' and 'constant-function' as independent dimensions. I think there are some close connections. 'inline' implies 'constant-function' and 'constant-function' allows (but doesn't require) 'inline' compilation. Small 'constant-function's would likely be compiled 'inline'. re: As a special case (declare constant-function) in a DEFUN is equivalent to both a proclaim and the defun. This is too special-casey. Any declare in a DEFUN (or any other place that admits 'declare') should have only local, lexical scope; or at least, so I think. That is a reasonable interpretation of declare, but I think there should be some way to closely associate global declaration-type stuff with a function's definition. For example, make-array, defstruct and (ZL) defflavor have syntactic places for arbitrary declarations about the new entity. DEFUN does not except, perhaps, using an embedded DECLARE. Of course, the world will not come to an end because people have to use a separate proclaim. I just think it would be nicer to put everything about a function definition into a single form. Another solution is to define a macro encapsulaing the DEFUN and PROCLAIM. For example ZL defsubst could be implemented this way quite trivially. I have a more radical (sounding) proposal that builds on this. I don't have time to defend it, so I am hoping that it will grow out of the discussion naturally. I also don't have a good name for such a macro. 'Defconfun' is rather bletcherous. 'define' would do, but Sussman's students would start schemeing against me.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 9 May 88 21:40:10 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 9 May 88 18:27:42 PDT Received: from EUPHRATES.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 401217; Mon 9-May-88 21:25:50 EDT Date: Mon, 9 May 88 21:25 EDT From: David A. Moon Subject: [not about] Constant Functions To: Jon L White cc: barmar@think.com, ELIOT@cs.umass.edu, common-lisp@SAIL.STANFORD.EDU In-Reply-To: <8805092017.AA12364@bhopal.lucid.com> Message-ID: <19880510012540.8.MOON@EUPHRATES.SCRC.Symbolics.COM> Date: Mon, 9 May 88 13:17:35 PDT From: Jon L White re: Date: Sat, 7 May 88 03:13:06 PDT From: Jon L White CLtL, p162 speaks of the VALUES declaration; it says nothing at all like that. That's a type-specifier, not a declaration. Extended the way implied by barmar, it's also a declaration; see CLtL p158. Just for the record, when one can do (DECLARE ( X Y Z)), one usually speaks of this as the declaration, even when is basically a type-specifier. The rationale is apparently that this form is an abbreviation for (DECLARE (TYPE X Y Z)). I should just not answer this, but read table 4-1 and then resend your message.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 9 May 88 17:32:42 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 9 May 88 14:16:18 PDT Received: by labrea.stanford.edu; Mon, 9 May 88 14:16:25 PDT Received: from bhopal.lucid.com by edsel id AA22951g; Mon, 9 May 88 13:14:41 PDT Received: by bhopal id AA12364g; Mon, 9 May 88 13:17:35 PDT Date: Mon, 9 May 88 13:17:35 PDT From: Jon L White Message-Id: <8805092017.AA12364@bhopal.lucid.com> To: Moon@stony-brook.scrc.symbolics.com Cc: barmar@think.com, ELIOT@cs.umass.edu, common-lisp@sail.stanford.edu In-Reply-To: David A. Moon's message of Mon, 9 May 88 12:24 EDT <19880509162404.9.MOON@EUPHRATES.SCRC.Symbolics.COM> Subject: [not about] Constant Functions re: Date: Sat, 7 May 88 03:13:06 PDT From: Jon L White CLtL, p162 speaks of the VALUES declaration; it says nothing at all like that. That's a type-specifier, not a declaration. Extended the way implied by barmar, it's also a declaration; see CLtL p158. Just for the record, when one can do (DECLARE ( X Y Z)), one usually speaks of this as the declaration, even when is basically a type-specifier. The rationale is apparently that this form is an abbreviation for (DECLARE (TYPE X Y Z)). re: One could introduce a different word for this type of declaration, instead of using DECLARE, but I think that would be more confusing than enlightening. DECLARE is good enough. I'm happy to see that Symbolics didn't perpetrate the lossage implied in recent messages that such a declare would be equivalent to a (non-lexical) PROCLAIM. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 9 May 88 12:45:37 EDT Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 9 May 88 09:26:06 PDT Received: from EUPHRATES.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 400672; Mon 9-May-88 12:24:29 EDT Date: Mon, 9 May 88 12:24 EDT From: David A. Moon Subject: [not about] Constant Functions To: Barry Margolin , edsel!jonl@labrea.stanford.edu cc: ELIOT@cs.umass.edu, common-lisp@SAIL.STANFORD.EDU In-Reply-To: <8805080407.AA26147@fafnir.think.com> Message-ID: <19880509162404.9.MOON@EUPHRATES.SCRC.Symbolics.COM> Date: Sun, 8 May 88 00:07:09 EDT From: Barry Margolin Date: Sat, 7 May 88 03:13:06 PDT From: Jon L White CLtL, p162 speaks of the VALUES declaration; it says nothing at all like that. That's a type-specifier, not a declaration. Sorry, I was thinking of Symbolics's VALUES declaration. They allow: (defun fun (arg) (declare (values name1 name2)) ...) Symbolics has a large number of declarations that specify aspects of the function being defined. However, I now realize that none of the standard CL declarations behave like this. Note that it would be wrong to say that such declarations are not lexically scoped. The declarations are attached to a particular binding of the name "fun" to a function definition, and they have the same scope as that binding. Another way of saying roughly the same thing is that the definitions are attached to the function object, not to the function name. This is a better way to think of it, since such declarations work in LAMBDA expressions as well, which don't have names. One could introduce a different word for this type of declaration, instead of using DECLARE, but I think that would be more confusing than enlightening.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 9 May 88 12:45:32 EDT Received: from ALDERAAN.SCRC.Symbolics.COM ([128.81.41.109]) by SAIL.Stanford.EDU with TCP; 9 May 88 09:26:11 PDT Received: from WINTER.SCRC.Symbolics.COM by ALDERAAN.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 191680; Mon 9-May-88 10:51:48 EDT Date: Mon, 9 May 88 10:51 EDT From: Charles Hornig Subject: Re: Constant Functions To: Rob.MacLachlan@WB1.CS.CMU.EDU, Gail Zacharias cc: edsel!jonl@labrea.stanford.edu, barmar@think.com, ELIOT@cs.umass.edu, common-lisp@sail.stanford.edu In-Reply-To: The message of 7 May 88 13:59 EDT from Rob.MacLachlan@WB1.CS.CMU.EDU Message-ID: <19880509145146.1.HORNIG@WINTER.SCRC.Symbolics.COM> The approach we have taken at Symbolics is that all function references are assumed to be "constant" unless they are declared (or proclaimed) to be NOTINLINE. The idea is that failing to indirect through the function cell is a minor form of inlining. This has several advantages: The "constant" case is by far the most common in normal code. Avoiding a user declaration here is very important. We use an existing declaration which already has the desired meaning. Declaring a function NOTINLINE is the standard way to make it traceable and (as we see it) replaceable. The environment does not have to carry this too far. Our environment supports redefinition at the user level (compiling a new definition from the editor) even when it doesn't at the code level (SETF (SYMBOL-FUNCTION ...) ...).  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 May 88 00:22:36 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 7 May 88 21:09:08 PDT Received: from fafnir.think.com by Think.COM; Sun, 8 May 88 00:07:13 EDT Return-Path: Received: by fafnir.think.com; Sun, 8 May 88 00:07:09 EDT Date: Sun, 8 May 88 00:07:09 EDT From: Barry Margolin Message-Id: <8805080407.AA26147@fafnir.think.com> To: edsel!jonl@labrea.stanford.edu Cc: ELIOT@cs.umass.edu, common-lisp@sail.stanford.edu In-Reply-To: Jon L White's message of Sat, 7 May 88 03:13:06 PDT <8805071013.AA05614@bhopal.lucid.com> Subject: Constant Functions Date: Sat, 7 May 88 03:13:06 PDT From: Jon L White I think you may have missed the thrust of my critique of Eliot's proposal. It sarted out like this: Isn't it the case that *any* proclaim about a function is equivalent to saying that that aspect of the function is "constant"? I didn't address that part of your message in my response because I agreed with it. That didn't seem to be the main thrust of your message, though; you then went on to describe in detail a particular type of optimization that seemed to be what you thought he was proposing. Basically, a compiler can't make *any* assumptions at all about a function it is compiling a call to without assuming "constant-function" also. This is as true of FTYPE and INLINE declarations as it would be for the more limiting items you mention like number of required arguments, etc. This is not true. If there has been an FTYPE declaration, the compiler may make assumptions about the types of arguments and values of a function, but certainly not about the implementation. Similarly, an INLINE declaration must already imply "constant function"; but my critique claims that a general "constant function" declaration must not by itself imply INLINE. He merely suggested that "constant function" + speed=3 + space=0 might cause a compiler to open-code. Remember how he first introduced his idea: he wanted a declaration that encompassed everything that INLINE does, except that it wouldn't FORCE open-coding. However, a compiler might decide to open-code based on other factors, such as optimization levels. Of course, it should be ok to redefine a "constant function" providing the particular assumptions made during compilation aren't changed. That leaves very little you can do to a function that has been inline'd. Or to a function that has been declared CONSTANT-FUNCTION. re: That's already not true of the VALUES declaration. It specifies an attribute of the function being defined, just as Eliot was suggesting above. CLtL, p162 speaks of the VALUES declaration; it says nothing at all like that. Would you like to try again to say what you meant? Remember also that Eliot was suggesting that a such a declare be equivalent to a proclaim (which modifies a global database) and that would give it indefinite scope; but every other declare is lexically scoped. Sorry, I was thinking of Symbolics's VALUES declaration. They allow: (defun fun (arg) (declare (values name1 name2)) ...) Symbolics has a large number of declarations that specify aspects of the function being defined. However, I now realize that none of the standard CL declarations behave like this. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 May 88 14:10:03 EDT Received: from FRED.SLISP.CS.CMU.EDU by SAIL.Stanford.EDU with TCP; 7 May 88 10:59:26 PDT Received: from FRED.SLISP.CS.CMU.EDU by FRED.SLISP.CS.CMU.EDU; 7 May 88 14:00:27 EDT To: gz@spt.entity.com (Gail Zacharias) cc: edsel!jonl@labrea.stanford.edu, barmar@think.com, ELIOT@cs.umass.edu, common-lisp@sail.stanford.edu Subject: Re: Constant Functions In-reply-to: Your message of Sat, 07 May 88 12:41:12 -0400. <8805071241.AA26134@spt.entity.com> Date: Sat, 07 May 88 13:59:52 EDT From: Rob.MacLachlan@WB1.CS.CMU.EDU I agree with your analysis of the meaning of a function constant declaration, but not with your comments on the desirability of standardizing something of the sort. I agree that the most common way of using this sort of knowledge would be a "block compliation" mode, but I think finer granularity of control is also useful. In my compiler cleanup proposal, I suggest an "integration level" that ranges from 0 to 3 (like an optimization quality). Any value greater than 0 allows the compiler to assume the function is constant, but increasing values suggest increased inclination toward inline expansion. There is also a "default integration level", which can be set by a proclamation and applies to subsequently compiled DEFUNs. It is worth standardizing on something of the sort insofar as it helps in the writing of portable programs. Programs the redefine functions at run time may not run in implementations that assume functions are constant. This means that Common Lisp programs may only work in "go slow" mode. If I were designing a new Lisp dialect, I would definitely have the function defining form implicitly declare the function variable constant. It is probably too late to make anything this sensible be the default in Common Lisp, but it could be added as an upward compatible extension. The 99.99 percent of programs that don't redefine functions could then have: (PROCLAIM '(DEFAULT-INTEGRATION-LEVEL 1)) added at the beginning of the file, and could run fast. Rob  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 May 88 13:11:52 EDT Received: from EDDIE.MIT.EDU by SAIL.Stanford.EDU with TCP; 7 May 88 09:59:56 PDT Received: by EDDIE.MIT.EDU with UUCP with smail2.5 with sendmail-5.45/4.7 id ; Sat, 7 May 88 12:56:56 EDT Received: by spt.entity.com (smail2.5); 7 May 88 12:41:12 EDT (Sat) To: edsel!jonl@labrea.stanford.edu Cc: barmar@think.com, ELIOT@cs.umass.edu, common-lisp@sail.stanford.edu In-Reply-To: Jon L White's message of Sat, 7 May 88 03:13:06 PDT <8805071013.AA05614@bhopal.lucid.com> Subject: Constant Functions Message-Id: <8805071241.AA26134@spt.entity.com> Date: 7 May 88 12:41:12 EDT (Sat) From: gz@spt.entity.com (Gail Zacharias) I believe the point of a CONSTANT-FUNCTION declaration would be to allow references to the function cell of a symbol to be replaced with its compile-time contents (or moral equivalent thereof). I.e. to tell the compiler that it can replace (FOO ...) with (FUNCALL '# ...). This is very different from declaring, say, that FOO returns a float. That certainly doesn't give the compiler license to assume that I will never redefine FOO, just that any definition I ever give it will be a float-returning-function. Regarding inlining, I think it is perfectly valid for a compiler to inline explicit constant references to compiled functions (i.e. references of the form '#) since there is nothing in common lisp that would allow you to tell the difference. Allowing CONSTANT-FUNCTION's to get inlined under some SPEED/SPACE settings would just be a special case of that. Having said all that, I don't think a CONSTANT-FUNCTION declaration would be very useful. Unlike variables, most functions in most programs are constant (once debugging is done), and you don't really want to maintain huge sets of CONSTANT-FUNCTION declarations all over the place (that you have to keep turning off when you need to debug). I think it would be more useful to have some syntax for requesting block compilation of a file or a set of files (presumably with some argument to compile-file), and a way to declare exceptions (for which purpose NOTINLINE declarations seem to be the defacto standard). I don't really see any need here for language extensions, since requesting block compilation is sort of an environmental issue that I don't think needs to be standardized; and for the exceptions, NOTINLINE will do fine since any implementation that 'snaps links' on functions declared NOTINLINE is asking to lose anyway given current usage.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 May 88 08:08:14 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 7 May 88 04:56:34 PDT Received: by labrea.stanford.edu; Sat, 7 May 88 04:56:42 PDT Received: from bhopal.lucid.com by edsel id AA13963g; Sat, 7 May 88 03:10:22 PDT Received: by bhopal id AA05614g; Sat, 7 May 88 03:13:06 PDT Date: Sat, 7 May 88 03:13:06 PDT From: Jon L White Message-Id: <8805071013.AA05614@bhopal.lucid.com> To: barmar@think.com Cc: ELIOT@cs.umass.edu, common-lisp@sail.stanford.edu In-Reply-To: Barry Margolin's message of Fri, 6 May 88 17:34 EDT <19880506213427.6.BARMAR@OCCAM.THINK.COM> Subject: Constant Functions I think you may have missed the thrust of my critique of Eliot's proposal. It sarted out like this: Isn't it the case that *any* proclaim about a function is equivalent to saying that that aspect of the function is "constant"? Basically, a compiler can't make *any* assumptions at all about a function it is compiling a call to without assuming "constant-function" also. This is as true of FTYPE and INLINE declarations as it would be for the more limiting items you mention like number of required arguments, etc. Similarly, an INLINE declaration must already imply "constant function"; but my critique claims that a general "constant function" declaration must not by itself imply INLINE. Of course, it should be ok to redefine a "constant function" providing the particular assumptions made during compilation aren't changed. That leaves very little you can do to a function that has been inline'd. re: That's already not true of the VALUES declaration. It specifies an attribute of the function being defined, just as Eliot was suggesting above. CLtL, p162 speaks of the VALUES declaration; it says nothing at all like that. Would you like to try again to say what you meant? Remember also that Eliot was suggesting that a such a declare be equivalent to a proclaim (which modifies a global database) and that would give it indefinite scope; but every other declare is lexically scoped. -- JonL--  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 6 May 88 17:48:37 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 6 May 88 14:34:39 PDT Received: from fafnir.think.com by Think.COM; Fri, 6 May 88 17:33:04 EDT Return-Path: Received: from OCCAM.THINK.COM by fafnir.think.com; Fri, 6 May 88 17:32:57 EDT Date: Fri, 6 May 88 17:34 EDT From: Barry Margolin Subject: Constant Functions To: Jon L White Cc: ELIOT@cs.umass.edu, common-lisp@sail.stanford.edu In-Reply-To: <8805060205.AA29673@bhopal.lucid.com> Message-Id: <19880506213427.6.BARMAR@OCCAM.THINK.COM> Date: Thu, 5 May 88 19:05:54 PDT From: Jon L White Isn't it the case that *any* proclaim about a function is equivalent to saying that that aspect of the function is "constant"? What you are looking for is a way to say that "constant folding" is ok; of course, the function must be defined and usable in the compilation environment for this to work. Generally speaking, "constant folding" is ok as long as the function is side-effect free; so maybe that is the declaration you want? This isn't how I interpreted Eliot's CONSTANT-FUNCTION request. In Multics PL/I, we called the above "reducible". If the compiler knows that a function is reducible, then it can use common subexpression elimination to optimize multiple calls, e.g. (+ (red-fun 10) (red-fun 10)) could be optimized to (* (red-fun 10) 2). But that's not what Eliot was talking about. His CONSTANT-FUNCTION declaration promises that a function is not going to be redefined, so the compiler may build in assumptions about things like the calling sequence, the location of the code, etc. It is the case that if the compiler does flow analysis and can determine that a function is reducible on its own (for example, if a function references no free variables and only calls reducible functions, it is also reducible), then a CONSTANT-FUNCTION declaration would also allow the compiler to make optimizations based on the reducibility. If the function happens to be reducible, but not declared CONSTANT-FUNCTION, the compiler can't make the optimization because the function might be redefined to a non-reducible function. re: The declaration (CONSTANT-FUNCTION foo) . . . With SPACE=0, SPEED=3 this should be equivalent to an INLINE declaration. I think "should" should be "could". CL doesn't yet specify the precise meaning of the various optimization levels, so it would be up to an implementor to decide that this combination means that it should inline-code all constant functions. I don't think so, or at least not if what you primarily want is a way to legitimze "constant folding". For example, (defun run-around-and-double (x) ...lots of contorted code ... ... ultimately returning (* 2 x) ... ) Then declaring this a constant-function should permit the compiler to convert (run-around-and-double '6) into '12; but hopefully wouldn't cause in-lining of (run-around-and-double x). I see 'inline' and 'constant-function' as independent dimensions. I agree with Eliot's original statement. However, your version follows as a natural occurrence. If the compiler is smart enough to determine that RUN-AROUND-AND-DOUBLE does nothing but return its argument doubled, then it should be able to determine this about the inline-substituted code, too. re: As a special case (declare constant-function) in a DEFUN is equivalent to both a proclaim and the defun. This is too special-casey. Any declare in a DEFUN (or any other place that admits 'declare') should have only local, lexical scope; or at least, so I think. That's already not true of the VALUES declaration. It specifies an attribute of the function being defined, just as Eliot was suggesting above. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 6 May 88 14:34:03 EDT Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 6 May 88 11:15:36 PDT Received: from cvaxa.sussex.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP id aa09773; 6 May 88 18:19 BST Received: from csuna (csuna.ARPA) by cvaxa.sussex.ac.uk; Fri, 6 May 88 17:34:50 bst From: John Williams Date: Fri, 6 May 88 12:07:14 BST Message-Id: <14798.8805061107@csuna.cvaxa.sussex.ac.uk> To: common-lisp@sail.stanford.edu Subject: constant-function A CONSTANT-FUNCTION declaration might save an indirection on function call. Also, it would enable the compiler to make use of information about a function that it (the compiler) has worked out for itself. For example, in my Common Lisp, more efficient function calling code can be planted if the compiler knows how many results a function will return. For many function definitions, the compiler can deduce the number of results. But without some kind of CONSTANT-FUNCTION declaration, this information can not be acted upon. john  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 5 May 88 22:49:41 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 5 May 88 19:15:53 PDT Received: by labrea.stanford.edu; Thu, 5 May 88 19:15:14 PDT Received: from bhopal.lucid.com by edsel id AA06909g; Thu, 5 May 88 19:03:16 PDT Received: by bhopal id AA29673g; Thu, 5 May 88 19:05:54 PDT Date: Thu, 5 May 88 19:05:54 PDT From: Jon L White Message-Id: <8805060205.AA29673@bhopal.lucid.com> To: ELIOT@cs.umass.edu Cc: common-lisp@sail.stanford.edu In-Reply-To: ELIOT@cs.umass.edu's message of Wed, 4 May 88 10:35 EDT <8805051650.AA04252@edsel.lucid.com> Subject: Constant Functions Isn't it the case that *any* proclaim about a function is equivalent to saying that that aspect of the function is "constant"? What you are looking for is a way to say that "constant folding" is ok; of course, the function must be defined and usable in the compilation environment for this to work. Generally speaking, "constant folding" is ok as long as the function is side-effect free; so maybe that is the declaration you want? re: The declaration (CONSTANT-FUNCTION foo) . . . With SPACE=0, SPEED=3 this should be equivalent to an INLINE declaration. I don't think so, or at least not if what you primarily want is a way to legitimze "constant folding". For example, (defun run-around-and-double (x) ...lots of contorted code ... ... ultimately returning (* 2 x) ... ) Then declaring this a constant-function should permit the compiler to convert (run-around-and-double '6) into '12; but hopefully wouldn't cause in-lining of (run-around-and-double x). I see 'inline' and 'constant-function' as independent dimensions. re: As a special case (declare constant-function) in a DEFUN is equivalent to both a proclaim and the defun. This is too special-casey. Any declare in a DEFUN (or any other place that admits 'declare') should have only local, lexical scope; or at least, so I think. -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 5 May 88 22:48:27 EDT Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 5 May 88 17:39:54 PDT Received: by labrea.stanford.edu; Thu, 5 May 88 17:39:28 PDT Received: from bhopal.lucid.com by edsel id AA06119g; Thu, 5 May 88 17:27:51 PDT Received: by bhopal id AA29328g; Thu, 5 May 88 17:30:29 PDT Date: Thu, 5 May 88 17:30:29 PDT From: Jon L White Message-Id: <8805060030.AA29328@bhopal.lucid.com> To: common-lisp@sail.stanford.edu Subject: Industrial-strength Lisp? At the end of this message, I've reproduced a portion of an interchange taking place on the mailing list scheme@mc.lcs.mit.edu. The topic is a somewhat broad argument centered around clarity of some publicly-available code, and in general I can't get exicted about such issues (one man's clarity and elegance is another man's poison). However, I find it verrry interesting that this publicly-available Scheme implementation has grown in size to rival Common Lisp. At least some of the original fathers of Scheme recognize that it is a dialect of Lisp not all that different from Common Lisp; their attraction to it was that it was succinctly defined, and not ossified by the needs of productization, so it was a choice vehicle for programming language research (indeed, this justification was part of Lisp's glory for over 20 years). But I have often claimed that as soon as you develop a language system (like Lisp, Prolog, or Smalltalk) to the point of really being "industrial quality", it will have grown so cancerously as to have lost virtually all its original pristine beauty (** but see footnote below). Conventional languages like C/FORTRAN/ADA/PASCAL/MODULA don't seem to have this property because, I think, there is generally an "off line" approach to programming in them; in fact, the correlate of an "Industrial Strength" Common Lisp is more likely C+Unix(tm) rather than just C alone. ZetaLisp exhibits this operating-system character much more so than Common Lisp (one of whose goals was to be a portable language). -- JonL -- ------------------------------------------------------------------------------- Date: Wed, 4 May 88 11:12:23 MDT From: shebs%defun@cs.utah.edu (Stanley T. Shebs) To: cph@zurich.ai.mit.edu Cc: scheme@mc.lcs.mit.edu In-Reply-To: Chris Hanson's message of Wed, 4 May 88 03:47:10 edt <8805040747.AA21368@kleph> Subject: Re: Extending the address space of MIT Cscheme (long reply) . . . There are probably others, I haven't looked at every single one of the 120+ files and 50K+ lines of the C code... > * Have you seen a lisp of comparable (or greater) functionality > that is significantly better in either respect? Please name it, > and explain why. In the absence of a manual describing the "functionality" of CScheme, it's impossible to compare it on that basis. I hope there's lots of functionality, CScheme is larger than commercial Common Lisps (which is amusing considering how Schemers abuse Common Lisp for its "bloat"). Spice Lisp/CMU Common Lisp has its flaws, but it's better overall (for one thing, it's smaller!). T/Orbit has better structure and style, but its documentation is too scanty to recommend. I would say that PSL/PCLS is cleaner, but I am biased! . . . ------------------------------------------------------------------------------- ** [Footnote]: Smalltalk-80 *might* be excepted from this criticism even though it is rather large (some folks are aghast at the complexity of the initial class structure). The early "pristine" versions were probably vintage circa 72, but the world at large only really saw it after the publication of the Smalltalk books (vintage 80).  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 5 May 88 11:02:02 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 5 May 88 07:13:11 PDT Received: from relay2.cs.net by RELAY.CS.NET id ad29834; 5 May 88 9:38 EDT Received: from cs.umass.edu by RELAY.CS.NET id at04994; 5 May 88 9:34 EDT Date: Wed, 4 May 88 10:35 EDT From: ELIOT@cs.umass.edu Subject: Constant Functions To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.EDU" CLtL P.68: "Defconstant ... does licence the compiler to buildassumptions about the value into programs being compiled." This mechanism has been in place for some time, and I imagine most people agree that it is useful. I don't know of any equivalent mechanism for declaring that the definition of a function will not change. A good compiler could make use of this knowledge to do some useful optimizations. For example, knowing that the definition of SIN won't change, and looking to see that SIN is defined as a mathematical function (this might be hard) implies that (sin pi) can be compiled into a number. Similarly, the compiler could freely eliminate code to check argument counts and types if the call is correct at compile time, and the callee is guaranteed (by declaration) not to change. As a specific proposal I would add a weak version of the INLINE declaration. INLINE already effectively gives the compiler a licence to assume that a function definition will not change. However, it also gives the compiler a licence to compile "bloated" code. My proposal is to add to CLtL P.159 a new declaration for CONSTANT-FUNCTION. The declaration (CONSTANT-FUNCTION foo) specifies that the compiler may assume that the semantics of FOO are fixed. The actual effect depends upon the definition of FOO, the call, and any DECLARE (OPTIMIZE ..) that are in effect. With SPACE=0, SPEED=3 this should be equivalent to an INLINE declaration. As a special case (declare constant-function) in a DEFUN is equivalent to both a proclaim and the defun. In any case, an implementation is free to completely ignore this declaration. Chris Eliot Student, Umass Amherst.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 27 Apr 88 00:30:49 EDT Received: from labrea.Stanford.EDU by SAIL.Stanford.EDU with TCP; 26 Apr 88 21:14:20 PDT Received: by labrea.Stanford.EDU; Tue, 26 Apr 88 21:14:23 PDT Received: from bhopal.lucid.com by edsel id AA12440g; Tue, 26 Apr 88 19:57:24 PDT Received: by bhopal id AA03767g; Tue, 26 Apr 88 19:59:27 PDT Date: Tue, 26 Apr 88 19:59:27 PDT From: Jon L White Message-Id: <8804270259.AA03767@bhopal.lucid.com> To: goldman@vaxa.isi.edu Cc: common-lisp@sail.stanford.edu, cl-cleanup@sail.stanford.edu In-Reply-To: goldman@vaxa.isi.edu's message of Tue, 26 Apr 88 13:27:25 PDT <8804262027.AA08691@vaxa.isi.edu> Subject: miscellaneous questions about declarations and type specfiers re: 1)is there any portable way to obtain the expansion of a type specifier (FOO ...), given that FOO was defined by (deftype FOO ...) I don't think so. Sounds reasonable enough though -- I'll put it on my personal list of items which ought to be submitted to the X3J13 Cleanup committee for consideration. [I already have 7 or 8 issues relating to the type system] 2) is there any portable way to ask if DEC is a legitimate declaration specifier in an implementation (including the possibility that DEC has been legitimized with (PROCLAIM '(DECLARATION DEC)) Again I don't think so. Maybe this ought to go in with a proposal for some functions that will query the global database relevant to proclamations and declarations (e.g., has a particular variable been proclaimed special? what is the current global settings of the OPTIMIZE qualities? and so on.) 3) is there any portable way to ask if a symbol or list S is a legitimate type specifier in an implementation? Guy Steele circulated several pages of "Clarifications" in December 1985, in which he proposed adding a function TYPE-SPECIFIER-P. I don't see it on the current agenda of the X3J13 Cleanup committee; consequently it has been on my personal list of items that ought to be submitted "soon" -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 26 Apr 88 21:58:11 EDT Received: from FRED.SLISP.CS.CMU.EDU by SAIL.Stanford.EDU with TCP; 26 Apr 88 18:40:43 PDT Received: from FRED.SLISP.CS.CMU.EDU by FRED.SLISP.CS.CMU.EDU; 26 Apr 88 21:41:49 EDT To: goldman@vaxa.isi.edu cc: common-lisp@sail.stanford.edu Subject: Re: miscellaneous questions about declarations and type specfiers In-reply-to: Your message of Tue, 26 Apr 88 13:27:25 -0700. <8804262027.AA08691@vaxa.isi.edu> Date: Tue, 26 Apr 88 21:41:32 EDT From: Rob.MacLachlan@WB1.CS.CMU.EDU To all three questions, the answer is no. Perhaps there should be. I believe that proposals for TYPE-SPECIFIER-P have flown by in the past. Rob  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 26 Apr 88 20:16:03 EDT Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 26 Apr 88 16:19:36 PDT Posted-Date: Tue, 26 Apr 88 13:27:25 PDT Message-Id: <8804262027.AA08691@vaxa.isi.edu> Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51) id AA08691; Tue, 26 Apr 88 13:27:56 PDT To: common-lisp@sail.stanford.edu From: goldman@vaxa.isi.edu Subject: miscellaneous questions about declarations and type specfiers Date: Tue, 26 Apr 88 13:27:25 PDT Sender: goldman@vaxa.isi.edu 1)is there any portable way to obtain the expansion of a type specifier (FOO ...), given that FOO was defined by (deftype FOO ...) 2) is there any portable way to ask if DEC is a legitimate declaration specifier in an implementation (including the possibility that DEC has been legitimized with (PROCLAIM '(DECLARATION DEC)) 3) is there any portable way to ask if a symbol or list S is a legitimate type specifier in an implementation?  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 21 Apr 88 14:00:23 EDT Received: from cs.utah.edu by SAIL.Stanford.EDU with TCP; 21 Apr 88 10:27:54 PDT Received: by cs.utah.edu (5.54/utah-2.0-cs) id AA11273; Thu, 21 Apr 88 11:28:21 MDT Received: by cons.utah.edu (5.54/utah-2.0-leaf) id AA01376; Thu, 21 Apr 88 11:28:17 MDT Date: Thu, 21 Apr 88 11:28:17 MDT From: kessler%cons@cs.utah.edu (Robert R. Kessler) Message-Id: <8804211728.AA01376@cons.utah.edu> To: common-lisp@sail.stanford.edu Subject: Lisp & Functional Programming 88 (LONG) What follows is the Advance Program for L&FP 88. There is no electronic version of the registration form, so if you want a copy, please send me your US Mail address, and I'll mail you a copy. If you are a member of SIGPLAN, SIGART, or SIGACT, then you will be receiving a copy in about 3 weeks. Bob. ==================================================================== 1988 Lisp and Functional Programming Conference Advance Program Snowbird, Utah, July 25-27, 1988 A conference sponsored by the ACM Special Interest Groups on Programming Languages, Artificial Intelligence, and Computer Architecture. Chairs and Committee Members General Chair: Jerome Chailloux INRIA Domainede Voluceau-Rocquencourt B.P. 105 Le Chesnay Cedex, France chaillou@inria.inria.fr Program Chair: Robert Cartwright, Rice University Committee: Harold Abelson, MIT Richard Bird, Oxford University Luca Cardelli, DEC Systems Res. Ctr. Robert Cartwright, Rice University Richard Gabriel, Lucid Inc. Christopher Haynes, Indiana University Gerard Huet, INRIA Rocquencourt Gilles Kahn, INRIA Sophia Antipolis David Moon, Symbolics Inc. Guy Steele, Thinking Machines Corp. Carolyn Talcott, Stanford University Local Robert Kessler Arrangements: University of Utah Department of Computer Science Salt Lake City, Utah 84112 kessler@cs.utah.edu (801) 581-5017 Treasurer: Shane Robison, Apple Computer ! Sunday, July 24th 06:00-09:00 pm Reception Monday, July 25th 08:00-08:30 Continental Breakfast 08:30-09:30 Tutorial: Abstraction in Numerical Methods Gerald Jay Sussman and Matthew Halfant (MIT) 09:30-10:30 Session 1: Chaired by Harold Abelson (MIT) "Expressing Mathematical Subroutines Constructively" Gerald Roylance (MIT) "Exact Real Computer Arithmetic with Continued Fractions" Jean Vuillemin (INRIA Rocquencourt) 10:30-11:00 Break 11:00-12:00 Session 2: Chaired by Richard Gabriel (Lucid, Inc.) "Parallel Execution of Sequential Scheme with ParaTran" Pete Tinker, Morry Katz (Rockwell International Science Center) "Buckwheat: Graph Reduction on a Shared-Memory Multiprocessor" Benjamin Goldberg (New York University) 12:00-02:00 Lunch 02:00-03:30 Session 3: Chaired by Christopher Haynes (Indiana University) "A MathematicalSemantics for Handling Full Functional Jumps" Matthias Felleisen (Rice University) Mitch Wand (Northeastern University) Daniel Friedman, Bruce Duba (Indiana University) "Continuations May Be Unreasonable" Albert Meyer, Jon G. Riecke (MIT) "Lambda-V-CS: An Extended Lambda Calculus for Scheme" Matthias Felleisen (Rice University) 03:30-04:00 Break 04:30-05:30 Session 4: Chaired by Guy Steele (Thinking Machines Corp.) "Syntactic Closures" Alan Bawden, Jonathan Rees (MIT) "Concrete Syntax for Data Objects in Functional Languages" Kent Peterson (Chalmers University) ! "A Variable-Arity Procedural Interface" R. Kent Dybvig, Robert Hieb (Indiana University) 08:00-09:45 pm Session 5: Chaired by David Moon (Symbolics Inc.) "The Scheme86 Pro ject: A System for Interpreting Scheme" Andrew Berlin, Henry Wu (MIT) "Strategies forImplementing Continuations" Will Clinger, Anne Hartheimer (Semantic Microsystems) Eric Ost (Metaphor Corp.) "An Implementation of Portable Standard LISP on the BBN Butterfly" Mark Swanson, Robert Kessler, Gary Lindstrom (University of Utah) "Preliminary Results with the Initial Implementation of Qlisp" Ron Goldman, Richard Gabriel (Lucid, Inc.) Tuesday, July 26th 08:00-08:30 Continental Breakfast 08:30-10:00 Session 6: Chaired by Robert Cartwright (Rice University) "PartialPolymorphic Type Inference and Higher-Order Unification" Frank Pfenning (Carnegie-Mellon University) "Bounded Quantifiers Have Interval Models" Simone Martini (Universitadi Pisa) "Type Inferencein a Database Programming Language" Atsushi Ohori, Peter Buneman (University of Pennsylvania) 10:30-11:00 Break 10:30-12:00 Session 7: Chaired by Luca Cardelli (DEC Systems Res. Ctr.) "The Milner-Mycroft Calculus is Tractable" Fritz Henglein (New York University) "ML With Extended Pattern Matching and Subtypes" Lalita Jategaonkar, John Mitchell (Stanford University) "An Implementation of Standard ML Modules" David MacQueen (AT&T Bell Laboratories) 12:00-02:00 Lunch 02:00-03:30 Session 8: Chaired by Jerome Chailloux (INRIA Rocquencort) "Graphinators and the Duality of SIMD and MIMD" Paul Hudak, Eric Mohr (Yale University) ! "Faster Combinator Reduction Using Stock Hardware" A.C. Norman (Cambridge University) "The SpinelessG-Machine" G. L. Burn (GEC Research Limited) S. L. Peyton Jones (University College London) J. D. Robson (GEC Research Limited) 03:30-04:00 Break 04:00-05:30 Session 9: Chaired by Richard Gabriel (Lucid, Inc.) "A Simple and Efficient Implementation Approach for Single Assignment Languages" Kourosh Gharachorloo, Vivek Sarkar, John L. Hennessy (Stanford University) "An Improved Replacement Strategy for Function Caching" William Pugh (Cornell University) "Object-oriented Programming in Scheme" Norman Adams (Tektronix) Jonathan Rees (MIT) 06:30- Banquet Wednesday, July 27th 08:00-08:30 Continental Breakfast 08:00-10:00 Session 10: Chaired by Gilles Kahn (INRIA Sophia Antipolis) "Objects as Closures: Abstract Semantics of Object-oriented Languages" Uday Reddy (University of Illinois at Urbana-Champaign) "Types, Classes, Metatypes, Metatypes Classes: An Open-ended Data Representation Model for EU_LISP" Christian Queinnec (LITP, Universite Paris) Pierre Cointe(Rank Xerox) "The Common Lisp Ob ject System Metaobject Kernel: A Status Report" Daniel G. Bobrow, Gregor Kiczales (Xerox Palo Alto Research Center) 10:00-10:30 Break 10:30-12:00 Session 11: Chaired by Carolyn Talcott (Stanford University) "A Unified System of Parameterization for Programming Languages" John Lamping (Stanford University) "Intensions and Extensions in a Reflective Tower" Olivier Danvy, Karoline Malmkjaer (University of Copenhagen) "Reification without Evaluation" Alan Bawden (MIT) ! Conference Information The 1988 ACM LISP and Functional Programming Conference will be held at the Snowbird Ski and Summer Resort at Snowbird, Utah. Snowbird is a world renowned resort in the mountains near Salt Lake City that offers outstanding skiing in the winter and a variety of recreational activities including hiking, climbing, swimming, and tennis in the summer. Summer temperatures typically range between 60 F and 80 F in the day and 30 F to 50 F at night. Sweaters are advisable for evening wear. The meeting rooms, book exhibits, and guest rooms for the Conference will all be housed in the Cliff Lodge, which features an eleven story glass atrium with a cocktail lounge and restaurant overlooking the rugged Peruvian Gulch. The Lodge includes four restaurants offering a wide variety of cuisines. The entire Snowbird complex includes seventeen full-service restaurants, lounges, and fast-food operations. You will also have access to the Cliff Lodge Health and Beauty Spa, which offers an array of services ranging from the unique (herbal wraps, parafango treatments) to the stimulating (whirlpool, steamroom, saunas, roof-top heated swimming pool, aerobics and weight training). You can make room reservations with Snowbird's Central Reservations Office by calling (800)453-3000 or (801)532-1700. Snowbird requires a deposit for one night's lodging within ten days of booking. The deposit will be refunded if the room is cancelled within 48 hours of arrival. If you book reservations by June 24, 1988, you are entitled to the following special rates: $64 for a single occupancy; $70 for a double occupancy; $104 for a deluxe bedroom, single occupancy; and $110 for a deluxe bedroom, double occupancy. To receive these special rates you must mention the ACM L&FP Conference when you place your reservations. Each additional person will be charged $6 per day; children under the age of 16 may stay for free in a room with a parent. These rates are available from Saturday, July 23, 1988 through Friday, July 29, 1988, permitting conference attendees to extend their conference stay into a short vacation. Some possible activities include rock climbing lessons, backpacking trips, and helicopter tours. Delta Airlines, which has a major hub in Salt Lake City, is offering special round-trip fares to North American conferees of the 1988 ACM Conference on Lisp and Functional Programming. First, Delta will allow an additional 5% savings off published round-trip fares within the United States and San Juan; and for passengers not qualifying for any published discounts, Delta will allow the following two (seven-day advance purchase) discounts off unrestricted round-trip coach fares: 40% from domestic cities and 35% from Canadian cities. Delta also serves Europe and Japan. To take advantage of these discounts, call (800) 345-1647 (within Indiana (800) 822-4730; from Canada (812) 333-3360 collect) and ask for Lana. The Internet address may be used for initial contact, as well (acmtravel@iuvax.cs.indiana.edu); include daytime phone number and hours. These fares are valid from July 23 to July 30, 1988. Snowbird is located 31 miles or 40 minutes from the Salt Lake City International Airport, and is easily accessible by taxi, car, bus (or helicopter). Various transportation companies provide van and motorcoach service to Snowbird. For four or more people, the current van cost is $10 per person. Limousine and car rental service is also available as well as City Cab, Ute Cab and Yellow Cab (Cab fares should be about $42). Conference activities will include a reception Sunday night and a chairlift ride to an open meadow for a BBQ lunch on Monday. Tuesday's lunch will includea tram ticket and a box lunch. You can ride Snowbird's 125 passenger aerial tram to the top of the 11,000 foot Hidden Peak, with its spectacular view of the Wasatch Mountain Range and Salt Lake Valley. You may either hike back down where you will have the opportunity of seeing historic silver mine shafts from the 1800's, or you can make the return trip by tram. That night will include the banquet dinner on the Pavilion. Advance registration for the Conference is $225 for ACM and SIG members (SIGPLAN, SIGART, or SIGACT), $250 for ACM or SIG members, or $290 for non-members. Advance registration cutoff is June 24, 1988. After June 24, fees are $275 for ACM and SIG, $300 for ACM or SIG, and $350 for non-members. The registration fee includes a copy of the proceedings, the reception Sunday evening, luncheons on Monday and Tuesday, refreshments during the breaks, continental breakfast Monday through Wednesday, and the Tuesday night banquet. Speakers and program/conference committee members should use the $225 rate. Extra banquet tickets can be purchased for $40. Student advance registration is $75 for the Conference (June 24 cutoff date), and $100 for late registration. The student registration fee does not include the lunches or the banquet. On-site registration will be accepted Sunday evening, and during the conference. We hope you will enjoy your stay at Snowbird and we are looking forward to seeing you at the Conference.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 15 Apr 88 02:32:09 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 14 Apr 88 23:15:47 PDT Received: from relay2.cs.net by RELAY.CS.NET id ac18084; 15 Apr 88 2:07 EDT Received: from cs.umass.edu by RELAY.CS.NET id av18068; 15 Apr 88 1:59 EDT Date: Thu, 14 Apr 88 12:07 EDT From: ELIOT@cs.umass.edu Subject: &rest [discussion] replacement/addition To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.EDU" From: IN%"pf@ti-csl.csc.ti.COM" "Paul Fuqua" 14-APR-1988 03:50 The general rule around here is, "Don't modify a list if you don't know where it came from." Many constants in our implementation end up in read-only areas, and there are other instances of sharing than APPLY/&REST, so it's seen as a bad idea to use destructive operations on random data objects. Anyone who doesn't follow this rule is writing potentially buggy code. One of the central points of the &rest discussion is the proposal to stipulate, by definition, that &rest lists "come from" the function which recieves them. The only ramification of this definition for otherwise correct Common Lisp implementations is that APPLY/&rest lists cannot be shared. So close, and yet so far. From your discussion of the TI microcode, it sounds like the runtime penalty would be limited to some extra stack allocation (NO real consing) except in cases where the &rest list is actually saved. This is better than I had expected was possible. My measurements did not count functions with &key arguments. I believe there are other possible ways to implement &key, so it would not be fully fair to lump them with &rest. My measurement code was included in my earlier message, and it can easily be modified to measure &key (or &optional or &aux for that matter.) Chris Eliot  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 14 Apr 88 23:33:25 EDT Received: from space-tech.arpa by SAIL.Stanford.EDU with TCP; 14 Apr 88 20:15:59 PDT Date: 14 Apr 88 22:12:00 CST From: "Perry Alexander" Subject: Reader references To: "common-lisp" Reply-To: "Perry Alexander" Does anyone out there know of any references having to do with the Lisp reader and read macros? (Besides CLtL) We are beginning to write some very complicated databases and realize that taking full advantage of read macros will help performance. However, no one seems to deal with this in detail besides in CLtL. Any pointers? - Perry =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Perry Alexander ARPA : alexander@space-tech.arpa The University of Kansas Center for Research/TISL 2291 Irving Hill Dr. Lawrence, KS. 66045 (913)-864-7753 -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- ------  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 14 Apr 88 04:14:49 EDT Received: from uunet.UU.NET by SAIL.Stanford.EDU with TCP; 14 Apr 88 00:53:39 PDT Received: from mcvax.UUCP by uunet.UU.NET (5.54/1.14) with UUCP id AA18873; Thu, 14 Apr 88 03:53:17 EDT From: mcvax!pilatus!ceb@uunet.UU.NET Received: by mcvax.cwi.nl; Thu, 14 Apr 88 08:27:15 +0200 (MET) Received: by cernvax.uucp (1.2/Ultrix2.0-B) id AA25175; Wed, 13 Apr 88 15:06:39 +0200 Date: Wed, 13 Apr 88 15:06:39 +0200 Message-Id: <8804131306.AA25175@cernvax.uucp> To: REM@sail.stanford.edu Cc: common-lisp@sail.stanford.edu In-Reply-To: Robert Elton Maas's message of Mon, 11 Apr 88 13:35:53 Subject: LetRec Date: Mon, 11 Apr 88 13:35:53 X-Date-Last-Edited: 1988 April 11 13:35:53 PDT (=GMT-7hr) X-Date-Posted: 1988 April 11 13:38:04 PDT (=GMT-7hr) From: Robert Elton Maas From: mcvax!pilatus!ceb@uunet.UU.NET I nominate using BBN/UCI-lisp editor terminology here, namely "embed". CONS and LIST are embedding functions. . . . terminology, namely "extract". CAR and NTH (in regard to its list argument) are extracting functions. (:- Or cut off their damn heels :-) (N.B. That's from a comedy album played on KFAT dealing with chain saw.) In this case of LetRec, have low-level mechanism (part of LetRec) pass a dummy forwarding cell, evaluate normally, then after return more low-level LetRec mechanism do the replacement for the true value to create circularity. This localizes the implementation work to LetRec itself, not random functions such as CONS, thus it can be done outside a Scheme-style lazy-evaluator within a normal evaluator. Now that you mention chain saws, it occurs to me that you really don't have to declare a special class of functions at all. If what you meant above was something like: "Whenever a reference occurs to a structure chunk that occurs elsewhare in the structure, you substitute in place a forwarding cell, and then as you exit the letrec context, you go through and replace al of these forwarding cells (which you have kept around in a list) with their true references, then . . . *Should you make a such a reference inside an non-embedding or extracting function, then as your forwarding cell tries to work its way through the offending procedural filter before you exit, then you will get a "Warning: non-numeric argument passed to (whatever)"." (Its just like trying to pass something which won't cut through a circular saw => it jams). Otherwise, it seems you've got the idea well framed. [But then again, all this is probably inside that 1980 ACM article Steele mentioned as well; wheels tend to get reinvented.] Ps. Glad to see KFAT back.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 13 Apr 88 14:23:59 EDT Received: from ti.com by SAIL.Stanford.EDU with TCP; 13 Apr 88 11:00:27 PDT Received: by ti.com id AA29855; Wed, 13 Apr 88 12:58:18 CDT Received: from Islington-Terrace by tilde id AA05452; Wed, 13 Apr 88 12:54:53 CDT Message-Id: <2785945967-1737834@Islington-Terrace> Sender: pf@Islington-Terrace.csc.ti.com Date: Wed, 13 Apr 88 12:52:47 CDT From: Paul Fuqua To: common-lisp@sail.stanford.edu Subject: Re: &rest [discussion] replacement/addition In-Reply-To: Msg of 8 Apr 88 20:43:52 GMT from Jon L White Date: Friday, April 8, 1988 3:43pm (CDT) From: Jon L White Subject: &rest [discussion] replacement/addition Of course, the problem isn't only the sharing of &rest lists, but the more common flaw that they may, unannouncedly, have dynamic extent. By this, I mean the bug where a stack-allocated &rest list can creep out into global data structures, even though it will surely disappear when the frame that created it returns. Allegedly, Symbolics is going to fix this bug in their next release (and TI may have already fixed it?); but we are now five years beyond the first CL specification! We fixed it for Release 3, which came out some time ago. We use a separate internal data type for stack-lists, which, when the list is returned from a function or stored into the heap, is noticed and causes the list to copied out of the stack. There's other hair to preserve EQness and to cope with stack-groups and special-bindings. As a matter of fact, I asked about the problem of APPLYing a function with a &REST arg back when I was doing the function-calling microcode. The easy approach was to spread the list and re-collect it into a stack-list, which would avoid both the sharing and the consing, but we decided at the time to avoid the spreading overhead. If the standard says not to share, we'll spread and re-collect. Incidentally, our implementation of keyword arguments also uses a &REST arg, so &KEY implies &REST internally. Did that appear in the statistics? I don't know if other implementations do the same. The general rule around here is, "Don't modify a list if you don't know where it came from." Many constants in our implementation end up in read-only areas, and there are other instances of sharing than APPLY/&REST, so it's seen as a bad idea to use destructive operations on random data objects. pf Paul Fuqua Texas Instruments Computer Science Center, Dallas, Texas CSNet: pf@csc.ti.com (ARPA too, eventually) UUCP: {smu, texsun, im4u, rice}!ti-csl!pf  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 12 Apr 88 10:12:17 EDT Received: from MCC.COM by SAIL.Stanford.EDU with TCP; 12 Apr 88 06:54:18 PDT Received: from HAL.CAD.MCC.COM by MCC.COM with TCP; Tue 12 Apr 88 08:51:03-CDT Received: from CHANGABANG.CAD.MCC.COM by HAL.CAD.MCC.COM via CHAOS with CHAOS-MAIL id 78811; Tue 12-Apr-88 08:47:48 CDT Date: Tue, 12 Apr 88 08:48 CDT From: William D. Gooch Subject: &rest [discussion] replacement/addition To: barmar%Think.COM@MCC.COM cc: edsel!jonl%labrea.Stanford.EDU@mcc.com, common-lisp%sail.stanford.edu@mcc.com, spe%spice.cs.cmu.edu@mcc.com, ELIOT%cs.umass.edu@mcc.com, gz%spt.entity.com@mcc.com In-Reply-To: <19880408222959.6.BARMAR@OCCAM.THINK.COM> Message-ID: <880412084804.2.GOOCH@CHANGABANG.CAD.MCC.COM> Reply-To: gooch@MCC.COM Postal-address: MCC-CAD 3.8108 Business-phone: (512) 338-3661 Date: Fri, 8 Apr 88 18:29 EDT From: Barry Margolin I noticed you didn't try the following version. This is identical to the version you included in your message, except that it takes the previous words as a single argument rather than as an &REST argument. One definite advantage of this version is that it won't exceed CALL-ARGUMENTS-LIMIT if it recurses deeply. I had run this version before, but neglected to include it in the timing runs. input string code version runtime (sec) list consing (words) ------------------------------------------------------------------------- hi there no &rest, cons 14.25 1280 ian gooch no &rest, cons 138.3 4626 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Date: Sat, 9 Apr 88 12:35 EDT From: ELIOT%cs.umass.edu@RELAY.CS.NET ...I think &rest should always have a form which allows its user to control consing, regardless of how performance might or might not be affected. After ALL the discussion about this topic, it seems that this claim should be justified, if it is going to be made at all. I think there is general agreement that the only reason why the user might need control over consing &rest lists is the effect on performance. You're right. I guess I didn't mean that the way it came out. Performance is the object, but my current assumption is that consing must adversely affect overall performance. Your data does not seem to show such an effect. Another experiment you could try would be to run the same examples many times (100 or 1000 times) with the garbage collector on. The idea is to do so much consing that the GC must run. That way you can claim that the timings include the GC overhead. Good idea. Results later. If you do that and still get practically the same runtime results for all of the different versions, then I think you should conclude that the runtime of your example does not depend upon how the &rest list is handled. -- William D. Gooch  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 11 Apr 88 17:53:29 EDT Received: from tully.Berkeley.EDU by SAIL.Stanford.EDU with TCP; 11 Apr 88 14:34:15 PDT Received: by tully.Berkeley.EDU (5.57/1.25) id AA01491; Mon, 11 Apr 88 14:34:39 PDT From: hilfingr%tully.Berkeley.EDU@ginger.Berkeley.EDU (Paul Hilfinger) Message-Id: <8804112134.AA01491@tully.Berkeley.EDU> To: common-lisp@sail.stanford.edu Subject: Question on terminology Date: Mon, 11 Apr 88 14:34:36 PDT [Forgive me if I missed the following point in the volume of articles on letrec]. In the current debate about letrec, I've noticed many references to circular data structures as "recursive." With all due respect, is this a proper use of the term? I've usually seen the term "recursive data TYPE"" used to refer to types that are recursively defined, as in "a list is either null or comprises a head of arbitrary type and a tail that is a list." Alternatively, I have seen recursive data structures defined as those that contain components having the same type ("same type", not "pointers to objects of the same type", although of course, pointers might be used in the implementation). C.A.R. Hoare, among others, have used the latter terminology (which, because it does not mention "pointers", actually excludes circular structures, since an object cannot contain itself.) Even discounting the definitions of such people as Hoare---who is famous but far outside the Lisp community---I don't like the equation of "recursive" and "circular" for the simple reason that MY recursive programs, at least, eventually terminate. (Usually) Paul Hilfinger hilfingr@ginger.Berkeley.EDU  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 11 Apr 88 16:59:55 EDT Received: from SAIL.Stanford.EDU by SAIL.Stanford.EDU with TCP; 11 Apr 88 13:40:40 PDT Date: Mon, 11 Apr 88 13:35:53 X-Date-last-edited: 1988 April 11 13:35:53 PDT (=GMT-7hr) X-Date-posted: 1988 April 11 13:38:04 PDT (=GMT-7hr) From: Robert Elton Maas To:common-lisp@sail.stanford.edu CC:edsel!jonl@uunet.UU.NET,edsel!jlm@uunet.UU.NET Subject:LetRec From: mcvax!pilatus!ceb@uunet.UU.NET It was mentioned earlier that any scheme of this type would only work for "special" operators (I forget the exact adjective used, but it was later stamped as inappropriate or unclear.) The nature of this speciality seem to me to be best described as "encapsulating". A function is encapsulating when it takes its arguments and buries them in some topological structure in memory (including, but not limited to, cons-cell spaghetti) without interfering with them procedurally in any way. The functions cons and list are encapsulating, but +, -, etc. are not, since they feed their arguments back into some procedural operation. I nominate using BBN/UCI-lisp editor terminology here, namely "embed". CONS and LIST are embedding functions. For simplicity's sake, functions such as car, cdr, and their descendants should be considered as non-encapsulating, They do the opposite. Again I nominate using BBN/UCI-lisp editor terminology, namely "extract". CAR and NTH (in regard to its list argument) are extracting functions. IDENTITY is both the trivial embedding and the trivial extracting function. To avoid recursion loops we should require nontrivial (strict) embedding functions for LetRec. (declare (encapsulating-function . . .)) (declare (embedding-function . . .)) Because "encapsulating" is a more elaborate concept usually, having to do with closures and abstraction etc., I prefer to avoid that term for the simple structural concept we're discussing here. ... to permit users to identify their own functions having this property (and to shoot themselves in the foot if they lie). (:- Or cut off their damn heels :-) (N.B. That's from a comedy album played on KFAT dealing with chain saw.) The other implementational hurdles then seem surmountable *but* you would have to change the order in which encapsulating functions are evaluated - it would no longer be acceptable to grind through its arguments first. In this case of LetRec, have low-level mechanism (part of LetRec) pass a dummy forwarding cell, evaluate normally, then after return more low-level LetRec mechanism do the replacement for the true value to create circularity. This localizes the implementation work to LetRec itself, not random functions such as CONS, thus it can be done outside a Scheme-style lazy-evaluator within a normal evaluator. Whether it is worth adding to the language depends on how hard it is to implement, and how much additional cognitive clutter the language can stand. More importantly, it shouldn't become part of CLtL until after it has been implemented by at least several experimental implementations to work out the bugs in the basic design and see if it really is useful.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 11 Apr 88 14:54:42 EDT Received: from uunet.UU.NET by SAIL.Stanford.EDU with TCP; 11 Apr 88 11:29:53 PDT Received: from mcvax.UUCP by uunet.UU.NET (5.54/1.14) with UUCP id AA17400; Mon, 11 Apr 88 14:29:23 EDT From: mcvax!pilatus!ceb@uunet.UU.NET Received: by mcvax.cwi.nl; Sun, 10 Apr 88 16:53:25 +0200 (MET) Received: by cernvax.uucp (1.2/Ultrix2.0-B) id AA13469; Sun, 10 Apr 88 16:18:19 +0200 Date: Sun, 10 Apr 88 16:18:19 +0200 Message-Id: <8804101418.AA13469@cernvax.uucp> To: edsel!jonl@uunet.UU.NET, edsel!jlm@uunet.UU.NET Cc: common-lisp@sail.stanford.edu In-Reply-To: Jon L White's message of Sat, 9 Apr 88 05:20:53 PDT Subject: LetRec the way you want it IS in Common-lisp Date: Fri, 8 Apr 88 19:08:52 PDT From: Jim McDonald . . . To return to the original question: Assuming that backquote (or whatever) could give you dynamically created recursive data structures, and that recursive forms in general are impossible to handle, is there something in-between that you want? Date: Sat, 9 Apr 88 05:20:53 PDT From: Jon L White . . . Now, maybe what he wanted was a freshly-consed-up copy of some circular structure; say, something equivalent to `#1=(a . ,#1#). . . . [On the other hand, although this sort of data-pattern is just what a programmer might like, I'm not sure that the folks who thought this suggestion meant solving simultaneous recursive equations were way off base. Give that man a turing machine. Complete with halting problem.] I would find it useful to have dynamic functional specification of non-arborescent structures in CL, but the problems are indeed large. In response to jlm's question about something in-between, the following suggestion is made: It was mentioned earlier that any scheme of this type would only work for "special" operators (I forget the exact adjective used, but it was later stamped as inappropriate or unclear.) The nature of this speciality seem to me to be best described as "encapsulating". A function is encapsulating when it takes its arguments and buries them in some topological structure in memory (including, but not limited to, cons-cell spaghetti) without interfering with them procedurally in any way. The functions cons and list are encapsulating, but +, -, etc. are not, since they feed their arguments back into some procedural operation. For simplicity's sake, functions such as car, cdr, and their descendants should be considered as non-encapsulating, although I haven't ruled out for myself the possibility of getting around *their* particular kind of procedural hacking with a modicum of cleverness. This concept in place, in implementing this feature in the context of something like backquote, it would then be simple only to permit references to recursive reference points when these appear as arguments to encapsulating functions, and to permit these to refer only to constants, or other encapsulating functions. There would, of course, have to be a "(declare (encapsulating-function . . .))" form to permit users to identify their own functions having this property (and to shoot themselves in the foot if they lie). The other implementational hurdles then seem surmountable *but* you would have to change the order in which encapsulating functions are evaluated - it would no longer be acceptable to grind through its arguments first. However, it seems that under the definition of encapsulability, this will always be legal, and you will still be able to satisfy the thrust of the original suggestion. From shipboard, this seems a simple yet reasonably robust way to get beyond the "impossibility of general recursive structures" Muffel. Whether it is worth adding to the language depends on how hard it is to implement, and how much additional cognitive clutter the language can stand. ceb  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 11 Apr 88 14:43:10 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 11 Apr 88 11:24:50 PDT Return-Path: Received: from kali.think.com by Think.COM; Mon, 11 Apr 88 14:23:11 EDT Received: by kali.think.com; Mon, 11 Apr 88 14:23:08 EDT Date: Mon, 11 Apr 88 14:23:08 EDT From: gls@Think.COM Message-Id: <8804111823.AA05656@kali.think.com> To: Rice@sumex-aim.stanford.edu Cc: Common-Lisp@sail.stanford.edu In-Reply-To: James Rice's message of Fri, 8 Apr 88 12:58:57 PDT <12388881557.13.RICE@SUMEX-AIM.Stanford.EDU> Subject: LetRec Date: Fri, 8 Apr 88 12:58:57 PDT From: James Rice Sorry to all of you who might have been confused by my message. I was not thinking explicitly of Scheme's Letrec. I was thinking of a general recursive let construct, particularly for non-function objects, though I see no reason why such a construct could not be used for function objects too. Rice. ------- See, for example, the paper by F. Lockwood Morris and Jerald S. Schwarz, "Computing Cyclic List Structures" in the Proceedings of the 1980 Lisp Conference (which has been reprinted by ACM). --Guy  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 10 Apr 88 10:17:33 EDT Received: from ucbvax.Berkeley.EDU by SAIL.Stanford.EDU with TCP; 10 Apr 88 07:02:44 PDT Received: by ucbvax.Berkeley.EDU (5.59/1.28) id AA04531; Sun, 10 Apr 88 01:22:36 PDT From: trwrb!smpvax1!jrg@ucbvax.Berkeley.EDU Received: by trwrb (5.51/1.36) id AA21005; Fri, 8 Apr 88 17:10:51 PDT Date: Fri, 8 Apr 88 17:10:51 PDT Message-Id: <8804090010.AA21005@trwrb> To: common-lisp@sail.stanford.edu Subject: &rest arguments For Inference commercial products written in Common Lisp where stack consing of &rest is not supported, we do not use &rest arguments. The overriding consideration is to avoid generating the cons garbage of the &rest argument. We NEVER maintain pointers to conses in &rest arguments outside the extent of the function call that caused the &rest argument to be set up. We do use &rest arguments where stack consing of the &rest argument is available; in fact, this is fast becoming a de facto lisp language requirement for our code -- we've pointed this out to numerous Lisp vendors. So, I advocate adding a declaration to Common Lisp much like the DYNAMIC-EXTENT declaration already available in Lucid Lisp. Functionality like this is, I believe, mandatory for a Lisp to be viable as the basis for a commercial software product. As for APPLY and &rest arg copying or sharing, we'd never use such a construct in our code anyway, so I don't care. I believe that not guaranteeing the sharing is the best approach, if you want an opinion. In general, APPLY is just too slow. We've avoided it for mini-object systems used internally for this reason (that is, to call methods from a generic function). --Joe  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 10 Apr 88 01:30:04 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 9 Apr 88 22:12:20 PDT Return-Path: Received: from fafnir.think.com by Think.COM; Sun, 10 Apr 88 01:10:47 EDT Received: by fafnir.think.com; Sun, 10 Apr 88 01:10:45 EDT Date: Sun, 10 Apr 88 01:10:45 EDT From: barmar@Think.COM Message-Id: <8804100510.AA05684@fafnir.think.com> To: Rice@sumex-aim.stanford.edu Cc: Common-Lisp@sail.stanford.edu In-Reply-To: James Rice's message of Fri, 8 Apr 88 16:16:43 PDT <12388917560.13.RICE@SUMEX-AIM.Stanford.EDU> Subject: LetRec Date: Fri, 8 Apr 88 16:16:43 PDT From: James Rice Mmmm, I see what you're getting at. Maybe it's a wimp-out but how about: It is an error to use the named structure in the definition of a letrec variable as an argument to a strict operator during the evaluation of its definition. What is the definition of "strict operator"? Is a user-defined function a strict operator? e.g. (letrec ((foo (+ 1 foo))) <---- error (letrec ((bar (cons 42 bar))) <--- ok. In this case, I don't think this facility is appropriate for the standard language. Are there any Lisp implementations that have such a facility? If not, I think it would be a bad idea to suddenly thrust it into the standard.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 9 Apr 88 08:43:31 EDT Received: from labrea.Stanford.EDU by SAIL.Stanford.EDU with TCP; 9 Apr 88 05:28:43 PDT Received: by labrea.Stanford.EDU; Sat, 9 Apr 88 04:28:15 PST Received: from bhopal.lucid.com by edsel id AA11679g; Sat, 9 Apr 88 05:20:00 PDT Received: by bhopal id AA08970g; Sat, 9 Apr 88 05:20:53 PDT Date: Sat, 9 Apr 88 05:20:53 PDT From: Jon L White Message-Id: <8804091220.AA08970@bhopal.lucid.com> To: Gumby@mcc.com Cc: Rice@sumex-aim.stanford.edu, BarMar@think.com, Common-Lisp@sail.stanford.edu In-Reply-To: David Vinayak Wallace's message of Fri, 8 Apr 88 19:21 CDT <19880409002104.5.GUMBY@BRAHMA.ACA.MCC.COM> Subject: LetRec the way you want it IS in Common-lisp re: In common-lisp you can get the reader to do this for you: ==> (prog1 nil (setf foo '#1=(a . #1#))) I've been sitting on the sideline of this discussion wondering what the heck anyone expected of LetRec in the line of "recursive" data structures. It seemed just too obvious that the originator of this question had overlooked the #= and ## notation of the Common Lisp Reader for expressing circular *constants*. Now, maybe what he wanted was a freshly-consed-up copy of some circular structure; say, something equivalent to `#1=(a . ,#1#). Just by coincidence, the way Lucid's reader implements the #= and ## stuff is awfully close to the way one might naively implement backquote; so with very little more work this notation could actually do the expected thing! Looks pretty "functional" to me! [On the other hand, although this sort of data-pattern is just what a programmer might like, I'm not sure that the folks who thought this suggestion meant solving simultaneous recursive equations were way off base. Give that man a turing machine. Complete with halting problem.] -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Apr 88 22:31:21 EDT Received: from labrea.Stanford.EDU by SAIL.Stanford.EDU with TCP; 8 Apr 88 19:15:35 PDT Received: by labrea.Stanford.EDU; Fri, 8 Apr 88 18:14:32 PST Received: from bhopal.lucid.com by edsel id AA10081g; Fri, 8 Apr 88 19:08:00 PDT Received: by bhopal id AA07844g; Fri, 8 Apr 88 19:08:52 PDT Date: Fri, 8 Apr 88 19:08:52 PDT From: Jim McDonald Message-Id: <8804090208.AA07844@bhopal.lucid.com> To: labrea!Gumby%MCC.COM@labrea.Stanford.EDU Cc: labrea!Common-Lisp%Sail.Stanford.EDU@labrea.Stanford.EDU Subject: LetRec the way you want it IS in Common-lisp > In common-lisp you can get the reader to do this for you: > > ==> (prog1 nil (setf foo '#1=(a . #1#))) > nil > ==> (first foo) > a > ==> (second foo) > a > ==> (third foo) > a That was my first reaction, but this creates a global structure. I think the goal is to get a dynamically generated recursive structure. You could do something awful like (let ((foo (eval (read-from-string "'#1=(a . #1#)")))) ...) but this seems too bletcherous to suggest as a canonical solution. Perhaps one could extend backquote to include something like the #n= feature of the reader. (Perhaps this feature is already in backquote and I don't know about it?) The following unhappy syntax should not be that hard to implement: (let ((foo `,=1=(a ,.=1=))) ...) Someone who cares could improve on it. To return to the original question: Assuming that backquote (or whatever) could give you dynamically created recursive data structures, and that recursive forms in general are impossible to handle, is there something in-between that you want? jlm  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Apr 88 20:39:13 EDT Received: from MCC.COM by SAIL.Stanford.EDU with TCP; 8 Apr 88 17:24:47 PDT Received: from BRAHMA.ACA.MCC.COM ([128.62.12.110].#Internet) by MCC.COM with TCP; Fri 8 Apr 88 19:24:00-CDT Date: Fri, 8 Apr 88 19:21 CDT From: David Vinayak Wallace Subject: LetRec the way you want it IS in Common-lisp To: James Rice cc: BarMar@Think.Com, Common-Lisp@Sail.Stanford.EDU In-Reply-To: <12388917560.13.RICE@SUMEX-AIM.Stanford.EDU> Message-ID: <19880409002104.5.GUMBY@BRAHMA.ACA.MCC.COM> Date: Fri, 8 Apr 88 16:16:43 PDT From: James Rice Mmmm, I see what you're getting at. Maybe it's a wimp-out but how about: It is an error to use the named structure in the definition of a letrec variable as an argument to a strict operator during the evaluation of its definition. e.g. (letrec ((foo (+ 1 foo))) <---- error (letrec ((bar (cons 42 bar))) <--- ok. In common-lisp you can get the reader to do this for you: ==> (prog1 nil (setf foo '#1=(a . #1#))) nil ==> (first foo) a ==> (second foo) a ==> (third foo) a  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Apr 88 19:32:07 EDT Received: from SUMEX-AIM.Stanford.EDU by SAIL.Stanford.EDU with TCP; 8 Apr 88 16:17:06 PDT Date: Fri, 8 Apr 88 16:16:43 PDT From: James Rice Subject: LetRec To: BarMar@Think.Com cc: Common-Lisp@Sail.Stanford.EDU Message-ID: <12388917560.13.RICE@SUMEX-AIM.Stanford.EDU> Mmmm, I see what you're getting at. Maybe it's a wimp-out but how about: It is an error to use the named structure in the definition of a letrec variable as an argument to a strict operator during the evaluation of its definition. e.g. (letrec ((foo (+ 1 foo))) <---- error (letrec ((bar (cons 42 bar))) <--- ok. Rice. -------  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Apr 88 19:14:03 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 8 Apr 88 15:59:43 PDT Return-Path: Received: from sauron.think.com by Think.COM; Fri, 8 Apr 88 18:58:12 EDT Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 8 Apr 88 18:58:09 EDT Date: Fri, 8 Apr 88 18:59 EDT From: Barry Margolin Subject: LetRec To: James Rice Cc: Common-Lisp@sail.stanford.edu In-Reply-To: <12388911060.13.RICE@SUMEX-AIM.Stanford.EDU> Message-Id: <19880408225924.8.BARMAR@OCCAM.THINK.COM> Date: Fri, 8 Apr 88 15:41:00 PDT From: James Rice Yes, it's clear that in order to implement a letrec, which would allow you to express: (letrec ((circular (list 1 2 3 circular)) ...circular) Something would have to be fixed up after the structure was created. I have no idea how one would best implement this but I would assume that the compiler would substitute all all appropriate references to the named object with some sort of forwaring cell, which would be smashed to point to the whole object after it was created. While that might work for simple data structure creation, there's just no way it could be generalized. What does: (letrec ((value (+ value 3))) value) mean? Or how about? (letrec ((circular (list* 1 2 3 (mapcar #'(lambda (x) (* x 2)) circular)))) circular) return? It looks like it should return something like (1 2 3 2 4 6 4 8 12 8 16 24 ...) but I don't think it is actually possible.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Apr 88 18:54:52 EDT Received: from SUMEX-AIM.Stanford.EDU by SAIL.Stanford.EDU with TCP; 8 Apr 88 15:40:53 PDT Date: Fri, 8 Apr 88 15:41:00 PDT From: James Rice Subject: LetRec To: Common-Lisp@Sail.Stanford.EDU Message-ID: <12388911060.13.RICE@SUMEX-AIM.Stanford.EDU> In order to create circular structure, you have to do something like (let ((circular (list 1 2 3 4))) (setf (cdr (last circular)) circular) circular) I don't know how to do this kind of thing in a purely functional style. Yes, it's clear that in order to implement a letrec, which would allow you to express: (letrec ((circular (list 1 2 3 circular)) ...circular) Something would have to be fixed up after the structure was created. I have no idea how one would best implement this but I would assume that the compiler would substitute all all appropriate references to the named object with some sort of forwaring cell, which would be smashed to point to the whole object after it was created. I also know of no way that a pure functional program can perform these fixups. That's why I thought that it was important for the system to provide this. If I'm being totally brain damaged here then I'm sorry. We can, after all get back to those messages about &Rest args. Noone, yet, seems to have said that such a letrec would be a totally worthless thing. Equally, noone has been saying things like "well, it's too late/hard to put it into CL." Rice. -------  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Apr 88 18:46:16 EDT Received: from MCC.COM by SAIL.Stanford.EDU with TCP; 8 Apr 88 15:31:22 PDT Received: from Think.COM by MCC.COM with TCP; Fri 8 Apr 88 17:30:28-CDT Return-Path: Received: from sauron.think.com by Think.COM; Fri, 8 Apr 88 18:28:48 EDT Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 8 Apr 88 18:28:44 EDT Date: Fri, 8 Apr 88 18:29 EDT From: Barry Margolin Subject: &rest [discussion] replacement/addition To: gooch@mcc.com Cc: edsel!jonl%labrea.Stanford.EDU@mcc.com, common-lisp%sail.stanford.edu@mcc.com, spe%spice.cs.cmu.edu@mcc.com, ELIOT%cs.umass.edu@mcc.com, gz%spt.entity.com@mcc.com In-Reply-To: <880408160418.1.GOOCH@CHANGABANG.CAD.MCC.COM> Message-Id: <19880408222959.6.BARMAR@OCCAM.THINK.COM> I noticed you didn't try the following version. This is identical to the version you included in your message, except that it takes the previous words as a single argument rather than as an &REST argument. One definite advantage of this version is that it won't exceed CALL-ARGUMENTS-LIMIT if it recurses deeply. (defun anagrams (string &optional previous-words) (let ((chars (unused-characters string previous-words))) (if chars ;; there are unused characters left (let ((new-word (find-word chars))) (when new-word ;; found a new word (anagrams string (cons new-word previous-words)) ;; if no new word could be found, just return )) ;; all characters are used by previous-words, we have a weiner (save-and/or-print-anagram string previous-words) )))  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Apr 88 18:23:02 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 8 Apr 88 15:03:15 PDT Return-Path: Received: from sauron.think.com by Think.COM; Fri, 8 Apr 88 18:01:31 EDT Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 8 Apr 88 18:01:26 EDT Date: Fri, 8 Apr 88 18:02 EDT From: Barry Margolin Subject: Re: LetRec? To: James Rice Cc: Common-Lisp@sail.stanford.edu In-Reply-To: <12388873983.13.RICE@SUMEX-AIM.Stanford.EDU> Message-Id: <19880408220237.5.BARMAR@OCCAM.THINK.COM> Date: Fri, 8 Apr 88 12:17:20 PDT From: James Rice Is there a good reason why this was omitted from CL? It wasn't. It is caled LABELS. It only supports function binding (like FLET), but that is the only case where the distinction between LETREC and LET* is useful. I beg to differ. I appreciate that I can declare recursive local functions with Labels. I cannot, however refine recusive/ circular data structures with it. There seems to me to be a good symetry argument in favour of non-function LetRec to match with Labels. There also seems to be an argument in favour of it in that those wanting to progam in a pure functional style will not be able to declare circular structures in CL. I don't think you can create circular structures with Scheme's LETREC, either. The reason is that you would actually have to evaluate the variable while creating the structure, and the values of the variables being bound are undefined until all the initializations have completed. In the case of procedures this is OK, because you don't actually evaluate the procedure values until you invoke the procedure; all that is needed in order to create the procedure is that the environment be created with a placeholder for the procedure. So, (letrec ((factorial (lambda (x) (if (< 2 x) 1 (* x (factorial (- x 1))))))) (factorial 100)) works, but (letrec ((circular (list* 1 2 3 4 circular))) circular) is undefined, because the value of CIRCULAR is undefined at the time the LIST* form is being evaluated. In order to create circular structure, you have to do something like (let ((circular (list 1 2 3 4))) (setf (cdr (last circular)) circular) circular) I don't know how to do this kind of thing in a purely functional style.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Apr 88 17:31:13 EDT Received: from MCC.COM by SAIL.Stanford.EDU with TCP; 8 Apr 88 14:12:49 PDT Received: from HAL.CAD.MCC.COM by MCC.COM with TCP; Fri 8 Apr 88 16:07:12-CDT Received: from CHANGABANG.CAD.MCC.COM by HAL.CAD.MCC.COM via CHAOS with CHAOS-MAIL id 78623; Fri 8-Apr-88 16:07:05 CDT Date: Fri, 8 Apr 88 16:04 CDT From: William D. Gooch Subject: &rest [discussion] replacement/addition To: edsel!jonl%labrea.Stanford.EDU@MCC.COM cc: common-lisp%sail.stanford.edu@MCC.COM, spe%spice.cs.cmu.edu@MCC.COM, ELIOT%cs.umass.edu@MCC.COM, gz%spt.entity.com@MCC.COM In-Reply-To: <8804080800.AA04139@bhopal.lucid.com> Message-ID: <880408160418.1.GOOCH@CHANGABANG.CAD.MCC.COM> Reply-To: gooch@MCC.COM Postal-address: MCC-CAD 3.8108 Business-phone: (512) 338-3661 I have a simple anagram generator which, being highly recursive, is an interesting test of &rest behavior. (If you already believe me, you may skip to the tables at the end of this message.) This is a toy program, but it may provide some insight. The approach taken is to find a word made up of characters from the input string, then recur on the unused characters. One argument to the recursive call is a list of previously found words; when an anagram that exactly uses all the characters is identified, it is saved and/or printed from within the innermost stack frame in the recursion. The previous-words argument data can be dealt with in a straightforward fashion using &rest. For example (oversimplified for the purpose of illustration): (defun anagrams (string &rest previous-words) (let ((chars (unused-characters string previous-words))) (if chars ;; there are unused characters left (let ((new-word (find-word chars))) (when new-word ;; found a new word (apply #'anagrams string new-word previous-words) ;; if no new word could be found, just return )) ;; all characters are used by previous-words, we have a weiner (save-and/or-print-anagram string previous-words) ))) Note that there are no undesirable side-effects of list sharing since the list isn't changed except when it grows at the time of recursion. The same end can of course be accomplished by other means (see below). The runtime results in the table below were obtained using the form (without-interrupts (time (do-anagrams "" NIL))) -- the final argument of NIL specifies that results should be saved in a data structure rather than printed as they are identified. I ran the test with some variations on argument passing: (1) no use of &rest in the code at all. Instead I used a list whose length equalled the number of characters in the input string, added new words via (setf (car (nthcdr nwords previous-words)) new-word) and passed it through as a single argument on recursion. Variation (2) used &rest in the fashion shown above, with the default behavior (on a Symbolics, this is stack consing). For variation (3), I just added the form (setf previous-words (copy-list previous-words)) at the beginning of the function to simulate a gratuitously-consing &rest implementation. Anagram timings -- Symbolics Genera 7.1 on a 3600 running 3670 microcode input string code version runtime (sec) list consing (words) ------------------------------------------------------------------------- hi there (1) no &rest 14.38 144 hi there (2) &rest, no copy 14.29 144 hi there (3) &rest, copy 14.35 1428 ian gooch (1) no &rest 138.7 464 ian gooch (2) &rest, no copy 138.5 464 ian gooch (3) &rest, copy 138.7 6913 Two more variations are also interesting. To reorder the characters without consing, it was convenient to add some intermediate levels of recursion which don't appear in the above example. When I use &rest and apply for the reordering function as well as in the function anagrams as shown above, I get the following: input string code version runtime (sec) list consing (words) ------------------------------------------------------------------------- hi there all &rest, no copy 14.28 144 hi there all &rest, copy 14.77 6814 ian gooch all &rest, no copy 138.4 464 ian gooch all &rest, copy 140.0 30777 paul gooch all &rest, no copy 1018 820 paul gooch all &rest, copy 1020 33770 I would include more results, but they are all pretty consistent. Draw your own conclusions. I'm not advocating a particular point of view here, although I think &rest should always have a form which allows its user to control consing, regardless of how performance might or might not be affected. -- William D. Gooch  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Apr 88 17:14:43 EDT Received: from Xerox.COM by SAIL.Stanford.EDU with TCP; 8 Apr 88 13:57:18 PDT Received: from Cabernet.ms by ArpaGateway.ms ; 08 APR 88 13:56:47 PDT Date: Fri, 8 Apr 88 13:56:33 PDT From: Pavel.pa@Xerox.COM Subject: Re: LetRec? In-reply-to: <12388873983.13.RICE@SUMEX-AIM.Stanford.EDU> To: James Rice Cc: Common-Lisp@Sail.Stanford.EDU Message-ID: <880408-135647-9308@Xerox> I appreciate that I can declare recursive local functions with Labels. I cannot, however refine recusive/ circular data structures with it. There seems to me to be a good symetry argument in favour of non-function LetRec to match with Labels. There also seems to be an argument in favour of it in that those wanting to progam in a pure functional style will not be able to declare circular structures in CL. How will you implement it? More interestingly, how will you define its semantics? In particular, while this human can tell that there's a solution to the equation x = (cons 1 x) how is your compiler (or interpreter) going to distinguish that from x = (+ 1 x) or x = (foo 1 x) where ``foo'' is a function that I've written? I understand very well about the usual least-fixed-point semantics for LETREC, but those fixed-points are usually infinite or non-existent; how do you propose that the interpreter discover representations of such fixed-points in general? Pavel  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Apr 88 16:13:43 EDT Received: from SUMEX-AIM.Stanford.EDU by SAIL.Stanford.EDU with TCP; 8 Apr 88 12:58:42 PDT Date: Fri, 8 Apr 88 12:58:57 PDT From: James Rice Subject: LetRec To: Common-Lisp@Sail.Stanford.EDU Message-ID: <12388881557.13.RICE@SUMEX-AIM.Stanford.EDU> Sorry to all of you who might have been confused by my message. I was not thinking explicitly of Scheme's Letrec. I was thinking of a general recursive let construct, particularly for non-function objects, though I see no reason why such a construct could not be used for function objects too. Rice. -------  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Apr 88 15:55:00 EDT Received: from Riverside.SCRC.Symbolics.COM (SCRC-RIVERSIDE.ARPA) by SAIL.Stanford.EDU with TCP; 8 Apr 88 12:43:51 PDT Received: from EUPHRATES.SCRC.Symbolics.COM by Riverside.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 247044; Fri 8-Apr-88 15:42:30 EDT Date: Fri, 8 Apr 88 15:42 EDT From: David A. Moon Subject: Re: LetRec? To: James Rice cc: BarMar@Think.COM, Common-Lisp@SAIL.STANFORD.EDU In-Reply-To: <12388873983.13.RICE@SUMEX-AIM.Stanford.EDU> Message-ID: <19880408194257.6.MOON@EUPHRATES.SCRC.Symbolics.COM> Date: Fri, 8 Apr 88 12:17:20 PDT From: James Rice Is there a good reason why this was omitted from CL? It wasn't. It is caled LABELS. It only supports function binding (like FLET), but that is the only case where the distinction between LETREC and LET* is useful. I beg to differ. I appreciate that I can declare recursive local functions with Labels. I cannot, however refine recusive/ circular data structures with it. Perhaps I'm confused, but I don't think Scheme LETREC allows you to define recursive or circular data structures. Could you provide a program example, please?  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Apr 88 15:33:04 EDT Received: from SUMEX-AIM.Stanford.EDU by SAIL.Stanford.EDU with TCP; 8 Apr 88 12:17:36 PDT Date: Fri, 8 Apr 88 12:17:20 PDT From: James Rice Subject: Re: LetRec? To: BarMar@Think.COM cc: Common-Lisp@Sail.Stanford.EDU Message-ID: <12388873983.13.RICE@SUMEX-AIM.Stanford.EDU> Is there a good reason why this was omitted from CL? It wasn't. It is caled LABELS. It only supports function binding (like FLET), but that is the only case where the distinction between LETREC and LET* is useful. I beg to differ. I appreciate that I can declare recursive local functions with Labels. I cannot, however refine recusive/ circular data structures with it. There seems to me to be a good symetry argument in favour of non-function LetRec to match with Labels. There also seems to be an argument in favour of it in that those wanting to progam in a pure functional style will not be able to declare circular structures in CL. Rice. -------  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Apr 88 15:19:54 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 8 Apr 88 12:03:05 PDT Return-Path: Received: from sauron.think.com by Think.COM; Fri, 8 Apr 88 15:01:24 EDT Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 8 Apr 88 15:01:21 EDT Date: Fri, 8 Apr 88 15:02 EDT From: Barry Margolin Subject: LetRec? To: James Rice Cc: Common-Lisp@sail.stanford.edu In-Reply-To: <12388852434.13.RICE@SUMEX-AIM.Stanford.EDU> Message-Id: <19880408190237.2.BARMAR@OCCAM.THINK.COM> Date: Fri, 8 Apr 88 10:18:58 PDT From: James Rice Is there a good reason why this was omitted from CL? It wasn't. It is caled LABELS. It only supports function binding (like FLET), but that is the only case where the distinction between LETREC and LET* is useful.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Apr 88 13:34:27 EDT Received: from SUMEX-AIM.Stanford.EDU by SAIL.Stanford.EDU with TCP; 8 Apr 88 10:18:43 PDT Date: Fri, 8 Apr 88 10:18:58 PDT From: James Rice Subject: LetRec? To: Common-Lisp@Sail.Stanford.EDU Message-ID: <12388852434.13.RICE@SUMEX-AIM.Stanford.EDU> Is there a good reason why this was omitted from CL? Is it before the cleanup committee? Rice. -------  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Apr 88 06:52:23 EDT Received: from labrea.Stanford.EDU by SAIL.Stanford.EDU with TCP; 8 Apr 88 03:35:43 PDT Received: by labrea.Stanford.EDU; Fri, 8 Apr 88 02:35:13 PST Received: from bhopal.lucid.com by edsel id AA06276g; Fri, 8 Apr 88 03:28:35 PDT Received: by bhopal id AA04444g; Fri, 8 Apr 88 03:29:24 PDT Date: Fri, 8 Apr 88 03:29:24 PDT From: Jon L White Message-Id: <8804081029.AA04444@bhopal.lucid.com> To: mike%acorn@LIVE-OAK.LCS.MIT.EDU Cc: POTHIERS%TUVA.SAINET.MFENET@nmfecc.arpa, COMMON-LISP@sail.stanford.edu In-Reply-To: mike@gold-hill.com any day now's message of Wed, 6 Apr 88 09:10 est <8804062003.AA27180@edsel.lucid.com> re: There are a few problems here. First, to compile (setf (foo-a x) 1) you would have to have the structure predefined, since "setters" are not even required to be callable functions by common lisp. Interestingly enough, one of the proposals before the X3J13 "Cleanup" committee is to add the notion of SETF-FUNCTIONS to the language. This would provide for every accessor name, a canonical updator name such that if that updator name is fboundp, then it is the "callable function" for doing the SETF. It isn't immediately obvious from the "Cleanup" proposal, but a consequence is that (SETF (FOO ...) Y) will never generate an error during compilation or macroexpansion; for if there is no "SETF macro", then the canonical updator name must be used, and it is quite permissible to supply the defunition for that name at a later time (but of course, not later than the first call to it!). -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Apr 88 06:52:22 EDT Received: from labrea.Stanford.EDU by SAIL.Stanford.EDU with TCP; 8 Apr 88 03:35:12 PDT Received: by labrea.Stanford.EDU; Fri, 8 Apr 88 02:34:38 PST Received: from bhopal.lucid.com by edsel id AA06261g; Fri, 8 Apr 88 03:17:06 PDT Received: by bhopal id AA04429g; Fri, 8 Apr 88 03:17:54 PDT Date: Fri, 8 Apr 88 03:17:54 PDT From: Jon L White Message-Id: <8804081017.AA04429@bhopal.lucid.com> To: Stever@waikato.s4cc.symbolics.com Cc: ELIOT@cs.umass.edu, common-lisp@sail.stanford.edu In-Reply-To: Stephen Robbins's message of Wed, 6 Apr 88 12:43 EDT <19880406164304.2.STEVER@JEWEL-CAVE.S4CC.Symbolics.COM> Subject: &rest replacement/addition re: . . . We found that &REST CONSing was taking time and space we couldn't afford (the things it was doing to the freelist! :-) You didn't say what implementation of Common Lisp you were using. Some do ordinary CONSing for &rest lists; some do "stack allocation"; and finally others offer a DYNAMIC-EXTENT declaration so that you can choose, on a per-function basis. From your comment about the "freelist!", I would assume you were in an implementation that did ordinary consing. I wonder how the selective use of a DYNAMIC-EXTENT would have affected the project? -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Apr 88 04:34:16 EDT Received: from labrea.Stanford.EDU by SAIL.Stanford.EDU with TCP; 8 Apr 88 01:15:37 PDT Received: by labrea.Stanford.EDU; Fri, 8 Apr 88 00:14:59 PST Received: from bhopal.lucid.com by edsel id AA05804g; Fri, 8 Apr 88 00:59:49 PDT Received: by bhopal id AA04139g; Fri, 8 Apr 88 01:00:38 PDT Date: Fri, 8 Apr 88 01:00:38 PDT From: Jon L White Message-Id: <8804080800.AA04139@bhopal.lucid.com> To: Sean.Engelson@SPICE.CS.CMU.EDU Cc: common-lisp@sail.stanford.edu, spe@spice.cs.cmu.edu, ELIOT@cs.umass.edu, gz@spt.entity.com In-Reply-To: Sean.Engelson@SPICE.CS.CMU.EDU's message of Mon, 04 Apr 88 10:24:30 EDT <8804041428.AA16440@edsel.lucid.com> Subject: &rest [discussion] replacement/addition re: (defun fu (a &more-args) (do-args (arg) ...code... (moby-calculation a arg) ...more code... )) VAX/NIL had an adequate solution that didn't involve the kind of hidden state implicit in ideas similar to MacLisp's LEXPR's. There were two indicators for functions with "more" arguments -- &RESTV and &RESTL -- the former produced a simple (general) vector of the remaining arguments and the latter produced a list. The reason for this was that constructing a stack-allocated vector out of the "remaining" arguments is something that a stock-hardware implementation can do in essentially no time; but re-structuring the "remaining" arguments into a stack-allocated list takes time equivalent to ordinary listification of that many items. So in VAX/NIL, &REST was *ambiguous* as to whether you got a vector or list. The safe and portable style was to use &REST and access its components only with sequence-like functions that accept either a vector or a list (such as ELT, LENGTH, etc). Needless to say, all the appropriate functions were generalized to take vectors as well as list -- APPLY, MAP and so on. In some cases, we found it prudent to duplicate code -- once for the case when the &rest arg was a vector and once for when it was a list. Here is a trivial example: (defun + (&rest args &aux (result 0)) (if (listp args) (dolist (x args) (incf result x)) (dovector (x args) (incf result x))) result) ["trivial" since Common-Lisp MAP would be adequate here anyway]. We found it genuinely hard to justify the assertion that micro-differences in timings (due to this design) could amount to anything important in system performance. Hence it was very disappointing to see the Common Lisp votes during '82 and '83 opt only for the version inspired by the special-purpose hardware of the MIT LispMachine and its descendents. It is also disappointing to see the amount of time (and mailer/diskspace) wasted in defending a very quirky semantics for &rest lists -- that they may be "shared" due to a potential optimization in APPLY. (Note that this couldn't happen with &rest vectors). Despite what Will Clinger has argued, I think Chris Eliot's reasoning is the norm accepted in the user community -- namely that from the viewpoint of the callee, (foo 1 2 3) and (apply #'foo '(1 2 3)) should be received identically. It is a gross burden on the user to have to worry about hidden state in the implementation; a burden which I should hope would be imposed only when there is *great* gain to be had from doing so. Gail Zacharias talked about the common idiom of simply doing a COPY-LIST on every &rest argument, to insure some normalcy. Her reasoning seems, to me, to bolster the case for those who claim that that CL semantics are deficient: Subject: &REST Lists Date: 24 Mar 88 12:23:15 EST (Thu) From: gz@spt.entity.com (Gail Zacharias) . . . If Common Lisp doesn't require unshared &rest lists, then I think it must provide a declarative version of this idiom so the COPY-LIST can be portably avoided when it's redundant. Seems to me that the fact that this is a common case where users find a need for conditionalization indicates a real deficiency in Common Lisp's specification. . . . Of course, the problem isn't only the sharing of &rest lists, but the more common flaw that they may, unannouncedly, have dynamic extent. By this, I mean the bug where a stack-allocated &rest list can creep out into global data structures, even though it will surely disappear when the frame that created it returns. Allegedly, Symbolics is going to fix this bug in their next release (and TI may have already fixed it?); but we are now five years beyond the first CL specification! Perhaps just one more word on what I think "*great* gain" would mean (in the second paragraph back). For almost two months we have heard numerous "experts" claim that this ability to share &rest lists is an important, nay *critical*, component of optimization in certain implementations. I just don't believe these conjectures. Eliot has done a "bang up" job of presenting reasonable evidence that they can't be all that important; so NOW, it is up to the advocates of this "optimization" to present some hard evidence to the contrary. And PLEASE, NO MORE hypothetical cases of what MIGHT occur, or what COULD CONCEIVABLY be; either "put up" with some benchmark numbers from real applications (i.e., not just some fragments of a few functions or a couple lines of microcode), or "shut up". -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 8 Apr 88 03:19:06 EDT Received: from labrea.Stanford.EDU by SAIL.Stanford.EDU with TCP; 8 Apr 88 00:01:08 PDT Received: by labrea.Stanford.EDU; Thu, 7 Apr 88 23:00:33 PST Received: from bhopal.lucid.com by edsel id AA05582g; Thu, 7 Apr 88 23:53:02 PDT Received: by bhopal id AA04002g; Thu, 7 Apr 88 23:53:51 PDT Date: Thu, 7 Apr 88 23:53:51 PDT From: Jon L White Message-Id: <8804080653.AA04002@bhopal.lucid.com> To: jeff%aiva.edinburgh.ac.uk@nss.cs.ucl.ac.uk Cc: Common-Lisp@sail.stanford.edu, @relay.cs.net:ELIOT@cs.umass.edu In-Reply-To: Jeff Dalton's message of Sat, 2 Apr 88 18:54:38 bst <29307.8804021754@aiva.ed.ac.uk> Subject: &Rest Lists re: > FOO is a null function needed to prevent optimization. > (dotimes (i 10000000) (cons 1 2)) is optimized to: > (dotimes (i 10000000) nil) so: Why isn't it optimized to just NIL? Conjecture: it is an easy optimization to notice that a side-effect-free function is being called in a place where no values are expected back (i.e., the call is only "for effects"); but it is much harder to have an analyzer for tagbodies which usefully notices that they "don't do anything". -- JonL --  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 7 Apr 88 14:03:57 EDT Received: from rutgers.edu by SAIL.Stanford.EDU with TCP; 7 Apr 88 10:45:08 PDT Received: by rutgers.edu (5.54/1.15) with UUCP id AA07408; Thu, 7 Apr 88 11:22:46 EDT Date: Thu, 7 Apr 88 11:22:46 EDT From: moss!whuts!davel@att.arpa Message-Id: <8804071522.AA07408@rutgers.edu> Received: by bellcore.bellcore.com (smail2.5) id AA09765; 7 Apr 88 10:06:12 EDT (Thu) To: common-lisp@sail.stanford.edu Subject: Re: Problems with SETF and structures Cc: davel@att.arpa >Using CLOS, there is a better solution to your problem. Using CLOS and >taking advantage of one of the cleanup committee's proposals to cleanup >setf there is an even better solution. >Solution 1 - Using CLOS. >(defsetf foo-a set-foo-a) >(defsetf foo-b set-foo-b) . . >(defun test () > (let (x) > (add-named-class > :name foo > :superclasses () > :slot-specifications '((a :reader foo-a > :writer set-foo-a) > (b :reader foo-b > :writer set-foo-b) > . > .)) > (setq x (make-instance 'foo)) > (setf (foo-a x) 1))) I fail to see the advantage of defining structures on the fly if you must define their accessors up front. How can the method above handle the situation if, for example, the slotnames or object name are unknown at compile time. E.g.: (DEFUN Make-Thingy (name slots) (ADD-NAMED-CLASS :name name :superclasses () :slot-specifications slots) (LET ((x (MAKE-INSTANCE name))) (SETF 1) x)) where is some notation for the accessor to the first slot of this new structure. >Solution 2 - Using CLOS and cleanup up setf >The basic difference is that you don't have to do the defsetfs. The >reason is that setf is defined to expand into a well-know function when ^^^^^^^^^ ^^^^^^^^ >there hasn't been an explicit defsetf done. >(defun test () > (let (x) > (add-named-class > :name foo > :superclasses () > :slot-specifications '((a :accessor foo-a) > (b :accessor foo-b) > . > .)) > (setq x (make-instance 'foo)) > (setf (foo-a x) 1))) I thought the idea behind add-named-class is to allow the creation on the fly of new structure classes. Since the structure is not created until run time, how can the compiler know at compile time how to expand (setf (foo-a x) 1)? If the compiler simply expands out the add-named-class at compile time, thereby defining foo-a and its setf form, how does this differ from (defstruct foo a b ...) (or its equivalent in Flavors or LOOPS)? As a further question, what is supposed to happen if two different functions each are capable of defining structure FOO, and a third function uses a FOO-A accessor? Depending upon which of the other two functions is run first, FOO-A could refer to either of two different slots in the actual FOO structure. What is a compiler supposed to do with that? How is the compiler supposed to distinguish FOO-A, a FOO accessor defined by both functions, from FOO-B, which is only defined by one of the functions, from FOO-C, which is a typo and should generate at least a warning? David Loewenstern AT&T Bell Labs -- Whippany, NJ {backbone}!rutgers!moss!whuts!davel -- or -- loewenst@paul.rutgers.edu  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 6 Apr 88 16:58:44 EDT Received: from Xerox.COM by SAIL.Stanford.EDU with TCP; 6 Apr 88 13:41:15 PDT Received: from Semillon.ms by ArpaGateway.ms ; 06 APR 88 13:40:56 PDT Date: Wed, 6 Apr 88 13:39 PDT From: Gregor.pa@Xerox.COM Subject: Problems with setf and structures To: "mike@gold-hill.com any day now" cc: POTHIERS%TUVA.SAINET.MFENET@NMFECC.ARPA, COMMON-LISP@SAIL.STANFORD.EDU Fcc: BD:>Gregor>mail>outgoing-mail-2.text In-Reply-To: The message of 6 Apr 88 07:10 PDT from "mike@gold-hill.com any day now" Message-ID: <880406133904.2.GREGOR@SPIFF.parc.xerox.com> Line-fold: no Using CLOS, there is a better solution to your problem. Using CLOS and taking advantage of one of the cleanup committee's proposals to cleanup setf there is an even better solution. Solution 1 - Using CLOS. (defsetf foo-a set-foo-a) (defsetf foo-b set-foo-b) . . (defun test () (let (x) (add-named-class :name foo :superclasses () :slot-specifications '((a :reader foo-a :writer set-foo-a) (b :reader foo-b :writer set-foo-b) . .)) (setq x (make-instance 'foo)) (setf (foo-a x) 1))) Solution 2 - Using CLOS and cleanup up setf The basic difference is that you don't have to do the defsetfs. The reason is that setf is defined to expand into a well-know function when there hasn't been an explicit defsetf done. (defun test () (let (x) (add-named-class :name foo :superclasses () :slot-specifications '((a :accessor foo-a) (b :accessor foo-b) . .)) (setq x (make-instance 'foo)) (setf (foo-a x) 1))) -------  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 6 Apr 88 15:40:42 EDT Received: from CAD.CS.CMU.EDU by SAIL.Stanford.EDU with TCP; 6 Apr 88 12:24:56 PDT Date: Wed, 6 Apr 88 15:25:26 EDT From: Mark.Perlin@CAD.CS.CMU.EDU To: POTHIERS%TUVA.SAINET.MFENET@NMFECC.ARPA, mike%acorn@LIVE-OAK.LCS.MIT.EDU Subject: Re: Cc: COMMON-LISP@SAIL.STANFORD.EDU Sorry about that; misdirected mail.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 6 Apr 88 14:54:26 EDT Received: from XX.LCS.MIT.EDU by SAIL.Stanford.EDU with TCP; 6 Apr 88 11:36:11 PDT Received: from LIVE-OAK.LCS.MIT.EDU by XX.LCS.MIT.EDU via Chaosnet; 6 Apr 88 09:41-EDT Received: from ACORN.Gold-Hill.DialNet.Symbolics.COM by MIT-LIVE-OAK.DialNet.Symbolics.COM via DIAL with SMTP id 86292; 6 Apr 88 09:28:01-EDT Received: from BOSTON.Gold-Hill.DialNet.Symbolics.COM by ACORN.Gold-Hill.DialNet.Symbolics.COM via CHAOS with CHAOS-MAIL id 98154; Wed 6-Apr-88 09:10:47-EST Date: Wed, 6 Apr 88 09:10 est From: mike%acorn@oak.lcs.mit.edu (mike@gold-hill.com any day now) COMMENTS: NOTE %acorn@oak... WILL BECOME @GOLD-HILL.COM ANY DAY NOW To: POTHIERS%TUVA.SAINET.MFENET@NMFECC.ARPA Subject: Cc: COMMON-LISP@SAIL.STANFORD.EDU Date: Tue, 5 Apr 88 11:29:13 PDT From: POTHIERS%TUVA.SAINET.MFENET@NMFECC.ARPA Subject: Defstructs Date: Tue, 5-APR-1988 10:55 MST X-VMS-Mail-To: @COMMON-LISP I'm trying to create structures on the fly. I have a problem with: (defun test (&aux x) (defstruct foo a b c) (setf x (make-foo)) (setf (foo-a x) 1) ) When TEST is interpreted, all is fine. When it is compiled the function (foo-a) is undefined since it isn't created by defstruct until run time. In my actual code FOO is a symbol that's build based upon some args to TEST, therefore I can't simply put the defstruct at the top level. Any ideas?? There are a few problems here. First, to compile (setf (foo-a x) 1) you would have to have the structure predefined, since "setters" are not even required to be callable functions by common lisp. I have to ask why you have to do this in this fashion. It appears you need to dynamically create named record "types". The way to do this is not necessarily to evaluate a defstruct at run time. I'd do it by inventing a meta-structure type. (defstruct record (name (gensym) :type symbol) (slots #() :type vector)) or something like that. Then I'd use the copier to create new instances, the constructor to create the initial "prototype" instance, etc. You'd have to create your own predicates for recognizing them and relating them. This is unfortunately, exactly the way you'd have to do it in a statically typed programming language. ...mike beckerle Gold Hill  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 6 Apr 88 13:13:12 EDT Received: from WAIKATO.S4CC.Symbolics.COM ([128.81.51.90]) by SAIL.Stanford.EDU with TCP; 6 Apr 88 09:56:26 PDT Received: from JEWEL-CAVE.S4CC.Symbolics.COM by WAIKATO.S4CC.Symbolics.COM via CHAOS with CHAOS-MAIL id 167878; Wed 6-Apr-88 12:43:05 EDT Date: Wed, 6 Apr 88 12:43 EDT From: Stephen Robbins Subject: &rest replacement/addition To: ELIOT@cs.umass.edu cc: common-lisp@sail.stanford.edu In-Reply-To: Msg of 5 Apr 1988 12:55-EDT from ELIOT at cs.umass.edu Message-ID: <19880406164304.2.STEVER@JEWEL-CAVE.S4CC.Symbolics.COM> Date: Tuesday, 5 April 1988 12:55-EDT From: ELIOT at cs.umass.edu There is the impression that this feature introduces an unacceptible inefficiency in programs. From the data that is available it seems that this is just being scared of the dark. It is also possible that my data sample is somehow unrepresentative. The code I analyzed was Lisp Machine system code. Last year, I wrote a window system in Common Lisp. I needed a simple flavors system to support it. My generic function dispatcher used &REST and APPLY to pass arguments from the generic function to the method handling the generic function. Since the window system was used everywhere in our product, we needed maximum efficiency in time and space. We found that &REST CONSing was taking time and space we couldn't afford (the things it was doing to the freelist! :-) So much so that we had to make it a general shop policy not to use &REST. Maybe this is an issue of "the compiler writers should be smarter." But we're a startup. We can't wait for the compiler writers to get smarter. For that matter, we can't wait for an &REST replacement. If Common Lisp wants to be commercially viable, it needs to address these issues in some form, however inelegant it may be to have to worry about them. There are certainly ways around using &REST in a flavor system. But they're bulky, cumbersome, and take time to write and debug. Time that we needed to spend writing the body of our product. Our choice: use &REST and be too slow and too large, or program around it, making it a useless feature. I'm not sure what the "correct" replacement/extension for it is, but in my experience, &REST \can/ be too slow and too space consuming for use in a real, deliverable product. -- Stephen  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 6 Apr 88 12:41:15 EDT Received: from NMFECC.ARPA by SAIL.Stanford.EDU with TCP; 6 Apr 88 09:26:16 PDT Received: from tuva.sainet.mfenet by ccc.mfenet with Tell via MfeNet ; Wed, 6 Apr 88 09:23:25 PDT Date: Wed, 6 Apr 88 09:23:25 PDT From: POTHIERS%TUVA.SAINET.MFENET@NMFECC.ARPA Message-Id: <880406092325.20a0021c@NMFECC.ARPA> To: COMMON-LISP@SAIL.STANFORD.EDU Subject: CLOS Date: Wed, 6-APR-1988 08:50 MST X-VMS-Mail-To: @[.SIGS]COMMON-LISP Anyone know where I can get CLOS? Steve Pothier  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 6 Apr 88 02:25:22 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 5 Apr 88 23:05:25 PDT Received: from relay2.cs.net by RELAY.CS.NET id ab00602; 6 Apr 88 1:54 EDT Received: from cs.umass.edu by RELAY.CS.NET id bk11113; 6 Apr 88 1:43 EDT Date: Tue, 5 Apr 88 12:55 EDT From: ELIOT@cs.umass.edu Subject: &rest replacement/addition To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.EDU" I had hoped that the semantics of &rest lists could be completely specified without or before getting into murky side issues like this. Given my position on previous issues it should not be a surprise that I am strongly opposed to all of the &rest replacement/additon proposals. I consider &rest to be a fine feature that is completely adequate for solving the problems of passing indefinate numbers of arguments. I consider it sufficiently good that it is worth spending considerable effort giving it a precise specification, as we have been trying to do. I don't think it needs replacement. There has only been one criticism of &Rest lists. There is the impression that this feature introduces an unacceptible inefficiency in programs. This impression is sufficiently strong that people are considering pulling one of Maclisp's kludgest features out of its grave, introducing new strange data types to Common Lisp and doing all kinds of horrible things in order to eliminate this ineficiency. From the data that is available it seems that this is just being scared of the dark. The statistics I collected do not directly measure the bottom line efficiency of using &Rest lists. This certainly means that it is "possible" for dynamic situations to exist where the efficiency of &Rest lists is exagerated. It is also possible that my data sample is somehow unrepresentative. Someone suggested that the low usage of &Rest could be explained because programmers fear its inefficiency. This is unlikely. The code I analyzed was Lisp Machine system code. Most of this code was written as ZetaLisp code, in which &Rest lists are *more* efficient than they are in Common Lisp. (Because of stack consing.) In fact, while &Rest may be less efficient in Common Lisp it may be used more, perhaps because it is better specified and thus more valuable from an algorithmic standpoint. About 10% of the Common Lisp functions used &Rest arguments. I believe this is probably an upper bound. A great deal of effort has been spent on this mailing list thinking of ways to generalize all of the primitives in Common Lisp. Despite this effort to generalize the primitives, 90% of the time there has been no good reason to use &Rest lists. Furthermore, I believe there is an explanation for why people "have the impression" that &rest/Apply must be highly optimized. Both of these are used in somewhat unusual coding situations that require somewhat more thought than normal. A tricky piece of code requires more attention from the programmer. A common trap is to think the program spends as much time executing code as the programmer spends writing it. Without any data to support another position all of the proposals to replace &Rest or augment it should be rejected, and its semantics should be precisely defined as I have previously proposed.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 6 Apr 88 02:18:28 EDT Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 5 Apr 88 22:57:35 PDT Received: from relay2.cs.net by RELAY.CS.NET id ah00702; 6 Apr 88 2:02 EDT Received: from cs.umass.edu by RELAY.CS.NET id cd11113; 6 Apr 88 1:50 EDT Date: Tue, 5 Apr 88 15:38 EDT From: MURRAY@cs.umass.edu Subject: &Rest args and Optimizations To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: CLMAIL NOTE: The ELIOT that has been arguing about &Rest args is Chris Eliot, and NOT Eliot Moss, as someone believed. Sharing an &Rest list with a list given to apply is clearly an optimization, and as such, should not be required. However, if it is allowed, destructively modifying an &rest list becomes extremely dangerous, and hence should never be done. In fact, it might be appropriate to say it is "an error" to modify one. I think this is a big mistake. The cleaner approach to this and other issues like it is to consider the language issues first. A well-defined language that is portable, easy to understand and debug is what's important. Optimizations are the domain of the implementation. That's the whole idea behind DECLARE. Smart Compilers, tricky type representations, multiple function entry points, etc, are important, but are all PERFORMANCE issues, not semantic ones. In the case of &Rest args, it seems to me that the right way to deal with it is to say the list is always freshly consed. If a compiler can recognize that the list is never modified, it would be free share it's structure with an Apply arg. If it can determine the list is inaccessable on function return, it is free to stack-allocate it. Providing declarations to help the compiler are very useful, but still can be ignored without changing the program's correctness. In regards to &More, or whatever, I think the &Rest mechanism is perfectly adequate. A stack consed &Rest eliminates the conses, which seems to be what people want to avoid.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 5 Apr 88 17:53:06 EDT Received: from NMFECC.ARPA by SAIL.Stanford.EDU with TCP; 5 Apr 88 14:37:35 PDT Received: from tuva.sainet.mfenet by ccc.mfenet with Tell via MfeNet ; Tue, 5 Apr 88 11:29:13 PDT Date: Tue, 5 Apr 88 11:29:13 PDT From: POTHIERS%TUVA.SAINET.MFENET@NMFECC.ARPA Message-Id: <880405112913.2020021c@NMFECC.ARPA> To: COMMON-LISP@SAIL.STANFORD.EDU Subject: Defstructs Date: Tue, 5-APR-1988 10:55 MST X-VMS-Mail-To: @COMMON-LISP I'm trying to create structures on the fly. I have a problem with: (defun test (&aux x) (defstruct foo a b c) (setf x (make-foo)) (setf (foo-a x) 1) ) When TEST is interpreted, all is fine. When it is compiled the function (foo-a) is undefined since it isn't created by defstruct until run time. In my actual code FOO is a symbol that's build based upon some args to TEST, therefore I can't simply put the defstruct at the top level. Any ideas?? Steve Pothier SAIC  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 5 Apr 88 09:07:31 EDT Received: from XX.LCS.MIT.EDU by SAIL.Stanford.EDU with TCP; 5 Apr 88 05:50:16 PDT Received: from LIVE-OAK.LCS.MIT.EDU by XX.LCS.MIT.EDU via Chaosnet; 5 Apr 88 08:49-EDT Received: from ACORN.Gold-Hill.DialNet.Symbolics.COM by MIT-LIVE-OAK.DialNet.Symbolics.COM via DIAL with SMTP id 86182; 5 Apr 88 08:47:36-EDT Received: from BOSTON.Gold-Hill.DialNet.Symbolics.COM by ACORN.Gold-Hill.DialNet.Symbolics.COM via CHAOS with CHAOS-MAIL id 98040; Tue 5-Apr-88 07:52:45-EST Date: Tue, 5 Apr 88 06:53 est From: mike%acorn@oak.lcs.mit.edu (mike@gold-hill.com any day now) COMMENTS: NOTE %acorn@oak... WILL BECOME @GOLD-HILL.COM ANY DAY NOW To: rst@Think.COM Subject: Re: &rest replacement/addition Cc: Sean.Engelson@spice.cs.cmu.edu, barmar@Think.COM, common-lisp@sail.stanford.edu, spe@spice.cs.cmu.edu But can an object of type MORE-ARGS be returned from a function, or otherwise stuffed in data structures which survive the dynamic extent of the function call that spawned them? That's what this whole argument started with... I agree. Are there any examples of CL constructs which allow a reference to an object which has only dynamic extent? The closest thing I can think of is WITH-OPEN-FILE, but that just insures that the stream is closed, not that it's storage is reclaimed. My intuition is also that allowing a first-class reference for a dynamic-extent object is a bad idea. ...mikeb  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 4 Apr 88 13:57:35 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 4 Apr 88 10:37:49 PDT Return-Path: Received: from sauron.think.com by Think.COM; Mon, 4 Apr 88 13:35:29 EDT Received: from OCCAM.THINK.COM by sauron.think.com; Mon, 4 Apr 88 13:35:24 EDT Date: Mon, 4 Apr 88 13:36 EDT From: Barry Margolin Subject: Re: &rest replacement/addition To: rst@Think.COM Cc: Sean.Engelson@spice.cs.cmu.edu, common-lisp@sail.stanford.edu, spe@spice.cs.cmu.edu In-Reply-To: <8804041629.AA00637@pozzo.think.com> Message-Id: <19880404173633.6.BARMAR@OCCAM.THINK.COM> Date: Mon, 4 Apr 88 12:29:50 edt From: rst@Think.COM From: Barry Margolin Subject: &rest replacement/addition Actually, if this were added, the operations that extract the arguments need not be special forms. &MORE-ARGS could bind to an object of type MORE-ARGS. Common Lisp would only specify accessors for this object, so it could be passed along with no possibility of strange side-effects. APPLY could also be extended to allow a MORE-ARGS in place of a list as its last argument. barmar But can an object of type MORE-ARGS be returned from a function, or otherwise stuffed in data structures which survive the dynamic extent of the function call that spawned them? That's what this whole argument started with... No, I don't think that's what started this particular argument. The issue of stack-consed &REST lists is completely independent of the issue of side-effects on shared &REST lists. They are two orthogonal mechanisms for speeding up calls to &REST functions; in fact, they each address different cases (stack consing speeds up normal calls, sharing speeds up calls via APPLY). The above only addresses the issue of preventing the strange side-effects that the latter allows, which is what this discussion has been about. I almost added a sentence that said that this doesn't affect the stack-allocation issue, as those implementations that currently allocate &REST lists on the stack would probably want to allocate &MORE-ARGS objects there, too. Dynamic-extent &REST lists have never been valid Common Lisp (there are examples on p.64 of CLtL that fail when &REST lists are stack-consed). If this new proposal were to be adopted, I doubt X3J13 would allow them to be stack-allocated, either. Presumably, Symbolics's excuse for continuing to stack-cons &REST lists is that they were doing so before Common Lisp, and they haven't gotten around to changing it. They wouldn't have such an excuse with the new mechanism. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 4 Apr 88 13:19:25 EDT Received: from rdcf.sm.unisys.com by SAIL.Stanford.EDU with TCP; 4 Apr 88 10:01:40 PDT Received: by rdcf.sm.unisys.com (sdcrdcf) (5.51/Domain/jpb/2.9) id AA19097; Mon, 4 Apr 88 09:01:17 PST Message-Id: <8804041701.AA19097@rdcf.sm.unisys.com> Received: from XERXES by sdcrdcf with PUP; Mon, 4 Apr 88 09:00 PST From: darrelj@sm.unisys.com Date: 4 Apr 88 10:00 PDT (Monday) Subject: Re: &rest replacement/addition In-Reply-To: Barry Margolin 's message of Mon, 4 Apr 88 11:09 EDT To: Barry Margolin Cc: Sean.Engelson@spice.cs.cmu.edu, common-lisp@sail.stanford.edu, spe@spice.cs.cmu.edu Date: Mon, 4 Apr 88 11:09 EDT From: Barry Margolin Subject: &rest replacement/addition To: Sean.Engelson@spice.cs.cmu.edu Cc: common-lisp@sail.stanford.edu, spe@spice.cs.cmu.edu Date: Mon, 04 Apr 88 10:24:30 EDT From: Sean.Engelson@spice.cs.cmu.edu (defun fu (a &more-args) (do-args (arg) ...code... (moby-calculation a arg) ...more code... )) This is similar in spirit to MacLisp's lexprs, which also had special forms for accessing the arguments. However, it needs a minor fix to prevent it from sharing one of their faults, too. &MORE-ARGS should be followed by a symbol, which would be used as an argument to the special forms.... barmar Or like the Interlisp nospread, in which (LAMBDA N (COND ((> N 3) (F (ARG N 1) ...)...) has the same result as Common Lisp (LAMBDA (&REST N) (COND((> (LENGTH N)3) (F (NTH N 1) ...)....) The lambda variable is bound to the count, the actual arguments usually hide in the stack, but that is of course an implementation decision. (ARG var pos) fetches the specified positional argument for the named nospread variable. The compiler often produces better code when the named variable is the local argument (in Interlisp-D (ARG N 1) emits identical code for a local nospread argument as for the first argument of a regular lambda arglist). There is even a (SETARG var pos) for modifying one of the arguments. It of course has most of the same implementation problems that started the &REST and APPLY discussion if you decide to implement it via lists. However, since there is no name for all arguments, you don't give APPLY the same oportunity to copy or not copy the list which might be coming in. Darrel J. Van Buer p.s. Most interlisp functions which use nospread arguments are of two kinds: Ones like append which might otherwise be coded as commonlisp &REST where compiler macros would normally get rid of the arglist consing anyway. Ones implementing a Commonlisp &OPTIONAL argument.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 4 Apr 88 12:47:09 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 4 Apr 88 09:31:56 PDT Return-Path: Received: from pozzo.think.com by Think.COM; Mon, 4 Apr 88 12:29:54 EDT Received: by pozzo.think.com; Mon, 4 Apr 88 12:29:50 edt Date: Mon, 4 Apr 88 12:29:50 edt From: rst@Think.COM Message-Id: <8804041629.AA00637@pozzo.think.com> To: Sean.Engelson@spice.cs.cmu.edu, barmar@Think.COM Subject: Re: &rest replacement/addition Cc: common-lisp@sail.stanford.edu, spe@spice.cs.cmu.edu From: Barry Margolin Subject: &rest replacement/addition Actually, if this were added, the operations that extract the arguments need not be special forms. &MORE-ARGS could bind to an object of type MORE-ARGS. Common Lisp would only specify accessors for this object, so it could be passed along with no possibility of strange side-effects. APPLY could also be extended to allow a MORE-ARGS in place of a list as its last argument. barmar But can an object of type MORE-ARGS be returned from a function, or otherwise stuffed in data structures which survive the dynamic extent of the function call that spawned them? That's what this whole argument started with... (Sean's original proposal had no &more-args variables. Any implementation would, of necessity, have some such thing internally, but users would not be able to get their hands on them). rst  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 4 Apr 88 11:23:40 EDT Received: from Think.COM by SAIL.Stanford.EDU with TCP; 4 Apr 88 08:10:03 PDT Return-Path: Received: from sauron.think.com by Think.COM; Mon, 4 Apr 88 11:08:12 EDT Received: from OCCAM.THINK.COM by sauron.think.com; Mon, 4 Apr 88 11:08:08 EDT Date: Mon, 4 Apr 88 11:09 EDT From: Barry Margolin Subject: &rest replacement/addition To: Sean.Engelson@spice.cs.cmu.edu Cc: common-lisp@sail.stanford.edu, spe@spice.cs.cmu.edu In-Reply-To: <8804041424.AA20946@Think.COM> Message-Id: <19880404150918.4.BARMAR@OCCAM.THINK.COM> Date: Mon, 04 Apr 88 10:24:30 EDT From: Sean.Engelson@spice.cs.cmu.edu (defun fu (a &more-args) (do-args (arg) ...code... (moby-calculation a arg) ...more code... )) This is similar in spirit to MacLisp's lexprs, which also had special forms for accessing the arguments. However, it needs a minor fix to prevent it from sharing one of their faults, too. &MORE-ARGS should be followed by a symbol, which would be used as an argument to the special forms. This way you can have nested functions that use &MORE-ARGS and be able to access the outer function's arguments from the inner function. Actually, if this were added, the operations that extract the arguments need not be special forms. &MORE-ARGS could bind to an object of type MORE-ARGS. Common Lisp would only specify accessors for this object, so it could be passed along with no possibility of strange side-effects. APPLY could also be extended to allow a MORE-ARGS in place of a list as its last argument. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 4 Apr 88 10:39:00 EDT Received: from SPICE.CS.CMU.EDU by SAIL.Stanford.EDU with TCP; 4 Apr 88 07:24:49 PDT Received: from SPICE.CS.CMU.EDU by SPICE.CS.CMU.EDU; 4 Apr 88 10:24:40 EDT To: common-lisp@sail.stanford.edu cc: spe@SPICE.CS.CMU.EDU Subject: &rest replacement/addition Date: Mon, 04 Apr 88 10:24:30 EDT From: Sean.Engelson@SPICE.CS.CMU.EDU In view of all of the recent furor about &rest, perhaps, as Mr. Gooch suggests, a different mechanism is in order. I'd like to suggest one, as a starting point for discussion. This idea may have been discussed already, or maybe even implemented somewhere, but I'll suggest it anyway. We need a way to have indefinite numbers of arguments, without the overhead and semantic problems inherent in consing up (or not consing up) lists. How about a new lambda-list keyword, maybe &more-args, and a couple of special forms to deal with them, DO-ARGS and NEXT-ARG, maybe ARGS-TO-LIST even. So you'd have code like the following: (defun fu (a &more-args) (do-args (arg) ...code... (moby-calculation a arg) ...more code... )) etc... The nice thing about this is that the implementation can do whatever it wants with things, shove them on the stack, save APPLY lists, etc., and the semantics remain clean. The disadvantage is that this introduces more 'side-effecting' semantics into the language, but then, Common Lisp was never too clean on that score anyway. What do you all think? -Sean Engelson- Carnegie-Mellon University  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 4 Apr 88 10:04:17 EDT Received: from HAL.CAD.MCC.COM by SAIL.Stanford.EDU with TCP; 4 Apr 88 06:49:01 PDT Received: from CHANGABANG.CAD.MCC.COM by HAL.CAD.MCC.COM via CHAOS with CHAOS-MAIL id 77805; Mon 4-Apr-88 08:21:10 CDT Date: Mon, 4 Apr 88 08:20 CDT From: William D. Gooch Subject: RE: &Rest Lists To: ELIOT%cs.umass.edu@MCC.COM cc: Common-Lisp@SAIL.STANFORD.EDU In-Reply-To: <8804020802.AA15477@cadillac> Message-ID: <880404082053.2.GOOCH@CHANGABANG.CAD.MCC.COM> Reply-To: gooch@MCC.COM Postal-address: MCC-CAD 3.8108 Business-phone: (512) 338-3661 Instead of beating &rest into dust because it isn't exactly the thing you want, why not talk adding about a different mechanism that is? Perhaps you would like something that supports an indefinite number of arguments but does not make them accessible as a list. -- William D. Gooch  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 2 Apr 88 13:11:14 EST Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 2 Apr 88 09:58:26 PST Received: from aiva.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP id aa01191; 2 Apr 88 18:55 BST From: Jeff Dalton Date: Sat, 2 Apr 88 18:54:38 bst Message-Id: <29307.8804021754@aiva.ed.ac.uk> To: Common-Lisp@sail.stanford.edu, ELIOT <@relay.cs.net:ELIOT@cs.umass.edu> Subject: Re: &Rest Lists > Date: Fri, 1 Apr 88 15:15 EDT > From: ELIOT@edu.umass.cs > the fact that &Rest is used in a small minority of function > definitions, while APPLY is very rare strongly suggests that > their combined use in a single function call is very rare > indeed. Consequently these statistics do not support the idea > that this case needs to be highly optimized. While it is true that the statistics do not support the optimization, there are clearly additional factors to consider (as you have mentioned). One is that programmers may avoid this case because they know it will often be inefficient. Another is that, in a dynamic analysis, the cases where the construction is used may turn out to be important. I know that I use it less often than I would like to. > FOO is a null function needed to prevent optimization. > (dotimes (i 10000000) (cons 1 2)) is optimized to: > (dotimes (i 10000000) nil) so: Why isn't it optimized to just NIL?  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 2 Apr 88 02:45:54 EST Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 1 Apr 88 23:27:52 PST Received: from relay2.cs.net by RELAY.CS.NET id ab03466; 2 Apr 88 2:23 EST Received: from cs.umass.edu by RELAY.CS.NET id cd10549; 2 Apr 88 2:14 EST Date: Fri, 1 Apr 88 15:15 EDT From: ELIOT@cs.umass.edu Subject: &Rest Lists To: Common-Lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"Common-Lisp@sail.stanford.edu" In order to clarify the importance of optimized handling of &Rest arguments, compared to the importance of specifying their semantics more precisely I have collected some statistics. The functions used to collect these are included at the end of this message. I encourage others to use these functions to obtain measurements of their own code. Using APROPOS it is possible to measure how many functions take &Rest arguments. On an Explorer I got the following results: PACKAGE with &Rest Without Percent ------------------------------------ LISP 70 580 10.7 SI 73 3384 2.1 ZWEI 66 2324 2.7 TV 79 1177 6.2 FS 54 707 7.0 FORMAT 11 105 9.4 ------------------------------------ Subtotal 283 7697 3.5 KEE 234 5120 4.3 (IntelliCorp's package) ------------------------------------ Total 517 12817 3.8 Unfortunately, since calls to APPLY are optimized they cannot be analyzed with WHO-CALLS. Instead I searched the source code of the NIL compiler for lines containing the strings "(APPLY" and "&REST". These include comment lines, and parsing of argument lists. (The paren in "(APPLY" eliminates some of that.) From nil$disk:[nil.h]*.lsp Lines Textually Containing: "(APPLY" "&Rest" "defun" TOTAL LINES ------------------------------------------------- 18 61 859 24799 So 7.1% of these function definitions take &rest arguments. (Including NIL specific &Restv, &Restl.) Too many assumptions must be made for a realistic estimate of the actual optimization value of specially handling &rest lists to be made using these numbers. These numbers all refer to source code statistics, while the actual optimization depends upon instruction stream characteristics. However, the fact that &Rest is used in a small minority of function definitions, while APPLY is very rare strongly suggests that their combined use in a single function call is very rare indeed. Consequently these statistics do not support the idea that this case needs to be highly optimized. The 70 Explorer LISP package (i.e. Common Lisp) functions with &Rest arguments are: ------------------------------------------------------ ;;; Unclassified: MAPHASH MAKE-CONCATENATED-STREAM ARRAY-ROW-MAJOR-INDEX MAKE-BROADCAST-STREAM ADJUST-ARRAY ROOM ;;; IO Functions: YES-OR-NO-P CERROR ERROR FORMAT WARN BREAK Y-OR-N-P ;;; Primitives perhaps known to the compiler: APPEND MAPC = MAX NOTANY SBIT BIT < MAPCON /= MAPLIST LIST* MAPCAN AREF ARRAY-IN-BOUNDS-P / CONCATENATE MAPCAR MAPL - VECTOR FUNCALL MIN XOR EVERY NOTEVERY <= APPLY + MAP VALUES * >= SOME LIST NCONC IGNORE > LOGIOR LOGEQV LOGXOR LOGAND LCM GCD BOOLE CHAR-NOT-GREATERP CHAR-NOT-LESSP CHAR-NOT-EQUAL CHAR> CHAR< CHAR/= CHAR-EQUAL CHAR= CHAR<= CHAR-LESSP CHAR-GREATERP CHAR>= ------------------------------------------------------ The overall importance of optimizing CONSing also depends upon the speed of CONSing. Since one of the most important known uses of APPLY where &Rest arguments are an issue involves calling FORMAT it is important to compare CONSing speed with I/O speed. On an Explorer II, GC-ON, everything compiled: Function Calls Time Normalized to 1,000,000 Calls ------------------------------------------------------------------- (foo (cons 1 2)) 10,000,000 140.8 14.8 NIL 1,000,000 1.3 1.3 (foo 2) 1,000,000 4.53 4.53 (write-char #\a) 10,000 3.74 374.0 (probe-file ...) 100 43.7 437,000 [using a string as a pathname, non-local file, connection already established.] FOO is a null function needed to prevent optimization. (dotimes (i 10000000) (cons 1 2)) is optimized to: (dotimes (i 10000000) nil) so: (dotimes (i 10000000) (foo (cons 1 2))) must be used instead. FOO is defined with: (defun foo (x) x) On the basis of this I conclude that the common idiom (apply #'format ...) does not deserve special attention to the number of CONSes performed in creating the &Rest list for FORMAT. ================================================================= The actual functions used to collect some of this data follow. ;;; -*- Mode:Common-Lisp; Package:USER; Base:10 -*- (defvar *count* 0) (defvar *not-count* 0) (defvar *fns* nil) (defun rest-p (x) (cond ((and (not (macro-function x)) (not (special-form-p x)) (member '&rest (arglist x))) (push x *fns*) (incf *count*) t) (t (incf *not-count*) nil))) (defun test (pkg) (setq *count* 0) (setq *not-count* 0) (setq *fns* nil) (apropos "" :package pkg :inherited nil :predicate #'rest-p :fboundp t :inheritors nil) (format t "~&There are ~a functions with &Rest arguments, ~a without in package ~a" *count* *not-count* pkg)) (defun file-search (file str) (let ((count 0) (lines 0)) (with-open-file (stream file) (loop for line = (read-line stream nil nil) while line do (incf lines) (when (search str line :test #'char-equal) (format t "~&~a" line) (incf count)))) (values count lines))) (defun file-search-list (files str) (let ((count 0) (lines 0)) (dolist (file files) (multiple-value-bind (a b) (file-search file str) (setq count (+ count a)) (setq lines (+ lines b)) (format t "~&File ~a Count ~a; lines ~a Total count ~a, lines ~a" file a b count lines))) (format t "~&Grand Total count ~a; lines ~a" count lines) (values count lines))) ;;; (file-search-list (pathname "nil$disk:[nil.h]*.lsp") "(APPLY")  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 30 Mar 88 15:04:35 EST Received: from Think.COM by SAIL.Stanford.EDU with TCP; 30 Mar 88 11:40:19 PST Return-Path: Received: from sauron.think.com by Think.COM; Wed, 30 Mar 88 07:14:53 EST Received: from OCCAM.THINK.COM by sauron.think.com; Wed, 30 Mar 88 07:14:46 EST Date: Wed, 30 Mar 88 07:16 EST From: Barry Margolin Subject: &Rest Lists To: ELIOT@cs.umass.edu Cc: common-lisp@sail.stanford.edu In-Reply-To: <8803300741.AA28407@Think.COM> Message-Id: <19880330121607.8.BARMAR@OCCAM.THINK.COM> Date: Tue, 29 Mar 88 12:12 EDT From: ELIOT@cs.umass.edu From: Barry Margolin To: ELIOT@cs.umass.EDU Date: Thu, 24 Mar 88 17:12 EDT From: ELIOT@cs.umass.edu From: Barry Margolin To: ELIOT@cs.umass.EDU What I mean by saying that "Using APPLY is probably inefficient anyhow" is that you will incur the overhead of a full extra function call that probably cannot be optimized away. ... What extra function call? I would hope that the compiler will inline code calls to APPLY. (apply #'foo '(1 2 3)) should generate code at least as good as (foo 1 2 3), and the only difference between (apply #'foo '(1 2 3)) and (apply foo '(1 2 3)) should be whether it extracts the function from FOO's function or value cell. In the implementation I use (a Lispm), APPLY is a single instruction. Is it an instruction, or a microcoded subroutine? :-) I don't have access to the microcode source, so I can't tell. All I know is that it is one macroinstruction. It is probably a microcode routine, because it still has to do a significant amount of work, such as checking the number of arguments supplied against the allowed number of arguments for the function. The only extra inefficiency that APPLY might incur is the one YOU are advocating -- copying its last argument -- which makes your reasoning circular. I looked at both VAXLISP and NIL to see what they do. Both of these implementations spread the arguments out on the stack in the calling function and collect them back into a list when entering the function with the &Rest argument. Consequently they might use stack lists, but they cannot share list stucture as you are proposing. Because these implementors chose not to share the apply argument and the &rest argument, they must do the spread and collect. This extra function call you mentioned is directly caused by the non-sharing. You implied that there was some inefficiency already inherent in APPLY, so that adding the spread/collect wouldn't make it much slower. A normal function call [i.e. (foo 1 2 3)] gets compiled as a series of individual PUSHES as the arguments are evaluated. (Equivalently, memory for the entire set of arguments can be allocated on the stack and individual values MOVEd into the correct location.) A function call using APPLY would PUSH the initial arguments and then call a hand-coded assembly routine to push the rest of the arguments. Consequently, the state of the stack when FOO is entered is the same regardless of how FOO gets called, so FOO cannot differentiate calls moderated by APPLY from normal function calls. Your APPLY microprogram might do something similar, and it certainly could. Calls made using APPLY are not specially optimized. However, FOO can be compiled using full knowledge of the body of FOO. So if FOO does not return its &Rest list it can be CONSed on the stack. On a LISPM you might find it possible to change some type bits in the stack words to make the arguments PUSHed onto the stack into a CDR-coded list. What I believe the Lispm APPLY does is to push each of the regular arguments onto the stack, then push the list argument onto the stack, and set a bit indicating that the last argument should be spread if necessary. When entering the callee, if there are fewer regular lambda variables than regular arguments, the extra regular arguments are turned into a stack-consed list whose tail is the list argument (as you described in your last sentence above), and the &rest argument is bound to this. If there are more regular lambda variables than regular arguments, then values are popped from the list argument and stored in the appropriate stack locations for those lambda variables, and the &rest arg is bound to what is left of the list argument. Except for the use of stack lists for regular arguments that become part of an &rest variable, no special support is necessary for the above. And the use of stack lists is independent of the other features. Stack-consed &rest arguments merely guarantee that they NEVER cons. While we are discussing such low-level issues, it is worth thinking about how difficult it is to take advantage of the possibility of sharing &Rest lists. Basically there are two ways to do it. If you are willing to give up or tremendously complicate separate compilation you can compile a function CALL using special knowledge of the definition of the Callee. For example, a call using APPLY could jump into the middle of the function entry sequence, after the point where &Rest lists normally get created. This would be a major break with Lisp tradition. Alternatively, you must use several different calling conventions and pass along enough information so that the Callee knows how its arguments have been encoded. This will slow down every function call by the amount needed to encode/decode this information, and complicate the implementation considerably. Which option do you prefer? Well, I guess what the Lispm does is the latter (actually, there is also some of the former -- optional arguments are implemented by having each of the first N instructions do the defaulting for the corresponding argument, and the first M are skipped when M optional arguments have been supplied). But I don't think the overhead need be as much as you think. I suspect that it could be implemented such that its worst case behavior is the same expense as NIL's regular case. Here's how I would describe a good argument processing algorithm (I'm using Lisp for convenience, this code doesn't come from the Lispm, or any existing implementation): (defun process-arguments (function arg-array spread-last-arg-p) ;; ARG-ARRAY is the portion of the activation record containing the arguments, ;; which were pushed by the caller. (multiple-value-bind (n-bound-vars spread-last-var-p) ; n-bound-vars doesn't ; include &rest var (function-arg-info function) ;; ignore optional/key for now (let ((n-ordinary-args (if spread-last-arg-p (1- (length arg-array)) (length arg-array)))) ;; Check for optimal case first (unless (and (= n-bound-vars n-ordinary-args) (eq spread-last-arg-p spread-last-var-p)) (let ((spread-arg (if spread-last-arg-p (aref arg-array n-ordinary-args) nil))) (cond ((< n-bound-vars n-ordinary-args) (do ((i (1- n-ordinary-args) (1- i))) ((= i n-bound-vars)) (push (aref arg-array i) spread-arg))) ((> n-bound-vars n-ordinary-args) (do ((i n-bound-vars (1+ i))) ((= i n-ordinary-args)) (if (null spread-arg) (error "Not enough arguments supplied") (push-argument (pop spread-arg)))))) (if (and spread-arg spread-last-var-p) (push-argument spread-arg) (error "Too many arguments supplied"))))))) The above example doesn't try to do stack-consing. Therefore its worst-case performance is in the case of (apply #'(lambda (&rest arg) ...) NIL), consing n elements, just like NIL. But in the case where the &rest arg exactly matches the last argument to APPLY, neither loop executes. (apply #'(lambda () ...) ) also does O(n) work, but it doesn't cons, so it is cheaper than the first example. In general, my algorithm is O(n-ord-args - n-ord-vars), whereas NIL is O(length(last-apply-arg)). Well, I know that I use APPLY a whole lot. Not as often as LIST and CAR, certainly, but more often than I would have expected. I don't use APPLY very much. I am sure that neither of us are biased because of our programming styles, right? Actually, I suspect it has to do with the applications more than style. APPLY is used frequently when writing intermediary routines dealing with things like files, because you are passed an options list suitable for OPEN, and you must use APPLY to invoke OPEN. Much of what I do requires this. One nice thing about the modularity of the NIL generated code: it could easily be converted to an implementation like this without changing the code generator. Something equivalent to the above could be implemented in CL$MS_STACKIFY (it would do almost nothing), CL$MS_HNDL_RS (this would contain the two loops), and CL$MS_ANDREST_LIST (this would correspond to my last IF form). In fact, how do I know from only looking at the code you supplied that it DOESN'T do that? (The answer is that I assume you have looked at the implementation, and it does what you say). barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 30 Mar 88 14:12:32 EST Received: from XX.LCS.MIT.EDU by SAIL.Stanford.EDU with TCP; 30 Mar 88 10:52:48 PST Received: from LIVE-OAK.LCS.MIT.EDU by XX.LCS.MIT.EDU via Chaosnet; 30 Mar 88 11:00-EST Received: from ACORN.Gold-Hill.DialNet.Symbolics.COM by MIT-LIVE-OAK.DialNet.Symbolics.COM via DIAL with SMTP id 85770; 30 Mar 88 09:07:29-EST Received: from BOSTON.Gold-Hill.DialNet.Symbolics.COM by ACORN.Gold-Hill.DialNet.Symbolics.COM via CHAOS with CHAOS-MAIL id 97731; Wed 30-Mar-88 08:50:23-EST Date: Wed, 30 Mar 88 08:52 est From: mike%acorn@oak.lcs.mit.edu (mike@gold-hill.com after 1-April-88) COMMENTS: NOTE %acorn@oak... CHANGES TO @GOLD-HILL.COM ON 1-April-88 To: ELIOT@cs.umass.edu Subject: &Rest Lists Cc: common-lisp@SAIL.STANFORD.EDU Calls made using APPLY are not specially optimized. However, FOO can be compiled using full knowledge of the body of FOO. So if FOO does not return its &Rest list it can be CONSed on the stack. This "analysis" stuff is not really valuable. Without global program knowledge, the vast majority of these cases will be undecidable. If you pass any cons of the rest arg to any function, and return the value of any other function, then you can't decide it because the two functions could communicate via shared state: e.g., --> file 1: (let ((shared-state nil)) (defun bar (x) (setq shared-state x)) (defun foo () shared-state)) --> file 2: (defun test (&rest arg) (bar arg) (foo)) Clearly, TEST returns its rest arg, and the only way for the compiler to know this is to have global knowledge of the functions FOO and BAR The only way around this is to re-write test: (defun test (&rest arg1) (let ((arg (copy-list arg1))) (bar arg) (foo))) Which is exactly what you have to do to eliminate sharing when the default is to allow sharing. (Note that in this case, the compiler could infer that arg1 could be a "stack-list" :-) My point: relying on the compiler to "infer" stuff that should be directly expressable is a bad idea. It should be clear that if the default is to share rest-arg conses passed by apply, one can get the desired behavior possibly at the cost of having to call copy-list. If the default is to copy, then in most cases, the compiler will not be able to eliminate the copying and there will be run-time cost. While we are discussing such low-level issues, it is worth thinking about how difficult it is to take advantage of the possibility of sharing &Rest lists. Basically there are two ways to do it. If you are willing to give up or tremendously complicate separate compilation you can compile a function CALL using special knowledge of the definition of the Callee. For example, a call using APPLY could jump into the middle of the function entry sequence, after the point where &Rest lists normally get created. This would be a major break with lisp tradition. you must use several different calling conventions and pass along enough information so that the Callee knows how its arguments have been encoded. This will slow down every function call by the amount needed to encode/decode this information, and complicate the implementation considerably. Which option do you prefer? Having mulitple function entry points to support different calling conventions sounds like a good strategy to exploit compile-time knowledge of the structure of the called function. A classic example of this is for type-checking. If checked and unchecked entries are available, then the compiler can set up an unchecked call if the types are known to be correct. There need be no run-time set-up or overhead. ...mike beckerle Gold Hill  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 30 Mar 88 02:58:22 EST Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 29 Mar 88 23:40:19 PST Received: from relay2.cs.net by RELAY.CS.NET id ag11003; 30 Mar 88 2:21 EST Received: from cs.umass.edu by RELAY.CS.NET id bz05482; 30 Mar 88 2:08 EST Date: Tue, 29 Mar 88 12:12 EDT From: ELIOT@cs.umass.edu Subject: &Rest Lists To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.EDU" From: Barry Margolin To: ELIOT@cs.umass.EDU Date: Thu, 24 Mar 88 17:12 EDT From: ELIOT@cs.umass.edu From: Barry Margolin To: ELIOT@cs.umass.EDU What I mean by saying that "Using APPLY is probably inefficient anyhow" is that you will incur the overhead of a full extra function call that probably cannot be optimized away. ... What extra function call? I would hope that the compiler will inline code calls to APPLY. (apply #'foo '(1 2 3)) should generate code at least as good as (foo 1 2 3), and the only difference between (apply #'foo '(1 2 3)) and (apply foo '(1 2 3)) should be whether it extracts the function from FOO's function or value cell. In the implementation I use (a Lispm), APPLY is a single instruction. Is it an instruction, or a microcoded subroutine? :-) The only extra inefficiency that APPLY might incur is the one YOU are advocating -- copying its last argument -- which makes your reasoning circular. I looked at both VAXLISP and NIL to see what they do. Both of these implementations spread the arguments out on the stack in the calling function and collect them back into a list when entering the function with the &Rest argument. Consequently they might use stack lists, but they cannot share list stucture as you are proposing. A normal function call [i.e. (foo 1 2 3)] gets compiled as a series of individual PUSHES as the arguments are evaluated. (Equivalently, memory for the entire set of arguments can be allocated on the stack and individual values MOVEd into the correct location.) A function call using APPLY would PUSH the initial arguments and then call a hand-coded assembly routine to push the rest of the arguments. Consequently, the state of the stack when FOO is entered is the same regardless of how FOO gets called, so FOO cannot differentiate calls moderated by APPLY from normal function calls. Your APPLY microprogram might do something similar, and it certainly could. Calls made using APPLY are not specially optimized. However, FOO can be compiled using full knowledge of the body of FOO. So if FOO does not return its &Rest list it can be CONSed on the stack. On a LISPM you might find it possible to change some type bits in the stack words to make the arguments PUSHed onto the stack into a CDR-coded list. While we are discussing such low-level issues, it is worth thinking about how difficult it is to take advantage of the possibility of sharing &Rest lists. Basically there are two ways to do it. If you are willing to give up or tremendously complicate separate compilation you can compile a function CALL using special knowledge of the definition of the Callee. For example, a call using APPLY could jump into the middle of the function entry sequence, after the point where &Rest lists normally get created. This would be a major break with Lisp tradition. Alternatively, you must use several different calling conventions and pass along enough information so that the Callee knows how its arguments have been encoded. This will slow down every function call by the amount needed to encode/decode this information, and complicate the implementation considerably. Which option do you prefer? Well, I know that I use APPLY a whole lot. Not as often as LIST and CAR, certainly, but more often than I would have expected. I don't use APPLY very much. I am sure that neither of us are biased because of our programming styles, right? APPENDIX The rest of this message is an edited dribble file, showing how NIL compiles function calls using &Rest arguments. My comments are shown /* C Style */ to distinguish them from comments inserted by the disassembler. I deleted several screenfuls to shorten the message, so this does not fully illustrate how much hidden complexity there is in a function call. (:OPENED "VAX5::OFFICE$DISK:[ELIOT]FOO.TXT;2") (defun foo (&rest x) (setf (cadr x) 'bang)) (defun bar (z) (apply #'foo z)) (defun baz (a b c) (foo a b c)) ;[Compiled foo bar and baz.] (defvar z '(1 2 3)) Z (bar z) BANG z (1 2 3) ;Didn't get side effected. (disassemble 'foo) 0: WORD 1024 ;Save register(s) FLP 2: MOVAL l^-420,FLP 9: MINICALL CL$MS_HNDL_RS,(COMPILER:REQ 0) 13: MINICALL CL$MS_ANDREST_LIST,-8(FP) 17: MOVL AR1,b^-8(FP) 21: MOVL b^-8(FP),AR1 25: MINICALL CL$MS_CDR 28: PUSHL AR1 30: MOVL b^4(FLP),AR1 ;'BANG 34: MINICALL CL$MS_SET_CAR 37: RET (disassemble 'bar) ... /* 15 lines deleted */ 41: PUSHL b^-4(FLP) ;#'FOO 50: MINICALL CL$MS_STACKIFY /* The arguments get spread out here */ 54: CALLS R0,@b^8(SP) 58: RET (disassemble 'baz) /* 13 lines deleted */ 33: PUSHL b^24(AP) 36: PUSHL b^20(AP) 39: PUSHL b^16(AP) 50: PUSHL b^-4(FLP) ;#'FOO 55: CALLS s^#6,@b^8(SP) 59: RET ============== Vaxlisp is similar. BAZ essentially compiles into a jump to FOO. BAR remains complex. ==============  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 30 Mar 88 00:02:04 EST Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 29 Mar 88 19:50:31 PST Received: from relay2.cs.net by RELAY.CS.NET id ad07769; 29 Mar 88 22:10 EST Received: from tektronix.tek.com by RELAY.CS.NET id bp04223; 29 Mar 88 22:00 EST Received: by tektronix.TEK.COM (5.51/6.24) id AA21206; Tue, 29 Mar 88 13:33:30 PST Received: by tekchips.CRL.TEK.COM (5.51/6.24) id AA24417; Tue, 29 Mar 88 13:17:22 PST Message-Id: <8803292117.AA24417@tekchips.CRL.TEK.COM> To: common-lisp@SAIL.STANFORD.EDU Cc: willc@tekchips.crl.tek.com Subject: Re: &REST lists Date: 29 Mar 88 13:17:17 PST (Tue) From: willc%tekchips.CRL@tektronix.tek.com Page 272 of CLtL, talking about RPLACA and RPLACD, says: ...caution should be exercised when using these functions, as strange side effects can occur if portions of list structure become shared. If APPLY is permitted to side effect its last argument, as advocated by most participants in the recent discussion, then language similar to that above should be added to the discussion of APPLY on page 107. The cautionary language is much more important for APPLY than for RPLACA and RPLACD because side effects are the whole point of the latter, but it would be easy for a naive programmer to assume that APPLY has no gratuitous side effects. In a recent posting, Eliot Moss revealed that he does not have the correct model of argument transmission in Common Lisp. He erroneously believes that CL procedures take sequences of arguments; if this were the case, one could of course prove that APPLY cannot side effect the top level of its last argument. Because APPLY can have such side effects, however, any correct model of CL argument transmission must have it that at least some CL procedures (those that have a &REST arg) can accept a linked list (not a sequence) of arguments. If procedures are to be treated uniformly by the model, then all CL procedures must accept a linked list of arguments rather than a sequence. Although this might seem to imply that the CL runtime must cons up these argument lists for all calls that don't involve APPLY, it happens that the CL compiler can in practice avoid the consing by observing that the first operation performed by all procedures except those with &REST arguments is to take the argument list apart into a sequence; furthermore there is enough slack in the semantics of procedures with &REST arguments -- the &REST argument need not share structure with the argument list, although it may -- that it's ok to avoid the consing even when the compiler is unable to prove that the procedure being called does not take a &REST argument. I think Moss would agree with me that this is a ridiculous model of argument transmission, but it shows that the semantics advocated by his opponents can be made consistent. William Clinger Semantic Microsystems, Inc.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 25 Mar 88 02:51:56 EST Received: from Think.COM by SAIL.Stanford.EDU with TCP; 24 Mar 88 23:32:46 PST Return-Path: Received: from pozzo.think.com by Think.COM; Fri, 25 Mar 88 02:32:10 EST Received: by pozzo.think.com; Fri, 25 Mar 88 02:32:06 est Date: Fri, 25 Mar 88 02:32:06 est From: Barry Margolin Message-Id: <8803250732.AA12798@pozzo.think.com> To: ELIOT@cs.umass.edu Cc: Common-Lisp@sail.stanford.edu In-Reply-To: ELIOT@cs.umass.edu's message of Thu, 24 Mar 88 17:12 EDT <8803250647.AA07083@Think.COM> Subject: &Rest Lists Date: Thu, 24 Mar 88 17:12 EDT From: ELIOT@cs.umass.edu From: Barry Margolin To: ELIOT@cs.umass.EDU What I mean by saying that "Using APPLY is probably inefficient anyhow" is that you will incur the overhead of a full extra function call that probably cannot be optimized away. Truly efficient code requires modifying the arguments so that the list is passed directly, rather than using &Rest lists, so you can eliminate the function call involved in using APPLY. What extra function call? I would hope that the compiler will inline code calls to APPLY. (apply #'foo '(1 2 3)) should generate code at least as good as (foo 1 2 3), and the only difference between (apply #'foo '(1 2 3)) and (apply foo '(1 2 3)) should be whether it extracts the function from FOO's function or value cell. In the implementation I use (a Lispm), APPLY is a single instruction. The only extra inefficiency that APPLY might incur is the one YOU are advocating -- copying its last argument -- which makes your reasoning circular. If this kind of recursive function has to run quickly it would probably be better to define an auxillary function with a fixed number of arguments to do the real work. Besides, most function calls are not made using APPLY. Recursive function calls using APPLY are too rare to justify a blemish in the semantics of all function calls. Well, I know that I use APPLY a whole lot. Not as often as LIST and CAR, certainly, but more often than I would have expected. It's not just recursive calls. Consider all the functions that take arguments just like FORMAT. They all call various intermediate functions, which call other intermediates, and eventually they call FORMAT itself. The &rest list shouldn't be duplicated at each call. Many other functions take &rest arguments that are simply passed on to other functions using APPLY. Some might argue that the correct way to disambiguate this situation is to specify that APPLY must share its final argument with any &Rest list argument as much as possible. This doesn't make sense to me. I don't believe that it would make Common Lisp more efficient to any significant degree. I think it creates an undesirable inconsistency in the semantics of function calls, as I argued above. Furthermore, modifying &Rest lists as a way to indirectly modify some argument to APPLY sounds like one of the worst dirty programming tricks I have heard of in a long time. The possibility of causing exceedingly obscure bugs makes my skin crawl. I don't think anyone is actually suggesting that people intentionally modify &rest lists. Personally, I prefer making it be undefined whether &rest lists share, so programmers aren't tempted to write such code. barmar I agree that modifying &Rest lists is bad programming style. But I also think that leaving issues undefined is bad language design, unless there are very compelling reasons. Compelling reasons include externally imposed constraints on an implementation (forcing us to live with ambiguity in the Common Lisp file system operations) and the possibility of major optimizations on different types of machines. Ambiguity in the implementation of Arrays allows different types of machines to be used for efficient CL implementations. The special case of using APPLY to call a function with an &REST argument fits neither of these categories. Anything that can be made more efficient by allowing the last argument of APPLY to be shared as part of an &Rest list can be implemented MORE efficiently by using a normal function call directly. For example, you suggest that FORMAT like functions could not be implemented efficiently. They could be implemented like this: (defun format (stream fmt &rest args) (format-1 stream fmt args)) (defun format-1 (stream fmt args) ...) (defun errror (fmt &Rest args) (format-1 *error-io* fmt args) (call-debugger)) These solutions only work for built-in functions. Portable code can't call FORMAT-1. I certainly could make non-&rest versions of my functions, but this means that I must write two functions when I previously would have written only one, and if I make all my &rest functions just invoke the non-&rest versions I also incur an extra function call (like you thought was inherent in using APPLY). Also, if you were going to do (apply #'format str fmt arg2 rest) and you recoded it to call FORMAT-1, you end up with (format-1 str fmt (cons arg2 rest)) Actually, this last argument isn't as compelling as I first thought, because it only reduces efficiency in implementations that cons &rest lists on the stack, and we've decided that they are violating the standard by doing this. I think these are good efficiency justifications for making the sharing behavior of &rest lists and list given to APPLY be undefined. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 25 Mar 88 02:11:36 EST Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 24 Mar 88 22:46:07 PST Received: from relay2.cs.net by RELAY.CS.NET id ab04582; 25 Mar 88 1:26 EST Received: from cs.umass.edu by RELAY.CS.NET id aq23262; 25 Mar 88 1:10 EST Date: Thu, 24 Mar 88 17:12 EDT From: ELIOT@cs.umass.edu Subject: &Rest Lists To: Common-Lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"Common-Lisp@sail.stanford.edu" From: Barry Margolin To: ELIOT@cs.umass.EDU Common Lisp does commit itself to doing whatever has to be done so that interpreted and compiled code behaves the same. How did the compiler/interpreter distinction enter into this? No one has proposed distinguishing them. I was using an analogy to try to clarify my line of reasoning. I am not saying that Common Lisp should actually specify that APPLY copy the list structure in its final argument, but I am saying that this may be required in order to correctly implement the semantics that I fell APPLY should have. Good compilers are free to implement APPLY so that it shares list structure as long as it does not affect the semantics. Calls to any function which provably does not modify its &Rest lists could be implemented more efficiently by such a compiler. Consider : (setq x '(1 2 3)) [1] (apply #'foo 1 2 3 NIL) [2] (apply #'foo 1 2 (cddr x)) [3] (apply #'foo 1 (cdr x)) [4] (apply #'foo x) [5] (funcall #'foo 1 2 3) [6] (eval (cons 'foo x)) [7] (eval (list 'foo 1 2 3)) [8] (foo 1 2 3) I strongly believe that all of [1-8] are the same function call and must have the same semantics. Since the list, x, cannot be modified by [1, 5, 7, 8] it should not be allowed to modify it in [2, 3, 4, 6]. I disagree with this. [5, 7, 8] don't even reference the list x, so how can they be considered the same? Ignore what happened before the actual function call to FOO. At the moment FOO actually is called all of its arguments are EQ in all of these cases. Obviously, my intuituiton is that a function call should be completely defined by its arguments but not by the computation that produced them. And I believe that the function call makes explicit what constitutes a distinct "argument", regardless of the function definition. Consequently I think that "&Rest x" means that x is a list of the rest of the argumentS - (plural). In other words the argumentS that are collected into an &Rest list are totally distinct. And the difference between [4] and [6] would be quite obvious if any of the elements of x were objects that don't self-evaluate, e.g.: (setq a 1 b 2 c 3 x '(a b c)) (apply #'list x) => (a b c) (which, by the way, should not share structure with x) (eval (cons 'list x)) => (1 2 3) 2. If APPLY copies its last argument, recursive programs that receive an &REST argument and pass it to APPLY become inefficient. A linear time algorithm can change to a quadratic time algorithm. While the efficiency could be regained through compiler flow analysis in many cases, I think it's better not to put the inefficiency into the language in the first place. Using APPLY is probably inefficient anyhow. I sure hope not! Many implementations of EVAL use APPLY internally for all function calls, something along the lines of: (apply (symbol-function (car form)) (mapcar #'eval (cdr form))) (yes, this is extremely simplified, I know that the real thing is much more complex). This only applies to interpreted code, not compiled code. And a real interpreter can be written using implementation dependant primitives, so the defined Common Lisp behavior of APPLY has nothing to do with the real efficiency of anything except explicit calls to APPLY. Certainly normal function calls need not be effected. What I mean by saying that "Using APPLY is probably inefficient anyhow" is that you will incur the overhead of a full extra function call that probably cannot be optimized away. Truly efficient code requires modifying the arguments so that the list is passed directly, rather than using &Rest lists, so you can eliminate the function call involved in using APPLY. If this kind of recursive function has to run quickly it would probably be better to define an auxillary function with a fixed number of arguments to do the real work. Besides, most function calls are not made using APPLY. Recursive function calls using APPLY are too rare to justify a blemish in the semantics of all function calls. It's not just recursive calls. Consider all the functions that take arguments just like FORMAT. They all call various intermediate functions, which call other intermediates, and eventually they call FORMAT itself. The &rest list shouldn't be duplicated at each call. Many other functions take &rest arguments that are simply passed on to other functions using APPLY. Some might argue that the correct way to disambiguate this situation is to specify that APPLY must share its final argument with any &Rest list argument as much as possible. This doesn't make sense to me. I don't believe that it would make Common Lisp more efficient to any significant degree. I think it creates an undesirable inconsistency in the semantics of function calls, as I argued above. Furthermore, modifying &Rest lists as a way to indirectly modify some argument to APPLY sounds like one of the worst dirty programming tricks I have heard of in a long time. The possibility of causing exceedingly obscure bugs makes my skin crawl. I don't think anyone is actually suggesting that people intentionally modify &rest lists. Personally, I prefer making it be undefined whether &rest lists share, so programmers aren't tempted to write such code. barmar I agree that modifying &Rest lists is bad programming style. But I also think that leaving issues undefined is bad language design, unless there are very compelling reasons. Compelling reasons include externally imposed constraints on an implementation (forcing us to live with ambiguity in the Common Lisp file system operations) and the possibility of major optimizations on different types of machines. Ambiguity in the implementation of Arrays allows different types of machines to be used for efficient CL implementations. The special case of using APPLY to call a function with an &REST argument fits neither of these categories. Anything that can be made more efficient by allowing the last argument of APPLY to be shared as part of an &Rest list can be implemented MORE efficiently by using a normal function call directly. For example, you suggest that FORMAT like functions could not be implemented efficiently. They could be implemented like this: (defun format (stream fmt &rest args) (format-1 stream fmt args)) (defun format-1 (stream fmt args) ...) (defun errror (fmt &Rest args) (format-1 *error-io* fmt args) (call-debugger)) (defun warn (fmt &rest args) (format-1 *error-io* fmt args) (when *break-on-warnings* (call-debugger))) (defun break (fmt &rest args) (format-1 t fmt args) (break-loop)) etc.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 24 Mar 88 13:09:20 EST Received: from EDDIE.MIT.EDU by SAIL.Stanford.EDU with TCP; 24 Mar 88 09:30:25 PST Received: by EDDIE.MIT.EDU with UUCP with smail2.5 with sendmail-5.45/4.7 id ; Thu, 24 Mar 88 12:28:18 EST Received: by spt.entity.com (smail2.5); 24 Mar 88 12:23:15 EST (Thu) To: common-lisp@SAIL.STANFORD.EDU Subject: &REST Lists Message-Id: <8803241223.AA05234@spt.entity.com> Date: 24 Mar 88 12:23:15 EST (Thu) From: gz@spt.entity.com (Gail Zacharias) I don't think requiring &rest lists to be (conceptually) freshly consed is somehow "automatically unsharing" structure. It depends on how you see the semantics of function calling - I think a function gets a certain number of individual arguments, and &REST requests that some of those arguments be constructed into a list. It's all internal to the function and nobody else's business. APPLY's contract is to pass *elements* of a list to a function as arguments. From this point of view, having a list given to APPLY suddenly show up inside some function, without being passed as an argument to that function, is not a natural case of sharing -- it's a case of unexpected collapsing of equal structures, not that much different from, say, (eq (union (list 'a) (list 'b)) (union (list 'a) (list 'b))) ==> T. On the practical side, there is an idiom that occurs in almost every non-trivial portable common lisp program I've seen, which looks something like this: (DEFUN FN (&REST FOO) #+ (SETQ FOO (COPY-LIST FOO)) ...) or sometimes just like this: (DEFUN FN (&REST FOO) (SETQ FOO (COPY-LIST FOO)) ...) For example, a quick scan through PCL (it happened to be handy) finds at least 5 instances of this idiom, 2 with the conditionalization and 3 without. The COPY-LIST is of course wasteful in implementations which guarantee no user-visible sharing of &rest lists, but it is also wasteful in the APPLY/&REST-optimizing implementations when the function is being called normally (i.e. with no handy pre-consed arg list to reuse), which is usually most of the time. If Common Lisp doesn't require unshared &rest lists, then I think it must provide a declarative version of this idiom so the COPY-LIST can be portably avoided when it's redundant. Seems to me that the fact that this is a common case where users find a need for conditionalization indicates a real deficiency in Common Lisp's specification. Regarding the case of a format-like function applying a format-like function and so on, wouldn't it be cleaner and even more efficient to provide some special construct for that case, such as (off the top of my head) a RE-APPLY, which would request the caller's args to be passed on to the callee? (And wasn't somebody working on designing an &MORE or some such abstraction which avoided consing altogether? Whatever happened to that?)  Received: from REAGAN.AI.MIT.EDU (CHAOS 13065) by AI.AI.MIT.EDU 23 Mar 88 23:32:46 EST Received: from SAIL.Stanford.EDU (SAIL.STANFORD.EDU) by REAGAN.AI.MIT.EDU via INTERNET with SMTP id 100678; 23 Mar 88 23:29:55 EST Received: from Think.COM by SAIL.Stanford.EDU with TCP; 23 Mar 88 17:31:21 PST Return-Path: Received: from sauron.think.com by Think.COM; Wed, 23 Mar 88 20:30:47 EST Received: from OCCAM.THINK.COM by sauron.think.com; Wed, 23 Mar 88 20:30:43 EST Date: Wed, 23 Mar 88 20:31 EST From: Barry Margolin Subject: &Rest Lists To: ELIOT@cs.umass.edu Cc: common-lisp@sail.stanford.edu In-Reply-To: <8803232113.AA02705@Think.COM> Message-Id: <19880324013118.3.BARMAR@OCCAM.THINK.COM> Date: Wed, 23 Mar 88 12:50 EDT From: ELIOT@cs.umass.edu From: IN%"Moon@SCRC-STONY-BROOK.ARPA" "David A. Moon" 20-MAR-1988 08:07 Subj: &REST args As I stated in an earlier message I think that Common Lisp should prohibit sharing of list structure in the last argument to APPLY. 1. In no other place does Common Lisp automatically unshare structure, except when the user is explicitly modifying the structure (as in REMOVE). Making APPLY automatically unshare would be a semantic wart. Common Lisp does commit itself to doing whatever has to be done so that interpreted and compiled code behaves the same. How did the compiler/interpreter distinction enter into this? No one has proposed distinguishing them. In the environment I use, they both behave the same regarding &rest lists. And even so, the compiler and interpreter are allowed to have different ways of dealing with a situation that is undefined ("is an error", to use CLtL wording), because portable applications are not permitted to depend on the behavior in such situations. Actually I don't care whether that last argument to APPLY can be shared. But I stongly believe that Common Lisp should do whatever has to be done so that all variants of the same function call are equivalent. Consider: (setq x '(1 2 3)) [1] (apply #'foo 1 2 3 NIL) [2] (apply #'foo 1 2 (cddr x)) [3] (apply #'foo 1 (cdr x)) [4] (apply #'foo x) [5] (funcall #'foo 1 2 3) [6] (eval (cons 'foo x)) [7] (eval (list 'foo 1 2 3)) [8] (foo 1 2 3) I strongly believe that all of [1-8] are the same function call and must have the same semantics. Since the list, x, cannot be modified by [1, 5, 7, 8] it should not be allowed to modify it in [2, 3, 4, 6]. I disagree with this. [5, 7, 8] don't even reference the list x, so how can they be considered the same? And the difference between [4] and [6] would be quite obvious if any of the elements of x were objects that don't self-evaluate, e.g.: (setq a 1 b 2 c 3 x '(a b c)) (apply #'list x) => (a b c) (which, by the way, should not share structure with x) (eval (cons 'list x)) => (1 2 3) 2. If APPLY copies its last argument, recursive programs that receive an &REST argument and pass it to APPLY become inefficient. A linear time algorithm can change to a quadratic time algorithm. While the efficiency could be regained through compiler flow analysis in many cases, I think it's better not to put the inefficiency into the language in the first place. Using APPLY is probably inefficient anyhow. I sure hope not! Many implementations of EVAL use APPLY internally for all function calls, something along the lines of: (apply (symbol-function (car form)) (mapcar #'eval (cdr form))) (yes, this is extremely simplified, I know that the real thing is much more complex). If this kind of recursive function has to run quickly it would probably be better to define an auxillary function with a fixed number of arguments to do the real work. Besides, most function calls are not made using APPLY. Recursive function calls using APPLY are too rare to justify a blemish in the semantics of all function calls. It's not just recursive calls. Consider all the functions that take arguments just like FORMAT. They all call various intermediate functions, which call other intermediates, and eventually they call FORMAT itself. The &rest list shouldn't be duplicated at each call. Many other functions take &rest arguments that are simply passed on to other functions using APPLY. Some might argue that the correct way to disambiguate this situation is to specify that APPLY must share its final argument with any &Rest list argument as much as possible. This doesn't make sense to me. I don't believe that it would make Common Lisp more efficient to any significant degree. I think it creates an undesirable inconsistency in the semantics of function calls, as I argued above. Furthermore, modifying &Rest lists as a way to indirectly modify some argument to APPLY sounds like one of the worst dirty programming tricks I have heard of in a long time. The possibility of causing exceedingly obscure bugs makes my skin crawl. I don't think anyone is actually suggesting that people intentionally modify &rest lists. Personally, I prefer making it be undefined whether &rest lists share, so programmers aren't tempted to write such code. barmar  Received: from REAGAN.AI.MIT.EDU (CHAOS 13065) by AI.AI.MIT.EDU 23 Mar 88 23:27:18 EST Received: from SAIL.Stanford.EDU (SAIL.STANFORD.EDU) by REAGAN.AI.MIT.EDU via INTERNET with SMTP id 100675; 23 Mar 88 23:24:29 EST Received: from Think.COM by SAIL.Stanford.EDU with TCP; 23 Mar 88 17:31:21 PST Return-Path: Received: from sauron.think.com by Think.COM; Wed, 23 Mar 88 20:30:47 EST Received: from OCCAM.THINK.COM by sauron.think.com; Wed, 23 Mar 88 20:30:43 EST Date: Wed, 23 Mar 88 20:31 EST From: Barry Margolin Subject: &Rest Lists To: ELIOT@cs.umass.edu Cc: common-lisp@sail.stanford.edu In-Reply-To: <8803232113.AA02705@Think.COM> Message-Id: <19880324013118.3.BARMAR@OCCAM.THINK.COM> Date: Wed, 23 Mar 88 12:50 EDT From: ELIOT@cs.umass.edu From: IN%"Moon@SCRC-STONY-BROOK.ARPA" "David A. Moon" 20-MAR-1988 08:07 Subj: &REST args As I stated in an earlier message I think that Common Lisp should prohibit sharing of list structure in the last argument to APPLY. 1. In no other place does Common Lisp automatically unshare structure, except when the user is explicitly modifying the structure (as in REMOVE). Making APPLY automatically unshare would be a semantic wart. Common Lisp does commit itself to doing whatever has to be done so that interpreted and compiled code behaves the same. How did the compiler/interpreter distinction enter into this? No one has proposed distinguishing them. In the environment I use, they both behave the same regarding &rest lists. And even so, the compiler and interpreter are allowed to have different ways of dealing with a situation that is undefined ("is an error", to use CLtL wording), because portable applications are not permitted to depend on the behavior in such situations. Actually I don't care whether that last argument to APPLY can be shared. But I stongly believe that Common Lisp should do whatever has to be done so that all variants of the same function call are equivalent. Consider: (setq x '(1 2 3)) [1] (apply #'foo 1 2 3 NIL) [2] (apply #'foo 1 2 (cddr x)) [3] (apply #'foo 1 (cdr x)) [4] (apply #'foo x) [5] (funcall #'foo 1 2 3) [6] (eval (cons 'foo x)) [7] (eval (list 'foo 1 2 3)) [8] (foo 1 2 3) I strongly believe that all of [1-8] are the same function call and must have the same semantics. Since the list, x, cannot be modified by [1, 5, 7, 8] it should not be allowed to modify it in [2, 3, 4, 6]. I disagree with this. [5, 7, 8] don't even reference the list x, so how can they be considered the same? And the difference between [4] and [6] would be quite obvious if any of the elements of x were objects that don't self-evaluate, e.g.: (setq a 1 b 2 c 3 x '(a b c)) (apply #'list x) => (a b c) (which, by the way, should not share structure with x) (eval (cons 'list x)) => (1 2 3) 2. If APPLY copies its last argument, recursive programs that receive an &REST argument and pass it to APPLY become inefficient. A linear time algorithm can change to a quadratic time algorithm. While the efficiency could be regained through compiler flow analysis in many cases, I think it's better not to put the inefficiency into the language in the first place. Using APPLY is probably inefficient anyhow. I sure hope not! Many implementations of EVAL use APPLY internally for all function calls, something along the lines of: (apply (symbol-function (car form)) (mapcar #'eval (cdr form))) (yes, this is extremely simplified, I know that the real thing is much more complex). If this kind of recursive function has to run quickly it would probably be better to define an auxillary function with a fixed number of arguments to do the real work. Besides, most function calls are not made using APPLY. Recursive function calls using APPLY are too rare to justify a blemish in the semantics of all function calls. It's not just recursive calls. Consider all the functions that take arguments just like FORMAT. They all call various intermediate functions, which call other intermediates, and eventually they call FORMAT itself. The &rest list shouldn't be duplicated at each call. Many other functions take &rest arguments that are simply passed on to other functions using APPLY. Some might argue that the correct way to disambiguate this situation is to specify that APPLY must share its final argument with any &Rest list argument as much as possible. This doesn't make sense to me. I don't believe that it would make Common Lisp more efficient to any significant degree. I think it creates an undesirable inconsistency in the semantics of function calls, as I argued above. Furthermore, modifying &Rest lists as a way to indirectly modify some argument to APPLY sounds like one of the worst dirty programming tricks I have heard of in a long time. The possibility of causing exceedingly obscure bugs makes my skin crawl. I don't think anyone is actually suggesting that people intentionally modify &rest lists. Personally, I prefer making it be undefined whether &rest lists share, so programmers aren't tempted to write such code. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 23 Mar 88 16:32:22 EST Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 23 Mar 88 13:13:10 PST Received: from relay2.cs.net by RELAY.CS.NET id ai11131; 23 Mar 88 15:12 EST Received: from cs.umass.edu by RELAY.CS.NET id ah11782; 23 Mar 88 15:03 EST Date: Wed, 23 Mar 88 12:50 EDT From: ELIOT@cs.umass.edu Subject: &Rest Lists To: common-lisp@SAIL.STANFORD.EDU X-VMS-To: IN%"common-lisp@sail.stanford.EDU" From: IN%"Moon@SCRC-STONY-BROOK.ARPA" "David A. Moon" 20-MAR-1988 08:07 Subj: &REST args For the record, I strongly disagree with this. I believe Common Lisp should specify that the value of an &REST parameter is permitted, but not required, to share structure with the last argument to APPLY. I have two reasons for this belief (both of which have come up on the mailing list before). I disagree with this. As I stated in an earlier message I think that Common Lisp should prohibit sharing of list structure in the last argument to APPLY. 1. In no other place does Common Lisp automatically unshare structure, except when the user is explicitly modifying the structure (as in REMOVE). Making APPLY automatically unshare would be a semantic wart. Common Lisp does commit itself to doing whatever has to be done so that interpreted and compiled code behaves the same. Actually I don't care whether that last argument to APPLY can be shared. But I stongly believe that Common Lisp should do whatever has to be done so that all variants of the same function call are equivalent. Consider: (setq x '(1 2 3)) [1] (apply #'foo 1 2 3 NIL) [2] (apply #'foo 1 2 (cddr x)) [3] (apply #'foo 1 (cdr x)) [4] (apply #'foo x) [5] (funcall #'foo 1 2 3) [6] (eval (cons 'foo x)) [7] (eval (list 'foo 1 2 3)) [8] (foo 1 2 3) I strongly believe that all of [1-8] are the same function call and must have the same semantics. Since the list, x, cannot be modified by [1, 5, 7, 8] it should not be allowed to modify it in [2, 3, 4, 6]. 2. If APPLY copies its last argument, recursive programs that receive an &REST argument and pass it to APPLY become inefficient. A linear time algorithm can change to a quadratic time algorithm. While the efficiency could be regained through compiler flow analysis in many cases, I think it's better not to put the inefficiency into the language in the first place. Using APPLY is probably inefficient anyhow. If this kind of recursive function has to run quickly it would probably be better to define an auxillary function with a fixed number of arguments to do the real work. Besides, most function calls are not made using APPLY. Recursive function calls using APPLY are too rare to justify a blemish in the semantics of all function calls. Common Lisp already has a large number of undefined cases. I don't think that a possible minor optimization of a special case of using APPLY is sufficiently important to justify allowing any ambiguity in the semantics of &Rest lists. Especially since it is acknowledged that a good compiler can probably implement the unambiguous semantics equally efficiently. Some might argue that the correct way to disambiguate this situation is to specify that APPLY must share its final argument with any &Rest list argument as much as possible. This doesn't make sense to me. I don't believe that it would make Common Lisp more efficient to any significant degree. I think it creates an undesirable inconsistency in the semantics of function calls, as I argued above. Furthermore, modifying &Rest lists as a way to indirectly modify some argument to APPLY sounds like one of the worst dirty programming tricks I have heard of in a long time. The possibility of causing exceedingly obscure bugs makes my skin crawl.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 21 Mar 88 11:28:41 EST Received: from Xerox.COM by SAIL.Stanford.EDU with TCP; 21 Mar 88 08:10:16 PST Received: from Riesling.ms by ArpaGateway.ms ; 21 MAR 88 08:08:22 PST Sender: "James_L_Mayer.WBST128"@Xerox.COM Date: 21 Mar 88 08:07:13 PST (Monday) Subject: CLOS Status From: "James_L_Mayer.WBST128"@Xerox.COM To: Common-Lisp@SAIL.STANFORD.EDU cc: Common-Lisp-Object-System@SAIL.STANFORD.EDU Reply-to: "James_L_Mayer.WBST128"@Xerox.COM Message-ID: <880321-080822-3332@Xerox> Some questions about the Common Lisp Object System: (1) What is the status of the standard? When was the last draft spec released and how can I get a copy? (2) What is the implementation status? Is PCL still the best approximation available? (3) I will be running in Sun Common Lisp. What CLOS options are/will be open to me? Thank you. -- Jim Mayer  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 20 Mar 88 02:23:07 EST Received: from uunet.UU.NET by SAIL.Stanford.EDU with TCP; 19 Mar 88 23:04:34 PST Received: from mcvax.UUCP by uunet.UU.NET (5.54/1.14) with UUCP id AA07506; Sun, 20 Mar 88 02:05:03 EST From: mcvax!pilatus!ceb@uunet.UU.NET Received: by mcvax.cwi.nl; Sun, 20 Mar 88 07:49:03 +0100 (MET) Received: by cernvax.uucp (1.2/Ultrix2.0-B) id AA24818; Sun, 20 Mar 88 07:03:27 +0100 Date: Sun, 20 Mar 88 07:03:27 +0100 Message-Id: <8803200603.AA24818@cernvax.uucp> To: barmar@think.com Cc: common-lisp@sail.stanford.edu In-Reply-To: Barry Margolin's message of Sat, 19 Mar 88 04:55:38 est Subject: &rest lists should not be copied Date: Sat, 19 Mar 88 04:55:38 est From: Barry Margolin From: mcvax!pilatus!ceb@uunet.uu.net Date: Sun, 13 Mar 88 13:22:44 +0100 If you want to be able to freely modify the structures which are used to implement these features, something imbedded in the kernel of the language is going to have to *copy* them. While this is true, it is not really significant. . . . &REST lists, however, have the additional potential for being EQ with the list passed as the last argument to APPLY, and this is what needs to be specified more carefully. . . . as they should. What made me write were suggestions that the *default* behavior be (at least top-level) cons structure copying. I wanted to demonstrate that this could be potentially expensive, but I guess it was counter-productive to draw in the issue of lower-level copying. Anyhow, even enforcing only top-level copying, even if you restrict yourself to rest lists of "reasonable" size, can cost many conses, and should not be forced upon you. Assuming both kinds of behavior are desirable; one only should ask: 1. Which one should be the default? 2. How do you specify your choice? A number have written drawing attention to existing or proposed (mainly declare) forms to accomplish this. As I understand these though, I don't like them because: 1. The default behavior is copying, the more expensive of the two. 2, If the default behavior were not to copy, it would not cost much if at all more to ask for copying explicitly with a (let . . . (copy-list ) construct. Burying such stuff away in the guts of a language only bring about over-use. On the other hand, explicit mention has positive effects on user optimization. 3. One should avoid fueling the "there's too much junk in common-lisp" fire whenever possible. 4. Declare forms are reminiscent of other programming languages I switched *from* to come to Lisp. I accept them as means for advising the compiler to obtain faster compiled code, as long as I can safely ignore them when rapid prototyping. However, at issue here is averting potentially incorrect behavior (I include cancer-like consing in this), regardless of whether you run interpreted or compiled. About the only real efficiency argument I have been able to drum up for intervening at the moment of function invocation (as opposed to within the called function body) is that stack consing might be cheaper than general consing (even if you cdr code?). If this is really a consideration, then why not simply add keywords to apply and friends, such as :stack-copy-args and/or :copy-args, with defaults set up reasonably? This would keep all of the strangeness in source code *and* and in the compiler localized to the trouble point (within apply). ceb  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 19 Mar 88 17:19:02 EST Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 19 Mar 88 14:04:29 PST Received: from EUPHRATES.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 366372; Sat 19-Mar-88 17:04:33 EST Date: Sat, 19 Mar 88 17:04 EST From: David A. Moon Subject: &REST args To: Charles Hornig , Jeff Barnett , goldman@vaxa.isi.edu, common-lisp@SAIL.STANFORD.EDU In-Reply-To: <19880317053813.3.HORNIG@WINTER.SCRC.Symbolics.COM> Message-ID: <19880319220430.6.MOON@EUPHRATES.SCRC.Symbolics.COM> Date: Thu, 17 Mar 88 00:38 EST From: Charles Hornig Yes, declarations would be a good thing if we decide that Common Lisp permits valid programs to store pointers to or to destructively modify &REST arguments. If we decide that Common Lisp does not permit it, or leaves the result undefined (which is another way of saying the same thing), then there is no need for declarations. Agreed. I believe that there is general agreement that one is allowed to save pointers to &REST arguments. Agreed. There seems to be no agreement about destructive modification. The X3J13 Cleanup subcommittee has taken on this issue. We discussed it at a meeting on Tuesday and will be discussing it further. It's likely that X3J13 will make a decision on this issue in June. Of course, nothing X3J13 decides is final until a language specification is created, accepted by written ballot, and reported out of the X3J13 committee to the parent standards organizations. I, personally, believe that destructive modification should be permitted and that the language implementation must guarantee that this will not currupt structures passed as APPLY arguments. This guarantee can be done through declarations, code analysis, or just consing a lot. For the record, I strongly disagree with this. I believe Common Lisp should specify that the value of an &REST parameter is permitted, but not required, to share structure with the last argument to APPLY. I have two reasons for this belief (both of which have come up on the mailing list before). 1. In no other place does Common Lisp automatically unshare structure, except when the user is explicitly modifying the structure (as in REMOVE). Making APPLY automatically unshare would be a semantic wart. 2. If APPLY copies its last argument, recursive programs that receive an &REST argument and pass it to APPLY become inefficient. A linear time algorithm can change to a quadratic time algorithm. While the efficiency could be regained through compiler flow analysis in many cases, I think it's better not to put the inefficiency into the language in the first place.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 19 Mar 88 15:12:35 EST Received: from elroy.Jpl.Nasa.Gov by SAIL.Stanford.EDU with TCP; 19 Mar 88 11:52:08 PST Received: by elroy.Jpl.Nasa.Gov (4.0/SMI-3.2+DXR) id AA07184; Sat, 19 Mar 88 04:33:48 PST Received: by grian.cps.com (3.2/SMI-3.2) id AA08488; Sat, 19 Mar 88 03:38:28 PST To: cps-common Path: grian!uucp From: Barry Margolin Newsgroups: cps.common Subject: &rest lists and other things ground through function application Message-Id: <454@grian.UUCP> Date: 19 Mar 88 11:38:26 GMT Sender: grian!uucp@elroy.Jpl.Nasa.Gov Lines: 24 From: mcvax!pilatus!ceb@uunet.uu.net Date: Sun, 13 Mar 88 13:22:44 +0100 If you want to be able to freely modify the structures which are used to implement these features, something imbedded in the kernel of the language is going to have to *copy* them. You could do a top-level copy, but then you are still not protected if someone does a (setf (cadr passed-argument-structure 'truc). In order to beat this, you have to do an arbitrary depth copy, and then, when you pass tangled, circular, non-ending horrible things which make print go bananas (I do this often), you have to do circular list detection, etc. . . . and you very quickly get into a game which can't be won. While this is true, it is not really significant. In the case of the substructure, this is no different from ordinary arguments - the Nth parameter seen by a function is always EQL to the Nth argument passed to the function. &REST lists, however, have the additional potential for being EQ with the list passed as the last argument to APPLY, and this is what needs to be specified more carefully. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 19 Mar 88 15:12:32 EST Received: from elroy.Jpl.Nasa.Gov by SAIL.Stanford.EDU with TCP; 19 Mar 88 11:54:06 PST Received: by elroy.Jpl.Nasa.Gov (4.0/SMI-3.2+DXR) id AA06784; Sat, 19 Mar 88 03:38:42 PST Received: by grian.cps.com (3.2/SMI-3.2) id AA08302; Sat, 19 Mar 88 02:41:02 PST To: cps-common Path: grian!uucp From: K. Shane Hartman Newsgroups: cps.common Subject: &REST args Message-Id: <453@grian.UUCP> Date: 19 Mar 88 10:40:58 GMT Sender: grian!uucp@elroy.Jpl.Nasa.Gov Lines: 17 Date: Wed, 16 Mar 88 15:35:28 PST From: Jeff Barnett In regards to the properties of &REST arguments: There may be a way to have our cake and eat it too given that CL has a declaration mechanism in place already and optimization hints are considered first class citizens. I propose an anology to the SYS:DOWNWARD-FUNCTION and SYS:DOWNWARD-FUNARG decls in the Symbolics implementations. In the function with the &REST arg, that arg could be declared DOWNWARD meaning that pointers to it and top-level Lucid uses the declaration DYNAMIC-EXTENT for this purpose. -[Shane]->  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 19 Mar 88 05:08:58 EST Received: from Think.COM by SAIL.Stanford.EDU with TCP; 19 Mar 88 01:56:20 PST Return-Path: Received: from pozzo.think.com by Think.COM; Sat, 19 Mar 88 04:55:44 EST Received: by pozzo.think.com; Sat, 19 Mar 88 04:55:38 est Date: Sat, 19 Mar 88 04:55:38 est From: Barry Margolin Message-Id: <8803190955.AA09901@pozzo.think.com> To: mcvax!pilatus!ceb@uunet.uu.net Cc: common-lisp@sail.stanford.edu In-Reply-To: mcvax!pilatus!ceb@uunet.uu.net's message of Sun, 13 Mar 88 13:22:44 +0100 <8803131222.AA20860@cernvax.uucp> Subject: &rest lists and other things ground through function application From: mcvax!pilatus!ceb@uunet.uu.net Date: Sun, 13 Mar 88 13:22:44 +0100 If you want to be able to freely modify the structures which are used to implement these features, something imbedded in the kernel of the language is going to have to *copy* them. You could do a top-level copy, but then you are still not protected if someone does a (setf (cadr passed-argument-structure 'truc). In order to beat this, you have to do an arbitrary depth copy, and then, when you pass tangled, circular, non-ending horrible things which make print go bananas (I do this often), you have to do circular list detection, etc. . . . and you very quickly get into a game which can't be won. While this is true, it is not really significant. In the case of the substructure, this is no different from ordinary arguments - the Nth parameter seen by a function is always EQL to the Nth argument passed to the function. &REST lists, however, have the additional potential for being EQ with the list passed as the last argument to APPLY, and this is what needs to be specified more carefully. barmar  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 19 Mar 88 04:09:09 EST Received: from elroy.Jpl.Nasa.Gov by SAIL.Stanford.EDU with TCP; 19 Mar 88 00:52:48 PST Received: by elroy.Jpl.Nasa.Gov (4.0/SMI-3.2+DXR) id AA04650; Fri, 18 Mar 88 19:34:53 PST Received: by grian.cps.com (3.2/SMI-3.2) id AA06610; Fri, 18 Mar 88 18:34:19 PST To: cps-common Path: grian!uucp From: K. Shane Hartman Newsgroups: cps.common Subject: &REST args Message-Id: <450@grian.UUCP> Date: 19 Mar 88 02:34:17 GMT Sender: grian!uucp@elroy.Jpl.Nasa.Gov Lines: 16 Date: Wed, 16 Mar 88 15:35:28 PST From: Jeff Barnett In regards to the properties of &REST arguments: There may be a way to have our cake and eat it too given that CL has a declaration mechanism in place already and optimization hints are considered first class citizens. I propose an anology to the SYS:DOWNWARD-FUNCTION and SYS:DOWNWARD-FUNARG decls in the Symbolics implementations. In the function with the &REST arg, that arg could be declared DOWNWARD meaning that pointers to it and top-level Lucid uses the declaration DYNAMIC-EXTENT for this purpose. -[Shane]->  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 18 Mar 88 18:00:57 EST Received: from XX.LCS.MIT.EDU by SAIL.Stanford.EDU with TCP; 18 Mar 88 14:44:08 PST Received: from LIVE-OAK.LCS.MIT.EDU by XX.LCS.MIT.EDU via Chaosnet; 18 Mar 88 17:45-EST Received: from JASPER.Palladian.COM (JASPER.Palladian.COM) by MIT-LIVE-OAK.DialNet.Symbolics.COM via DIAL with SMTP id 84701; 18 Mar 88 17:35:44-EST Received: from KITTYHAWK.Palladian.COM by JASPER.Palladian.COM via CHAOS with CHAOS-MAIL id 27421; Fri 18-Mar-88 17:30:36 EST Date: Fri, 18 Mar 88 17:30 EST From: K. Shane Hartman Subject: &REST args To: jbarnett@nrtc.northrop.com cc: common-lisp@sail.stanford.edu In-Reply-To: The message of 16 Mar 88 18:35 EST from Jeff Barnett Message-ID: <880318173025.0.SHANE@KITTYHAWK.Palladian.COM> Date: Wed, 16 Mar 88 15:35:28 PST From: Jeff Barnett In regards to the properties of &REST arguments: There may be a way to have our cake and eat it too given that CL has a declaration mechanism in place already and optimization hints are considered first class citizens. I propose an anology to the SYS:DOWNWARD-FUNCTION and SYS:DOWNWARD-FUNARG decls in the Symbolics implementations. In the function with the &REST arg, that arg could be declared DOWNWARD meaning that pointers to it and top-level Lucid uses the declaration DYNAMIC-EXTENT for this purpose. -[Shane]->  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 17 Mar 88 08:22:22 EST Received: from ALDERAAN.SCRC.Symbolics.COM ([128.81.41.109]) by SAIL.Stanford.EDU with TCP; 17 Mar 88 05:11:18 PST Received: from WINTER.SCRC.Symbolics.COM by ALDERAAN.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 179199; Thu 17-Mar-88 07:47:51 EST Date: Thu, 17 Mar 88 00:38 EST From: Charles Hornig Subject: &REST args To: Jeff Barnett , goldman@vaxa.isi.edu, common-lisp@sail.stanford.edu In-Reply-To: The message of 16 Mar 88 18:35 EST from Jeff Barnett , <8803162317.AA14565@vaxa.isi.edu> Message-ID: <19880317053813.3.HORNIG@WINTER.SCRC.Symbolics.COM> Yes, declarations would be a good thing if we decide that Common Lisp permits valid programs to store pointers to or to destructively modify &REST arguments. If we decide that Common Lisp does not permit it, or leaves the result undefined (which is another way of saying the same thing), then there is no need for declarations. I believe that there is general agreement that one is allowed to save pointers to &REST arguments. There seems to be no agreement about destructive modification. I, personally, believe that destructive modification should be permitted and that the language implementation must guarantee that this will not currupt structures passed as APPLY arguments. This guarantee can be done through declarations, code analysis, or just consing a lot.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 16 Mar 88 23:06:41 EST Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 16 Mar 88 17:53:58 PST Posted-Date: Wed, 16 Mar 88 15:17:23 PST Message-Id: <8803162317.AA14565@vaxa.isi.edu> Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51) id AA14565; Wed, 16 Mar 88 15:17:27 PST To: common-lisp@sail.stanford.edu From: goldman@vaxa.isi.edu Subject: &rest args -- (declarations) Date: Wed, 16 Mar 88 15:17:23 PST Sender: goldman@vaxa.isi.edu Has consideration been given to providing at least some declaration(s) the programmer can make -- e.g., (DEFUN FOO (&REST L) (DECLARE (DYNAMIC-EXTENT L) (READ-ONLY L)) ...) that would effectively AUTHORIZE a compiler to perform certain optimizations/transformations even when it could NOT otherwise PROVE the optimization/transformation preserved equivalence? [At least one implementation already provides a similar declaration for functional arguments, that authorizes the "consing" of lexical closures on the stack.] There is no doubt some latitude for choosing relevant declarations. I'm NOT proposing a particular set here in the hope that the matter has already been given more thought by someone else. Has it? neil  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 16 Mar 88 23:03:53 EST Received: from nrtc.nrtc.northrop.com (NRTC.NORTHROP.COM) by SAIL.Stanford.EDU with TCP; 16 Mar 88 17:47:21 PST Date: Wed, 16 Mar 88 15:35:28 PST From: Jeff Barnett To: common-lisp@sail.stanford.edu Subject: &REST args In regards to the properties of &REST arguments: There may be a way to have our cake and eat it too given that CL has a declaration mechanism in place already and optimization hints are considered first class citizens. I propose an anology to the SYS:DOWNWARD-FUNCTION and SYS:DOWNWARD-FUNARG decls in the Symbolics implementations. In the function with the &REST arg, that arg could be declared DOWNWARD meaning that pointers to it and top-level CDRS are not stored upward and/or it could be declared NO-SETF meaning that none of the structure (top-level or otherwise) is modified. The intention here is that the function not mdify part of the &REST arg because it is part of that arg---the function's contract (documentation) could specify that some other structure might be modified and if part of that structure is shared by the &REST parameter, then caveat caller as usual. On the call to apply, the last argument could be declared to be SMASHABLE and/or SHARABLE when it is and/or compiler optimizers can detect when the list is freshly consed or a quote etc. Apply could decide whether to pass the original, stack cons, or heap cons as appropriate. When in doubt, it would always do the latter.  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 16 Mar 88 22:47:38 EST Received: from XX.LCS.MIT.EDU by SAIL.Stanford.EDU with TCP; 16 Mar 88 11:58:21 PST Received: from LIVE-OAK.LCS.MIT.EDU by XX.LCS.MIT.EDU via Chaosnet; 15 Mar 88 11:14-EST Received: from ACORN.Gold-Hill.DialNet.Symbolics.COM by MIT-LIVE-OAK.DialNet.Symbolics.COM via DIAL with SMTP id 84390; 15 Mar 88 11:07:32-EST Received: from BOSTON.Gold-Hill.DialNet.Symbolics.COM by ACORN.Gold-Hill.DialNet.Symbolics.COM via CHAOS with CHAOS-MAIL id 96800; Tue 15-Mar-88 10:08:06-EST Date: Tue, 15 Mar 88 10:09 est From: mike%acorn@oak.lcs.mit.edu (mike@gold-hill.com after 1-April-88) COMMENTS: NOTE %acorn@oak... CHANGES TO @GOLD-HILL.COM ON 1-April-88 To: ELIOT@cs.umass.edu Subject: &Rest Lists Cc: common-lisp@SAIL.STANFORD.EDU (defun foo (&rest x) ...) Should behave as if it were defined: (defun foo (&rest G0047) ;Gensym really (let ((x (copy-list G0047))) ...)) I think this fully and precisely specifies the semantics of &Rest. Chris Eliot I couldn't disagree more. This implementation prohibits the programmer from exploiting sharing of list substructure. It really takes away some expressive power. One can get back the behavior that you want with the transform you've outlined here. Common lisp is not a functional language, it has tons of destructive operations. It is out of character for such a language to prohibit sharing of substructure by copying data structures implicitly. In general, when destructive operations are being used it should be the programmer's responsibility to copy a data structure manually. &REST should never cause copying of a list passed to it from APPLY. ...mike beckerle GOLD HILL  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 16 Mar 88 22:22:05 EST Received: from XX.LCS.MIT.EDU by SAIL.Stanford.EDU with TCP; 16 Mar 88 11:58:21 PST Received: from LIVE-OAK.LCS.MIT.EDU by XX.LCS.MIT.EDU via Chaosnet; 15 Mar 88 11:14-EST Received: from ACORN.Gold-Hill.DialNet.Symbolics.COM by MIT-LIVE-OAK.DialNet.Symbolics.COM via DIAL with SMTP id 84390; 15 Mar 88 11:07:32-EST Received: from BOSTON.Gold-Hill.DialNet.Symbolics.COM by ACORN.Gold-Hill.DialNet.Symbolics.COM via CHAOS with CHAOS-MAIL id 96800; Tue 15-Mar-88 10:08:06-EST Date: Tue, 15 Mar 88 10:09 est From: mike%acorn@oak.lcs.mit.edu (mike@gold-hill.com after 1-April-88) COMMENTS: NOTE %acorn@oak... CHANGES TO @GOLD-HILL.COM ON 1-April-88 To: ELIOT@cs.umass.edu Subject: &Rest Lists Cc: common-lisp@SAIL.STANFORD.EDU (defun foo (&rest x) ...) Should behave as if it were defined: (defun foo (&rest G0047) ;Gensym really (let ((x (copy-list G0047))) ...)) I think this fully and precisely specifies the semantics of &Rest. Chris Eliot I couldn't disagree more. This implementation prohibits the programmer from exploiting sharing of list substructure. It really takes away some expressive power. One can get back the behavior that you want with the transform you've outlined here. Common lisp is not a functional language, it has tons of destructive operations. It is out of character for such a language to prohibit sharing of substructure by copying data structures implicitly. In general, when destructive operations are being used it should be the programmer's responsibility to copy a data structure manually. &REST should never cause copying of a list passed to it from APPLY. ...mike beckerle GOLD HILL  Received: from SAIL.Stanford.EDU (TCP 1200000013) by AI.AI.MIT.EDU 16 Mar 88 15:13:21 EST Received: from XX.LCS.MIT.EDU by SAIL.Stanford.EDU with TCP; 16 Mar 88 11:58:21 PST Received: from LIVE-OAK.LCS.MIT.EDU by XX.LCS.MIT.EDU via Chaosnet; 15 Mar 88 11:14-EST Received: from ACORN.Gold-Hill.DialNet.Symbolics.COM by MIT-LIVE-OAK.DialNet.Symbolics.COM via DIAL with SMTP id 84390; 15 Mar 88 11:07:32-EST Received: from BOSTON.Gold-Hill.DialNet.Symbolics.COM by ACORN.Gold-Hill.DialNet.Symbolics.COM via CHAOS with CHAOS-MAIL id 96800; Tue 15-Mar-88 10:08:06-EST Date: Tue, 15 Mar 88 10:09 est From: mike%acorn@oak.lcs.mit.edu (mike@gold-hill.com after 1-April-88) COMMENTS: NOTE %acorn@oak... CHANGES TO @GOLD-HILL.COM ON 1-April-88 To: ELIOT@cs.umass.edu Subject: &Rest Lists Cc: common-lisp@SAIL.STANFORD.EDU (defun foo (&rest x) ...) Should behave as if it were defined: (defun foo (&rest G0047) ;Gensym really (let ((x (copy-list G0047))) ...)) I think this fully and precisely specifies the semantics of &Rest. Chris Eliot I couldn't disagree more. This implementation prohibits the programmer from exploiting sharing of list substructure. It really takes away some expressive power. One can get back the behavior that you want with the transform you've outlined here. Common lisp is not a functional language, it has tons of destructive operations. It is out of character for such a language to prohibit sharing of substructure by copying data structures implicitly. In general, when destructive operations are being used it should be the programmer's responsibility to copy a data structure manually. &REST should never cause copying of a list passed to it from APPLY. ...mike beckerle GOLD HILL