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.
After my talk at FLOPS 2008, Chung-chieh Shan 單中杰 pointed out that — because test-case generation is a search problem — heuristic search techniques from AI could be applied to improve the usual-case performance of test-case generation. Specifically, he pointed me at Adaptive Tree Search (ATS) which aims at finding good leaves in a search tree early by guiding the search based on the quality of leaves found earlier.
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
Until I write my own stuff on resource-based web applications, look what others wrote about REST..
foldr is a versatile function for list processing:
foldr cons nil  = nil foldr cons nil (x:xs) = cons x (foldr cons nil xs)
It replaces every
nil. If you apply this idea to FlatCurry dataterms instead of lists, you can define selectors, test and update operations and useful auxiliary functions based on one primitive for each datatype inspired by the
foldr idea. You get over 800 lines of boring code and you never need to rewrite it for your program transformations. Just watch FlatCurryGoodies and use the versatile predefined functions to do exactly what you need.