Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Fw: Logic Programming for Perl6 (Was Re: 3 Good Reasons... (typo alert!))

10 views
Skip to first unread message

Ovid

unread,
May 25, 2006, 2:45:19 PM5/25/06
to perl6-l...@perl.org
Larry pointed out that this topic is better suited for perl6-language instead of perl6-users, so I'm forwarding this along. Feel free to exercise your "delete" key.

Cheers,
Ovid

-- If this message is a response to a question on a mailing list, please send follow up questions to the list.

Web Programming with Perl -- http://users.easystreet.com/ovid/cgi_course/

----- Forwarded Message ----
From: Ovid <publiustemp...@yahoo.com>
To: perl6...@perl.org
Sent: Thursday, May 25, 2006 11:40:54 AM
Subject: Re: Logic Programming for Perl6 (Was Re: 3 Good Reasons... (typo alert!))

----- Original Message ----
From: David Romano <david....@gmail.com>

> > duplicate results and this is almost always wrong. (See http://use.perl.org/~Ovid/journal/28378
> > for an SQL example of this problem).
> I re-read your journal entry and comments (I had read it back when you
> first had posted it), and I'm curious about what obstacles that you
> think need to be overcome for Perl6 to support logic programming.

If anyone wants to know what the heck this is about, you can read http://search.cpan.org/dist/AI-Prolog/lib/AI/Prolog/Article.pod

That's an article I originally had published in The Perl Review (http://www.theperlreview.com/) and it explains the basics of logic programming and how to do it in Perl5. It also explains the append/3 predicate, something I mention below.

The first hurdle would be the syntax. The programmer just looking at the code would need to know when one section of code represents a snippet of logic programming. Is the following a function call or a Prolog fact?

loves( 'foo', 'bar' );

How would one assert facts and rules in Perl6? How would one know that a variable is a logic variable and not a normal one? Assignment to a logic variable which is still subject to rebinding could break code. On the other hand, using normal variables for logic variables could let us use objects for them and I think this might get us contraint programming (long story).

