From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: "Pascal J. Bourguignon" Newsgroups: gmane.emacs.help Subject: Re: why are there [v e c t o r s] in Lisp? Date: Fri, 16 Oct 2015 07:16:08 +0200 Organization: Informatimago Message-ID: <871tcve6lj.fsf@kuiper.lan.informatimago.com> References: <87mvvjeg29.fsf@kuiper.lan.informatimago.com> <87io67pmr7.fsf@debian.uxu> <87mvvjzgup.fsf@fastmail.com> <87d1wfplu5.fsf@debian.uxu> <87a8rjea8m.fsf@kuiper.lan.informatimago.com> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: ger.gmane.org 1444972828 5122 80.91.229.3 (16 Oct 2015 05:20:28 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 16 Oct 2015 05:20:28 +0000 (UTC) To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Fri Oct 16 07:20:24 2015 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1ZmxRG-0001Ef-61 for geh-help-gnu-emacs@m.gmane.org; Fri, 16 Oct 2015 07:20:22 +0200 Original-Received: from localhost ([::1]:50973 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZmxRF-0007IV-Jf for geh-help-gnu-emacs@m.gmane.org; Fri, 16 Oct 2015 01:20:21 -0400 Original-Path: usenet.stanford.edu!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail Original-Newsgroups: gnu.emacs.help Original-Lines: 66 Original-X-Trace: individual.net iSSejwBcqTswpDMOBjmjFgZYUM+Zba17iCKMywTniTeHLJjbXA Cancel-Lock: sha1:NTAzMWE1YTcyNzNkYmZkNTdlMzVkMDE0MGQyY2I2NmE2YzBkYjQ0ZA== sha1:GUcRezNmM52IrxdSukA4T74zI1Y= Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwAQMAAABtzGvEAAAABlBMVEUAAAD///+l2Z/dAAAA oElEQVR4nK3OsRHCMAwF0O8YQufUNIQRGIAja9CxSA55AxZgFO4coMgYrEDDQZWPIlNAjwq9 033pbOBPtbXuB6PKNBn5gZkhGa86Z4x2wE67O+06WxGD/HCOGR0deY3f9Ijwwt7rNGNf6Oac l/GuZTF1wFGKiYYHKSFAkjIo1b6sCYS1sVmFhhhahKQssRjRT90ITWUk6vvK3RsPGs+M1RuR mV+hO/VvFAAAAABJRU5ErkJggg== X-Accept-Language: fr, es, en User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) Original-Xref: usenet.stanford.edu gnu.emacs.help:215389 X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.help:107673 Archived-At: Random832 writes: > "Pascal J. Bourguignon" writes: >> Random832 writes: >>> Well, what happens if you cdr that list? Does it make a >>> copy? >> >> cdr'ing is no problem you just increment your pointer. >> >>> The thing is, if you can car a string people will wonder why >>> you can't cdr it. And with mutable objects it's hard to make >>> cdr work right. (fsvo "right") >> >> It's rplacd which becomes much more complex. > > You didn't mention my issue with "list of 5000 elements, cdr > 4000 times" - does the garbage collector know to discard the > first 4000 elements which are no longer reachable? Well, I don't know if the implementations that had cdr-coding could collect the prefix of the vector of cars that wasn't referenced anymore. It's a little complexity for the garbage collector, but not too hard to implement. The problem is more when you want to discard the 1 element which is no longer reachable: this becomes quite costly. >> Also, when you program with such a system, you might be afraid that >> rplacd leads to fragmented chains, and will have a tendency to call >> copy-list to compact them. > > Hmm... can the garbage collector compact them? Compacting lists at garbage collection time is indeed a good idea, when you have cdr-coding. On the other hand, I believe the implementations that had cdr-coding had a simple mark-and-sweap garbage collector, not a copying one. Some archeology would be in order there. >> But indeed, copy-list means that less >> structure is shared, and therefore would waste time and memory. This is >> what they do in C++ and why they believe lists are costly. > > Also with this kind of list I think you still lose the > ability to have constant-time indexing, since you have to > check every cell for the cdr bit. Of course. Worse, to have O(1) indexing, you'd need to know the length in advance, and this is what is killing, you cannot have an efficient length when you have mutation and structure sharing. rplacd would have to update an unbound number of length slots. However, it is possible to have a compiler that will map lists to vectors in the generated code, as long as this compiler is able to perform global analysis to ensure the semantics. With global analysis, you can easily determine whether there is structure sharing, whether rplaca is used, and determine the length of the list at compilation time or know to store it. -- __Pascal Bourguignon__ http://www.informatimago.com/ “The factory of the future will have only two employees, a man and a dog. The man will be there to feed the dog. The dog will be there to keep the man from touching the equipment.” -- Carl Bass CEO Autodesk