PPDP  

08:30
Registration
[Location:
2nd floor, Hörsaalzentrum]
The registration desk will be opened from 8:30 a.m. It is located in the second floor of the building while the conference room (lecture hall HZ 10) is in the third floor of the building. 

08:30
Registration
[Location:
2nd floor, Hörsaalzentrum]
The registration desk will be opened from 8:30 a.m. It is located in the second floor of the building while the conference room (lecture hall HZ 10) is in the third floor of the building. 

09:00
PPDP: Contributed Talks #1
[Chair:
Magnus Madsen • Location:
HZ 10 (third floor, Hörsaalzentrum)]
09:00
Cosette: Symbolic Execution for JavaScript
José Fragoso Santos, Petar Maksimović, Théotime Grohens, Julian Dolby and Philippa Gardner We present a new framework for trustworthy, compositional symbolic execution of JavaScript programs. Its aim is to provide generalpurpose symbolic analysis and assist developers in the testing of their code: the developer writes symbolic tests for which we provide concrete countermodels. We follow a new, general methodology for designing compositional program analyses for dynamic languages and prove that the underlying symbolic execution is sound and does not generate false positives. We establish additional trust by using the theory to precisely guide the implementation and by thorough testing. We apply our framework to wholeprogram symbolic testing of realworld JavaScript libraries and compositional debugging of separation logic specifications of JavaScript programs. 09:30
Verse: An EDSL for cryptographic primitives
Abhishek Dang and Piyush Kurur Cryptographic primitives need highspeed implementations that are also resistant to side channel attacks. The absolute control over instructions and registers that such implementations demand makes assembly language programming a necessity. In this article, we describe Verse, a typed lowlevel language embedded in Coq designed specifically to generate assembly language programs for cryptographic primitives. Despite being a lowlevel language, the programming experience is markedly highlevel: • The type system of Verse is rich enough to even prevent errors in array indexing and endian conversion. • Being embedded in Coq, we have at our disposal Gallina, the underlying functional programming language, as a macro assembler for code generation, and Ltac, the tactic language, as an automation tool for proof obligations inherent to our type system. We also provide a generic framework to formulate semantic aspects of Verse. This framework has value beyond providing an interpretation of Verse in Coq. We demonstrate this versatility by using it to localise uninitialised/clobbered variable use, and arithmetic overflows. 

09:00
PPDP: Contributed Talks #1
[Chair:
Magnus Madsen • Location:
HZ 10 (third floor, Hörsaalzentrum)]
09:00
Cosette: Symbolic Execution for JavaScript
José Fragoso Santos, Petar Maksimović, Théotime Grohens, Julian Dolby and Philippa Gardner We present a new framework for trustworthy, compositional symbolic execution of JavaScript programs. Its aim is to provide generalpurpose symbolic analysis and assist developers in the testing of their code: the developer writes symbolic tests for which we provide concrete countermodels. We follow a new, general methodology for designing compositional program analyses for dynamic languages and prove that the underlying symbolic execution is sound and does not generate false positives. We establish additional trust by using the theory to precisely guide the implementation and by thorough testing. We apply our framework to wholeprogram symbolic testing of realworld JavaScript libraries and compositional debugging of separation logic specifications of JavaScript programs. 09:30
Verse: An EDSL for cryptographic primitives
Abhishek Dang and Piyush Kurur Cryptographic primitives need highspeed implementations that are also resistant to side channel attacks. The absolute control over instructions and registers that such implementations demand makes assembly language programming a necessity. In this article, we describe Verse, a typed lowlevel language embedded in Coq designed specifically to generate assembly language programs for cryptographic primitives. Despite being a lowlevel language, the programming experience is markedly highlevel: • The type system of Verse is rich enough to even prevent errors in array indexing and endian conversion. • Being embedded in Coq, we have at our disposal Gallina, the underlying functional programming language, as a macro assembler for code generation, and Ltac, the tactic language, as an automation tool for proof obligations inherent to our type system. We also provide a generic framework to formulate semantic aspects of Verse. This framework has value beyond providing an interpretation of Verse in Coq. We demonstrate this versatility by using it to localise uninitialised/clobbered variable use, and arithmetic overflows. 

10:00
Coffee Break
[Location:
2nd floor, Hörsaalzentrum]


10:00
Coffee Break
[Location:
2nd floor, Hörsaalzentrum]


10:30
PPDP: Honour and Memory of Martin Hofmann
[Chair:
Philippa Gardner • Location:
HZ 10 (third floor, Hörsaalzentrum)]
We sadly note that one of our pc members and friends, Martin Hofmann, died in January during a mountain trip close to Nikko, Japan. He is missed dearly. The session is a brief remembrance on his behalf. Remembering Martin Hofmann: Semantic Equivalence Checking for HHVM Bytecode (Invited Talk)
Nick Benton We describe a semantic differencing tool used to compare the bytecode generated by two different compilers for Hack/PHP at Facebook. The tool is a prover for a simple relational logic for lowlevel code and is used in testing, allowing developers to focus on semantically significant differences between the outputs of the old and new compilers. 

