Changes between Version 8 and Version 9 of RelaxedDependencyAnalysis

Jul 9, 2009 2:50:46 PM (5 years ago)

report delta and other issues


  • RelaxedDependencyAnalysis

    v8 v9  
    1818== Summary == 
     20Haskell 98 specifies that type inference be performed in dependency order to increase polymorphism.  However most Haskell implementations use a more liberal rule (proposed by Mark Jones). 
     22== Description == 
    2024In Haskell 98, a group of bindings is sorted into strongly-connected components, and then type-checked in dependency order ([ H98 s4.5.1]). As each dependency group is type-checked, any binders of the group that have an explicit type signature are put in the type environment with the specified polymorphic type, and all others are monomorphic until the group is generalized ([ H98 s4.5.2]). 
    4145Dependency groups are smaller, and more programs type-check. 
    43 == Description == 
    45 Modify the definition of dependency group in the above section to 
    47   Two variables bound by value declarations are in the same declaration group if either 
    49   1) they are bound by the same pattern binding, or 
    51   2) their bindings are mutually recursive (perhaps via some other declarations that are also part of the group), ''ignoring uses of variables that have an explicit type signature''  
    53 The semi-formal rules in the rest of the section would have to go: it would no longer be possible to make binding groups explicit with a source-to-source transformation. 
    5547== References == 
    6052== Report Delta == 
     54Replace [ section 4.5.1] with: 
     56  In general the static semantics are given by the normal Hindley-Milner inference rules.  A dependency analysis transformation is first performed to increase polymorphism. 
     58  A variable ''x'' ''depends'' on a variable ''y'' (bound in the same list of declarations) if 
     60    1) they are bound by the same pattern binding, or 
     62    2) ''y'' has no type signature and the binding defining ''x'' contains an occurrence of ''y'', or 
     64    3) ''x'' depends on a variable ''z'' that depends on ''y''.  
     66  A ''declaration group'' is a minimal set of bindings of mutually dependent variables.  Hindley-Milner type inference is applied to each declaration group in dependency order. 
     69 * also tightens up the original wording, which didn't mention that the declarations had to be in the same list and also defined ''declaration group'' but not dependency. 
     70 * the transformations formerly listed in this section are no longer always possible. 
     72== Other issues == 
     74 * The Report sometimes speaks of "value bindings", "value declarations" or "function and pattern bindings".  It might be best to standardize on "value bindings". 
     75 * Similarly "declaration groups" might more precisely be called "binding groups", since other kinds of declaration are not involved. 
     76 * The first paragraph of [ section 4.5.2] isn't quite right: 
     77    * It deals with {{{let}}}'s consisting of a single binding, instead of declaration groups.  Note that we can no longer assume that a {{{let}}} has a single declaration group. 
     78    * It does not seem to deal with functions, non-trivial patterns or recursion.