[Haskell-cafe] unique identity and name shadowing during type
lennart at augustsson.net
Sat Jun 20 16:40:10 EDT 2009
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:
> 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 ), 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)?
> : http://www.haskell.org/~simonmar/bib/ghcinliner02_abstract.html
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe