All for one and none forall: Compiling polymorphic relations without monomorphization
2026-07-27 • Programming Languages
Programming Languages
AI summaryⓘ
The authors introduce semiringKanren, a new programming language that works by combining relations and weights from the bottom up. They show how to add polymorphism—letting parts of the program work with many types without creating separate copies. Their key idea is a way to turn these polymorphic programs into simpler, non-polymorphic ones using patterns and big examples. They also prove that their approach works correctly and compare it to earlier research, pointing out future possibilities.
polymorphismbottom-up relational programmingsemiringKanrenmonomorphizationweighted relationsprogram compilationequality patternstype systemsrelational languages
Authors
Dmitri Volkov, Yafei Yang, Chung-Chieh Shan
Abstract
We present a new approach for implementing polymorphism for bottom-up relational languages that avoids monomorphization. We begin by introducing semiringKanren, a bottom-up weighted relational programming language. We extend this base language to support polymorphism. We describe a new method to compile polymorphic semiringKanren programs into non-polymorphic ones, based on equality patterns and large-enough instances of polymorphic relations. We explain the correctness of this method. Finally, we consider existing work and suggest directions for future research.