The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Math-Logic-Predicate-0.03
River stage zero No dependents
++
/ Math::Logic::Predicate

NAME

Math::Logic::Predicate - Manage and query a predicate assertion database.

VERSION

Math::Logic::Predicate version 0.03, July 28, 2002. I first began work on this module July 26, 2002.

SYNOPSIS

    use Math::Logic::Predicate;
    
    $db = new Math::Logic::Predicate;

    # Enter some predicates into the database
    $db->add(<<EOA);
        human(lister).
        human(kochanski).
        plays(lister, guitar).
        smart(holly).
        smart(rimmer).
        name(lister, 'Dave Lister').
        name(kochanski, 'Kristine Kochanski').
        name(rimmer, 'Arnold Rimmer').
    EOA

    # Retract a predicate
    $db->retract( 'plays(lister, guitar)' );
    # Or based on a pattern
    $db->retract( 'smart(_)' );

    # Make a query
    $query = $db->parse( 'human(H) & name(H, X) ?' );
    $iter = $db->match($query, $iter);

    # Get the results
    $name = $db->get($iter, 'X');
    
    # Store it in a rule
    $db->add( 'human_name(H, N) := human(H) & name(H, N).' );
    
    # Use it in a query
    $iter = $db->match( 'human_name(lister, N) ?' );
    
    # Save it to a file
    use Storable;
    store($db->rules, 'red_dwarf');

DESCRIPTION

Overview

Math::Logic::Predicate implements a solver for a subset of First Order Predicate Calculus. By version 1.0, it will support the entire First Order Predicate Calculus. It provides:

%

A miniture Prolog-like language with which to specify rules and predicates.

%

The option to not use that language and build rules by hand.

%

A fast solver.

%

The ability to specify coded rules, rather than asserted ones (see below).

%

A smart data organizer, to make solving even faster.

And it differs from the Predicate Calculus as follows:

%

You may only use the existential quantifier in queries.

%

You may only use the universal quantifier on variables in assertions. To use the existential quantifier, you must know precicely which object it is you are talking about.

%

There is no support for functions, that is, properties of objects, beyond simple predicates.

Fortunately, the first two of these are often what you need, and the last poses no restriction on what is representable; however, its existance does make things a lot easier in some cases. All of these things will be implemented soon.

Using Math::Logic::Predicate

Math::Logic::Predicate is fully object-oriented and is created in the standard way. There is no set up beyond this, except for just adding the rules you want.

As far as this goes, Math::Logic::Predicate supports two methods: A high-level and low-level specification. Really the high-level is just a small Parse::RecDescent grammar interface, but it helps a lot. The low-level is better for automated building, for instance, when traversing a parse tree (Though I plan to make this easier to use, as it's strangely reminiscent of C, and that's just terrible).

The High Level Interface

This interface uses a parser to implement a small Prolog-like language in which you can specify rules and assertions. This language is described here.

To assert something, follow it by a period. To query, follow with a question mark.

    color(orange, orange).      # Assertion    
    color(orange, orange)?      # Query

(Note that comments are not recognized and would result in a syntax error.)

In the above example, the word "color" is the predicate and the "orange"s are it's arguments. In multi-argument predicates, the first argument usually refers to the target and the rest to properties of the target (seems a little like Perl's OO style, doesn't it?).

Variables start with uppercase letters (by default; see below) and can appear anywhere. If they are used in an assertion, they refer to a "wildcard" which matches anything. You can use the special variable _ as an anonymous variable if you don't need to use it later. If you use them as the predicate itself, it will only work if the variable is already bound (i.e. already has a value).

    color(orange, X)?           # X now refers to the color of an orange
    color(Everything, black).   # The gothic ideal

I have only used symbols so far, but everywhere I used /\w+/, I could use a whole variety of data types.

    weight(duck, 13.75).
    weight(witch, 13.75).

    speech('Old man from scene 24', 'Who would cross the Bridge of Death...').
    q{Favorite color}(galahad, "Blue--no, yel--ahhhhhhhhh").

Note that if the first character of a string is a capital letter, it doesn't count as a variable.

