On Tue, Jul 19, 2011 at 11:14 PM, yi huang wrote:

2011/7/20 Eugene Kirpichov

...

reallyUnsafePointerEq#, and it really is as unsafe as it sounds :)

Why is it so unsafe? i can't find any documentation on it. I think always compare pointer first is a good optimization.

False positives and false negatives are both possible, depending on GC timing. Don't use it, unless you know why it can result in both false positives and false negatives, and you know why neither of those are bad for your use case. I'm not aware of any use case that's resilient to both failure modes, offhand. Carl

Hello all, I'm a newbie at Haskell and I was not aware of this problem. So, equality comparison can run into an infinite-loop? My current knowledge of the language tells me that everything is Haskell is a thunk until it's value is really needed. Is it possible to implement (==) that first check these thunks before evaluating it? (Considering both arguments has pure types). E.g., Equivalent thunks, evaluates to True, does not need to evaluate its arguments: [1..] == [1..] Another case: fib = 1:1:zipWith (+) fib (tail fib) fibA = 1:tail fib fib == fibA -- True Evaluating: 1:1:zipWith (+) fib (tail fib) == 1:tail fib -- first item match, check further 1:zipWith (+) fib (tail fib) == tail fib -- thunks do not match, evaluate arguments 1:zipWith (+) fib (tail fib) == 1:zipWith (+) fib (tail fib) -- thunks matches, comparison stops and the value is True As I said before, I'm a newbie at Haskell. Sorry if my question or examples makes no sense. Thanks, Thiago.

On Wed, Jul 20, 2011 at 10:48 AM, Thiago Negri wrote:

Hello all, I'm a newbie at Haskell and I was not aware of this problem. So, equality comparison can run into an infinite-loop?

My current knowledge of the language tells me that everything is Haskell is a thunk until it's value is really needed. Is it possible to implement (==) that first check these thunks before evaluating it? (Considering both arguments has pure types).

One thing to remember is that (==) is an ordinary Haskell function - it isn't a special built-in operator. Every type that implements implements it as an ordinary Haskell function. There is support to have the compiler right the function for you in some cases, but I don't believe it uses any facilities unavailable to an ordinary app/library author. The notion of "thunks" is a deep implementation detail - there's no mandate that the concept be used in a Haskell implementation, so the language doesn't expose the concept in a concrete way. I think that some folks have released libraries that call into internal GHC hooks to see if a run-time value points to an unevaluated thunk.

E.g.,

Equivalent thunks, evaluates to True, does not need to evaluate its arguments:    [1..] == [1..]

How would we measure "equivalence" on thunks? We would need to open up the thunk, inspect the pieces, and then somehow call the appropriate (==) method on the different pieces - and then some of the pieces themselves might be thunks on the LHS but not the RHS, and the thunks on the LHS and the RHS might be equivalent but of completely different nature: think of:

f x == g y

Where f & g are completely different functions. Both might evaluate to [1..] through independent means, the only way to know would be to evaluate them, which might not terminate.

Another case:

fib = 1:1:zipWith (+) fib (tail fib) fibA = 1:tail fib fib == fibA -- True

Evaluating:

1:1:zipWith (+) fib (tail fib) == 1:tail fib -- first item match, check further 1:zipWith (+) fib (tail fib) == tail fib -- thunks do not match, evaluate arguments 1:zipWith (+) fib (tail fib) == 1:zipWith (+) fib (tail fib) -- thunks matches, comparison stops and the value is True

As I said before, I'm a newbie at Haskell. Sorry if my question or examples makes no sense.

One other thing to note is that GHC strips away almost all types during the process of compilation, so a lot of advanced reflection needs to be done with structures that explicitly keep the type around during run-time,

Thanks, Thiago.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On 07/21/2011 10:30 AM, Pedro Vasconcelos wrote:

On Wed, 20 Jul 2011 12:48:48 -0300 Thiago Negri wrote:

...

Is it possible to implement (==) that first check these thunks before evaluating it? (Considering both arguments has pure types).

E.g.,

Equivalent thunks, evaluates to True, does not need to evaluate its arguments: [1..] == [1..]

Thunks are just expressions and equality of expressions is undecidable in any Turing-complete language (like any general-purpose programming language). Note that syntactical equality is not sufficient because (==) should be referentially transparent.

