Pointers in Haskell??

Hamilton Richards ham@cs.utexas.edu
Fri, 7 Dec 2001 16:52:05 -0600


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
------------------------------------------------------------------