Of course, to get more use out of predicates, you have to chain them. To make a list of dependent predicates, do this:

    weight(duck, W) & weight(X, W) ? # Find all things X that
                                     # weigh the same as a duck

The & denotes "and," where following predicates will match only if the predicate to the right does. There's also | "or," which guarantees that only one of the series will bind it's argumens. And finally, there's - "minus," which succeeds only if left side succeeds and the right side fails. These all end up working like you expect.

For instane, to find all humans or holograms X that aren't smart:

    human(X) | hologram(X) - smart(X) ?

All operators are left-associative and have the same precedence.

To define a rule, i.e. a predicate that expands to a query, use the := operator.

    dumb_human_like(X) := human(X) | hologram(X) - smart(X).

Then you can use dumb_human_like in place of that other long string. You get another benefit: rules can recurse.

Finally, you can define a rule to execute Perl code instead of going through the matcher. See the section on that below.

Interface Functions

There's just a couple of functions involved here. You can add a rule to the database with add:

    $db->add( 'color(orange, orange).' );

You can retract a rule from the database with retract:

    $db->retract( 'color(_, orange).' );  # Get rid of all orange things

You can create a rule or query without doing anything with it with parse.

    $query = $db->parse( 'human(X) - smart(X)?' );

You need this to match pattern, which is the hardest part. First, you need an iterator, which stores your results and is capable of getting the rest of the answers.

    $iter = $db->match($query, $iter);      # Get the first match

Once the iterator is defined, you need to pass it to match. You don't have to the first time, but I do for consistency. You get the variable you want out of $iter:

    $dumb = $db->get($iter, 'X');

And to get the next match, call match again with that iterator as an argument.

    $iter = $db->match($query, $iter);      # Get the next match

When there are no more iterators, match returns undef. Keep in mind that the assignment in that last one was still just for consistency; match modifies $iter in place.

You can throw away the iterator once you're done with that particular query.

How It Works

If you're wondering why this section is awkwardly in the middle, it's because you'll need to know it to write embedded code. So, say you have a query:

    month(X) & person(X) ?

This finds all people who are named after a month of the year (with suitable definitions of month and person). Say we're running that on top of this data set:

    month('January'). month('February').            # ... et cetera
    person('Larry'). person('Damian').              # ... and of course
    person('April'). person('May'). person('June'). # ... et cetera

It would start in by looking at month, and trying the first thing it found that would fit into X, which would be "January." Since month succeeded, it would move on to person, fill in the variable, and see if person('January') existed. Well, she doesn't, so it backtracks to month and tries the next month. It tries them in alphabetical order; strings first, then numbers, then symbols (I munged a bit, as the example didn't take note of this).

It does this up until "April." Then it tries person('April'), succeeds and returns from match, with X bound to "'April." (Remember the apostraphe thing?) If you tell match to try again, it goes back as if whatever came after person had failed. It sees if there's another person named "April," and since there aren't, it goes back to month. Finally, if month fails, it backtracks through the beginning, which causes the whole query to fail.

In an | "or," each operand is tried in sequence, as if you had taken all the others out.

    human(P) | hologram(P) | android(P) ?

This first returns a match for each human, then each hologram, then each android. Each one is tried only when it needs to be. On backtracking, it's only tried again if it's the one that was tried going forward.

In a - "minus," the second operand is only tried if the first one succeeded. That's because nothing minus anything (in set theory) is still nothing. The second rule of a minus never tries on backtracking.

Embedding Code

The built in data management is quite useful, but sometimes you'd like more functionality; for instance, the ability to do arithmetic, or the ability to print the value of a variable en passent. So rather than trying to satisfy everyone by bloating with built-in predicates, I just allow you to write your own.

    print(X) := { $track ? print "$X\n" : undef }.

Let's talk about that. First, you can only embed code like that if you give it a name. You can't put it in the middle of a chain.

    # WRONG
    printcolors := color(X) & { $track ? print "$X\n" : undef } & fail.

In that example, $track tells us if we're matching or backtracking. It will be true when matching, and false otherwise. Usually you don't want your predicates to do anything on backtracking but fail.

