Sharing of Computations

Abstract

The main purpose of the thesis is to develop a model enabling one to reason about various techniques for program optimization, in particular wrt.\ speedup and correctness. Moreover, several methods to increase the amount of sharing are discussed, and a new one (to be termed ''ultimate sharing'') is treated in detail.

Concerning speedup, a main point is to factor out the reasons why a program transformation may yield more than a constant speedup.

Concerning correctness, the interesting part is preservation of termination properties. This issue is mainly addressed for a logic language, where previous results from the literature are generalized -- but also for a functional language some (more limited) results are presented.