There's also the question of non-logical behavior in logic programming. What happens if you try to use math in Perl6 logic programming? Generally speaking, math is "non-logical" in the sense that it's used in Prolog (see the aforementioned article). Opening and reading from a file is also non-logical (you can't backtrack over it). How are those issues to be handled?

My biggest concern, though, is a rule like the following:

customer_cities(City) :-
700 <= credit_rating(Customer),
customer(Customer, City).

That's logically equivalent to the SQL I posted in a previous email and, like that SQL, will very likely return duplicates. Prolog students are constantly faced wtih the "how do I get rid of duplicates?" problem. This results in inefficient queries and a lot of time spent culling the duplicate answers when the person just wants to know the list of cities which meets their requirements.

Perl6 grammars may be able to assist with this, but grammars (as far as I can tell) are still based around strings and not data structures. Admittedly, Prolog is essentially a fancy string rewriting system, but it's not clear how the grammars would be applied to this problem.

For anyone familiar with logic programming and the append/3 predicate, here's one way of representing it in Perl5:

use re 'eval';
my $string = "abc";
my $length = length $string;
my $regex = qr/(\G[$string]{0,$length}(?{print "# [$&][$'][$string]\n"}))/ x 2;
$string =~ $regex;

Can you say "yuck"? However, that only represents a limited subset of append/3's functionality and trying to generalize it would be a very difficult task. One approach might be to write a wrapper around http://www.perlmonks.org/?node_id=318350. That's an approach I found to leverage Perl5's regex engine for logic programming, but I discovered that Perl5's regexen aren't re-entrant, killing that project. Perl6 rules might be perfect for this.

In short, there are lots of questions which would need to be answered to get logic programming done correctly in Perl6. I'm quite happy that @Larry decided not to answer those questions since things would have been delayed. We can hack in logic programming later.

Cheers,
Ovid

-- If this message is a response to a question on a mailing list, please send follow up questions to the list.

Web Programming with Perl -- http://users.easystreet.com/ovid/cgi_course/


Jonathan Lang

unread,
May 25, 2006, 8:05:42 PM5/25/06
to Ovid, perl6-l...@perl.org
Hmm...

How about this:

Treat each knowledge base as an object, with at least two methods:
.fact() takes the argument list and constructs a prolog-like fact or
rule out of it, which then gets added to the knowledge base.
.query() takes the argument list, constructs a prolog-like query out
of it, and returns a lazy list of the results.

There would be a default knowledge base, meaning that you wouldn't
have to explicitly state which knowledge base you're using every time
you declare a fact or make a query.

--
Jonathan Lang

mAsterdam

unread,
May 26, 2006, 3:54:14 AM5/26/06
to perl6-l...@perl.org
Ovid wrote:

> Larry pointed out that this topic is better suited
> for perl6-language instead of perl6-users, so I'm
> forwarding this along.

Is there a reason perl6-users isn't fed through to nntp.perl.org ?
Maybe it is but I don't know to which group?

Ruud H.G. van Tol

unread,
May 26, 2006, 4:41:04 AM5/26/06
to perl6-l...@perl.org
mAsterdam schreef:
> Ovid:

news://nntp.perl.org/perl.perl6.users

There is also

perl.perl6.announce
perl.perl6.compiler
perl.perl6.documentation
perl.perl6.internals
perl.perl6.language

--
Groet, Ruud

Sage La Torra

unread,
May 26, 2006, 10:46:05 AM5/26/06
to perl6-l...@perl.org
From a language standpoint, I think this is a great solution. As Jonathan
suggests, have a default knowledge base that is referenced by default, with
the option to declare more knowledgebases. Each one can have facts set and
queries exectued seperately. I have only a passing knowledge of Prolog, but
I think this should handle Logic programming, as long as Perl facts and
queries have the same elements as their Prolog equivalents.

From an internal standpoint, I think this may be slightly harder to do.
While this is a great syntax for the problem, some of the other issues David
mentioned were internals oriented. Obviously, that's beyond this list, but
the internal implementation of this may be a bit trickier.

Sage

Brad Bowman

unread,
May 27, 2006, 1:44:19 AM5/27/06
to Ovid, perl6-l...@perl.org

Hi,

I used AI::Prolog once briefly, and that's the extent of my logic programming
knowledge. There do seem to be a few Perl 6 features that may be useful for
logic programming, although I'm not really qualified to judge.

> How would one assert facts and rules in Perl6? How would one know
> that a variable is a logic variable and not a normal one? Assignment
> to a logic variable which is still subject to rebinding could break
> code. On the other hand, using normal variables for logic variables
> could let us use objects for them and I think this might get us
> contraint programming (long story).

"let" variables and "hypothetical" assignments within rules may be a
good starting point.

Hypothetical variables are mentioned here:
http://dev.perl.org/perl6/doc/design/syn/S04.html#Definition_of_Success

While they usually occur within rules, hypothetical assignments can
be to a target variable:
http://dev.perl.org/perl6/doc/design/syn/S05.html#External_aliasing

and "let" can now be used in any other closure.

More details in A05:
http://dev.perl.org/perl6/doc/design/apo/A05.html#Hypothetical_Variables,_er_Values

> There's also the question of non-logical behavior in logic
> programming. What happens if you try to use math in Perl6 logic
> programming? Generally speaking, math is "non-logical" in the sense
> that it's used in Prolog (see the aforementioned article). Opening
> and reading from a file is also non-logical (you can't backtrack over
> it). How are those issues to be handled?

Closures may have an "undo" trait which should be written to revert
the side-effects of the closure when it receives an UNDO control
exception (the block fails, see Definition of Success above).

http://dev.perl.org/perl6/doc/design/syn/S04.html#Closure_traits

For file reading the undo would seek back to the correct point.
This does require the programmer to code the undo operation, which
may not be possible (with non-seekable handles for examples).

Are there other languages that blend logic and imperative styles that
can be stolen from?

> Perl6 grammars may be able to assist with this, but grammars (as far
> as I can tell) are still based around strings and not data
> structures. Admittedly, Prolog is essentially a fancy string
> rewriting system, but it's not clear how the grammars would be
> applied to this problem.

There's some information about this in S05, with more info promised:

http://dev.perl.org/perl6/doc/design/syn/S05.html#Matching_against_non-strings

Brad

--
Dohaku's wife suffered some severed fingers. Dohaku's wound was a severed
neck bone, and since only his throat remained intact, his head hung down in
front. Now boosting his head up with his own hands, Dohaku went off to the
surgeon's. -- Hagakure http://bereft.net/hagakure/

Ovid

unread,
May 27, 2006, 2:34:44 PM5/27/06
to perl6-l...@perl.org
----- Original Message ----
> From: Brad Bowman <li...@bereft.net>
>
> "let" variables and "hypothetical" assignments within rules may be a
> good starting point.

Hi Brad,

Caveat: I'm also tremendously underqualified to to make serious proposals here.

Interesting idea. As I understand hypothetical variables, they are similar in concept to variables in Prolog, but they still have the problem that they really are variables which can be assigned to. Thus, if you have a "logical" iterator binding values to variables and someone else assigns a value, what then? You can break everything in very mysterious ways. That's why Luke Palmer (I think it was Luke) suggested a "twigil" for the variables:

let $`x = 3;

That could be a logic variable which could only be assigned to hypothetically. Any initial assignment to a logical variable would effectively be declaring a constant.

> > There's also the question of non-logical behavior in logic
> > programming. What happens if you try to use math in Perl6 logic
> > programming? Generally speaking, math is "non-logical" in the sense
> > that it's used in Prolog (see the aforementioned article). Opening
> > and reading from a file is also non-logical (you can't backtrack over
> > it). How are those issues to be handled?
>
> Closures may have an "undo" trait which should be written to revert
> the side-effects of the closure when it receives an UNDO control
> exception (the block fails, see Definition of Success above).

Hmm, the only real problem, as you noted, is having to explicitly code the UNDO behavior, but for non-logical behaviors, maybe that's not too bad? Still, what would happen with deleting a file? It's very likely that you can't easily UNDO that, so certain behaviors can't be backtracked over. I wonder how Mercury and Haskell handle issue like this? (I realize Haskell is functional and not logical, but I still don't know how their monads work or if they would be applicable :)

> There's some information about this in S05, with more info promised:

> http://dev.perl.org/perl6/doc/design/syn/S05.html#Matching_against_non-strings

Ooh, looks promising. In that scenario, is a hash viewed as an array of pairs? If so, we could potentially have logic programming matching just about any abitrary data structure.

0 new messages