Stable Names in Haskell

Stable names in GHC “are a way of performing fast (O(1)), not-quite-exact comparison between objects.”  Andy Gill showed how to use them to extract the explicit graph from writing recursive functions in his Data.Reify package (and associated paper).  It’s a great idea and very practical for embedded domain-specific languages—we’ve used the idea in Copilot to recover sharing.

However, consider this example, with three tests executed in GHCI.

For a function with type constraints, stable names fails to “realize” that we are pointing to the same object. As a couple of my colleagues pointed out, the cause is the dictionary being passed around causing new closures to be created. Simon Marlow noted that if you compile with -O, the explicit dictionaries get optimized away.

Here are the solutions I have to “fixing” the problem, in the context of a DSL:

  • Tell your users that recursive expressions must be monomorphic—only “pure functions” over the expressions of your DSL can be polymorphic.
  • Implement a check in your reifier to see how many stable names have been created—if some upper-bound is violated, then the user has created an infinite expression, the expression is extremely large (in which case the user should try to use some sharing mechanism, such as let-expressions inside the language), or we’ve hit a stable-names issue.
  • Ensure your DSL programs are always compiled.
  • Of course, you can always take another approach, like Template Haskell or not using recursion at the Haskell level; also check out Andy Gill’s paper for other solutions to the observable sharing problem.

I don’t see how to use (deep)seq to fix the problem, at least as it’s presented in the example above, but I’d be keen to know if there are other solutions.

4 Responses to “Stable Names in Haskell”

  1. Heinrich Apfelmus Says:

    The behavior of GHC is arguably correct because a polymorphic expression is actually a function from * (i.e. types) to Expr a and there is no reason to assume that the values returned are equal for different type arguments.

  2. Levent Erkok Says:

    Can you fix the example you posted? The “analyzeExpr” function seems botched; what’s sn in there?

    I doubt that you can recover sharing of polymorphic things due to what Apfelmus says above, but a solution might be possible with some engineering compromise. If you can fix your “analyzeExpr”, I’d like to give it a try.

  3. Levent Erkok Says:

    Indeed, you are at GHC’s mercy when it comes to dictionaries. You’d expect it to recognize that the same dictionary is being passed but looks like it doesn’t, at least not in this case. As I was playing around, I found that the following diverges as well:

    expr2 :: Typed a => Expr a
    expr2 = x
    where x :: Typed a => Expr a
    x = Op x

    i.e., if you add a signature for the x in expr2; which I find quite unintuitive. Oh, ces’t la vie..

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: