Abstract

Developing efficient and reliable software is a difficult task. Increasingly larger and dynamic data sets and parallel hardware further add to the complexity by making it more challenging to achieve efficiency and performance. I present practical and powerful abstractions for taming software complexity in two large domains: 1)dynamic software that interacts with dynamically changing data, and 2)parallel software that utilizes multiple processing units or cores. Together with the algorithmic models and programming-languages that embody them, these abstractions enable designing and developing efficient, reliable software by using high-level reasoning principles and programming techniques. As evidence of their effectiveness, I consider a broad range benchmarks involving lists, arrays, matrices, and trees, as well as sophisticated applications in geometry, machine-learning, and large-scale cloud computing. On the theoretical side, I show asymptotically significant improvements in efficiency and present solutions to several major open problems. On the practical side, I present programming languages, compilers, and related software systems that deliver massive speedups with little or no programmer effort.