Write a Blog >>
ICFP 2020
Thu 20 - Fri 28 August 2020
Wed 26 Aug 2020 12:45 - 13:00 at ICFP NY 5 - New York 5 Chair(s): Richard A. Eisenberg
Wed 26 Aug 2020 23:45 - 00:00 at ICFP Asia 5 - Asia 5 Chair(s): Richard A. Eisenberg

This paper defines a new type system applied to the fully automatic verification of safety properties of tree-processing higher order functional programs. We use term rewriting systems to model the program and its semantics and tree automata to model algebraic data types. We define the regular abstract interpretation of the input term rewriting system where the abstract domain is a set of regular languages. From the regular abstract interpretation we derive a type system where each type is a regular language. We define an inference procedure for this type system which allows us check the validity of safety properties. The inference mechanism is built on an invariant learning procedure based on the tree automata completion algorithm. This invariant learning procedure is regularly-complete and complete in refutation, meaning that if it is possible to give a regular type to a term then we will eventually find it, and if there is no possible type (regular or not) then we will eventually find a counter-example.

Wed 26 Aug

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

11:00 - 13:00
New York 5ICFP Program at ICFP NY 5
Chair(s): Richard A. Eisenberg Tweag I/O

Public livestreams: YouTube, Bilibili (China)

11:00
15m
Talk
Denotational Recurrence Extraction for Amortized Analysis
ICFP Program
Joseph W. Cutler Wesleyan University, Daniel R. Licata Wesleyan University, Norman Danner Wesleyan University
DOI Media Attached
11:15
15m
Talk
Separation Logic for Sequential Programs (Functional Pearl)
ICFP Program
DOI Media Attached
11:30
15m
Talk
Strong Functional Pearl: Harper's Regular-Expression Matcher in Cedille
ICFP Program
Aaron Stump The University of Iowa, USA, Chris Jenkins The University of Iowa, Stephan Spahn The University of Iowa, Colin McDonald University of Notre Dame
DOI Media Attached
11:45
15m
Talk
Duplo: A Framework for OCaml Post-Link Optimisation
ICFP Program
Nandor Licker University of Cambridge, Timothy M. Jones University of Cambridge, UK
DOI Media Attached
12:00
15m
Talk
Recovering Purity with Comonads and Capabilities
ICFP Program
Vikraman Choudhury Indiana University & University of Cambridge, Neel Krishnaswami Computer Laboratory, University of Cambridge
DOI Media Attached
12:15
15m
Talk
A General Approach to Define Binders Using Matching Logic
ICFP Program
Xiaohong Chen University of Illinois at Urbana-Champaign, Grigore Roşu University of Illinois at Urbana-Champaign
DOI Media Attached
12:30
15m
Talk
Parsing with Zippers (Functional Pearl)
ICFP Program
Pierce Darragh University of Utah, Michael D. Adams University of Michigan
DOI Media Attached
12:45
15m
Talk
Regular Language Type Inference with Term Rewriting
ICFP Program
Timothée Haudebourg Univ Rennes, Inria, CNRS, IRISA, Thomas Genet IRISA, Univ Rennes, Thomas P. Jensen INRIA Rennes
DOI Media Attached
22:30 - 00:00
Asia 5ICFP Program at ICFP Asia 5
Chair(s): Richard A. Eisenberg Tweag I/O

Public livestreams: YouTube, Bilibili (China)

22:00
30m
Talk
Denotational Recurrence Extraction for Amortized Analysis
ICFP Program
Joseph W. Cutler Wesleyan University, Daniel R. Licata Wesleyan University, Norman Danner Wesleyan University
DOI Media Attached
22:15
15m
Talk
Separation Logic for Sequential Programs (Functional Pearl)
ICFP Program
DOI Media Attached
22:30
15m
Talk
Strong Functional Pearl: Harper's Regular-Expression Matcher in Cedille
ICFP Program
Aaron Stump The University of Iowa, USA, Chris Jenkins The University of Iowa, Stephan Spahn The University of Iowa, Colin McDonald University of Notre Dame
DOI Media Attached
22:45
15m
Talk
Duplo: A Framework for OCaml Post-Link Optimisation
ICFP Program
Nandor Licker University of Cambridge, Timothy M. Jones University of Cambridge, UK
DOI Media Attached
23:00
15m
Talk
Recovering Purity with Comonads and Capabilities
ICFP Program
Vikraman Choudhury Indiana University & University of Cambridge, Neel Krishnaswami Computer Laboratory, University of Cambridge
DOI Media Attached
23:15
15m
Talk
A General Approach to Define Binders Using Matching Logic
ICFP Program
Xiaohong Chen University of Illinois at Urbana-Champaign, Grigore Roşu University of Illinois at Urbana-Champaign
DOI Media Attached
23:30
15m
Talk
Parsing with Zippers (Functional Pearl)
ICFP Program
Pierce Darragh University of Utah, Michael D. Adams University of Michigan
DOI Media Attached
23:45
15m
Talk
Regular Language Type Inference with Term Rewriting
ICFP Program
Timothée Haudebourg Univ Rennes, Inria, CNRS, IRISA, Thomas Genet IRISA, Univ Rennes, Thomas P. Jensen INRIA Rennes
DOI Media Attached