SPLASH 2021
Sun 17 - Fri 22 October 2021 Chicago, Illinois, United States
Thu 21 Oct 2021 10:50 - 11:05 at Zurich E - ICFP 2020 Papers Chair(s): Stefan K. Muller

We propose a novel definition of binders using matching logic, where the binding behavior of object-level binders is directly inherited from the built-in exists binder of matching logic. We show that the behavior of binders in various logical systems such as lambda-calculus, System F, pi-calculus, pure type systems, can be axiomatically defined in matching logic as notations and logical theories. We show the correctness of our definitions by proving conservative extension theorems, which state that a sequent/judgment is provable in the original system if and only if it is provable in matching logic, in the corresponding theory. Our matching logic definition of binders also yields models to all binders, which are deductively complete with respect to formal reasoning in the original systems. For lambda-calculus, we further show that the yielded models are representationally complete, a desired property that is not enjoyed by many existing lambda-calculus semantics. This work is part of a larger effort to develop a logical foundation for the programming language semantics framework K (http://kframework.org).

Thu 21 Oct

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

10:50 - 12:10
ICFP 2020 PapersSIGPLAN Papers at Zurich E
Chair(s): Stefan K. Muller Illinois Institute of Technology
10:50
15m
Talk
A General Approach to Define Binders using Matching Logic
SIGPLAN Papers
Xiaohong Chen University of Illinois at Urbana-Champaign, Grigore Roşu University of Illinois at Urbana-Champaign
DOI
11:05
15m
Talk
Denotational Recurrence Extraction for Amortized Analysis
SIGPLAN Papers
Joseph W. Cutler University of Pennsylvania, Daniel R. Licata Wesleyan University, Norman Danner Wesleyan University
DOI
11:20
15m
Talk
Program Sketching with Live Bidirectional Evaluation
SIGPLAN Papers
Justin Lubin University of California at Berkeley, Nick Collins University of Chicago, Cyrus Omar University of Michigan, Ravi Chugh University of Chicago
DOI
11:35
15m
Talk
Liquid Information Flow Control
SIGPLAN Papers
Nadia Polikarpova University of California at San Diego, Jean Yang Carnegie Mellon University, Deian Stefan University of California at San Diego, USA, Shachar Itzhaky Technion, Armando Solar-Lezama Massachusetts Institute of Technology, Travis Hance Carnegie Mellon University
DOI
11:50
20m
Live Q&A
Discussion, Questions and Answers
SIGPLAN Papers