Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Who's a thief? -- the follow up

by Ovid (Cardinal)
on Jan 14, 2005 at 04:54 UTC ( #422158=perlmeditation: print w/ replies, xml ) Need Help??

This is just a little follow-up note to those who wondered what ever happened to my work with AI in Perl. This is part of it. (And it's cross-posted from my use.perl journal.)

OK, I finally got off my butt and checked Language::Prolog::Yaswi. The docs need some work and it helps if you know Prolog, and if you use a 5.1 or 5.2 version SWI-Prolog (compiled with thread support: ./configure --enable-mt) and a version of Perl compiled with ithreads. However, if you jump through all of those hoops, you can figure out Who's a thief?.

steals(PERP, STUFF) :- thief(PERP), valuable(STUFF), owns(VICTIM,STUFF), not(knows(PERP,VICTIM)). thief(badguy). valuable(gold). valuable(rubies). owns(merlyn,gold). owns(ovid,rubies). knows(badguy,merlyn).

In short, I finally admitted defeat and have stopped trying to do predicate logic in pure Perl. Implementing a predicate logic engine in pure Perl that is easy to use and extensible involves understanding streams, patterns, a pattern matcher and generating arbitrary streams from complex data structure and handling unification without the benefit of tail call recursion optimizations. In short, to fully enjoy the First Order Predicate Calculus in pure Perl involves writing an NFA regex engine that operates on data structures instead of strings.

I am not that smart.

I went ahead and used the SWI-Prolog version. And it works :)

#!/usr/local/bin/perl use strict; use warnings; use Language::Prolog::Yaswi qw/:query :assert/; use Language::Prolog::Types::overload; use Language::Prolog::Sugar functors => [qw/steals thief valuable owns knows/], functors => { NOT => 'not' }, # BUGFIX: this was in chains vars => [qw/PERP STUFF VICTIM/], chains => { AND => ',', }; swi_assert( steals(PERP, STUFF) => AND( valuable(STUFF), thief(PERP), owns(VICTIM, STUFF), NOT(knows(PERP, VICTIM)), )); swi_facts( thief('badguy'), valuable('gold'), valuable('rubies'), owns(qw/merlyn gold/), owns(qw/ovid rubies/), knows(qw/badguy merlyn/), ); swi_set_query(steals('badguy', STUFF)); while(swi_next) { print swi_var(STUFF), $/; }

Regrettably, this does not work with the latest version of SWI-Prolog, so be warned. I just emailed the author and hope to hear back soon on whether or not he plans an update.

Cheers,
Ovid

New address of my CGI Course.

Comment on Who's a thief? -- the follow up
Select or Download Code
Re: Who's a thief? -- the follow up
by sleepingsquirrel (Hermit) on Jan 14, 2005 at 17:09 UTC
    For inspiration on prolog in perl, you might want to take a look at chapter 24 of Paul Graham's On Lisp. He creates an embedded prolog-like language in about 200 lines of Common Lisp. I'd be willing to bet that a Perl implementation wouldn't be too much longer.


    -- All code is 100% tested and functional unless otherwise noted.

      He does that in Chapter 15 of ANSI Common Lisp, but I never checked it out. Thanks for the pointer. I tried working through the implementation in Structure and Interpretation of Computer Programs, but it quickly got a bit too hairy for me. I'll look at Paul Graham's version more closely, but one problem that happens with larger systems like this is the systems tend to rely heavily on recursion and this is not Perl's strength :/ Lisp and Scheme don't have this problem.

      Cheers,
      Ovid

      New address of my CGI Course.

        ...one problem that happens with larger systems like this is the systems tend to rely heavily on recursion and this is not Perl's strength :/
        You're not giving perl enought credit for what it can do. The following program executes in under 9 seconds on my (1GB) machine.
        #!/usr/bin/perl -w print deep(2_500_000); sub deep { $_[0]>0 ? deep($_[0]-1) : "done\n"; }
        ...and I can calculate the 36th fibonacci number using the simplistic algorithm below in about a minute. It ends up calling "fib" over 48 million times.
        #!/usr/bin/perl -w $count = 0; my $n = ($ARGV[0] < 1) ? 1 : $ARGV[0]; print fib($n)."\ncount = $count\n"; sub fib { $count++; $_[0]<2 ? 1 : fib($_[0]-2) + fib($_[0]-1) }


        -- All code is 100% tested and functional unless otherwise noted.
Re: Who's a thief? -- Quantum::Superpositions
by sleepingsquirrel (Hermit) on Jan 15, 2005 at 17:19 UTC
    In short, to fully enjoy the First Order Predicate Calculus in pure Perl involves writing an NFA regex engine that operates on data structures instead of strings.
    If you don't want to roll your own non-deterministic operators, you might want to use the ones provided by Quantum::Superpositions. Using that module would probably go a long way towards making your problem much more straight forward.


    -- All code is 100% tested and functional unless otherwise noted.

      Then again, it would also add another whole new level of sluggishness. Q::SP is nice, but it's also much slower than situation specific hand rolled solutions. :-/ So long as both your problem and the number of times it is solved are small, Q::SP is lovely, but it doesn't scale well at all.

      Makeshifts last the longest.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://422158]
Approved by rlb3
Front-paged by ysth
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (9)
As of 2014-08-28 00:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (254 votes), past polls