A UNIFORM TREATMENT OF ORDER OF EVALUATION AND AGGREGATE UPDATE

The article presents an algorithm for the destructive update optimizat ion in first-order lazy functional languages. The main component of th e method is a new static analysis of the order of evaluation of expres sions which, compared to other published work, has a much lower comple xity and is not restricted to pure lazy evaluation. The other componen t, which we call reduction to variables; is a method of detecting the variables which denote locations where the result of an expression mig ht be stored. Starting with the operational semantics of the language, we introduce some markers for the values in the basic domain. By choo sing appropriately the set of markers M and the method of propagating them during evaluation, we can extract some property of the evaluation in which an expression can participate by looking at the marker of it s value. We then define an equivalent denotational semantics and deriv e the above analyses, in a uniform way, by abstract interpretation ove r a subdomain of P(M(perpendicular-to)).