Fri 17 Jun 2022 16:10 - 16:30 at Macaw - Refinement Types Chair(s): Sorav Bansal

Refinement types enable lightweight verification of functional programs. Algorithms for statically inferring refinement types typically work by reduction to solving systems of constraint Horn clauses extracted from typing derivations. An example is Liquid type inference, which solves the extracted constraints using predicate abstraction. However, the reduction to constraint solving in itself already signifies an abstraction of the program semantics that affects the precision of the overall static analysis. To better understand this issue, we study the type inference problem in its entirety through the lens of abstract interpretation. We propose a new refinement type system that is parametric with the choice of the abstract domain of type refinements as well as the degree to which it tracks context-sensitive control flow information. We then derive an accompanying parametric inference algorithm as an abstract interpretation of a novel data flow semantics of functional programs. We further show that the type system is sound and complete with respect to the constructed abstract semantics. Our theoretical development reveals the key abstraction steps inherent in refinement type inference algorithms. The trade-off between precision and efficiency of these abstraction steps is controlled by the parameters of the type system. Existing refinement type systems and their respective inference algorithms, such as Liquid types, are captured by concrete parameter instantiations. We have implemented our framework in a prototype tool and evaluated it for a range of new parameter instantiations (e.g., using octagons and polyhedra for expressing type refinements). The tool compares favorably against other existing tools. Our evaluation indicates that our approach can be used to systematically construct new refinement type inference algorithms that are both robust and precise

Fri 17 Jun

Displayed time zone: Pacific Time (US & Canada) change

15:30 - 16:50
Refinement TypesSIGPLAN Track at Macaw
Chair(s): Sorav Bansal IIT Delhi and CompilerAI Labs
15:30
20m
Talk
(OOPSLA 2020) Verifying Replicated Data Types with Typeclass Refinements in Liquid Haskell
SIGPLAN Track
Yiyun Liu University of Maryland at College Park, James Parker Galois, Inc., Patrick Redmond University of California at Santa Cruz, Lindsey Kuper University of California at Santa Cruz, Michael Hicks University of Maryland at College Park, Niki Vazou IMDEA Software Institute
15:50
20m
Talk
(PLDI 2021) RefinedC: Automating the Foundational Verification of C Code with Refined Ownership Types
SIGPLAN Track
Michael Sammler MPI-SWS, Rodolphe Lepigre MPI-SWS, Robbert Krebbers Radboud University Nijmegen, Kayvan Memarian University of Cambridge, Derek Dreyer MPI-SWS, Deepak Garg MPI-SWS
Link to publication DOI Authorizer link Pre-print
16:10
20m
Talk
(POPL 2021) Data Flow Refinement Type Inference
SIGPLAN Track
Zvonimir Pavlinovic Google, USA, Yusen Su University of Waterloo, Thomas Wies New York University
16:30
20m
Talk
(PLDI 2021) RbSyn: type- and effect-guided program synthesis
SIGPLAN Track
Sankha Narayan Guria University of Maryland, College Park, Jeffrey S. Foster Tufts University, David Van Horn University of Maryland
Link to publication DOI Authorizer link Pre-print