your mail

[Armin Rigo]

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.


Armin