Log in

No account? Create an account
"Efficient representations for triangular substitutions: A comparison in miniKanren" - Lindsey Kuper [entries|archive|friends|userinfo]
Lindsey Kuper

[ website | composition.al ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

"Efficient representations for triangular substitutions: A comparison in miniKanren" [Oct. 28th, 2009|01:58 am]
Lindsey Kuper

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.


(Deleted comment)
[User Picture]From: lindseykuper
2009-10-29 04:52 am (UTC)
*flips through*

Chain pruning aka path compression? Actually, we do (but without side-effecting the substitution -- we just stick the last thing in the chain on the front of the substitution so it's faster to look up the next time). (Does path compression come from Cardelli? If so, awesome -- I was looking for an appropriate reference.)

We have a couple of other tricks for dealing with long chains, as well, but part of the gist of our paper is that we find that most of the substitutions that arise from running real miniKanren programs don't contain very long chains; rather, they're just big. So, we present some techniques that make real mK programs run faster. (Although our suite of "real" mK programs includes, you know, the Zebra Puzzle, so I guess "real" is debatable.)

Would you be interested in looking over the paper? I'd love to get comments from you (in a couple of days, probably, once I finish making all the revisions that are already on my list).
(Reply) (Parent) (Thread)
(Deleted comment)
[User Picture]From: lindseykuper
2009-10-30 07:19 am (UTC)
Great! I'll get it to you.
(Reply) (Parent) (Thread)
(Deleted comment)
From: (Anonymous)
2009-10-30 04:14 pm (UTC)
> By chain pruning I mean...

Hee. I love how reading this journal always gives me great tips for my own thesis... about a month or so after I've learned about the same principle the hard way.
(Reply) (Parent) (Thread)