develooper Front page | perl.perl6.language | Postings from March 2005

Logic Programming with Rules

Rod Adams
March 9, 2005 00:41
Logic Programming with Rules
Message ID:
There's been rumblings on this list lately about making Perl perform more
Logic based programming functions, a la Prolog. Having done some work
with Prolog in academia, I fully understand why this is desirable.

It occurs to me that underlying functionality of Prolog is moderately
similar to the P6RE.

In particular, they both:
- ultimately declare a given assertion as true, or fail.
- backtrack like crazy, if needed, to get a given assertion to be true.
- have concepts of sub-assertions that take parameters.
- bind various variables to given values along the way, and report those
  values along the way.

Indeed, a great deal of logical testing can be performed with the
current P6RE definition.

For instance:

    rule Equal  ($x, $y) {{ $x ~~ $y or fail }};
    rule Substr (Str $str, Str $in) {{ $in ~~ /<$str>/ or fail }};
    rule IsAbsValue (Num $x, Num $y) {
        {$x ==  $y or fail} |
        {$x == -$y or fail} };

There are some things that are lacking, however. The first is that all
of the C<or fail>'s will get very old for typing and viewing. I would
propose that we add :a/:assert as a rule modifier, making all closures
assertions that behave exactly as if you typed a C< or fail > at the end
of each of them.

Also, since matching null is going to be rather common should one go
this route, I'd add a :z/:zerolength modifier, disabling that
restriction. It would probably make sense to have :a imply :z.

The really big problem, however, is the lack of generators.

I'll establish a working definition of "generator" as "something which
offers a possible value, giving the new value each time the
expression is backtracked over, and fails when there are no more
values to give". Clearly, desirable generators include lazy lists,
arrays, and closures. All of which P6RE supports as ways of attempting
different rules/strings to match against, but not as different values to
assign a given $<var> to feed into later rules. Capturing assumes a
string to match and capture against. Capturing the null string that I
"match" is not terribly useful.

The only suggestion I can give for how to do this is by introducing the
hyper operator. I'm very open to other ideas, because this one does not
sit well with me, but it's all I've got at the moment. So, to give an
array as a generator, one could write:

    /:a {$<x> »=« @values} <test($<x>)>/

which would have the net effect of $/<x> holding the first value in
@values that made the test work, assuming any of them did. I didn't use
the regular C< = > assignment because it would not distinguish between a
single function call and a function as an iterator.

After all that, I need multi-rules. Most specificly, I need to know if the
parameters being fed to me are already bound/defined. The purpose of
this is to write rules which act as both tests and pseudo-generators.

    multi rule Equal ($x where defined(),
                      $y where defined())
        {{$x ~~ $y}};

    multi rule Equal ($x where defined(),
                      $y where {!defined()} is rw)
        {{$y = $x}};

    multi rule Equal ($x where {!defined()} is rw,
                      $y where defined())
        {{$x = $y}};

Ideally I'd like something more like C< is Bound > and C< is Unbound >
more than those crufty C< where defined() >, but I don't think that
would mesh well with the rest of Perl6.

It's a lot more work to build than the equiv Prolog statement, but I
can't justify the level of effort it would take to define and implement
the auto-generation capabilities.

-- Rod Adams Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About