Author:

Keywords:

prolog, logic programming, side effects, algebraic effect handlers, delimited control, program transformation, Science & Technology, Technology, Computer Science, Software Engineering, Computer Science, Theory & Methods, Logic, Computer Science, Science & Technology - Other Topics, cs.PL, 0801 Artificial Intelligence and Image Processing, 0802 Computation Theory and Mathematics, 0803 Computer Software, Computation Theory & Mathematics, 4602 Artificial intelligence, 4613 Theory of computation

Abstract:

Recent work has provided delimited control for Prolog to dynamically manipulate the program control-flow, and to implement a wide range of control-flow and dataflow effects on top of. Unfortunately, delimited control is a rather primitive language feature that is not easy to use. As a remedy, this work introduces algebraic effect handlers for Prolog, as a high-level and structured way of defining new side-effects in a modular fashion. We illustrate the expressive power of the feature and provide an implementation by means of elaboration into the delimited control primitives. The latter add a non-negligible performance overhead when used extensively. To address this issue, we present an optimised compilation approach that combines partial evaluation with dedicated rewrite rules. The rewrite rules are driven by a lightweight effect inference that analyses what effect operations may be called by a goal. We illustrate the effectiveness of this approach on a range of benchmarks.