unique identity and name shadowing during type inference
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
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
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
participants (2)
-
Geoffrey Irving -
Lennart Augustsson