Siva Kamesh Somayyajula

Total Correctness Type Refinements for Communicating Processes Degree Type: Ph.D. in Computer Science
Advisor(s): Frank Pfenning
Graduated: May 2024

Abstract:

Process calculi are language-based formalisms for investigating software systems with concurrent and/or parallel behaviors. In particular, reasoning about the correctness of such systems can be carried out by proving theorems in a program logic tailored to said behaviors. In sequential functional programming, the celebrated Curry-Howard correspondence interprets logical propositions as types–sets of correct program states–so that a proof of a proposition can be identified as a well-typed and, therefore, correct program. With enough expressive power, type systems in this tradition can collapse the distinction between programming language and program logic.

Due to this singular advantage, much effort has been devoted to realizing this correspondence for process calculi. What remains elusive is a system with dependent types, analogous to logical quantification over process components, that accommodates rich schemes of terminating recursion. In fact, the tension between recursion and logical consistency has traditionally led to design shortcomings and complications in the sequential functional setting. Yet, typability in such a system would imply total correctness: a high-water mark of formal verification where interacting processes are guaranteed to terminate in a desirable state. Thus, many have advocated for establishing total correctness by a decomposition into partial correctness–correctness oblivious to termination–and termination on its own. Type refinement systems, which can encode such properties on top of an existing type system, satisfy the desideratum for orthogonality implied by this decomposition.

The primary contributions of this thesis are two type refinement systems such that typability of the same process in both establishes its total correctness: sized type refinements determine the termination of mixed inductive-coinductive processes, whereas dependent type refinements verify partial correctness–even in the presence of general recursion. The secondary contribution of this thesis is a design regime based on proof theory. Starting with a simply-typed asynchronous process calculus based on the intuitionistic semi-axiomatic sequent calculus, the design and metatheory of these type refinement systems begin with a novel variation of bidirectional typing to manage the structural presence of refinements, reaching for infinitary proof theory to integrate recursion. We demonstrate the utility of both type refinement systems by building up to an idealized model of verified asynchronous reactive programming.

Thesis Committee:
Frank Pfenning (Chair)
Robert Harper
Karl Crary
Brigitte Pientka (McGill University)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Keywords:
Process calculus, type refinements, type-based termination, dependent types, correctness, futures, proof theory