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

Re: Logic Programming with Rules (and Argument Patterns)

Luke Palmer
March 9, 2005 02:13
Re: Logic Programming with Rules (and Argument Patterns)
Message ID:
Rod Adams writes:
> 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.

Or you could avoid the global modifier and write your tests in <( )>
blocks instead... after all, that's what it's there for.

> 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".

One generator is the * combinator.  It gives the longest string, then
the next shorter, then the next shorter...

> 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>)>/

You could do all of this with a library of rules.

    / $<x>:=<generate(@values)>  <test($<x>)> /

How the <generate> rule is actually written is getting into some rule
engine internal stuff, but we're making sure that the rule engine has
enough hooks to do that.

I think you'll be interested in where my 'Argument Patterns' proposal
was going next, before I ran off to class (and got scared of posting it,
because people would get scared of me).  But it seems to be related to
what you're talking about.  Maybe we could unify the pattern proposal
and your generation ideas for logic programming.

[WARNING: highly speculative, abstract, scary content ahead]

You can create patterns outside of argument lists, too.  One kind of
pattern that we're already familiar with is the junction (that's right,
I just redefined what a junction is). If you give a pattern to an array
as a subscript, it returns the pattern that matches each thing
referenced by any subscript pattern, if that makes sense.  

Now, certain types of patterns can be generated.  What exactly can be
generated depends on what types of patterns implement a GENERATE method
that succeeds when you call it.  

Allow me to use $^ as a 'pattern variable' marker for outside of
parameter lists.

    @array[$^i]  # returns a lazy pattern of everything in @array, bound
                 # together with the corresponding $i

    (@array[$^i]).GENERATE   # generates every element of @array

Now, let's just combine that with another array pattern:

    @a[$^i] + @b[$^i]  # returns lazy pattern of everything in @a
                       # added to its corresponding element in @b
    (@a[$^i] + @b[$^i]).GENERATE  # vector sum

Now if we just spell .GENERATE with «»:

    « @a[$^i] + @b[$^i] »

We have my tensor-hyper proposal back.

Not only does it work with arrays, it works with any combination of
things that can be generated.  This includes arrays whose shapes are not
declared, hashes, even roles if their implementor decides to implement

Now «» could have a similar meaning within rules, which would give you
your generator.

    # print everything in @array that matches test()
    / $<x> := «@array[$^i]»  <( test($<x>) )>  { say $<x>; fail } /

Of course, that can much more easily be done with a grep, but hey,
TMTOAWTDI*, right?

The biggest question is how this interacts with sub calls.  We can't
really expect sub calls to be pattern-aware: that puts constraints on
what we're allowed to do in a sub (no side-effect constraints; gee,
those kinds of constraints really go a long way).  But &test could
certainly implement a GENERATE method:

    sub is_prime(
        $x will GENERATE { primes() }
        ?grep { $_ == $x } primes()

The will generate says that the sub can accept a generic pattern and
will fill it in on the spot.

That's my first-order approximation.  There is probably some higher
order stuff that proves that I'm way off.

In particular, it would be great if this stuff could be crammed into a
library, but I understand that that would be very hard for such


* A = Awkward Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About