Back to search

University of Washington

Optimizing the Automated Programming Stack

Abstract

dc:description.abstract

The scale and pervasiveness of modern software poses a challenge for programmers: software reliability is more important than ever, but the complexity of computer systems continues to grow. Automated programming tools are a powerful way for programmers to tackle this challenge: verifiers that check software correctness, and synthesizers that generate new correct-by-construction programs. These tools are most effective when they apply domain-specific optimizations, but doing so today requires considerable formal methods expertise. This dissertation shows that new abstractions and techniques can empower programmers to build specialized automated programming tools that ensure software reliability. We first demonstrate the importance and effectiveness of automated tools in the context of memory consistency models, which define the behavior of multiprocessor CPUs and whose subtleties often elude even experts. MemSynth is a tool that automatically synthesizes formal descriptions of memory consistency models from examples of CPU behavior, and has found ambiguities and underspecifications in two major computer architectures. We then introduce two new programmer techniques for developing automated programming tools. Metasketches are a new abstraction for building program synthesis tools that integrate search strategy into the problem definition, allowing a metasketch solver to solve synthesis problems that other tools cannot. Symbolic profiling is a technique for systematically identifying and resolving scalability bottlenecks in automated programming tools. Symbolic profiling generalizes across different symbolic evaluation engines and has been used to improve the performance of state-of-the-art automated tools by orders of magnitude. Together, these three contributions demonstrate the value of automated programming tools for building reliable software, and offer guidance on how to build such tools efficiently for new problem domains.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Bornholt, James
Advisors dc:contributor.advisor
  • Torlak, Emina
  • Grossman, Dan

Subjects

dc:subject × 2

Rights

dc:rights
Statement dc:rights
  • CC BY
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1773/44772

Chain of custody

source
Harvested from
University of Washington
Base URL
digital.lib.washington.edu/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Bornholt, James. Optimizing the Automated Programming Stack. 2019. http://hdl.handle.net/1773/44772