I think the following code pretty much models what Thiago meant for a small subset of haskell that constructs possibly infinite lists. Thunks are made explicit as syntax trees. 'Cycle' is the syntactic symbol for a function whose definition is given by the respective case in the definition of 'evalOne'. (I chose cycle here instead of the evalFrom example above to because it doesn't need an Enum constraint). The interesting part is the definition of 'smartEq'. import Data.List (unfoldr) import Data.Function (on) -- let's say we have syntactic primitives like this data ListExp a = Nil | Cons a (ListExp a) | Cycle (ListExp a) deriving (Eq, Ord, Read, Show) -- derives syntactic equality conss :: [a] -> ListExp a -> ListExp a conss xs exp = foldr Cons exp xs fromList :: [a] -> ListExp a fromList xs = conss xs Nil -- eval the next element, return an expression defining the tail -- (if non-empty) evalOne :: ListExp a -> Maybe (a, ListExp a) evalOne Nil = Nothing evalOne (Cons h t) = Just (h, t) evalOne e@(Cycle exp) = case eval exp of [] -> Nothing (x:xs) -> Just (x, conss xs e) eval :: ListExp a -> [a] eval = unfoldr evalOne -- semantic equality evalEq :: (Eq a) => ListExp a -> ListExp a -> Bool evalEq = (==) `on` eval -- semantic equality, but check syntactic equality first. -- In every next recursion step, assume the arguments of the current recursion -- step to be equal. We can do that safely because two lists are equal iff -- they cannot be proven different. smartEq :: (Eq a) => ListExp a -> ListExp a -> Bool smartEq a b = smartEq' a b [] smartEq' :: (Eq a) => ListExp a -> ListExp a -> [(ListExp a, ListExp a)] -> Bool smartEq' a b eqPairs = if a == b || (a, b) `elem` eqPairs then True else case (evalOne a, evalOne b) of (Just _, Nothing) -> False (Nothing, Just _) -> False (Nothing, Nothing) -> True (Just (h1, t1), Just (h2, t2)) -> h1 == h2 && smartEq' t1 t2 ((a, b):eqPairs) Examples: *Main> smartEq (Cycle $ fromList [1]) (Cycle $ fromList [1,1]) True *Main> smartEq (Cons 1 $ Cycle $ fromList [1]) (Cycle $ fromList [1]) True *Main> smartEq (Cons 2 $ Cycle $ fromList [1]) (Cycle $ fromList [1]) False Any examples for hangups of 'smartEq' are greatly appreciated, I couldn't produce any so far. -- Steffen

On 07/21/2011 02:15 PM, Alexey Khudyakov wrote:

...

Any examples for hangups of 'smartEq' are greatly appreciated, I couldn't produce any so far.

Following sequences will hang smartEq. They are both infinite and aperiodic. smartEq (fromList primes) (fromList primes) smartEq (fromList pidigits) (fromList pidigits)

Err, yeah, of course. I would expect expressions of type ListExp to be finite as they represent written text. fromList therefore expects to receive only finite lists. Defining 'primes' using my method seems to be a bit of a challenge due to its recursive definition.

On Wed, Jul 20, 2011 at 13:22, Chris Smith wrote:

On Tue, 2011-07-19 at 23:33 -0700, Carl Howells wrote:

...

False positives and false negatives are both possible, depending on GC timing. Don't use it, unless you know why it can result in both false positives and false negatives, and you know why neither of those are bad for your use case.

Can you clarify what you mean by false positives? Do you just mean it may return true but then later behave as if there's no sharing? Or do you mean it may return true and then later the two expressions may be observably different? If the latter, then it seems this would be a

I think it's more correct to say that the compiler is free to do things that would lead to false positives if it knows that it's safe to do so (and purity means it can find more of those cases, and more of them *will* be safe) — but there is no way for it to crowbar pointer equality tests in that case. -- brandon s allbery allbery.b@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms

On Wed, Jul 20, 2011 at 10:40 AM, Chris Smith wrote:

I have looked up crowbar in a number of dictionaries of slang and informal usage... and still have no idea what you just said. Can you reword it?

Crowbars offer 'leverage'.

The point, I think, is that if pointer equality testing really does what it says, then there shouldn't *be* any correct implementation in which false positives are possible. It seems the claim is that the garbage collector might be moving things around, have just by chance happened to place the second value in the spot formerly occupied by the first, and have not updated the first pointer yet. But if that's the case, and it's executing arbitrary user code that may refer to that memory, then the garbage collector contains race conditions!

You assume that the GC uses the same primitive as the developer, and is inherently subject to its own race conditions. But Bertram has said that false positives are not possible. I can only assume that the pointer comparison is atomic with respect to the GC.

have not updated the first pointer yet.  But if that's the case, and it's executing arbitrary user code that may refer to that memory, then the garbage collector contains race conditions!

Not necessarily, if the garbage collection and the move happened between taking the pointers of the two sides of f1 == f2, it would update all the references to f1, and the pointer value you just got would be wrong. Sure it would be unlucky, but there's nothing worse than a bug that happens once in a billion times. Niklas

On Wed, Jul 20, 2011 at 23:53, Richard O'Keefe wrote:

On 21/07/2011, at 9:08 AM, Paul Johnson wrote:

...

I would have thought that the compiler, as a matter of optimisation, could insert a check to see if (==) is comparing an object with itself. The only way I can see this breaking is with perverse instances of Eq that would return False for "f == f".

Presumably inside the body of f, x and x would be identical pointers, but the only right answer is False, not True.

If you think this is a bit far fetched, consider the IEEE definition of equality for floating-point numbers:

let x = 0.0/0.0 in x == x

The answer is False, so the optimisation breaks down even with a system-defined type.

Also, NaNs are never equal to each other. Also consider SQL's NULL (relevant if you use Takusen, I suspect). -- brandon s allbery allbery.b@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms