I am currently developing a Haskell library for constraint functional-logic programming. It is in an early alpha stage (does not support higher-order functions and implements no constraint solvers) but can already be used to mimic simple lazy functional-logic programs in Haskell.
Recently, I thought about two seemingly different topics which turn out to form a fruitful combination.
One thing I have been thinking about a lot is how to model functional-logic programming in Haskell without using impure features to ensure call-time choice semantics of lazy computations. The other thing is how to integrate constraint solving in a purely functional setting, to improve the performance of test-case generation.
It turns out that a framework for constrained monadic computations is enough to express call-time choice in non-deterministic lazy computations. We can add constraint solving to any instance of the
MonadPlus type class and, hence, reuse existing instances of this class to model lazy functional-logic programming in pure Haskell.
Unhappy with the conclusion of this article, I began to develop a framework for lazy functional-logic programming in Haskell that allows to compare different search strategies in an in other respects identical environment. Specifically, I aim at comparing complete strategies like breath-first search or FBackTrack (cf. aforementioned articel) w.r.t. their run-time and memory requirements. Unlike described earlier, the combination of laziness and nondeterminism should conform to Call-Time Choice semantics without prohibiting compiler optimizations due to side effects.
At FLOPS 2008 Oleg Kiselyov showed me FBackTrack — a simple instantiation of the
MonadPlus class in Haskell which is fair (like breadth-first search) and seems to consume considerably less memory than BFS. I immediately started following an obvious plan: implement a traversal on Curry’s
SearchTree datatype treating choices like
mplus and values like