In-Reply-To: Hamilton Richards's message of Fri, 7 Dec 2001 12:11:23 -0600
In my previous example,
t = [0..] b = 3 : t c = 5 : t
lists b and c share t, but in
x = 3 : [0..] y = 5 : [0..]
lists x and y share nothing. Extensionally, they have the same values as b and c, but each has its own copy of [0..].
That's because you're interpreting "same value" extensionally. The same sort of issue comes up in Lisp or Java. But suppose in Java I have Object x = new Whatever(); and that new object has some large substructures. I can get one of those substructures to be shared, rather than copied, without having a variable whose value is that substructure. For instance, the substructure might be shared in Object[] anArray = new Object[](x.getSubstructure(), x.getSubstructure()); provided that x.getSubstructure() returns the very same substructure (not a copy) each time.
Unless, that is, the compiler is clever enough to recognize the subexpression [0..] which x and y have in common. I don't know whether any Haskell compilers look for common subexpressions, but it's certainly an option. So the question of whether names are "*the* (only) way" to obtain sharing isn't really a language question-- it's more of a compiler question.
Are they the only way that's guaranteed to result in sharing, or is even that not the case? Cheers, Jeff
At 12:29 PM -0600 12/7/01, Jeff Dalton wrote:
In-Reply-To: Hamilton Richards's message of Fri, 7 Dec 2001 12:11:23 -0600
... But suppose in Java I have
Object x = new Whatever();
and that new object has some large substructures. I can get one of those substructures to be shared, rather than copied, without having a variable whose value is that substructure. For instance, the substructure might be shared in
Object[] anArray = new Object[](x.getSubstructure(), x.getSubstructure());
provided that x.getSubstructure() returns the very same substructure (not a copy) each time.
As far as the semantics of Haskell programs is concerned, there's no distinction between *same* and *equivalent*. An efficient implementation will exploit this by using identity to implement equivalence. For example, in x = ["zero","one","two","three"] y = [x!!2, x!!2] -- (!!) is list indexing the components of y would most likely be implemented by pointers to the same string "two" in memory, but it would also be correct (although less efficient) for y's two components to be separate copies of "two".
... So the question of whether names are "*the* (only) way" to obtain sharing isn't really a language question-- it's more of a compiler question.
Are they the only way that's guaranteed to result in sharing, or is even that not the case?
Depends on what you mean by "guaranteed". Since in Haskell sharing vs. not sharing is not a semantic issue, you can't very well say that if sharing doesn't occur under such-and-such circumstances, the language specification is violated. This is very different from languages like Java, where Object[] x = new Object[](...) Object[] y = x; means that x and y refer to the same array (not merely equivalent arrays), and if they don't, it's not Java. And what's crucial is that you can write a Java program that detects whether x and y refer to the same array, by updating the array via x and observing the effect via y. In Haskell, no such program can be written, because there's no update operation. Hence an implementation is free to share or not, and neither choice violates the language definition. To determine under what circumstances a given Haskell implementation exploits sharing, you really have to look at the implementation's source code. Or you can make some time and space measurements of Haskell programs, and derive educated guesses. Cheers, --Ham ------------------------------------------------------------------ Hamilton Richards, PhD Department of Computer Sciences Senior Lecturer Mail Code C0500 512-471-9525 The University of Texas at Austin Taylor Hall 5.138 Austin, Texas 78712-1188 ham@cs.utexas.edu hrichrds@swbell.net ------------------------------------------------------------------
participants (2)
-
Hamilton Richards -
Jeff Dalton