On 27 Mar 2008, at 4:23 pm, Benjamin L. Russell wrote:
After briefly searching the Internet and coming up with a page entitled "CIS587: The Wumpus World" (http://www.cis.temple.edu/~ingargio/cis587/readings/wumpus.shtml),
I think that since the statement of this problem there, involving the Situation Calculus, chiefly involves a sequence of logical statements with truth values and the relations between the statements, the statements there could perhaps initially be more directly applied with Prolog than with Haskell.
A solution to the problem is a sequence of actions. In Prolog, action(right). action(left). action(forward). action(shoot). action(grab). action(release). action(climb). solution(Actions) :- initial_state(State0), length(Actions, _), fill_in(Actions, State0). fill_in([], State) :- final_state(State). fill_in([Action|Actions], State0) :- action(Action), effect(Action, State0, State1), fill_in(Actions, State1). Now all that's left is to implement effect(Action, State0, State1), which means "(known) action Action can be carried out in (known) state State0 and results in state State1". By inspection, we can see that [forward,left,forward,forward,grab,left,shoot, left,forward,forward,right,forward,climb] will solve the problem, so we must search to a depth of 13, and have 7 actions to choose from, so a blind iterative-deepening search like this must check on the order of 1.1x10**11 states.
Also, you may wish to keep in mind the following differences between Haskell and Prolog: [snip]
* Haskell code tends to be more succinct (as Paul Johnson mentioned)
Not really an issue for this problem.
* Haskell code tends to run faster, and can often be optimized to run at a speed on par with OCaml
* Prolog tends to be one of the slowest-running programming languages
That largely depends on which compiler you use and what coding style you follow. I've known Prolog code outperform published Fortran for the same problem, thanks to using a better algorithm that was easy to express in Prolog and practically impossible in Fortran 77. The Prolog results at http://shootout.alioth.debian.org/ are only for the open source system SWI Prolog, which is basically a one-man effort. The commercial SICStus Prolog is substantially faster. Some of the Prolog benchmark versions look distinctly odd. It is certainly true that Prolog can be slow *if* you try to write conventional imperative code in it, which many people do. But then, conventional imperative code isn't the best way to use Haskell either. Prolog's strongly-typed-and-moded brother, Mercury, gives you a combination of - logic programming - strict functional programming - Haskell-like typeclasses which makes it a candidate. However, checking 1.1x10**11 states is going to take a while no matter *what* language you use. Looking at the problem again, we see that if you can get the gold and shoot the wumpus, then you can certainly get out again by retracing your steps, because the pits do not move around. So in the solution [forward,left,forward,forward,grab,left,shoot, left,forward,forward,right,forward,climb] the second line consists of steps that are entirely predictable from the first. So we *really* only have to search to a depth of 7, checking 9.5x10**5 states. That's a speedup of 117649, which is much more than you are going to get from ANY programming language. I should point out that Prolog is not well suited to *directly* expressing rules like Smelly(l1) = > (EXISTS l2 At(Wumpus,l2,s) & (l2=l1 OR Adjacent(l1,l2))) This is going to require some programming. Something that might be rather fun would be feeding the Wumpus World axioms to the free theorem prover OTTER, which is quite impressive.