While the new iPods look fine, I was surprised to see the mess that was Apple’s Australian web site at 7:25 AM this morning.
Broken images everywhere and copy which refers to the old iPod nano. Surely the updates should have been ready for weeks, and deploying them should be a press of a button!
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:
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.
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:
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:
Do you suffer from Hindsight bias?
This is not one of those irritating quizzes which leave you thinking “But they didn’t ask the right questions!”, just a simple demonstration of hindsight bias.
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:
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. Read More
I’ve been programming in Java for the past 8 years. While I enjoy Java I think it’s important to keep your mind flexible and open by learning new languages where you have to think in different ways.About a year ago I decided to learn Haskell, which led on to an interest in CAL, a functional language which targets the JVM. (I find it hard to leave all the libraries available to Java behind.)The functional style is a bit of a revelation, and I fell in love with type inference—strong typing without the typing (of class names) so to speak! I have never been a fan of runtime-typed scripting languages like Ruby and Python, although they have many attractive features. I’ve found myself appreciating immutability much more, and being aware of reducing the amount of mutable state in my Java code.I’m still following functional languages in general and CAL in particular, (I wrote a very slow, but correct Endo DNA decoder in CAL for the 2007 ICFP contest, and plan to write a faster one) but I think it’s time to move on to a new language. Here’s my short list, for my next language and the future:
Prolog: A different paradigm, plenty of books and on line resources. I’ve installed SWI Prolog to play with.
Mercury: Mercury is a logic/functional programming language, with most of the logic programming capabilities of Prolog, but a Haskell style type system (Type inference, type classes). It is under active development right here in Australia.
Scala: Now that I’ve immersed myself in the functional paradigm, perhaps it’s time to try Scala, which supports both OO and functional programming and targets the JVM, which means that interfacing to Java libraries is easy. I have looked at Scala a couple of times and have always had the feeling that I wasn’t quite sure where to start—there seemed to be too many ways of doing the same thing. I’m sure a few hours of dedicated work would get me over that hump.
Erlang: Another functional language, Erlang would be worth learning for its approach to concurrency alone.
Inform 7: Out of left field comes Inform 7, a language for writing interactive fiction, aka ‘text adventures’. Amazingly English-like syntax, I’d like to find out more about it.
Objective C: I have a copy of Brad Cox’s original book on Objective C, written in 1986. That was the bad old days, when interesting new languages like Objective C and Eiffel cost thousands of dollars—all the languages I’m mentioning here have open source implementations. When OS X 10.5 arrives, Objective C will have ‘normal’ garbage collection, so it might be time for me to write a Cocoa application…
Scratch: Scratch is a very neat visual programming environment. It isn’t open source yet, although it is promised to be soon. It is geared towards little animated games, but can also interface to hardware. I think it is written in Smalltalk.