A Randomized Implementation of Multiple Functional Arrays

The array update problem in the implementation of a purely functional language is the following: once an array is updated, both the original array and the newly updated one must be preserved to maintain referential transparency. Previous approaches have mainly based on the detection or enforcement of single--threaded accesses to an aggregate, by means of compiler--time analyses or language restrictions. These approaches cannot deal with aggregates which are updated in a multi--threaded manner. Baker's shallow binding scheme can be used to implement multi--threaded functional arrays. His scheme, however, can be very expensive if there are repeated alternations between long binding paths. We design a scheme that fragments binding paths randomly. The randomization scheme is on--line, simple to implement, and its expected performance comparable to that of the optimal off--line solutions. All this is achieved without using compiler--time analyses, and without restricting the languages. The ..