This Lambda the Ultimate post links to a paper which compares writing a search algorithm in Prolog and Haskell, and notes that Haskell’s strong typing makes the task easier. While the paper mentions several embeddings of logic programming into functional languages it doesn’t mention Mercury.
I was able to easily create successor and goal predicates for this problem which work with the breadth first searching predicate I wrote earlier. Note that there is one significant shortcoming in my implementation — because I use lists where I should be using sets in the representation of nodes in my search space, nodes which should be equal are not, so the search takes far longer than it should. But it makes the point that Mercury’s discriminated unions and type system give a Prolog-like language the same benefit which Haskell’s type system gives a functional one.
The code for the solve client follows:
(more…)
The examples of state space searching described previously have all been tailored to a particular problem — the algorithms have been general, but the implementation has included type signatures specific to the problem, e.g.:
:- type block ---> a; b; c.
:- type stack == list(block).
:- type situation == list(stack).
:- type solution == list(situation).
:- pred solve(situation::in, solution::out) is nondet.
It would be convenient if we could write a ’solve’ predicate which would work with any problem, stated correctly.
To do this we will parameterise ’solve’ by the type of the nodes in the state space (i.e. block in the example above), and make the predicates which define our goal and produce our successors into parameters passed to ’solve’.
This gives us the Mercury interface:
:- interface.
:- import_module list.
/* the type of the successor predicate to be used by the solve predicate */
:- type succ_pred(T) == pred(T, T).
:- inst succ_pred == (pred(in,out) is nondet).
:- mode succ_pred_in == in(succ_pred).
/* the type of the goal predicate to be used by the solve predicate */
:- type goal_pred(T) == pred(T).
:- inst goal_pred == (pred(in) is semidet).
:- mode goal_pred_in == in(goal_pred).
:- pred solve(succ_pred(T)::succ_pred_in, goal_pred(T)::goal_pred_in, T::in, list(T)::out) is nondet.
And our predicates for searching for a path in a directed graph are defined like this:
:- type node ---> a; b; c; d; e; f; g.
:- pred s `with_type` succ_pred(node) `with_inst` succ_pred.
s(a,b).
...
s(e,g).
:- pred goal `with_type` goal_pred(node) `with_inst` goal_pred.
goal(Situation) :-
Situation = g.
The complete source code for the two modules is below the fold.
(more…)
One disadvantage of the depth first search with iterative deepening is that it regenerates all the search paths from the start node every iteration. A true breadth first search, as described by Bratko on pages 250-252 doesn’t need to do that — it can start with a short search path (just the start node in fact) and then extend the current paths by one node each iteration. This trades space for time, as it needs to keep all the current candidate paths in memory.
The algorithm is applied to the same block domain as in our previous examples. Note that we use the Mercury trace goal to print the sets of paths as they are generated:
(more…)
Our last algorithm gave us a result much longer than the shortest possible. We can improve that by generating first all paths of length one, then two and so on, until we find one which reaches a goal state.
Bratko describes this on pages 248 and 249.
This version arrives at the optimal solution:
[[[c, a, b], [], []],
[[a, b], [c], []],
[[b], [a], [c]],
[[], [b, c], [a]],
[[], [a, b, c], []]]
As Bratko mentions in Exercise 11.3 this algorithm will loop indefinitely if there is no solution. I will try to implement a solution to 11.3 in Mercury — the Prolog version uses a cut, so that at least will need to be changed.
The iterative deepening code is again just a minor modification:
(more…)
The algorithm implemented in my previous post pays no attention to the nodes in the search space already visited, so if the situation [[c,a,b],[],[]] is used as the starting point an infinite recursion will result, as the successor function starts to traverse a cycle in the state space graph before it finds a goal node.
On pages 246 and 247 (figure 11.7) Bratko adds cycle detection:
(more…)
I’m working through Bratko’s “Prolog Programming for Artificial Intelligence” rewriting the examples in Mercury.This series of posts will be my notes on the changes I needed to make to make these programs work.Page 243-244, defining successor states for stacks of blocks and performing a depth first search. Note that it’s a naive depth first search assuming no cycles.
(more…)