lisp code tree becoming a graph

[Pascal Bourguignon]

> Date: Tue, 26 Nov 2002 14:06:03 +0100 (CET)
> From: Armin Rigo <arigo@tunes.org>
> To: Gustavo Lacerda <gus@optimizelife.com>
> Cc: <tunes@tunes.org>
> Subject: Re: your mail
> 
> Hello,
> 
> On Mon, 25 Nov 2002, Gustavo Lacerda wrote:
> > "For example, a Lisp source file describes a tree. Apart from the implicit
> > root, the nodes are cons cells, nil, or literals. The former has two "up"
> > ports, car and cdr. All nodes have a "down" port, usually called its
> > address, its identity, or whatever. When the program runs, the tree might
> > cease to be a linear graph because of sharing -- in which case you have
> > several "pointers" to the same node, i.e. several edges connecting to its
> > "down" port."
> >
> > Can you give me an example of such a source file, and why it would cease to
> > be a linear graph?
> 
> The Lisp source files describe a tree (all trees are linear graphs). But
> when you execute your Lisp code, you will execute intructions that modify
> that structure; something that could happend is that we duplicate a
> pointer to a node. For example, you may store '(car x)' into '(car y)'.
> Then the "down" port of the now-shared node is no longer stricly speaking
> linear, because it is linked to both the 'car' of x and the 'car' of y.
> 
> Well, that was just an example. While I've been thinking more about graph
> reductions, it now seems interesting to explicitely allow non-linearity in
> some situations. For example, althought one can always make a graph
> explicitely linear by replacing the non-linear link
> 
>            _- Y
>          _-
>    X <---_
>           -_
>             - Z
> 
> with three links and a new "copy" node
> 
>                _- Y
>              _-
>     X ---copy_
>               -_
>                 - Z
> 
> there are levels of abstractions at which the upper situation is just the
> way to go because it directly models the idea that we can go from Z to X,
> or from Y to X, but not easily back --- e.g. following a pointer.
> 
> 
> > This sounds very interesting. I would like to work on it too, and I have a
> > lot of time. Do you have any suggestions?
> 
> I don't know. Not much work has been done recently at Tunes in this area.
> I'll try to copy my message to the tunes@tunes.org mailing list.

Have a look at this:

(defmacro repeat (n &rest body)
  (loop for i from 0 below n 
        append body into sequence
        finally return (cons 'progn sequence)))

(show (macroexpand (quote

                    (repeat 3 
                             (setq x (1+ x))
                             (format t "hello ~a ~%" x)
                             )
                    )))

==> (progn (setq x (1+ x)) (format t "hello ~a ~%" x) (setq x (1+ x)) (format t "hello ~a ~%" x) (setq x (1+ x)) (format t "hello ~a ~%" x))

(setq r (macroexpand (quote 
                      (repeat 3 
                             (setq x (1+ x))
                             (format t "hello ~a ~%" x)
                             ))))


(show r)

==> (progn (setq x (1+ x)) (format t "hello ~a ~%" x) (setq x (1+ x)) (format t "hello ~a ~%" x) (setq x (1+ x)) (format t "hello ~a ~%" x))

(show (eq (nth 2 r) (nth 4 r)))

==> t

(setq s '(progn (setq x (1+ x)) (format t "hello ~a ~%" x) (setq x (1+ x)) (format t "hello ~a ~%" x) (setq x (1+ x)) (format t "hello ~a ~%" x)))

(show s)

==> (progn (setq x (1+ x)) (format t "hello ~a ~%" x) (setq x (1+ x)) (format t "hello ~a ~%" x) (setq x (1+ x)) (format t "hello ~a ~%" x))

(show (eq (nth 2 s) (nth 4 s)))

==> nil




You could even come with a  macro that transforms the code tree into a
graph with cycles (loops):

      (setq some-sequence '(progn (setq x (1+ x))))
      (setf (cdr (last some-sequence))
            (list 'if '(< x 10) some-sequence))

(show some-sequence)

==> (progn (setq x (1+ x)) if (< x 10) #0)

(show (nth 4 some-sequence))

==> (progn (setq x (1+ x)) if (< x 10) #0)

(show (eq some-sequence (nth 4 some-sequence)))

==> t

-- 
__Pascal_Bourguignon__                   http://www.informatimago.com/
----------------------------------------------------------------------
There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him.  -- Robert Heinlein