We present partial evaluation by specialization-safe normalization, a novel partial evaluation technique that is Jones-optimal, that can be self-applied to achieve the Futamura projections, and that can be type-checked to ensure it always generates code with the correct type. Jones-optimality is the gold-standard for nontrivial partial evaluation and guarantees that a specializer can remove an entire layer of interpretation. We achieve Jones-optimality by using a novel affine-variable static analysis that directs specialization-safe normalization to always decrease a program's runtime. Our experiments confirm Jones-optimality for call-by-value, normal-order, and memoized normal-order.  Joint work with Matt Brown; presented at POPL 2018.

About the speaker: Jens Palsberg is a Professor and former Department Chair of Computer Science at University of California, Los Angeles (UCLA). His research interests span the areas of compilers, embedded systems, programming languages, software engineering, and information security. He is the chair of ACM SIGPLAN, a member of the editorial board of Information and Computation, and a former editor-in-chief of ACM Transactions of Programming Languages and Systems. He received his PhD from Aarhus University in 1992 and he received the ACM SIGPLAN Distinguished Service Award in 2012.