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.

Benjamin L. Russell wrote:

Not all students and researchers can afford a Personal License. Can you recommend an alternative, fast Prolog development system under a free licensing agreement, such as GPL/GLPL?

For Mac users, https://www.cs.tcd.ie/open-prolog/ might be worth a look

Not all students and researchers can afford a Personal License. Can you recommend an alternative, fast Prolog development system under a free licensing agreement, such as GPL/GLPL?

SWI-Prolog is about the best and most popular open Prolog system: http://www.swi-prolog.org It's not the fastest, just like GCC doesn't generates the fastest code. Who cares? If you want speed, then Yap is the best open Prolog system. http://www.ncc.up.pt/~vsc/Yap/ Cheers, Tom -- Tom Schrijvers Department of Computer Science K.U. Leuven Celestijnenlaan 200A B-3001 Heverlee Belgium tel: +32 16 327544 e-mail: tom.schrijvers@cs.kuleuven.be url: http://www.cs.kuleuven.be/~toms/

--- "Richard A. O'Keefe" wrote:

[snip]

Let me contrast SICStus Prolog with GHC. I *have* a personal copy of SICStus on my SunBlade 100/Solaris 2.10 system which installed absolutely trouble free. I *did* have a copy of GHC, but trying to install GHC 6.4 took a great deal of my time and now I don't have a working GHC any more. So for me, GHC is by far the more expensive: I've spent considerably more than 500 Euros of my time and got nothing for it. Much though I admire Jan, I've also had such a lot of trouble installing SWI Prolog on various machines that SICStus was *really* cheaper than the "free" Prolog after all. I do wish people would remember that not all the world is Linux.

Sorry to hear about your troubles with GHC. Have you tried documenting your problems and sending an inquiry to the Glasgow-haskell-bugs mailing list (see http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs)? That mailing list is dedicated to GHC-related bugs, and they tend to be quite responsive. FWIW, I have GHC 6.8.2, which installed trouble-free, running on a Windows XP (Service Pack 2) system at work. I did customize it (after installation) to restore the original banner, but that was a customization, not a bug-fix, and I haven't encountered any bugs per se with it so far.

153 Euros (why did the Europeans name their currency after the Common Wallaroo?) is NZD 303 or about the price of two textbooks. (Three copies of Bird's introduction to functional programming would do it, if they shipped free.)

You're telling me that *researchers* can't afford the price of a couple of books?

It's more than that, actually, because, in my case, I also want to study it at home on a PPC-based PowerBook running Mac OS X 10.2.8 Jaguar, soon-to-be-upgraded to the PPC version of Mac OS X 10.5.x Leopard, soon-to-be-replaced by an Intel-based MacBook Pro running the Intel version of Mac OS X 10.5.x Leopard. And this is alongside studying it at work. Granted, SICStus Prolog does appear to be an extremely easy-to-install, fast, well-documented, stable, industrial-grade version of Prolog. It would probably provide an extremely pleasant and rewarding Prolog experience. It is probably well-supported as well. However, the Personal License of SICStus Prolog is only valid for a single computer running a single copy at any one time. So I would actually need to purchase a minimum of two licenses if I used it at both work and home and then went through the trouble of uninstalling each version of SICStus Prolog every time I upgraded my OS at home (which I usually don't do, because it costs already purchased time), and a maximum of four licenses if I chose not to uninstall. Now, 4 * 153 euros = 612 euros which is much more than the price of a couple books.

The academic licence isn't that unreasonable. 1560 Euros is NZD 3091, which is about one month of a TA's pay. Another 880 Euros gives you the right to give your students free binaries, however many students you have, year after year after year.

...

Can you recommend an alternative, fast Prolog development system under a free licensing agreement, such as GPL/GLPL?

There is, after all, GNU Prolog. The last time I saw any benchmarks, it was substantially faster than SWI, while not quite as good as SICStus.

See http://gprolog.inria.fr/ or http://www.gprolog.org/

Yes, GNU Prolog does seem one alternative. Thank you for providing the link. I'll have to compare and contrast it with SICStus Prolog and SWI-Prolog. Although the ease of installation of SICStus Prolog does seem enticing, the need to purchase a new license every time I use a different computer seems a little frightening. What happens if one day, my boss suddenly tells me I'm fired and prohibits access to my work PC for "security" reasons, thereby preventing me from uninstalling SICStus Prolog at work, and I then need to continue studying it on a different PC at a new job? Wouldn't I need to purchase another Personal License, at another 153 euros? There is no such thing as real job "security" in the current job market. This could happen without warning at any time, for any reason or even lack of reason.

For what it's worth, GNU Prolog's developers *do* realise that not all the world's linux.

Yes, but I'm not quite sure what you mean by this, since SWI-Prolog is also available on Windows, and I don't use Linux, either--I use Mac OS X. So who is it that believes that all the world is Linux? Benjamin L. Russell

On 27 Mar 2008, at 8:25 pm, Robert Wills wrote:

This might also be relevant: http://web.engr.oregonstate.edu/~erwig/zurg/

But note that the Prolog code that they compared against was, um, let's put this kindly, seriously naive. For example, (a) it has 36 SLOC. You can do it naturally in 20. (b) it has 8 predicates. You can do it naturally in 4. (c) it does lots of list munching, and that inefficiently. You can do it much more naturally with the only list being the solution. Indeed, a very minor rewrite from the natural code gives you a Prolog program where NO heap storage is allocated except the list of move names. (d) It generates candidate solutions and then rejects ones that take too long. It is easier and more natural to reject over-time paths before extending them to solutions, so the Prolog code they used for comparison is *structurally* inefficient. 30 years ago people were writing papers showing that Lisp was better than very badly written Prolog. Now they are writing papers showing that Haskell is better than very badly written Prolog. How things have changed! NOT. Also note that the paper says "The most important feature of Haskell that supports [the impression that Haskell is good at this kind of thing] is the availability of multi-parameter type classes..." and that Haskell 98 had no multi-parameter type classes, which are a pretty advanced part of the language for beginners to understand.