Fergus Henderson wrote:
> I'm not sure off-hand what the best fix would be. One possible solution
> would be to force evaluation of the arguments if they are equal:
>
> equal x y = unsafePerformIO $ do
> ptrEq <- ptrEqual x y
> return (if ptrEq then x `hyperseq` True else deep_equals x y)
>
> However, this compromises the nice O(1) performance in that case.
>
> Another possible fix would be to rename `equal' as `unsafe_equal',
> noting that it is referentially transparent so long as neither of its
> arguments contains bottom or any exceptional value; it would then be
> the programmer's responsibility to check that all callers ensure that
> this condition is satisfied for all calls to `unsafe_equal'.
>
> The second fix is probably best. But it's still rather ugly.
Once opon a time (ca. 1986) I almost implemented a scheme which
would use pointer equality in a safe way. The idea is to have each
node in the heap tagged if it is fully evaluated or not. So if pointer equality
says `equal' and the node is tagged as fully evaluated we can safely
use the result, otherwise not.
But after considering it for a while, I decided that it would incur bigger
runtime costs than the savings for comparisons. AFAIK, it's not
been tried yet. Maybe nowadays we could get help from the type system
in deciding if a value can be bottom or not (well, I know we can, but again
I don't think it's been tried in practice).
> ... This is OK in Mercury because in Mercury
> although the operational semantics is required to be sound w.r.t. the
> declarative semantics, it is not required to be complete; in cases
> where the declarative semantics says that the result is `yes', it may
> still be acceptable for the implementation to throw an exception
> rather than computing the result `yes'. In Mercury, if you want to
> reason about whether your program will terminate or throw exceptions,
> you need to use the operational semantics rather than the declarative
> semantics.
Well, given that I think I'll stick to functional languages. ;-)
--
-- Lennart