10:30
PPDP: Honour and Memory of Martin Hofmann
[Chair:
Philippa Gardner • Location:
HZ 10 (third floor, Hörsaalzentrum)]
We sadly note that one of our pc members and friends, Martin Hofmann, died in January during a mountain trip close to Nikko, Japan. He is missed dearly. The session is a brief remembrance on his behalf. Remembering Martin Hofmann: Semantic Equivalence Checking for HHVM Bytecode (Invited Talk)
Nick Benton We describe a semantic differencing tool used to compare the bytecode generated by two different compilers for Hack/PHP at Facebook. The tool is a prover for a simple relational logic for lowlevel code and is used in testing, allowing developers to focus on semantically significant differences between the outputs of the old and new compilers. 

11:15
PPDP: Contributed Talks #2
[Chair:
Philippa Gardner • Location:
HZ 10 (third floor, Hörsaalzentrum)]
11:15
Nondeterministic Manifest Contracts
Yuki Nishida and Atsushi Igarashi We study a manifest contract systema typed calculus of higherorder contracts where contracts are tightly integrated into a refinement type systemfor a functional language with nondeterministic choice. The extension is not trivial, especially in the presence of dependent function types, because a naive extension would lead to inconsistent type equivalence, which makes contract information in refinement types meaningless. To solve the problem, we propose a new kind of nondeterministic choice called coordinated choice, in which each occurrence of a choice operator is given a name and choices of the same name coordinately take the same branch. We introduce the notion of orthant that helps both intuitive understanding and the development of formal semantics of the new choice. We formalize a manifest contract system λ^HΦ using the coordinated choice and show its basic properties of progress, type preservation, and contract satisfaction, the last of which states correctness of contracts in refinement types. 11:45
An Internalist Approach to CorrectbyConstruction Compilers
Alberto Pardo, Emmanuel Gunther, Miguel Pagano and Marcos Viera In this paper we present a methodology to organize the construction of a correct compiler, taking advantage of the power of full dependently type systems. The basic idea consists of decorating the abstract syntax of languages with their semantics, allowing to express the correctness of the compiler at type level. We show our methodology in a first small example and then explore how it can be promoted to more realistic languages, realizing that our internalistic approach is feasible for defining a correctbyconstruction compiler from an imperative language with general recursion to a stack based intermediate language. We also show how this methodology can be combined with the externalist approach, compiling from the intermediate language to an assemblylike low level code and separately proving its correctness. 

11:15
PPDP: Contributed Talks #2
[Chair:
Philippa Gardner • Location:
HZ 10 (third floor, Hörsaalzentrum)]
11:15
Nondeterministic Manifest Contracts
Yuki Nishida and Atsushi Igarashi We study a manifest contract systema typed calculus of higherorder contracts where contracts are tightly integrated into a refinement type systemfor a functional language with nondeterministic choice. The extension is not trivial, especially in the presence of dependent function types, because a naive extension would lead to inconsistent type equivalence, which makes contract information in refinement types meaningless. To solve the problem, we propose a new kind of nondeterministic choice called coordinated choice, in which each occurrence of a choice operator is given a name and choices of the same name coordinately take the same branch. We introduce the notion of orthant that helps both intuitive understanding and the development of formal semantics of the new choice. We formalize a manifest contract system λ^HΦ using the coordinated choice and show its basic properties of progress, type preservation, and contract satisfaction, the last of which states correctness of contracts in refinement types. 11:45
An Internalist Approach to CorrectbyConstruction Compilers
Alberto Pardo, Emmanuel Gunther, Miguel Pagano and Marcos Viera In this paper we present a methodology to organize the construction of a correct compiler, taking advantage of the power of full dependently type systems. The basic idea consists of decorating the abstract syntax of languages with their semantics, allowing to express the correctness of the compiler at type level. We show our methodology in a first small example and then explore how it can be promoted to more realistic languages, realizing that our internalistic approach is feasible for defining a correctbyconstruction compiler from an imperative language with general recursion to a stack based intermediate language. We also show how this methodology can be combined with the externalist approach, compiling from the intermediate language to an assemblylike low level code and separately proving its correctness. 

12:15
Lunch Break
[Location:
Mensa Casino]


12:15
Lunch Break
[Location:
Mensa Casino]


14:00
PPDP: Invited Talk
[Chair:
Peter Thiemann • Location:
HZ 10 (third floor, Hörsaalzentrum)]
Calculating Distributions (Invited Talk)
ChungChieh Shan The ways we reason about probability distributions and explore their applications have been naturally shifting: away from thoughtful proving with definitions using first principles, and towards mechanical calculation with expressions using derived principles. This talk reviews three useful operations on distributions that we have started to express using equational derivations and even to automate as program transformations. These operations are (1) to recognize a density function as belonging to a known distribution family, (2) to eliminate an unused random variable by summation or integration, and (3) to disintegrate a joint measure into a marginal and a conditional measure. It is thus promising to support probabilistic reasoning by drawing techniques from both programming languages and computer algebra. Ongoing challenges include how to handle a wide variety of container data types and generating programs, and how human guidance should interact with machine assistance. 

