Changes between Version 8 and Version 9 of Commentary/Compiler/StrictnessAnalysis/KirstenNotes
 Timestamp:
 Oct 26, 2006 3:05:16 PM (10 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

Commentary/Compiler/StrictnessAnalysis/KirstenNotes
v8 v9 1 = ~~Linearity~~ Patent nonsense =2 3 Instead of:4 {{{5 type DmdEnv = VarEnv Demand6 }}}7 we want:8 {{{9 type DmdEnv = Env CoreExpr Demand10 }}}11 12 We keep track of demands on partial applications.13 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 letbound 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 lambdaexpression as a oneshot lambda.17 18 This might work, but is kind of kludgy.19 20 This may be ''way'' too unnecessarily complicated. Can't we just get the same information from the demand on f in the freevar environment of the let body as it is, without changing the environment?21 22 suppose the demand on f is23 {{{24 S1K(S1K(LMX))25 }}}26 if f =27 {{{28 (\ x. (\ y. ...))29 }}}30 then we can mark the outer two lambdas as being oneshot. Right?31 32 Not exactly. Suppose:33 {{{34 let f = \ x. \ y. ... in35 ...(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.42 43 1 = Linearity = 44 The realsolution is to distinguish call demands from product demands. Consider again:2 The solution is to distinguish call demands from product demands. Consider again: 45 3 {{{ 46 4 let f = \ x. \ y. ... in … … 56 14 57 15 The 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. 16 17 Why does this make sense? Consider what it means if we see an example like: 18 {{{ 19 let baz = lazyF p in 20 case p of 21 (a,b) > strictF a b 22 }}} 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.