Changes between Version 10 and Version 11 of RelaxedDependencyAnalysis


Ignore:
Timestamp:
Jul 9, 2009 11:41:14 PM (6 years ago)
Author:
ross@…
Comment:

proposed revision of Generalization para

Legend:

Unmodified
Added
Removed
Modified
  • RelaxedDependencyAnalysis

    v10 v11  
    5252== Report Delta == 
    5353 
    54 Replace the body of [http://haskell.org/onlinereport/decls.html#sect4.5.1 section 4.5.1] '''Dependency analysis''' 
     54Replace the body of [http://haskell.org/onlinereport/decls.html#sect4.5.1 section 4.5.1] '''Dependency analysis''': 
    5555 
     56{{{ 
     57#!html 
     58<div style="background: #ffcccc"> 
     59}}} 
    5660  In general the static semantics are given by the normal Hindley-Milner inference rules. A ''dependency analysis transformation'' is first performed to increase polymorphism. Two variables bound by value declarations are in the same ''declaration group'' if either 
    5761 
     
    6670   2) {{{let}}} {''d,,1,,''; ''d,,2,,''} {{{in}}} ''e'' = {{{let}}} {''d,,1,,''} {{{in}}} (let {''d,,2,,''} {{{in}}} ''e'') 
    6771      (when no identifier bound in ''d,,2,,'' appears free in ''d,,1,,'')  
     72{{{ 
     73#!html 
     74</div> 
     75}}} 
    6876 
    6977with: 
    7078 
     79{{{ 
     80#!html 
     81<div style="background: #ccffcc"> 
     82}}} 
    7183  In general the static semantics are given by the normal Hindley-Milner inference rules.  A dependency analysis transformation is first performed to increase polymorphism. 
    7284 
     
    8092 
    8193  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.  The order of declarations in {{{where}}}/{{{let}}} constructs is irrelevant. 
     94{{{ 
     95#!html 
     96</div> 
     97}}} 
    8298 
    8399Notes: 
    84100 * 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. 
    85101 * the dependency analysis transformation formerly listed in this section is no longer always possible. 
     102Replace the first paragraph of [http://haskell.org/onlinereport/decls.html#sect4.5.2 section 4.5.2] '''Generalization''': 
     103 
     104{{{ 
     105#!html 
     106<div style="background: #ffcccc"> 
     107}}} 
     108  The Hindley-Milner type system assigns types to a {{{let}}}-expression in two stages. First, the right-hand side of the declaration is typed, giving a type with no universal quantification. Second, all type variables that occur in this type are universally quantified unless they are associated with bound variables in the type environment; this is called ''generalization''. Finally, the body of the {{{let}}}-expression is typed. 
     109{{{ 
     110#!html 
     111</div> 
     112}}} 
     113 
     114with 
     115 
     116{{{ 
     117#!html 
     118<div style="background: #ccffcc"> 
     119}}} 
     120  The Hindley-Milner type system assigns types to a {{{let}}}-expression in two stages: 
     121     1) The declaration groups are considered in dependency order.  For each group, a type with no universal quantification is inferred for each variable bound in the group.  Then, all type variables that occur in these types are universally quantified unless they are associated with bound variables in the type environment; this is called ''generalization''. 
     122 
     123     2) Finally, the body of the {{{let}}}-expression is typed. 
     124{{{ 
     125#!html 
     126</div> 
     127}}} 
     128 
     129Notes: 
     130 * The original 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. 
     131 * The original does not deal with functions, non-trivial patterns or recursion. 
    86132 
    87133== Other issues == 
     
    90136 * Similarly "declaration groups" might more precisely be called "binding groups", since other kinds of declaration are not involved. 
    91137 
    92 The first paragraph of [http://haskell.org/onlinereport/decls.html#sect4.5.2 section 4.5.2] isn't quite right: 
    93  
    94   The Hindley-Milner type system assigns types to a {{{let}}}-expression in two stages. First, the right-hand side of the declaration is typed, giving a type with no universal quantification. Second, all type variables that occur in this type are universally quantified unless they are associated with bound variables in the type environment; this is called ''generalization''. Finally, the body of the {{{let}}}-expression is typed. 
    95  
    96  * 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. 
    97  * It does not seem to deal with functions, non-trivial patterns or recursion.