Re: Wumpus World

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: Wumpus World

Paul Johnson-2
iliali16 wrote:
> Hi guys I have to build the wumpus world problem. I didn't start yet since
> this is the first time in my life I have to do something like that and I
> feel not confident in starting it. So I have basic idea of what prolog and
> haskell can do and I know a bit of Java. I am wandering if you can tell me
> which one is best to use to build this problem.Thanks couse I am really
> confused
>  
This sounds like a homework problem.  Any of those languages will do.  
Of course Haskell will be shorter.

Jump in, get started.  The way to solve a problem you don't understand
is to do any bit of it you do understand, and then look at the problem
again.

Paul.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Wumpus World

Benjamin L. Russell
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.

However, note that it has been demonstrated in the
following book that it is possible to consider logic
programming as a natural extension of functional
programming as well (although this book is on Scheme,
the concepts can be extended to Haskell as well):

* Daniel P. Friedman, William E. Byrd and Oleg
Kiselyov.  _The Reasoned Schemer._  Cambridge, MA: The
MIT Press, July 2005.
ISBN-10: 0-262-56214-6
ISBN-13: 978-0-262-56214-0
http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=10663

I would suggest that you read about both Prolog and
Haskell, take a look at the above book (after first
looking at its prerequisite, _The Little Schemer_),
and then compare whether you would prefer more
directly applying Prolog or using the above book and
extending it to apply Haskell.

Also, you may wish to keep in mind the following
differences between Haskell and Prolog:

* Prolog is initially better suited to representing
knowledge originally represented as a sequence of
logic statements and the relations among them

* Haskell is well-suited to writing programs that can
be expressed as mathematical functions, and
incorporates lazy evaluation, which allows delaying
the evaluation of an argument until evaluation is
required

* Haskell code tends to be more succinct (as Paul
Johnson mentioned)

* 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

I would also suggest that you take a look at the
HaskellWiki
(http://www.haskell.org/haskellwiki/Haskell), and in
particular, at the following example related to logic
programming:

* HaskellWiki Logic programming example:
http://www.haskell.org/haskellwiki/Logic_programming_example

Compare this example to examples of Prolog code, and
see which one suits your taste.

Lastly, when learning Haskell, please try to learn
from books, not tutorials.  Haskell has a very steep
learning curve, and is very difficult to cover
adequately in a short tutorial.  In particular, I
recommend the following titles:

* Hudak, Paul.  _The Haskell School of Expression._
New York: Cambridge University Press, 2000.
http://www.haskell.org/soe/
(Just make sure that you review your trigonometry
before reading this book, because some of the
exercises in it assume knowledge of trigonometry.  I
found this book extremely interesting, but discovered
that it does assume some domain knowledge in that
area.)

*  Kees Doets and Jan van Eijck.  _The Haskell Road to
Logic, Maths and Programming._  College Publications,
April 2004.
http://homepages.cwi.nl/~jve/HR/
A book that uses Haskell as a tool for learning about
logic and mathematics.  Nevertheless, the book is
highly readable, and does a good job of introducing
Haskell.  It also assumes less domain knowledge than
the above book.
(Write to me personally if you want more information
about this book.)

Good luck!

Benjamin L. Russell

--- Paul Johnson <[hidden email]> wrote:

> iliali16 wrote:
> > Hi guys I have to build the wumpus world problem.
> I didn't start yet since
> > this is the first time in my life I have to do
> something like that and I
> > feel not confident in starting it. So I have basic
> idea of what prolog and
> > haskell can do and I know a bit of Java. I am
> wandering if you can tell me
> > which one is best to use to build this
> problem.Thanks couse I am really
> > confused
> >  
> This sounds like a homework problem.  Any of those
> languages will do.  
> Of course Haskell will be shorter.
>
> Jump in, get started.  The way to solve a problem
> you don't understand
> is to do any bit of it you do understand, and then
> look at the problem
> again.
>
> Paul.
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Wumpus World

Richard A. O'Keefe
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.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Wumpus World

Robert Wills-2
In reply to this post by Benjamin L. Russell
This might also be relevant:
http://web.engr.oregonstate.edu/~erwig/zurg/


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Wumpus World

Richard A. O'Keefe

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.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Wumpus World

Benjamin L. Russell
In reply to this post by Richard A. O'Keefe

--- "Richard A. O'Keefe" <[hidden email]> wrote:

> [snip]
>
> 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.

The commercial SICStus Prolog is also substantially
more expensive (see
http://www.sics.se/isl/sicstuswww/site/index.html), at
153 euros for a Personal License (see
http://www.sics.se/isl/sicstuswww/site/order4.html).
Prices for Academic, Single-User Commercial, and
Multi-User Commercial licenses are even more
expensive, at 1560, 1980, and 7800 euros,
respectively.  An Evaluation License is only valid for
30 days.

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?

Benjamin L. Russell
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Wumpus World

Andrew Butterfield
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
>  

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Wumpus World

Tom Schrijvers-2
In reply to this post by Benjamin L. Russell
> 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: [hidden email]
url: http://www.cs.kuleuven.be/~toms/
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Wumpus World

jerzy.karczmarczuk
In reply to this post by Andrew Butterfield

> 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?

You have quite a choice if you relax your licensing requirements:

http://www.thefreecountry.com/compilers/prolog.shtml 

You will find there the GNU-Prolog, whose licensing should be as
you wish.

Jerzy Karczmarczuk


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Wumpus World

Richard A. O'Keefe
In reply to this post by Benjamin L. Russell
On 28 Mar 2008, at 10:59 pm, Benjamin L. Russell wrote:

> The commercial SICStus Prolog is also substantially
> more expensive (see
> http://www.sics.se/isl/sicstuswww/site/index.html), at
> 153 euros for a Personal License (see
> http://www.sics.se/isl/sicstuswww/site/order4.html).
> Prices for Academic, Single-User Commercial, and
> Multi-User Commercial licenses are even more
> expensive, at 1560, 1980, and 7800 euros,
> respectively.  An Evaluation License is only valid for
> 30 days.
>
> Not all students and researchers can afford a Personal
> License.

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.

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?

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/

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


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Wumpus World

Benjamin L. Russell

--- "Richard A. O'Keefe" <[hidden email]> 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
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe