Write a Blog >>
ICFP 2018
Sun 23 - Sat 29 September 2018 St. Louis, Missouri, United States
Sun 23 Sep 2018 10:20 - 11:00 at Frisco+Burlington Route - morning-2

Functional programmers have learned to emulate logic programming using the effect of nondeterminism, usually implemented as backtracking. However, backtracking search is often inefficient; logic programmers have explored other useful strategies. Datalog takes an extreme approach, allowing only predicates with finite extent. This allows bottom-up evaluation, which easily handles queries (such as transitive closure) that are inefficient to solve by brute-force search.

Datafun shows that higher-order functional programs can emulate Datalog using a bottom-up nondeterminism effect (a finite set monad) combined with monotone fixed points. Here, we sketch the translation to Datafun of a classic Datalog optimisation, seminaïve evaluation, which avoids needlessly re-deducing facts when evaluating a recursive predicate.

Datalog folklore suggests seminaïve evaluation can be understood in terms of derivatives; we substantiate this by showing that its analogue in Datafun can be defined by applying recent work by Cai et al. on derivatives for incremental computation in a higher-order setting.

Sun 23 Sep

Displayed time zone: Guadalajara, Mexico City, Monterrey change

10:20 - 11:00
Finding fixed points faster
Michael Arntzenius University of Birmingham, UK