14:00
PPDP: Invited Talk
[Chair:
Peter Thiemann • Location:
HZ 10 (third floor, Hörsaalzentrum)]
Calculating Distributions (Invited Talk)
ChungChieh Shan The ways we reason about probability distributions and explore their applications have been naturally shifting: away from thoughtful proving with definitions using first principles, and towards mechanical calculation with expressions using derived principles. This talk reviews three useful operations on distributions that we have started to express using equational derivations and even to automate as program transformations. These operations are (1) to recognize a density function as belonging to a known distribution family, (2) to eliminate an unused random variable by summation or integration, and (3) to disintegrate a joint measure into a marginal and a conditional measure. It is thus promising to support probabilistic reasoning by drawing techniques from both programming languages and computer algebra. Ongoing challenges include how to handle a wide variety of container data types and generating programs, and how human guidance should interact with machine assistance. 

15:00
Coffee Break
[Location:
2nd floor, Hörsaalzentrum]


15:00
Coffee Break
[Location:
2nd floor, Hörsaalzentrum]


15:30
PPDP: Most Influential Paper 10year Award and Contributed Talks #3
[Chair:
Anton Setzer • Location:
HZ 10 (third floor, Hörsaalzentrum)]
15:30
Most influential paper 10year award: Programming with proofs and explicit contexts
Brigitte Pientka and Joshua Dunfield 16:00
On Intersection Types and Probabilistic Lambda Calculi
Flavien Breuvart and Ugo Dal Lago We define two intersection type systems for the pure, untyped, probabilistic lambdacalculus, and prove that type derivations precisely reflect the probability of convergence of the underlying term. We first define a simple system of oracle intersection types in which derivations are annotated by binary strings and the probability of termination can be computed by combining all the different possible annotations. Although inevitable due to recursion theoretic limitations, the fact that (potentially) infinitely many derivations need to be considered is of course an issue when seeing types as a verification methodology. We thus develop a more complex system: the monadic intersection type system. In this second system, the probability of termination of a term is shown to be the least upper bound of the weights of its type derivations. 16:30
Sequential and Parallel Improvements in a Concurrent Functional Programming Language
Manfred SchmidtSchauss, David Sabel, and Nils Dallmeyer We propose a model for measuring the runtime of concurrent programs by the minimal number of evaluation steps. The focus of this paper are improvements, which are program transformations that improve this number in every context, where we distinguish between sequential and parallel improvements, for one or more processors, respectively. We apply the methods to CHF, a model of Concurrent Haskell extended by futures allowing declarative implementations of concurrent programs. The language CHF is a typed higherorder functional language with concurrent threads, monadic IO and MVars as synchronizing variables. We show that all deterministic reduction rules and several further useful program transformations are sequential and parallel improvements. 

15:30
PPDP: Most Influential Paper 10year Award and Contributed Talks #3
[Chair:
Anton Setzer • Location:
HZ 10 (third floor, Hörsaalzentrum)]
15:30
Most influential paper 10year award: Programming with proofs and explicit contexts
Brigitte Pientka and Joshua Dunfield 16:00
On Intersection Types and Probabilistic Lambda Calculi
Flavien Breuvart and Ugo Dal Lago We define two intersection type systems for the pure, untyped, probabilistic lambdacalculus, and prove that type derivations precisely reflect the probability of convergence of the underlying term. We first define a simple system of oracle intersection types in which derivations are annotated by binary strings and the probability of termination can be computed by combining all the different possible annotations. Although inevitable due to recursion theoretic limitations, the fact that (potentially) infinitely many derivations need to be considered is of course an issue when seeing types as a verification methodology. We thus develop a more complex system: the monadic intersection type system. In this second system, the probability of termination of a term is shown to be the least upper bound of the weights of its type derivations. 16:30
Sequential and Parallel Improvements in a Concurrent Functional Programming Language
Manfred SchmidtSchauss, David Sabel, and Nils Dallmeyer We propose a model for measuring the runtime of concurrent programs by the minimal number of evaluation steps. The focus of this paper are improvements, which are program transformations that improve this number in every context, where we distinguish between sequential and parallel improvements, for one or more processors, respectively. We apply the methods to CHF, a model of Concurrent Haskell extended by futures allowing declarative implementations of concurrent programs. The language CHF is a typed higherorder functional language with concurrent threads, monadic IO and MVars as synchronizing variables. We show that all deterministic reduction rules and several further useful program transformations are sequential and parallel improvements. 

18:00
PPDP and LOPSTR Reception (Welcome Drink and Snacks)
[Location:
Cafe Sturm und Drang (ground floor, Hörsaalzentrum)]


18:00
PPDP and LOPSTR Reception (Welcome Drink and Snacks)
[Location:
Cafe Sturm und Drang (ground floor, Hörsaalzentrum)]
