From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: pjb@informatimago.com (Pascal J. Bourguignon) Newsgroups: gmane.emacs.help Subject: Re: Basic questions about elisp Date: Sat, 07 Nov 2009 18:50:11 +0100 Organization: Informatimago Message-ID: <871vkab4x8.fsf@galatea.local> References: <1e9f8449-09ec-4a84-a332-9f05fadb8aa3@z41g2000yqz.googlegroups.com> <87iqdpdog1.fsf@galatea.local> <871vkdm2p1.fsf@lola.goethe.zz> <4d5245de-4a71-4be7-a445-6d033be48490@g23g2000yqh.googlegroups.com> <87zl6ziooo.fsf@lola.goethe.zz> <878wejcpys.fsf@galatea.local> <8229723a-5415-4a8e-b306-8e694f9cccb7@a32g2000yqm.googlegroups.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Trace: ger.gmane.org 1257619258 16563 80.91.229.12 (7 Nov 2009 18:40:58 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 7 Nov 2009 18:40:58 +0000 (UTC) To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Sat Nov 07 19:40:52 2009 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1N6qDT-0005qf-L0 for geh-help-gnu-emacs@m.gmane.org; Sat, 07 Nov 2009 19:40:51 +0100 Original-Received: from localhost ([127.0.0.1]:39435 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1N6qDT-0001Rv-47 for geh-help-gnu-emacs@m.gmane.org; Sat, 07 Nov 2009 13:40:51 -0500 Original-Path: news.stanford.edu!usenet.stanford.edu!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail Original-Newsgroups: gnu.emacs.help Original-Lines: 55 Original-X-Trace: individual.net wz/T3/zak20wv7YMaLAuuQE9xpPsZTylYPjFf1XbZKab1YIERq Cancel-Lock: sha1:OWFkZWFjN2MxNDg1Yjk5ZGQ1MmI5YmZlZWUzYWVlNmVhNjcyNDU0Zg== sha1:HsztmN65VAPQZrt1kWlbDFBxoqk= Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwAQMAAABtzGvEAAAABlBMVEUAAAD///+l2Z/dAAAA oElEQVR4nK3OsRHCMAwF0O8YQufUNIQRGIAja9CxSA55AxZgFO4coMgYrEDDQZWPIlNAjwq9 033pbOBPtbXuB6PKNBn5gZkhGa86Z4x2wE67O+06WxGD/HCOGR0deY3f9Ijwwt7rNGNf6Oac l/GuZTF1wFGKiYYHKSFAkjIo1b6sCYS1sVmFhhhahKQssRjRT90ITWUk6vvK3RsPGs+M1RuR mV+hO/VvFAAAAABJRU5ErkJggg== X-Accept-Language: fr, es, en X-Disabled: X-No-Archive: no User-Agent: Gnus/5.1008 (Gnus v5.10.8) Emacs/22.3 (darwin) Original-Xref: news.stanford.edu gnu.emacs.help:174514 X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.help:69589 Archived-At: Francis Moreau writes: > On 6 nov, 22:18, p...@informatimago.com (Pascal J. Bourguignon) wrote: >> Francis Moreau writes: >> >>> When I wrote '(2), I suppose the elisp interpreter to create a new >> >>> list. >> >> >> It does so, but at read time.  Not execution time. >> >> > Ah ok I see what you mean now. >> >> > That's a pretty important point, is this part covered by the elisp info ? >> >> Yes. >> >> > Actually the same stands for the implementation of the list, where >> > nconc, length... are O(n). I wouldn't have thought that lists are really >> > implemented by the car & cdr thing only. >> >> Why not?  If people have been repeating for 50 years that lisp lists >> are implemented with cons, car and cdr... > > Because I can understand there were some memory constraints 50 years > ago that force lisp lists to be as small as possible. But I would have > thought lisp lists (or (e)lisp) to evolve as computer memories did. Well, contrarily to Microsoft, we don't have enough time and money to grow a bloatware out of the language. If lists as chains of cons cells could be held in small memories 50 years ago, they can still be held in big memories nowadays, there's no point in changing that. However, if you need a "smarter" list abstract data type, you can always implement it (or use a library). Note however that you might have a hard time to reach the level of efficiency given by cons cells. That is, if you consider cons cells as immutable, then you can easily share them amongst several prefix lists, and therefore you spare a lot of cycles and a lot of memory not copying them. If you try to invent a list ADT where you keep references to both the first and last cells for "efficiency" reasons (so you can append an element in O(1)), then you lose this ability to share lists, and therefore you will have to copy these lists all over (copying the list is O(n), and you lost the benefit of O(1) element appending). If on the contrary you learn to use cons cell based lists, and you avoid appending elements at the end, but push them on the head (which is O(1)), then you can share them O(0) for no copying and spare memory at the same time. (Even if you need a final result in the other order, adding a call reverse (O(n)) won't be less efficient than making copies all the time). -- __Pascal Bourguignon__