Logic Programming with Rules
Rod Adams
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())
:a
{{$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
Luke Palmer
> 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
GENERATE.
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
features...
Luke
* A = Awkward
Rod Adams
>Rod Adams writes:
>
>
>
>Or you could avoid the global modifier and write your tests in <( )>
>blocks instead... after all, that's what it's there for.
>
>
I *knew* I had seen a syntax for that before... I just didn't see it
when I scanned S05 for it.
I still want the :z modifier for matching zero length strings. That
makes sense to be global.
>>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...
>
>
I agree that * works that way... when you're matching against a
string... which I'm not. I intend for the basic call to be something
like C< "" ~~ /<test(1)>/ >, or more likely just C< /<test(1)>/ >. I
won't care what the current topic is. I'll match the empty string, and
everything that includes it, or nothing at all. My entire rule set will
be a series of really complex zero-length assertions.
>>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>)> /
>
>
I don't think this does what I want. In this, &generate returns a rule
or string of some kind, matches the string being tested, captures what
matches, and then binds the capture to $<x>.
I have no underlying string, so the match fails right there. I want to
bind/assign to the variable _without_ matching, but _with_ backtracking
and iteration over several values.
I also now notice that I would need a C< let > in my example above.
>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.
>
>
There were some thoughts in the back of my head about how I actually
wanted a closure to be handled as a generator. I see the need to
initialize it many separate times, once on each forward attempt, can be
repeated if something after it fails, and something before it has an
alternative. But I wanted the basic concept out there before I tried
diving into that kind of detail.
>Maybe we could unify the pattern proposal and your generation ideas for logic programming.
>
>
There might be unification with logical programming to be had, but I'm
not sure it's with the generation part of things.
> @array[$^i] # returns a lazy pattern of everything in @array, bound
> # together with the corresponding $i
>
>
How is this any different from just @array ?
> (@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.
>
>
This example is easily done as:
@a »+« @b
But it's also not terribly far removed from my hyperthreader operator in
the Junctions thread (oh, when, oh when is Damian coming back?). There
are differences, but see if that does what you need.
Not to mention that « » are already taken in that context as q:w//
operators.
>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 } /
>
>
Problems with this:
1) « » in RE's are already taken for non-capturing meta's. And binding
doesn't work if you don't capture.
2) you're still trying to match the value against the string.
Not really a problem, but I had C< <test($<x>)> >, not C<
<(test($<x>))> > on purpose. I was feeding into a rule, not a function.
>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.
>
>
I don't see what this gives me over a regular lazy list generation with
gather/take.
-- Rod Adams
Luke Palmer
> >
> >You could do all of this with a library of rules.
> >
> > / $<x>:=<generate(@values)> <test($<x>)> /
> >
> >
> I don't think this does what I want. In this, &generate returns a rule
> or string of some kind, matches the string being tested, captures what
> matches, and then binds the capture to $<x>.
You're right. We probably need something like:
/ <generate($<x>, @values)> <test($<x>)> /
I don't know when $<x> is hypotheticalized there, if at all. It needs
to be.
> >Maybe we could unify the pattern proposal and your generation ideas for
> >logic programming.
>
> There might be unification with logical programming to be had, but I'm
> not sure it's with the generation part of things.
I was decently insane last night. This generator stuff probably isn't
going anywhere. It's too abstract, and not precise enough, to be a
truly powerful part of the language.
Luke
Larry Wall
: I was decently insane last night. This generator stuff probably isn't
: going anywhere. It's too abstract, and not precise enough, to be a
: truly powerful part of the language.
I suspect it's another one of the many things we just try to
stay within hailing distance of without trying to solve for 6.0.0.
The worst that can happen is that someone later defines "use coolness"
to turn their program into something that doesn't interoperate
with standard Perl 6. Then we either bend Perl 6 to where it is
interoperable, or someone rewrites all the libraries for coolness.
Biologically, it comes down to more sex and a bigger gene pool,
or less sex and more speciation and specialization. Sex is fun,
but it probably doesn't solve all your problems.
Larry
Rod Adams
>I suspect it's another one of the many things we just try to
>stay within hailing distance of without trying to solve for 6.0.0.
>
>
That's cool.
I was just relaying the observation that the P6RE was fairly close to
being able to implement Logical Programming, which several people seem
to be trying to get into Perl in some fashion or another. I can easily
wait until 6.2 for this to happen (for now at least).
-- Rod Adams
Ovid
> I was just relaying the observation that the P6RE was fairly close to
> being able to implement Logical Programming, which several people
> seem to be trying to get into Perl in some fashion or another.
When I get a chance to talk to someone about logic programming, there's
frequently an "aha!" moment where they start to see some of the
potential, but then I inevitably get the question "if it's so powerful,
why ain't it rich?" (or something like that.)
The answer, I think, is that it's generally not available in the tools
that most people use. SQL, regexen and makefiles all dance around
logic programming -- well, makefiles sort of stumble -- but if LP was
more readily available, people would be more likely to appreciate it.
Unfortunately, while Prolog is a piece of cake to learn, this thread
made my head hurt.
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/
Rod Adams
>--- Rod Adams <r...@rodadams.net> wrote:
>
>
>>I was just relaying the observation that the P6RE was fairly close to
>>being able to implement Logical Programming, which several people
>>seem to be trying to get into Perl in some fashion or another.
>>
>>
>
>When I get a chance to talk to someone about logic programming, there's
>frequently an "aha!" moment where they start to see some of the
>potential, but then I inevitably get the question "if it's so powerful,
>why ain't it rich?" (or something like that.)
>
>The answer, I think, is that it's generally not available in the tools
>that most people use.
>
And I think there's a decent reason for that. They are two fundamentally
different ways of processing. One way is the strict following of
commands, the other is kind a "quest for truth", with only a limited
notion of order. I know SWI-Prolog has the ability to merge into C++,
but I can't imagine the C++ side being what one would consider a "smooth
integration".
What made me post the thread was the observation that Rules share a
great deal of the mentality of LP.
>
>Unfortunately, while Prolog is a piece of cake to learn, this thread
>made my head hurt.
>
>
I was starting off with getting the basic functionality present. After
that, one could write a library of macros to clean it up a great deal.
But come to think of it, it almost definitely makes more sense to port
Prolog or some other LP engine to Parrot, and then intermingle the
languages at that level. I don't think very many of us have fully
grasped what Parrot can do for Perl yet.
-- Rod Adams
Ovid
I've been thinking that this would be a fun project for me to cut my
Parrot teeth on. Specifically, porting AI::Prolog. However, porting a
proper WAM (Warren Abstract Machine) would be a better choice.
Now to find the tuits :)
Cheers,
Ovid
--