Lazy Set-Sharing Analysis

Abstract. Sharing analysis is widely deployed in the optimisation, spe-cialisation and parallelisation of logic programs. Each abstract unifica-tion operation over the classic Jacobs and Langen domain involves the calculation of a closure operation that has exponential worst-case com-plexity. This paper explores a new tactic for improving performance: laziness. The idea is to compute partial sharing information eagerly and recover full sharing information lazily. The net result is an analysis that runs in a fraction of the time of the classic analysis and yet has compa-rable precision.