Seminaïve Evaluation for a Higher-Order Functional Language
One of the workhorse techniques for implementing bottom-up Datalog engines is seminaive evaluation. This optimization improves the performance of Datalog’s most distinctive feature: recursively defined predicates. Under a naive evaluation strategy, many values are unnecessarily re-computed; seminaive evaluation computes (a safe approximation of) just the new values generated at each step. This optimization is critical, as it can asymptotically improve the performance of Datalog queries.
Seminaive evaluation is defined partly as a program transformation on sets of Datalog rules, and partly as a modification of the fixed point computation algorithm, and takes heavy advantage of the fact that Datalog is fundamentally a first-order programming language. This paper gives an extended version of this transformation which works on higher-order programs written in the Datafun language, which extends Datalog with features like first-class relations, higher-order functions, and datatypes like sum types.
|Presentation Slides (popl20-presentation.pdf)||1.73MiB|
Thu 23 JanDisplayed time zone: Saskatchewan, Central America change
11:45 - 12:30
|Seminaïve Evaluation for a Higher-Order Functional LanguageDistinguished Paper|
Neel Krishnaswami Computer Laboratory, University of Cambridge, Michael Arntzenius University of Birmingham, UKLink to publication DOI Media Attached File Attached
|Decomposition Diversity with Symmetric Data and Codata|
David Binder University of Tübingen, Julian Jabs University of Tübingen, Ingo Skupin University of Tübingen, Klaus Ostermann University of Tübingen, GermanyLink to publication DOI Media Attached