March 25, 2022
Many advanced programming languages come with parametric polymorphism that allows the same program to work with data of different types, significantly reducing code duplication. What is less known is that polymorphic programs are also easier to test if correct techniques are applied. The intuition is that fewer programs are polymorphic, and thus lesser testing is needed to distinguish correct programs from incorrect ones. The ignorance of a program about its input type turns out to be its greatest strength. One central question is how to choose a concrete type to instantiate these polymorphic programs for testing. The insight from our POPL paper is that, given the type of functions to be tested, one can choose the “logarithm” of its input type! This talk will explain why logarithm works and discuss further improvements. The development of the theorems is joint work with my student Zhuyang Wang. It has been published in POPL 2022: https://dl.acm.org/doi/10.1145/3498726.