Changes between Version 9 and Version 10 of RelaxedDependencyAnalysis


Ignore:
Timestamp:
Jul 9, 2009 10:19:03 PM (5 years ago)
Author:
ross@…
Comment:

include current text

Legend:

Unmodified
Added
Removed
Modified
  • RelaxedDependencyAnalysis

    v9 v10  
    5252== Report Delta == 
    5353 
    54 Replace [http://haskell.org/onlinereport/decls.html#sect4.5.1 section 4.5.1] with: 
     54Replace the body of [http://haskell.org/onlinereport/decls.html#sect4.5.1 section 4.5.1] '''Dependency analysis''' 
     55 
     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. Two variables bound by value declarations are in the same ''declaration group'' if either 
     57 
     58   1) they are bound by the same pattern binding, or 
     59 
     60   2) their bindings are mutually recursive (perhaps via some other declarations that are also part of the group).  
     61 
     62  Application of the following rules causes each {{{let}}} or {{{where}}} construct (including the {{{where}}} defining the top level bindings in a module) to bind only the variables of a single declaration group, thus capturing the required dependency analysis: (A similar transformation is described in Peyton Jones' book [10].) 
     63 
     64   1) The order of declarations in where/let constructs is irrelevant. 
     65 
     66   2) {{{let}}} {''d,,1,,''; ''d,,2,,''} {{{in}}} ''e'' = {{{let}}} {''d,,1,,''} {{{in}}} (let {''d,,2,,''} {{{in}}} ''e'') 
     67      (when no identifier bound in ''d,,2,,'' appears free in ''d,,1,,'')  
     68 
     69with: 
    5570 
    5671  In general the static semantics are given by the normal Hindley-Milner inference rules.  A dependency analysis transformation is first performed to increase polymorphism. 
     
    6479    3) ''x'' depends on a variable ''z'' that depends on ''y''.  
    6580 
    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. 
     81  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. 
    6782 
    6883Notes: 
    6984 * 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. 
     85 * the dependency analysis transformation formerly listed in this section is no longer always possible. 
    7186 
    7287== Other issues == 
     
    7489 * The Report sometimes speaks of "value bindings", "value declarations" or "function and pattern bindings".  It might be best to standardize on "value bindings". 
    7590 * Similarly "declaration groups" might more precisely be called "binding groups", since other kinds of declaration are not involved. 
    76  * The first paragraph of [http://haskell.org/onlinereport/decls.html#sect4.5.2 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. 
     91 
     92The 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.