language: en

[Survey Paper]

Update-in-place Analysis for Sets

Chung Yung
Computer Science Department Courant Institute of Mathematical Sciences New York University
yung@cs.nyu.edu December 15, 1997

Abstract This survey paper describes the current approaches on the update-in-place analysis for sets. Pure functional languages do not allow mutations, destructive updates, or selective updates so that straightforward implementations of functional language compilers may induce large amounts of copying to preserve program semantics. The unnecessary copying of data can increase both the execution time and the memory requirements of an application. Introducing sets to functional languages as a primitive data constructor posts a new problem of update-in-place analysis in functional languages. Moreover, most of the compiler optimization techniques depend on the side-effects and the update-in-place analysis serves as the premise of applying such optimization techniques. Among other compiler optimization techniques, finite differencing captures common yet distinctive program constructions of costly repeated calculations and transforms them into more efficient incremental program constructions. This dissertation is an attempt to explore the update-in-place analysis for sets in functional languages in order to apply finite differencing to compiling pure functional languages. In this survey paper, we will describe the approaches of update-in-place analysis and the finite differencing techniques.

1 Motivation and Introduction