[Haskell-cafe] Proposal: TypeDirectedNameResolution

[Ben Lippmeier]

On 28/07/2009, at 6:41 AM, John Dorsey wrote:
> I'm assuming that name resolution is currently independent of type
> inference, and will happen before type inference.  With the proposal  
> this is
> no longer true, and in general some partial type inference will have  
> to
> happen before conflicting unqualified names are resolved.
>
> My worry is that the proposal will require a compliant compiler to
> interweave name resolution and type inference iteratively.
>
> To my untrained eye it looks complicated and invasive, even without  
> the
> mutually recursive case.  Can anyone shed light on whether this  
> would be a
> problem for, say, GHC?


My experimental compiler DDC [1] implements TDNR almost exactly as  
given on the Haskell' wiki.

Yes, you have to interweave name resolution with type inference,  
because there is no way to compute the binding dependency graph/call  
graph before type inference proper. This is discussed in section 3.5  
of my thesis [2] (which is currently under examination). For DDC I  
used a constraint based inference algorithm to compute the binding  
dependency graph "on the fly", but I don't know how easy it would be  
to retrofit this method into GHC.

Cheers,
Ben.


[1] http://www.haskell.org/haskellwiki/DDC
[2] http://cs.anu.edu.au/people/Ben.Lippmeier/project/thesis/thesis-lippmeier-sub.pdf