Towards a miniKanren with fair search strategies
We describe fairness levels in disjunction and conjunction implementations. Specifically, a disjunction implementation can be fair, almost-fair, or unfair. And a conjunction implementation can be fair or unfair. We compare the fairness level of four search strategies: the standard miniKanren interleaving depth-first search, the balanced interleaving depth-first search, the fair depth-first search, and the standard breadth-first search. The two non-standard depth-first searches are new. And we present a new, more efficient and shorter implementation of the standard breadth-first search. Using quantitative evaluation, we argue that each depth-first search is a competitive alternative to the standard one, and that our improved breadth-first search implementation is more efficient than the current one.
Thu 22 Aug
|15:20 - 15:55|
Gregory Rosenblatt, Lisa ZhangUniversity of Toronto, William E. ByrdUniversity of Alabama at Birmingham, USA, Matthew MightUniversity of Alabama at Birmingham | Harvard Medical SchoolLink to publication
|15:55 - 16:30|
|Link to publication|