The Effect of using a Trailing Persistent Array to Embed Logic Programming into a Functional Language

Logic programming is an important paradigm because of its declarative nature – a programmer declares values and facts and then the program executes by inferring their consequences via backtracking search and unification. There are many situations where logic programming allows elegant solutions that are difficult to emulate in other paradigms, such as implementing type inference or solving problems that require backtracking search. Unfortunately it is generally not feasible for a language to be purely based on logic – search spaces are often large or infinite and greater control is required, normally via constructs that move closer to other non-logical paradigms. An attractive approach that has been attempted by for example Felleisen [12] and Seres & Spivey [16] is to embed logic programming into a host language with rich control constructs such as a functional language. This report describes a new technique for implementing such an embedding that improves on previous embeddings by concealing trailing and reversion with the help of a persistent array data structure proposed by Baker [6]. This structure was recently used in a domain similar to ours with backtracking by Conchon & Filliatre [8]