(Part of IU Logic Seminar)

Time and Location

  • Date: Wednesday, April 15
  • Time: 3:00PM
  • Location: Ballantine Hall (BH) 142

Abstract

Logic programming languages usually choose one of two approaches: top-down search (Prolog, miniKanren, etc.), or bottom-up fact collection (Datalog, SQL, etc.). Polymorphism in programming languages means operating on unknown types of data. While polymorphism usually comes for free in top-down languages, it is at odds with the fact-collection approach of bottom-up languages. How can we collect facts like “x is related to y” when we don’t know what domains x and y are drawn from?

This talk introduces semiringKanren, a bottom-up variant of miniKanren with weights, algebraic data types, and polymorphic relations. In semiringKanren, weighted relations denote finite multidimensional arrays. Particularly, even polymorphic relations are stored as a single array; there is no need to generate separate versions for each type.