Changes between Version 9 and Version 10 of RelaxedDependencyAnalysis

Timestamp:

07/09/09 15:19:03 (4 years ago)

Author:

ross@…

Comment:

include current text

RelaxedDependencyAnalysis

@@ -52 +52 @@
 == Report Delta ==
 
-Replace [http://haskell.org/onlinereport/decls.html#sect4.5.1 section 4.5.1] with:
+Replace the body of [http://haskell.org/onlinereport/decls.html#sect4.5.1 section 4.5.1] '''Dependency analysis'''
+
+  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
+
+   1) they are bound by the same pattern binding, or
+
+   2) their bindings are mutually recursive (perhaps via some other declarations that are also part of the group). 
+
+  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].)
+
+   1) The order of declarations in where/let constructs is irrelevant.
+
+   2) {{{let}}} {''d,,1,,''; ''d,,2,,''} {{{in}}} ''e'' = {{{let}}} {''d,,1,,''} {{{in}}} (let {''d,,2,,''} {{{in}}} ''e'')
+      (when no identifier bound in ''d,,2,,'' appears free in ''d,,1,,'') 
+
+with:
 
   In general the static semantics are given by the normal Hindley-Milner inference rules.  A dependency analysis transformation is first performed to increase polymorphism.
@@ -64 +79 @@
     3) ''x'' depends on a variable ''z'' that depends on ''y''. 
 
-  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.
+  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.
 
 Notes:
  * 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.
- * the transformations formerly listed in this section are no longer always possible.
+ * the dependency analysis transformation formerly listed in this section is no longer always possible.
 
 == Other issues ==
@@ -74 +89 @@
  * The Report sometimes speaks of "value bindings", "value declarations" or "function and pattern bindings".  It might be best to standardize on "value bindings".
  * Similarly "declaration groups" might more precisely be called "binding groups", since other kinds of declaration are not involved.
- * The first paragraph of [http://haskell.org/onlinereport/decls.html#sect4.5.2 section 4.5.2] isn't quite right:
-    * 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.
-    * It does not seem to deal with functions, non-trivial patterns or recursion.
+
+The first paragraph of [http://haskell.org/onlinereport/decls.html#sect4.5.2 section 4.5.2] isn't quite right:
+
+  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.
+
+ * 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.
+ * It does not seem to deal with functions, non-trivial patterns or recursion.