Changes between Version 8 and Version 9 of Commentary/Compiler/StrictnessAnalysis/KirstenNotes

Oct 26, 2006 3:05:16 PM (11 years ago)



  • Commentary/Compiler/StrictnessAnalysis/KirstenNotes

    v8 v9  
    1 = ~~Linearity~~ Patent nonsense =
    3 Instead of:
    4 {{{
    5 type DmdEnv = VarEnv Demand
    6 }}}
    7 we want:
    8 {{{
    9 type DmdEnv = Env CoreExpr Demand
    10 }}}
    12 We keep track of demands on partial applications.
    14 After calling dmd_anal on the body of a let, which results in demand type {{{dmd_ty}}} with demand env {{{dmd_env}}}, we do the following for each let-bound variable {{{f}}}:
    15  1. Iterate through all the keys in {{{dmd_env}}}, finding all applications of {{{f}}} to ''n'' arguments.
    16  1. For each ''i'' from 1 through ''n'' (where ''n'' is {{{f}}}'s arity), if each of the applications of {{{f}}} to ''i'' arguments has usage demand {{{OneOrZero}}}, then it's safe to mark the corresponding lambda-expression as a one-shot lambda.
    18 This might work, but is kind of kludgy.
    20 This may be ''way'' too unnecessarily complicated. Can't we just get the same information from the demand on f in the free-var environment of the let body as it is, without changing the environment?
    22 suppose the demand on f is
    23 {{{
    24 S1K(S1K(LMX))
    25 }}}
    26 if f =
    27 {{{
    28 (\ x. (\ y. ...))
    29 }}}
    30 then we can mark the outer two lambdas as being one-shot. Right?
    32 Not exactly. Suppose:
    33 {{{
    34 let f = \ x. \ y. ... in
    35   ...(f 1 2)...(f 3 4)...
    36 }}}
    37 f will have demand on it:
    38 {{{
    39 SMK(SMK(LMX))
    40 }}}
    41 because it's called more than once. We really want the demand to reflect that (f 1) is called only once and (f 3) is called only once, but it doesn't. So it doesn't seem like we can figure out what we need to know just by looking at the demand on f.
    431= Linearity =
    44 The real solution is to distinguish call demands from product demands. Consider again:
     2The solution is to distinguish call demands from product demands. Consider again:
    464let f = \ x. \ y. ... in
    5715The solution is to treat call demands and product demands differently, and to define the {{{both}}} function for call demands to have the same behavior as {{{lub}}}. Then in the first example, {{{f}}} has demand {{{SM(S1(T))}}} placed on it, and in the second, {{{SM(T)}}}. This is what we want; now, if {{{f}}} has demand {{{D(D(T)}}} placed on it, that implies {{{f}}} is always called with two arguments.
     17Why does this make sense? Consider what it means if we see an example like:
     19let baz = lazyF p in
     20  case p of
     21    (a,b) -> strictF a b
     23(where {{{lazyF}}} is lazy in {{{p}}}, and {{{strictF}}} is strict in {{{a}}} and {{{b}}}). {{{p}}} is used both with demand {{{L}}} (in the call to {{{lazyF}}} and with demand {{{S(SS)}}} (in the call to {{{strictF}}}). This means it's perfectly same to strictly evaluate {{{p}}}, so when we both together the two demands, we should get {{{S(SS)}}}. On the other hand, if a function is ''called'' once with one argument and once with two, we don't want to treat it as a function that's always called with two arguments; we're only interested in functions that are ''always'' called with ''n'' arguments for a given ''n''. Hence, both should behave the same way as lub for call demands.