Relational Compilation for Performance-Critical Applications
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 JunDisplayed time zone: Pacific Time (US & Canada) change
15:30 - 16:50 | |||
15:30 20mTalk | 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 20mTalk | 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 20mTalk | 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 20mTalk | Computing Correctly with Inductive Relations PLDI Zoe Paraskevopoulou Northeastern University, Aaron Eline University of Maryland, Leonidas Lampropoulos University of Maryland DOI |
Sat 18 JunDisplayed time zone: Pacific Time (US & Canada) change
03:30 - 04:50 | |||
03:30 20mTalk | 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 20mTalk | 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 20mTalk | 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 20mTalk | Computing Correctly with Inductive Relations PLDI Zoe Paraskevopoulou Northeastern University, Aaron Eline University of Maryland, Leonidas Lampropoulos University of Maryland DOI |