Notice

The website of Tom Schrijvers has moved to http://people.cs.kuleuven.be/~tom.schrijvers. Please adjust any links you maintain as this copy will be taken down shortly.


Heuristics Entwined with Handlers Combined


Tom Schrijvers and Nicolas Wu and Benoit Desouter and Bart Demoen.
PPDP 2014.
2014.

Abstract

A long-standing problem in logic programming is how to cleanly separate logic and control. While solutions exist, they fall short in one of two ways: some are too intrusive, because they require significant changes to Prolog’s underlying implementation; others are lacking a clean semantic grounding. We resolve both of these issues in this paper. We derive a solution that is both lightweight and principled. We do so by starting from a functional specification of Prolog based on monads, and extend this with the effect handlers approach to capture the dynamic search tree as syntax. Effect handlers then express heuristics in terms of tree transformations. Moreover, we can declaratively express many heuristics as trees themselves that are combined with search problems using a generic entwining handler. Our solution is not restricted to a functional model: we show how to implement this technique as a library in Prolog by means of delimited continuations.

BibTeX

@inproceedings{ppdp2014,
  title = {Heuristics Entwined with Handlers Combined},
  author = {Tom Schrijvers and Nicolas Wu and Benoit Desouter and Bart Demoen},
  year = {2014},
  booktitle = {PPDP 2014},
  url = {/Research/papers/ppdp2014.pdf},
  talk = {/Research/talks/ppdp2014.pdf},
  abstract = {A long-standing problem in logic programming is how to cleanly separate logic and
control.  While solutions exist, they fall short in one of two ways: some are
too intrusive, because they require significant changes to Prolog’s underlying
implementation; others are lacking a clean semantic grounding. We resolve both
of these issues in this paper.

We derive a solution that is both lightweight and principled. We do so by
starting from a functional specification of Prolog based on monads, and extend
this with the effect handlers approach to capture the dynamic search tree as
syntax. Effect handlers then express heuristics in terms of tree
transformations. Moreover, we can declaratively express many heuristics as
trees themselves that are combined with search problems using a generic
entwining handler. Our solution is not restricted to a functional model: we
show how to implement this technique as a library in Prolog by means of
delimited continuations.
  },
}