Fri 17 Jun 2022 15:30 - 15:50 at Kon-Tiki - Verification II Chair(s): Thomas Wahl
Sat 18 Jun 2022 03:30 - 03:50 at Kon-Tiki - Verification II

To run, purely functional programs verified using interactive theorem provers (ITPs) typically need to be extracted: either to a similar language (like Coq to OCaml) or by proving equivalence with a deeply embedded implementation (like a C program). Traditionally, the first approach was unverified but automated, and the second verified but manual. More recently, advances in extraction have achieved automated extraction, with proofs. We introduce the unifying framework of \emph{relational compilation} to capture and extend these recent developments, and develop it through a series of examples, with a novel focus on sound extensibility. This culminates with the presentation of Rupicola, a proof-producing compiler-construction toolkit focused on automatically deriving fast, low-level code from purely functional models. We present novel solutions to loop-invariant inference and genericity in kinds of side effects. Overall, Rupicola is unique in its combination of modularity and extensibility, foundational proofs, and low-level performance. We demonstrate these achievements through a combination of case studies and performance benchmarks that highlight how little effort is required to extend Rupicola and how easy it makes it to generate low-level code with performance on par with that of handwritten C programs.

Fri 17 Jun

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

15:30 - 16:50
Verification IIPLDI at Kon-Tiki +12h
Chair(s): Thomas Wahl GrammaTech, Inc.
15:30
20m
Talk
Relational Compilation for Performance-Critical Applications
PLDI
Clément Pit-Claudel EPFL, AWS, Jade Philipoom MIT CSAIL, Dustin Jamner MIT CSAIL, Andres Erbsen MIT CSAIL, Adam Chlipala MIT CSAIL
Link to publication DOI Pre-print
15:50
20m
Talk
Formally Verified Lifting of C-compiled x86-64 Binaries
PLDI
Freek Verbeek Open University of The Netherlands & Virginia Tech, Joshua A. Bockenek Virginia Tech, Zhoulai Fu University of California, Davis, Binoy Ravindran Virginia Tech
DOI
16:10
20m
Talk
Leapfrog: Certified Equivalence for Protocol Parsers
PLDI
Ryan Doenges Cornell University, Tobias Kappé ILLC, University of Amsterdam, John Sarracino Cornell University, Nate Foster Cornell University, Greg Morrisett Cornell Tech
DOI Pre-print
16:30
20m
Talk
Computing Correctly with Inductive Relations
PLDI
Zoe Paraskevopoulou Northeastern University, Aaron Eline University of Maryland, Leonidas Lampropoulos University of Maryland
DOI

Sat 18 Jun

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

03:30 - 04:50
Verification IIPLDI at Kon-Tiki
03:30
20m
Talk
Relational Compilation for Performance-Critical Applications
PLDI
Clément Pit-Claudel EPFL, AWS, Jade Philipoom MIT CSAIL, Dustin Jamner MIT CSAIL, Andres Erbsen MIT CSAIL, Adam Chlipala MIT CSAIL
Link to publication DOI Pre-print
03:50
20m
Talk
Formally Verified Lifting of C-compiled x86-64 Binaries
PLDI
Freek Verbeek Open University of The Netherlands & Virginia Tech, Joshua A. Bockenek Virginia Tech, Zhoulai Fu University of California, Davis, Binoy Ravindran Virginia Tech
DOI
04:10
20m
Talk
Leapfrog: Certified Equivalence for Protocol Parsers
PLDI
Ryan Doenges Cornell University, Tobias Kappé ILLC, University of Amsterdam, John Sarracino Cornell University, Nate Foster Cornell University, Greg Morrisett Cornell Tech
DOI Pre-print
04:30
20m
Talk
Computing Correctly with Inductive Relations
PLDI
Zoe Paraskevopoulou Northeastern University, Aaron Eline University of Maryland, Leonidas Lampropoulos University of Maryland
DOI