The ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM), which has a history going back to 1991 and has co-located with POPL every year since 2006, originates in the discoveries of practically useful automated techniques for evaluating programs with only partial input. Over the years, the scope of PEPM has expanded to include a variety of research areas centred around the theme of semantics-based program manipulation — the systematic exploitation of treating programs not only as subject to black-box execution, but also as data structures that can be generated, analysed, and transformed while establishing or maintaining important semantic properties.

Scope

In addition to the traditional PEPM topics (see below), PEPM 2020 welcomes submissions in new domains, in particular:

• Semantics based and machine-learning based program synthesis and program optimisation.

• Modelling, analysis, and transformation techniques for distributed and concurrent protocols and programs, such as session types, linear types, and contract specifications.

More generally, topics of interest for PEPM 2020 include, but are not limited to:

• Program and model manipulation techniques such as: supercompilation, partial evaluation, fusion, on-the-fly program adaptation, active libraries, program inversion, slicing, symbolic execution, refactoring, decompilation, and obfuscation.

• Techniques that treat programs/models as data objects including metaprogramming, generative programming, embedded domain-specific languages, program synthesis by sketching and inductive programming, staged computation, and model-driven program generation and transformation.

• Program analysis techniques that are used to drive program/model manipulation such as: abstract interpretation, termination checking, binding-time analysis, constraint solving, type systems, automated testing and test case generation.

• Application of the above techniques including case studies of program manipulation in real-world (industrial, open-source) projects and software development processes, descriptions of robust tools capable of effectively handling realistic applications, benchmarking. Examples of application domains include legacy program understanding and transformation, DSL implementations, visual languages and end-user programming, scientific computing, middleware frameworks and infrastructure needed for distributed and web-based applications, embedded and resource-limited computation, and security.

