Write a Blog >>
ICFP 2018
Sun 23 - Sat 29 September 2018 St. Louis, Missouri, United States
Wed 26 Sep 2018 15:23 - 15:46 at Stifel Theatre - Complexity and Bounds Chair(s): Ilya Sergey

Parametricity, in both operational and denotational forms, has long been a useful tool for reasoning about program correctness. However, there is as yet no comparable technique for reasoning about program improvement, that is, when one program uses fewer resources than another. Existing theories of parametricity cannot be used to address this problem as they are agnostic with regard to resource usage. This article addresses this problem by presenting a new operational theory of parametricity that is sensitive to time costs, which can be used to reason about time improvement properties. We demonstrate the applicability of our theory by showing how it can be used to prove that a number of well-known program fusion techniques are time improvements, including fixed point fusion, map fusion and short cut fusion.

Wed 26 Sep

Displayed time zone: Guadalajara, Mexico City, Monterrey change

15:00 - 16:10
Complexity and BoundsResearch Papers at Stifel Theatre
Chair(s): Ilya Sergey University College London
15:00
23m
Talk
Parallel Complexity Analysis with Temporal Session Types
Research Papers
Ankush Das Carnegie Mellon University, Jan Hoffmann Carnegie Mellon University, Frank Pfenning Carnegie Mellon University, USA
DOI
15:23
23m
Talk
Parametric Polymorphism and Operational Improvement
Research Papers
Jennifer Hackett University of Nottingham, UK, Graham Hutton University of Nottingham, UK
DOI
15:46
23m
Talk
Tight Typings and Split Bounds
Research Papers
Beniamino Accattoli Inria & Ecole Polytechnique, St├ęphane Graham-Lengrand CNRS, France, Delia Kesner IRIF, France / University of Paris Diderot, France
DOI