Opened 3 years ago

Closed 3 years ago

#7036 closed feature request (wontfix)

StableNames in presence of class constraints / monadic functions

Reported by: ifigueroap Owned by:
Priority: normal Milestone:
Component: GHC API Version: 7.4.2
Keywords: Cc: ifigueroap@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Revisions:

Description

Hi,

I'm trying to implement a notion of function equality using the StableNames API. So far it has worked relatively well, but I'm facing the problem of getting negatives when functions have class constraints, like (Monad m).

I implemented de eq function as follows:

import System.Mem.StableName
import Control.Monad.State

eq :: a -> b -> IO Bool
eq a b = do
             pa <- makeStableName a
             pb <- makeStableName b
             return (hashStableName pa == hashStableName pb)

And for testing the following function and main program:

successor :: (Num a, Monad m) => a -> m a
successor n = return (n+1)

main :: IO () 
main = do 
       b1 <- eq (successor :: Int -> Maybe Int) (successor :: Int -> Maybe Int)       
       b2 <- eq (successor :: Int -> State Int Int) (successor :: Int -> State Int Int)
       print (show b1 ++ " " ++ show b2)

Running the program in ghci, gives "False False". Somewhere on the internet there is a tip to use a compiled module with optimizations, using ghc --make -O File.hs. Doing this, I get "True True".

However, with a slight modification of main the result is "True False":

main :: IO () 
main = do        
       b2 <- eq (successor :: Int -> State Int Int) (successor :: Int -> State Int Int)
       b1 <- eq (successor :: Int -> Maybe Int) (successor :: Int -> Maybe Int)       
       print (show b1 ++ " " ++ show b2)

After reading a lots of forums and mail lists, it seems the problem is because of the dictionary-passing style: somehow StableNames see that the dictionaries are different and then returns false [1]. Or maybe there are some closures created in background, that do not map to the same memory locations.

I know that doing a let/where binding, this particular example works, e.g.:

main :: IO ()
main = do
       b2 <- eq f2 f2
       b1 <- eq f1 f1
       print (show b1 ++ " " ++ show b2)
   where f1 = (successor :: Int -> Maybe Int)
             f2 = (successor :: Int -> State Int Int)

But in general it is cumbersome to do this way, and it is hard to anticipate whether the comparison is going to be "ok" or not. Another way I've found to solve the problem is to put very explicit type annotations, but this is problematic in monadic code that is intended to be generic.

I wonder if it is possible to implement some compiler flag to change the behavior of StableNames (or maybe a differente API?) so it returns true when the only difference is the dictionary?

In Scheme/Racket this notion of function equality is done tagging every function with a unique value, upon closure creation. Using the macro system this is done transparently for the programmer. I guess I could emulate this using a wrapper type for functions, and using GHC.Unique; but I want to see if there are other options. Maybe a compiler plugin can annotate functions in the same way? It seems with Template Haskell is not possible to intercept function definition.

Also, the example works correctly (returning "True True" in both cases) when the definition of eq is:

eq :: a -> b -> IO Bool
eq a b = do
             unsafeCoerce b a
             pa <- makeStableName a
             pb <- makeStableName b
             return (hashStableName pa == hashStableName pb)

I guess it is because the dictionaries are somehow unified. But using this eq in general leads to (predictable) Bus errors.

Thanks!

[1] http://www.haskell.org/pipermail/glasgow-haskell-users/2011-November/021272.html

Change History (5)

comment:1 Changed 3 years ago by ifigueroap

  • Cc ifigueroap@… added

comment:2 follow-up: Changed 3 years ago by simonpj

  • difficulty set to Unknown

You are skating on incredibly thin ice. Haskell in general, and GHC in particular, makes no claims about pointer equality. Any program that relies on it is likely to be fragile. For example, you probably expect f to be pointer-equal to f. And perhaps to head [f]? What about a partial application (f 1) and (f 1)? What about (f 1) and f (2-1)?

Rather than bend the language or compiler out of shape, I'd be inclined to look at the original goal, and see if it can be done some other way.

comment:3 in reply to: ↑ 2 ; follow-up: Changed 3 years ago by ifigueroap

Replying to simonpj:

You are skating on incredibly thin ice. Haskell in general, and GHC in particular, makes no claims about pointer equality. Any program that relies on it is likely to be fragile.

Indeed, I guess that StableNames is not the right API for my purposes, but I see it as a good starting point

For example, you probably expect f to be pointer-equal to f. And perhaps to head [f]? What about a partial application (f 1) and (f 1)? What about (f 1) and f (2-1)?

You are correct in that I would expect those cases to be equal. However my goal is not really "pointer" equality, but an approximation of function equality.

Rather than bend the language or compiler out of shape, I'd be inclined to look at the original goal, and see if it can be done some other way.

One "reasonable" approach (which would be more than good enough for my purposes) is used in AspectScheme [1] where they 'tag' every closure with a unique identifier.Their notion of equality is [1]: "Two function closures are equal if they have the same textual source location and their environments are identical." In the implementation they use the macro system to intercept the "lambda" symbol and inject the tag.

I don't know if it is possible to do that in Haskell in a way that is transparent to the user. I think I could use a wrapper type like

data MyFun a b = MyFun (a -> b)

but doing so I lose the language support for defining functions. In the case of partial application, the new tag could be deterministically determined from the tag of the applied function, maybe including a 'seed' along with the function tag.

However I agree maybe it is not possible to do as I expect because it would break all compiler optimizations -- and I don't really know about the internals of GHC.

So I guess my request could be rephrased as "is there any way to tag functions definitions and compare those tags at runtime?" but retaining normal Haskell syntax??

Thanks!

[1] http://www.cs.brown.edu/~sk/Publications/Papers/Published/dtk-sem-scope-aspects-ho-lang/paper.pdf

comment:4 in reply to: ↑ 3 Changed 3 years ago by ifigueroap

Replying to ifigueroap:

Sorry I think one encoding could be something like

data MyFun a b = MyFun (a->b) Unique
mkMyFun f = MyFun f newUnique

and to apply functions

app :: MyFun (a -> b) -> a -> b
app (MyFun f _) a = f a

and comparison would be trivially

eq :: MyFun a b -> My Fun a b -> Bool
eq (MyFun _ id1) (MyFun _ id2) = id1 == id2

and by "losing language support" I mean for instance having to wrap every function, and having to use app instead of normal application everywhere; and in general being unable to reuse all the existing goodies for functions.

comment:5 Changed 3 years ago by simonmar

  • Resolution set to wontfix
  • Status changed from new to closed

I don't think there's anything concrete we can do here - as Simon says, trying to get predictable behaviour from StableNames beyond the simple cases (x == x) is a losing game. Even for the simple cases, HPC and GHCi break things by introducing extra wrappers internally.

Perhaps you can implement something analogous to AspectScheme using Template Haskell. However, that's quite speculative, so I don't think it's useful to have a feature request open. Please do create a feature request if you have a specific feature in mind that would help.

Note: See TracTickets for help on using tickets.