[Haskell-cafe] unique identity and name shadowing during type inference

[Lennart Augustsson]

Use 1.  You'll probably need a monad in the type checker soon or later
anyway, e.g., for handling errors.

On Sat, Jun 20, 2009 at 7:57 PM, Geoffrey Irving<irving at naml.us> wrote:
> Hello,
>
> I am designing a type inference algorithm for a language with
> arbitrary function overloading.  For various reasons (beyond the scope
> of this email), it's impossible to know the full type of an overloaded
> function, so each function is assigned a unique primitive type and the
> inference algorithm gradually learns more information about the
> primitive.  For example, if we declare an identity function
>
>    f x = x
>
> the algorithm will create a primitive type F, and record f :: F.  If
> we use the function a few times,
>
>    f 1
>    f "blah"
>
> the algorithm will infer
>
>    F Int = Int
>    F String = String
>
> My question is: what's the best way to represent these unique
> primitive types in Haskell?  A new type primitive needs to be created
> whenever we process a function declaration.  Nested function
> declarations produce a different primitive each time the parent is
> invoked with different argument types.  These separate primitives can
> escape if local functions are returned, so the inference algorithm
> must be able to keep them separate and learn more about them after
> their parent function is forgotten.
>
> Here are a few ways I know of:
>
> 1. Thread a uniqueness generator monad through the whole algorithm.
> I'd prefer to avoid this extra plumbing if possible.
> 2. Label primitives with the full context of how they were created.
> If function f declares a nested function g, and f is called with Int
> and Char, the primitives for g would be labeled with "f Int" and "f
> Char" to keep them separate.  This is similar to lambda lifting.
> 3. Scary hacks involving makeStableName and unsafePerformIO.  Some
> sort of context would have to be thrown around here to make sure GHC
> doesn't merge the different makeStableName calls.
>
> Unfortunately, method (2) is complicated by the fact that variable
> names are not unique even in the internal representation (I'm using
> the trick from [1]), so I'm not sure what the minimal unique "context"
> would be.
>
> Does anyone know other methods outside of (1), (2), or (3), or clean
> ways of structuring (2) or (3)?
>
> Thanks!
> Geoffrey
>
> [1]: http://www.haskell.org/~simonmar/bib/ghcinliner02_abstract.html
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>