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: Circular lists/shared structures in org-element parse-tree Date: Sat, 29 Jun 2013 01:20:24 +0200 Organization: Informatimago Message-ID: <87mwq94ybr.fsf@informatimago.com> References: <87y59u3p1w.fsf@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 1372463067 12033 80.91.229.3 (28 Jun 2013 23:44:27 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 28 Jun 2013 23:44:27 +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 Jun 29 01:44:30 2013 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 1UsiL7-00080c-4m for geh-help-gnu-emacs@m.gmane.org; Sat, 29 Jun 2013 01:44:29 +0200 Original-Received: from localhost ([::1]:51800 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UsiL6-0002yi-GW for geh-help-gnu-emacs@m.gmane.org; Fri, 28 Jun 2013 19:44:28 -0400 Original-Path: usenet.stanford.edu!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail Original-Newsgroups: gnu.emacs.help Original-Lines: 61 Original-X-Trace: individual.net AmNbwL8c/XqGsdQ37d7VwAO4wAuJc4gBswkxfxcfKO3qDs1k82 Cancel-Lock: sha1:NzRlNzVjZjYyYWVmM2Q1ZWJjYWMyZTUzMTQ5ZDJiMDkyMDMxZDA1Nw== sha1:ENTHl5wVGfgijqEPsq5HpiUztwU= 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.2 (gnu/linux) Original-Xref: usenet.stanford.edu gnu.emacs.help:199569 X-Mailman-Approved-At: Fri, 28 Jun 2013 19:44:20 -0400 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:91835 Archived-At: Thorsten Jolitz writes: > Thank you for the detailled instructions, very helpful indeed! I thought > Emacs might have some inbuilt functionality to deal with circular list, > but it seems to require some individual effort. But it has, to be able to print circular structures with references. It may also have to avoid infinite recursions in compile circular code. Let's try it: (defun f (x) #1=(if (zerop x) 1 (* x . #1#))) (byte-compile 'f) --> Error: Lisp nesting exceeds `max-lisp-eval-depth' So, the emacs lisp compiler doesn't have any provision against circular code per se, just the usual deep stack protection. Indeed, it is not expect to have circular code in general, only circular data, which will be quoted in code, so that won't recurse while compiling. (require 'cl) (defun* g (x) (dolist (e '(a . #1=(b . #1#))) (if (eq x e) (return-from g 'found)))) (g 'a) --> found (g 'z) --> infinite loop. (byte-compile 'g) --> #[(x) … 2] So the only part of lisp that has to deal with circular structures is the lisp printer (and the lisp reader which must build circular structures when it finds back references). Otherwise, trying to generalize and parameterize the algorithm to make it easily reusable is not so easy. The proof is in the pudding, I mean, often, you're interested in the walking itself more than in finding the loops in the structure. This loop detection is only useful to avoid walking circles. See for example: https://gitorious.org/patchwork/patchwork/blobs/master/src/mclgui/circular.lisp compare print-identified-conses/1 with print-identified-conses/2. It's Common Lisp code, so you will have to set lexical-binding to t using emacs-24, and you may have some more work to port it to emacs lisp. But it's to illustrate the point that the interesting or complex parts is in deciding what edge to walk, not to record the node already reached. -- __Pascal Bourguignon__ http://www.informatimago.com/ A bad day in () is better than a good day in {}. You know you've been lisping too long when you see a recent picture of George Lucas and think "Wait, I thought John McCarthy was dead!" -- Dalek_Baldwin