Bender, David and Kuper, Lindsey and Byrd, William and Friedman, Daniel, 2015. Efficient representations for triangular substitutions: A comparison in miniKanren.
Abstract: Unication, a fundamental process for logic programming systems, relies on the ability to eciently look up values of variables in a substitution. Triangular substitutions, which allow associations to vari- ables that are themselves bound by another association, are an attractive choice for purely functional implementations of logic programming sys- tems because of their fast extension time and linear space requirement, but have the disadvantage of costly lookup. We present several repre- sentations for triangular substitutions that decrease the cost of lookup to linear or logarithmic time in the size of the substitution while main- taining most of their desirable properties. In particular, we show that triangular substitutions can be represented eciently using skew binary random-access lists, and that this representation provides a signicant decrease in running time for existing programs written in miniKanren, a declarative logic programming system implemented in a pure functional subset of Scheme.