This list of categories is not exhaustive, and we encourage submissions describing new theories and applications related to semantics-based program manipulation in general. If you have a question as to whether a potential submission is within the scope of the workshop, please contact the programme co-chairs, Casper Bach Poulsen (http://casperbp.net) and Zhenjiang Hu (http://sei.pku.edu.cn/~hu/).

Accepted Papers

Call for Papers

Submission categories and guidelines

Two kinds of submissions will be accepted: Regular Research Papers and Short Papers.

• Regular Research Papers should describe new results, and will be judged on originality, correctness, significance, and clarity. Regular research papers must not exceed 12 pages (excluding bibliography).

• Short Papers may include tool demonstrations and presentations of exciting if not fully polished research, and of interesting academic, industrial, and open-source applications that are new or unfamiliar. Short papers must not exceed 6 pages (excluding bibliography).

Both kinds of submissions should be typeset using the two-column ‘sigplan’ sub-format of the new ‘acmart’ format available at:

http://sigplan.org/Resources/Author/

and submitted electronically via HotCRP:

https://pepm20.hotcrp.com/

PEPM 2020 will employ lightweight double-blind reviewing according to the rules of POPL 2020. Quoting from POPL 2020’s call for papers:

submitted papers must adhere to two rules:

1. author names and institutions must be omitted, and

2. references to authors’ own related work should be in the third person (e.g., not “We build on our previous work …” but rather “We build on the work of …”).

The purpose of this process is to help the PC and external reviewers come to an initial judgment about the paper without bias, not to make it impossible for them to discover the authors if they were to try. Nothing should be done in the name of anonymity that weakens the submission or makes the job of reviewing the paper more difficult. In particular, important background references should not be omitted or anonymized. In addition, authors are free to disseminate their ideas or draft versions of their paper as usual. For example, authors may post drafts of their papers on the web or give talks on their research ideas.”

See POPL 2020’s Submission and Reviewing FAQ page for more information:

https://popl20.sigplan.org/track/POPL-2020-Research-Papers#Submission-and-Reviewing-FAQ

Submissions are welcome from PC members (except the two co-chairs).

Accepted papers will appear in formal proceedings published by ACM, and be included in the ACM Digital Library. Authors of short papers, however, can ask for their papers to be left out of the formal proceedings.

At least one author of each accepted contribution must attend the workshop and present the work. In the case of tool demonstration papers, a live demonstration of the described tool is expected. Suggested topics, evaluation criteria, and writing guidelines for both research tool demonstration papers will be made available on the PEPM 2020 web site: https://popl20.sigplan.org/home/pepm-2020

Student participants with accepted papers can apply for a SIGPLAN PAC grant to help cover travel expenses and other support. PAC also offers other support, such as for child-care expenses during the meeting or for travel costs for companions of SIGPLAN members with physical disabilities, as well as for travel from locations outside of North America and Europe. For details on the PAC programme, see its web page: https://www.sigplan.org/PAC/

Important dates

• Paper submission deadline (EXTENDED) : Friday 25th October 2019 (AoE)
• Author notification (EXTENDED) : Monday 18th November 2019 (AoE)
• Camera-ready version : Monday 25th November 2019
• Workshop : Monday 20th January 2020

The proceedings are expected to be published 2 weeks pre-conference.

AUTHORS TAKE NOTE: The official publication date is the date the proceedings are made available in the ACM Digital Library. This date may be up to two weeks prior to the first day of your conference. The official publication date affects the deadline for any patent filings related to published work. (For those rare conferences whose proceedings are published in the ACM Digital Library after the conference is over, the official publication date remains the first day of the conference.)

Best paper award

PEPM 2020 continues the tradition of a Best Paper award. The winner will be announced at the workshop.

PEPM 2020 has two Distinguished invited speakers, Xinyu Feng and Nate Foster.

Reasoning about Progress of Concurrent Objects

Xinyu Feng (Nanjing University)

Abstract

Implementations of concurrent objects should guarantee linearizability and a progress property such as wait-freedom, lock-freedom, starvation-freedom, or deadlock-freedom. These progress properties describe conditions under which a method call is guaranteed to complete. However, they fail to describe how clients are affected, making it difficult to utilize them in layered and modular program verification. Also, we lack verification techniques for starvation-free or deadlock-free objects. They are challenging to verify because the fairness assumption introduces complicated interdependencies among progress of threads. Even worse, none of the existing results applies to concurrent objects with partial methods, i.e., methods that are supposed NOT to return under certain circumstances.

In this talk we examine the progress properties of concurrent objects. We formulate each progress property (together with linearizability as a basic correctness requirement) in terms of contextual refinement. This essentially gives us progress-aware abstraction for concurrent objects. Thus, when verifying clients of the objects, we can soundly replace the concrete object implementations with their abstractions, achieving modular verification. For concurrent objects with partial methods, we formulate two new progress properties, partial starvation-freedom (PSF) and partial deadlock-freedom (PDF). Finally, we introduce a rely-guarantee style program logic LiLi for verifying linearizability and progress together for concurrent objects. It unifies thread-modular reasoning about all the six progress properties (wait-freedom, lock-freedom, starvation-freedom, deadlock-freedom, PSF and PDF) in one framework. We have successfully applied LiLi to verify starvation-freedom or deadlock-freedom of representative algorithms such as lock-coupling lists, optimistic lists and lazy lists, and PSF or PDF of lock algorithms.

Biography

Xinyu Feng is a professor in computer science at Nanjing University. He got his PhD degree at Yale University in 2007, after which he worked at Toyota Technological Institute at Chicago (TTIC) from 2007 to 2010, and University of Science and Technology of China (USTC) from 2010 t0 2017. He recently moved to Nanjing University in 2018. His research interest is about formal program verification and theories of programming languages. In particular, he is interested in verifying fine-grained or non-blocking concurrent algorithms, and verifying system software such as OS kernels and compilers.

Network Verification: Past, Present, and Future

Nate Foster (Cornell University)

Abstract

Networks today achieve robustness not by adhering to precise formal specifications but by building implementations that tolerate modest deviations from correct behavior. This philosophy can be seen in the slogan used by the Internet Engineering Task Force, “we believe in rough consensus and running code,” and by Jon Postel’s famous dictum to “be conservative in what you do, be liberal in what you accept from others.” But as networks have grown in scale and complexity, the frequency of faults has led to new interest in techniques for formally verifying network behavior.

This talk will discuss recent progress on practical tools for specifying and verifying formal properties of networks. In the first part of the talk, I will present p4v, a tool for verifying the low-level code that executes on individual devices such as routers and firewalls. In the second part of the talk, I will present NetKAT, a formal system for specifying and verifying network-wide behavior. In the third part of the talk, I will highlight some challenges and opportunities for future research in network verification.

Biography

Nate Foster is an Associate Professor of Computer Science at Cornell University and a Principal Research Engineer at Barefoot Networks, an Intel company. The goal of his research is to develop tools that make it easy for programmers to build secure and reliable systems. His current work focuses on the design and implementation of languages for programming software-defined networks. He received a PhD in Computer Science from the University of Pennsylvania, an MPhil in History and Philosophy of Science from Cambridge University, and a BA in Computer Science from Williams College. His honors include a Sloan Research Fellowship, an NSF CAREER Award, the ACM SIGCOMM Rising Star Award, and several best paper and teaching awards.