Tue Nov 26 07:51:02 2002
> On Mon, 25 Nov 2002, Gustavo Lacerda wrote:
> > "For example, a Lisp source file describes a tree. Apart from the
> > root, the nodes are cons cells, nil, or literals. The former has two
> > ports, car and cdr. All nodes have a "down" port, usually called its
> > address, its identity, or whatever. When the program runs, the tree
> > 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
> > "down" port."
> > Can you give me an example of such a source file, and why it would cease
> > be a linear graph?
Sorry. I should have asked this first: what is a linear graph, as opposed to
a non-linear graph? Is it one in which "edges" correspond to exactly two
ports? This is what I simply call "graph".
> The Lisp source files describe a tree (all trees are linear graphs). But
> when you execute your Lisp code, you will execute instructions that modify
> that structure;
i.e. the reduction of the code. I am familiar with reduction in Scheme.
> something that could happen is that we duplicate a
> pointer to a node. For example, you may store '(car x)' into '(car y)'.
I have no idea what you are saying. What do you mean by "store"?
> 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 explicitly allow non-linearity in
> some situations. For example, although one can always make a graph
> explicitly 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.
What is the type of X, Y, Z? Lisp code? Lisp atoms?
What does it mean to "go from A to B" ?
Are these trees parse trees for the code or are they possible code