Write a Blog >>
ICFP 2016
Sun 18 - Sat 24 September 2016 Nara, Japan
Mon 19 Sep 2016 10:45 - 11:10 at Noh Theater - Session 1 Chair(s): Akimasa Morihata

The increasing importance of parallelism has motivated the creation of better abstractions for writing parallel software, including structured parallelism using nested algorithmic skeletons. Such approaches provide high-level abstractions that avoid common problems, such as race conditions, and often allow strong cost models to be defined. However, choosing a combination of algorithmic skeletons that yields good parallel speedups for a program on some specific parallel architecture remains a difficult task. In order to achieve this, it is necessary to simultaneously reason both about the costs of different parallel structures and about the semantic equivalences between them. This paper presents a new type-based mechanism that enables strong static reasoning about these properties. We exploit well-known properties of a very general recursion pattern, hylomorphisms, and give a denotational semantics for structured parallel processes in terms of these hylomorphisms. Using our approach, it is possible to determine formally whether it is possible to introduce a desired parallel structure into a program without altering its functional behaviour, and also to choose a version of that parallel structure that minimises some given cost model.

Mon 19 Sep

Displayed time zone: Osaka, Sapporo, Tokyo change

10:45 - 12:25
Session 1Research Papers at Noh Theater
Chair(s): Akimasa Morihata University of Tokyo, Japan
10:45
25m
Talk
Farms, Pipes, Streams and Reforestation: Reasoning about Structured Parallel Processes using Types and Hylomorphisms
Research Papers
David Castro-Perez University of St. Andrews, UK, Kevin Hammond University of St. Andrews, UK, Susmit Sarkar University of St. Andrews, UK
DOI
11:10
25m
Talk
Dag-Calculus: A Calculus for Parallel Computation
Research Papers
Umut A. Acar Carnegie Mellon University, Arthur Charguéraud Inria, France, Mike Rainey Inria, France, Filip Sieczkowski Inria, France
DOI
11:35
25m
Talk
A Lambda-Calculus Foundation for Universal Probabilistic Programming
Research Papers
Johannes Borgström Uppsala University, Sweden, Ugo Dal Lago University of Bologna, France, Andrew D. Gordon Microsoft Research, UK, Marcin Szymczak University of Edinburgh, UK
DOI
12:00
25m
Talk
Deriving a Probability Density Calculator (Functional Pearl)
Research Papers
Wazim Mohammed Ismail Indiana University, USA, Chung-chieh Shan Indiana University, USA
DOI