On 27-Jul-1999, Andreas C. Doering <[EMAIL PROTECTED]> wrote:
> [Simon Peyton-Jones wrote:]
> >[Andreas Doering wrote:]
> >> let x=[1..] in x==x 
> >> would not terminate in the first case but succeed in the second. 
> > 
> > But, much worse
> > 
> >       let x = (a,b) in x `req` x      = True
> > but
> >       (a,b) `req` (a,b)                       = False
> > 
> > So referential transparency is lost.  This is a high price to pay.
> > You are right that *something* is needed; but I don't yet know what.

I agree that `req' is not the right primitive.  But unfortunately that
didn't stop it from being included in the ghc extensions library!
(ghc calls it `unsafePtrEq'.)  This is a design bug in the ghc, IMHO,
and it ought to be changed.

Instead of providing unsafe primitives such as `req', or `unsafePtrEq',
which can never be used in ways that can be guaranteed to be safe against
all possible compiler optimizations that assume referential transparency,
it's better to provide safe equivalents, by putting them in an appropriate
monad.

In this case what is desired is a nondeterminism monad.  The `IO' monad
will suffice as a nondeterminism monad, since it provides
nondeterminism as well as I/O, but it's not really ideal, because in
this case we only want the nondeterminism rather than the I/O.  Using
the `IO' monad works, but it doesn't do a good job of documenting the
properties of the function.

> I do not think that this is "worse". 
> Such a funtion would have to be used wise. 

In most circumstances the most wise use of such a function would be to
not use it at all, IMHO!

A compiler might make optimizations based on the assumption that all
functions are referentially transparent, and so if functions such as `req`
are not referentially transparent, then these optimizations would be based
on incorrect assumptions, and could therefore lead to undefined behaviour,
potentially including segmentation faults or worse.

As it happens, I can't think of any good examples of this off-hand.
But I'm sure such examples could be constructed.

> "True" means "Sure both terms are equal, we can save further actions"
> "False" means "Do not know,"
> It is a primitive which has to be used as in the list comparison. 
> Then, "referential transparency" is recreated, but the termination problem 
> remains. 

In circumstances where you have an `impure' function which is used in a manner
which is pure, you should enclose such uses inside `unsafePerformIO' or
something equivalent.  This is a *safe* use of `unsafePerformIO'.

Currently the Haskell report does not document `unsafePerformIO' and
does not state which uses are safe, but IMHO this is a bug in the current
Haskell report.

Note that there is a big difference between using a primitive which can
never be guaranteed to be referentially transparent, like `req', and using
a primitive like `unsafePerformIO' which *is* safe and referentially
transparent when used in an appropriate manner.  With the former, you
can never be sure that the compiler won't mis-optimize your code.

> > Meanwhile Jeff Lewis has a BDD library accessible from Haskell, I believe.
> >       [EMAIL PROTECTED]
> I will ask him. 
> I made a BDD-lib already, but it uses an array to store the nodes, and 
> garbage collection is explicitely programmed on this array 
> requiring reallocation, contents copying and so forth,  very ugly. 

Certainly using an array type for this, with the resulting need to do
manual garbage collection, is very ugly.  You should use a type which
matches your needs.  Such types do exist.  For instance, the ghc stable
name type is sufficient; an IO-monad version of the `req` operator that
you wanted can be implemented as

        import Stable
        x `ptrEqual` y = do
                x_name <- makeStableName x
                y_name <- makeStableName y
                return (x_name == y_name)

However, the ghc stable name type might impose more overhead than you need
for this application -- e.g. ghc might not be able to optimize the above
code to the simple pointer comparison that you would like.

-- 
Fergus Henderson <[EMAIL PROTECTED]>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger [EMAIL PROTECTED]        |     -- the last words of T. S. Garp.


Reply via email to