PEPM 2021: Proceedings of the 2021 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation

Structure editors make syntax errors impossible, but they still allow construction of programs with incomplete semantics, leading to program states that cannot be evaluated. We introduce a structure editor calculus for a simple functional programming language that allows for incomplete programs. Our editor expressions may interleave construction and evaluation of programs and can thus describe the history of the development of a program. We extend our editor calculus with types and define a resource-aware type system that prohibits editor expressions introducing type errors in the abstract syntax tree and prove that the type system is sound.

Coq proof assistant can be used to prove various properties of programs written in the Gallina language. It is also possible to translate Gallina programs to OCaml programs. However, OCaml is not suitable for low-level programs. Therefore, we are developing a Coq plugin for Gallina to C translation. This plugin transforms functions written in Gallina into a form as close to C as possible within Gallina. This transformation includes partial evaluation, which improves execution efficiency and eliminates polymorphism and dependent types. We can easily verify in Coq that this transformation does not change the execution result, and thus it is highly reliable. And Gallina functions after this transformation can be easily translated to C.

This paper presents a text-based syntax completion method using an LR parser. We propose formal definitions of candidate text to be completed based on the sentential forms, and we design algorithms for computing candidates through reductions in the LR parsing. This is in contrast to the existing methods that have not clearly stated what candidates they intend to produce. This is also different from a transformation approach using an LR parser, which transforms the grammar of the programming language, a burdensome task at this moment. The advantage of our method is that LR parsers can be adopted without modification, and a syntax completion system can be built using them, without incurring efforts. We implemented the algorithms as an Emacs server to demonstrate the feasibility of their application.

Type-based program verification, which reduces program verification to type inference, has been used as a lightweight approach to automated program verification. Whilst it is often effective and faster than other methods such as model checking, the type-based approach often fails to provide useful information upon a failure of the verification. We address this problem for a recent type-based verification tool called ConSORT for imperative programs. Producing a useful error message is particularly challenging for ConSORT, as the underlying type system combines the notions of ownership, refinement types, and context-sensitivity. This paper proposes a method to produce error messages for ConSORT and reports an implementation and experimental results. The proposed method is potentially useful also for other type-based tools for automated program verification.

We present a new, fair, conjunction evaluation strategy for relational programming language miniKanren. Unlike the original left-biased conjunction, our approach controls the order of conjunct execution based on the intrinsic properties of relation definitions. We present both the formal study of conjunction fairness and practical evaluation, which demonstrates the essential improvement in terms of both performance and convergence.

All functional languages need closures. Closure-conversion is a compiler transformation that embeds static code into the program for creating and manipulating closures, avoiding the need for special run-time closure support. For call-by-value languages, closure-conversion has been the focus of extensive studies concerning correctness, such as type preservation and contextual equivalence, and performance, such as space usage. Unfortunately, non-strict languages have been neglected in these studies. This paper aims to fill this gap.

We begin with both a call-by-name and a call-by-need source language whose semantics automatically generates closures at run-time. Next, we give type-preserving closure-conversions for these two non-strict languages into a lower-level target language without automatic closure generation at run-time. Despite the fact that our source languages are non-strict, we show that closures must be created eagerly, which requires a strict notion of product in the target language. We extend logical relation techniques used to prove compiler correctness for call-by-value languages, to apply to non-strict languages too. In doing so, we identify some important properties for reasoning about memoization with a heap.