Simonpj/Talk:OutsideIn

Modular type inference with local assumptions: OutsideIn(X)

This epic 73-page paper (JFP style) brings together our work on type inference for type functions, GADTS, and the like, in a single uniform framework.

• Modular type inference with local assumptions: OutsideIn(X): PDF
• Related papers (constraints)
• Related papers (GADTs)
• Related papers (type families)

Abstract. Advanced type system features, such as GADTs, type classes, and type families have have proven to be invaluable language extensions for ensuring data invariants and program correctness among others. Unfortunately, they pose a tough problem for type inference, because they introduce local type assumptions.

In this article we present a novel constraint-based type inference approach for local type assumptions. Our system, called OutsideIn(X), is parameterised over the particular underlying constraint domain X, in the same way as HM(X). This stratification allows us to use a common metatheory and inference algorithm.

Going beyond the general framework, we also give a particular constraint solver for X = type classes + GADTs + type families, a non-trivial challenge in its own right.

Please help us!. This Wiki page is a discussion page for the paper. If you are kind enough to read this paper, please help us by jotting down any thoughts it triggers off. Things to think about:

• It is a long paper; where did you get lost?
• What is unclear?
• What is omitted that you'd like to see?
• Is there anything we could leave out?

You can identify your entries by preceding them with four tildes. Doing so adds your name, and the date. Thus:

Simonpj 08:42, 19 April 2007 (UTC) Note from Simon

If you say who you are in this way, we'll be able to acknowledge your help in a revised version of the paper.

Simon Meier 15 May 2010:

• Typo on Page 7: "having type Bool" should probably be "having type Int".
• Typo on Page 18: "constraint siplifier"
• Typo on Page 28: "topl-level"
• Typo on Page 31: "But hang on! NoGen means ... in the beginning of Section 4.2 <text-missing-here>"
• Typo on Page 53: Formula below "Simplification rules" is missing a space.
• Typo on Page 59: "makes sens"

Batterseapower 14:24, 14 May 2010 (UTC) You say that local definitions such as "combine" and "swap" could harmlessly be defined at top level. However, there is a cost to doing so in that it pollutes the top-level namespace. Adding a facility for making definitions that are at the top level for the purposes of type checking but not for name resolution would fix this, at the cost of some ugliness.

Rgreayer 16:04, 14 May 2010 (UTC)

• Revisiting Typo on Page 7: "This means that any expression of type F [Bool] can be considered an expression of type F Bool". But would that not mean the axiom is: F [a] ~ F a, rather than: F [a] ~ a?
• Typo, Page 8 (middle): "An similar issue..."

Saizan 14:23, 16 May 2010 (UTC)

• Figure 2: VarCon uses \nu in the conclusion and x in the premises, it seems they should both be \nu considering the textual description below, but then the definition of "Type environments" in Figure 1 also needs to have \nu rather than x.
• typos in Section 9.1:
  • "f = case (Ex 3) of Ex -> False" should be "f = case (Ex 3) of Ex _ -> False".
  • "f :: Bool -> Bool" should be "f :: Bool".
• Have you considered adding support for partial type signatures?

niall 15:07, 17 May 2010 (UTC)

• Footnote on page 65 refers to an incorrect link (should perhaps be http://research.microsoft.com/en-us/um/people/simonpj/papers/gadt/ ) although the journal paper does not seem linked from there. The Appendix with the algorithm is perhaps meant to refer to the appendix of "Simple unification-based type inference for GADTs"?

Byorgey 09:10, 21 June 2010 (UTC)

• p.8: should be a colon after "Here is an example"
• p.10: end of section 2.2: "definition of g" should be "definition of test"
• p.15: Indentation of "The judgement Q ; Gamma |- prog..." is too small
• p.16: Grammar of Definition 3.1 needs fixing, for example, "An axiom scheme Q is consistent iff whenever ... *we have* (or, *it is also the case that*, etc.)
• p.17: add comma after however in "For now, however algorithmic constraints..."
• p.19: in Fig 7, should the Empty rule have a premise ftv(Q,Gamma) = empty?
• p.21: I find it very confusing to use the notation t1 <= t2 for "t1 is more general than t2"; we are using a "less than" symbol for a concept involving the word "more"...