Re: Circular lists/shared structures in org-element parse-tree

[Pascal J. Bourguignon]

Thorsten Jolitz <tjolitz@gmail.com> 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