$X is conveniently bound to the variable X, so you can just use it. If X was not bound upon entrance, it will be undef. To bind it, just assign to it (note that it works a lot of magic to make it this easy). To unbind a variable, just undef it.

There's one more special variable: $local. It's a reference to a hash where you can store persistant local data. Each time $track is true, you get a new $local. Thus, $local is a good place to store an iterator (incidentally, it's where normal-behaving predicates store their iterator data).

Here's an example predicate whole which says whether it's argument is a whole number. If it's argument was unbound, it gives all whole numbers starting from 1.

    whole(X) := {
        if (defined $X) {
            $track ? $X =~ /^[1-9]\d*$/ : undef
        }
        else {
            $X = ++$local->{num}
        }
    }.

(Don't forget that period.) You could combine that with the print example above to print all numbers in [1, inf):

    whole(X) & print(X) & fail ?

The fail needs to be there so the query doesn't succeed and exit.

The Low Level Interface

This interface is pretty yucky, but it's faster than building a string and running it through the parser (but don't use it just because of that). It's also good for automated generation of queries and rules.

Basically, everything is called a procedure. You can make a procedure using newproc. newproc takes the following form:

    $proc = $db->newproc($name, [ @args ], $context, $next, $prev);

$context and $next are optional.

$name is a string containing the name of the new procedure. It should start with a lowercase letter, a number, or an apostrophe indicating that it's a string. This can be accessed through $proc->{rule}.

@args (or $args if you already have a reference) is a list of the arguments that this procedure takes. They should all be strings (for now). If they start with a capital letter or an underscore, they are assumed to be a variable. As before, if they start with an apostrophe, they are a string, and anything else, they are a constant. This can be accessed through $proc->{args}.

$context is a string indicating the context of this procedure. In a chain, this is the type of operator that comes before it (or "and" if it's the first). This can be accessed through $proc->{context}. Valid contexts are:

true

Indicating that this procedure is always true, but in only one way (this is often what you want).

false

At the moment, does exactly the same as the rule not being defined at all. See the "Future Direction" section.

and

Indicates that the match should only proceed if this procedure matches.

or

Indicates that this procedure may be entered without it's preceeding one necessarily matching. Also that if it's preceeding one did match, that this should blindly succeed.

sub

Indicates that this procedure may only proceed if its preceeding one succeeded (whew!) and this one failed.

bind

Indicates that this is the left side of a binding (:=) operation.

Finally, $next and $prev are references to the next and previous items in the chain. These can be accessed through $proc->{next} and $proc->{fail} (because this is where it goes when it fails), respectively. If you supply $next, $next's $prev is set for you, so long as it's not already set.

You can add procedure's you've made with this interface. In fact, all parse does is builds a procedure with these functions through Parse::RecDescent.

As an example, here's how you would build and add this:

    crew(X) := human(X) | hologram(X) - smart(X).

With the low level interface:

    my $proc = $db->newproc('smart', [ 'X' ], 'sub');
    $proc = $db->newproc('hologram', [ 'X' ], 'or',   $proc);
    $proc = $db->newproc('human',    [ 'X' ], 'and',  $proc);
    $proc = $db->newproc('crew',     [ 'X' ], 'bind', $proc);
    $db->add($proc);

FUTURE DIRECTION

In the future, I plan to add:

%

Structures! This is the big one. This makes it so arguments can have arguments, and you can match against them.

%

The ability to differentiate between unprovable and false. This will give false context some meaning.

%

Perhaps comments in the parser. This isn't that important.

%

Easy access to the parser, so you can define infix operators, etc. The parser can now be accessed through $db->{parser}, so long as it has already parsed at least one thing.

%

Predicate searching. This would be cool, but inevitably slow. This is when you can give an unbound variable as the name of a predicate, and it would bind it to each predicate that matched those arguments.

BUGS

I can't find any bugs at the moment, but it's semi-dirty code, so there might be.

AUTHOR

Luke Palmer (fibonaci@babylonia.flatirons.org).

COPYRIGHT

Copyright (C) 2002, Luke Palmer. All Rights Reserved. This module is free software. It may be used, redistributed, and/or modified under the terms of the Perl Artistic License (http://www.perl.com/perl/misc/Artistic.html)