|"Efficient representations for triangular substitutions: A comparison in miniKanren"
||[Oct. 28th, 2009|01:58 am]
My colleague Dave and I are writing our butts off so we can submit a paper to FLOPS 2010! Here's the abstract, which I just turned in:
Unification, a fundamental process for logic programming systems,
relies on the ability to efficiently look up values of variables in
a substitution. Triangular substitutions, which allow associations
to values that are themselves bound by another association, are an
attractive choice for purely functional implementations of logic
programming systems because of their fast extension time and linear
space requirement, but have the disadvantage of costly lookup. We
present several representations for triangular substitutions that
decrease the cost of lookup to linear or logarithmic time in the
size of the substitution while maintaining most of their desirable
properties. In particular, we show that triangular substitutions can
be represented efficiently using deferred-extension skew binary
random access lists, and that this representation provides a
significant decrease in running time for existing programs written
in miniKanren, a declarative logic programming system implemented in
a pure functional subset of Scheme.
Yep, that says "deferred-extension skew binary random access lists". Best data structure ever! It's hilarious how I write about stuff like this, and then I go to job interviews and can't answer questions about hash tables.