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

NAME

Logic - logical programming and multimethod dispatch

SYNOPSIS

    use Logic::Easy;

    my ($X, $Y);
    
    # UNIFICATION
    Logic-> is(var $X, 2) -> bind($X);
    print $X;  # 2

    Logic-> is(var $X, [1, var $Y]) -> is([1, 2], $X) -> bind($X, $Y);
    print "@$X, $Y";  # 1 2, 2

    # CONS
    Logic-> is([1, 2, 3], cons(var $X, var $Y)) -> bind($X, $Y);
    print "$X, @$Y";  # 1, 2 3

    # ANY
    Logic-> is(var $X, any(1,2,3)) -> is($X, 4) -> bind($X);  # fail!

    # MULTIMETHODS
    no warnings 'redefine';

    sub process : Multi(process) {
        SIG [];
        print "No parameters!";
    }
    sub process : Multi(process) {
        SIG [$x] where { UNIVERSAL::isa($x, 'Cat') };
        print "Got a cat!";
    }
    sub process : Multi(process) {
        SIG cons($x, $xs);
        print "Got $x";  process($xs);
    }

    # RULES
    sub man {
        Logic-> any(
            Logic-> is([@_], 'adam'),
            Logic-> is([@_], 'peter'),
        );
    }
    sub parent {
        Logic-> any(
            Logic-> is([@_], ['adam', 'peter']),
            Logic-> is([@_], ['eve',  'peter']),
        );
    }
    sub father {
        my ($F, $C) = @_;
        Logic-> rule(sub { man($F) }) -> rule(sub { parent($F, $C) });
    }

DESCRIPTION

The Logic modules implement a logic programming framework in Perl. It does all the magic stuff that prolog does, it just doesn't have as big a standard library. But it has a bigger standard library, because it has CPAN. On top of being able to do logic programming without stepping outside the safe (?) world of Perl syntax, you can do pattern-matching multimethod dispatch with this module.

The Easy Life

To get started in 'Prolog with Perl' right away, use the Logic::Easy module. This exports just a few helpful routines, and uses chained method calls for the rest of the language.

The order of mention here has been optimized for the first-time reader, minimizing backrefrences. If you need a general reference, well, that's why computers have search functions.

var

Decalares a logic variable. Perl 5 introduces a variable the statement after it is declared, so you generally cannot use this function inline unless (a) you only mention the variable once in that statement, or (b) you don't follow it by my.

    var my $X;
    Logic->is($X, 42)->bind($X);   # see below for is and bind
    print $X;   # 42
vars

Declares several logic variables at once. See the comments for var.

    vars my ($X, $Y);
    Logic->is($X, $Y)->is($Y, 42)->bind($X, $Y);
    print "$X, $Y";  # 42, 42
bind

Forces evaluation of the whole chain, while mutating the given variables (which must be lvalues) into regular perl values. The function itself must be the last thing in a chain, since it does not return a chainable value.

If called in void context, the function dies if the chain fails. If called in any other context, it returns undef (or the empty list if in list context) upon failure and 1 upon success. It is fairly common to see a chain start with ! in order to say "I don't care whether this fails", by imposing boolean context. If the function fails, none of the variables in the list is changed.

If the variables cannot be resolved, they are resolved as much as possible in terms of other variables, which will be references of class Logic::Variable.

    var my $X;
    Logic->fail->bind($X);         # die
    !Logic->fail->bind($X);        # do nothing
    Logic->is($X, 42)->bind($X);   # $X is now 42
    var $X;                        # make $X into a variable again
    Logic->is($X, [$Y])->bind($X); # $X is now [Logic::Variable=HASH(...)]
all

Requires that all of its arguments (which are also Logic chains) succeed, and evaluates them in order. This function is generally redundant and useless.

    Logic->id->fail;                     # this can also be written
    Logic->all(Logic->id, Logic->fail);  # like this
any

Evaluates its arguments (which are Logic chains) until one of them succeeds.

    Logic->any(
        Logic->is(20, $X),
        Logic->is(20, $Y),
    )->bind;   # succeeds if $X is 20 or $Y is 20
assert

Asserts that a condition given by code is true. Optionally takes a list of variables to bind for the duration of the block before the block argument.

    Logic->is($X, 20)->assert($X, sub { $X < 10 })->bind;  # fails

You have to specify the variables to bind, otherwise you'll be comparing against references. Variables that are still in terms of other, unresolvable variables cause the assertion to automatically fail.

id

Always succeeds.

fail

Always fails.

block

Always succeeds. Differs from id in that it even succeeds on backtracking. Note that a chain with this as its first element will never fail, possibly causing an infinite loop. Use with caution. Generally used with assign, and with user input.

rule

Executes a block of code and interprets it as another Logic chain to be nested in the current chain. This is how you perform recursion.

    sub ancestor {
        my ($A, $B) = @_;
        var my $X;
        Logic->any(
            Logic->rule(sub { parent($A, $B) }),
            Logic->rule(sub { parent($A, $X) })->rule(sub { ancestor($X, $B) }),
        );
    }
is

Data structure unification: succeeds if its arguments are equal, binding variables along the way trying to make the structures equal.

    vars my ($X, $Y);
    Logic->is([$X, 2, 3], [1, 2, $Y])->bind($X, $Y);
    print "$X, $Y";   # 1, 3

Compares stringwise for two non-references. If the arguments are arrays, recursively unifies them elementwise. If they are other references, then delegates the decision to a unify method if one exists on either argument. If neither argument has a unify method, then compares them numerically (effectively testing whether they are exactly the same reference, unless one of them has the == operator overloaded). See Logic::Data::Cons for an example of a unify method.

assign

Executes some code and unifies the given variable(s) (given before the code) with the return value(s) of the block. If the block returns too few values for the number of variables, unifies the remaining ones with undef. If the block returns too many values, it ignores them.

    var my $X;
    Logic->block
         ->assert(sub { print "Enter a number less than 10: " })
         ->assign($X, sub { scalar <> }),
         ->assert($X, sub { $X < 10 })
         ->bind($X);
    print "You entered $X";
for

Unifies the given variable with each of the given values.

    var my $X;
    !Logic->for($X, 1..10)->assert($X, sub { print $X })->fail->bind;
    # prints 12345678910
cons

Not a chained method, but an exported sub. Creates a cons object, which represents the first element concatenated on the front of the second element, which is an array.

    vars my ($X, $Y);
    Logic->is(cons($X, $Y), [1,2,3,4,5])->bind($X, $Y);
    print "$X | @$Y";  # 1 | 2 3 4 5

Multimethods

Now that you're familiar with these basic predicates, you can forget about them. The multimethod functionality of Logic::Easy defines some syntactic sugar around all of this

Every variant should be declared with the :Multi(name) attribute, like:

    sub foo : Multi(foo) {
        # variant 1
    }
    sub foo : Multi(foo) {
        # variant 2
    }

The actual subs can be named differently, but I'd recommend against it. The names given to Multi are global, so you can define methods on your objects in their own packages as multis, and they will work correctly.

How do you specify the signatures of these multimethods? On the next line, in exactly one line, using the SIG syntax. Yes, it's implemented with a source filter. Don't sweat though, it's a very safe, non-intrusive one.

SIG takes a data structure of variables (which are declared var for you), usually an anonymous array that corresponds to [@_]. [@_] is unified against that list, and if it succeeds, then your method is run. For example:

    sub foo : Multi(foo) {
        SIG [$x, [$y]];
        # only takes a single-element array as its second argument
        # ...
    }

SIG takes an optional where clause:

    sub pow : Multi(pow) {
        SIG [$x, $y] where { $y == 2 };
        $x * $x;
    }
    sub pow : Multi(pow) {
        SIG [$x, $y];
        $x ** $y;
    }

The methods are tried in order of definition. The SIG argument doesn't have to be an anonymous array though; it just has to represent one:

    sub first : Multi(first) {
        SIG cons($x, $y);
        $x;
    }

If you need more mad chaining power, then you can no longer use the SIG syntactic sugar. Instead, use the sig semantic sugar:

    sub first : Multi(first) {
        vars my ($x, $y);
        Logic->sig(cons($x, $y))->bind($x);
        $x;
    }

You can chain sig in with whatever else you like. Keep in mind that it peeks at your @_ array, so don't abstract too much.

Down a little deeper

So what if there's something you want that's not in the small library I've given you? Well, you could ask me, but that's not going to be very time- efficient. It turns out, that by conforming to a simple interface, you can write your own predicates. An object that can be used as a predicate must have the following interface:

    sub create;  # ($self, $stack, $state)

This method, in turn, returns another object that represents a "predicate in progress", which must conform to the following interface:

    sub enter;      # ($self, $stack, $state)
    sub backtrack;  # ($self, $stack, $state)
    sub cleanup;    # ($self, $stack, $state)

Most commonly, create just returns $self and does nothing else.

The enter method is called right after the object was created, and is used for the initial setup for the state. If it returns a true value, then the engine moves on into the next prediciate in the chain. If it returns false, this predicate is aborted and the engine moves to the previous predicate in the chain.

The backtrack method is called (if enter succeeded) after the next predicate in the chain fails, if that ever happens. Again, if it returns a true value, the engine assumes that you changed something and moves forward. If it returns a false value, then your predicate has failed and the engine moves backward.

The cleanup method is called whenever your predicate fails. This is rarely used in a garbage-collecting language like Perl, but alas, it does need to be used once in a while. This is mostly for popping scopes in the Logic::Data::Unify predicate.

The three values that are passed in to all of these methods are as follows:

$self

The current object, of course.

$stack

The Logic::Data::Stack object, which you will use for calling sub-predicates. Call the descend method on this to descend into another layer. This should generally be called as the last method in your routine (the stack continues processing after your routine exits, so any cleanup code should go in cleanup or at the beginning of backtrack).

    sub TwoIsTwo::enter {
        my ($self, $stack, $state) = @_;
        $stack->descend(
            Logic::Data::Unify->new(2, 2),
        );
    }
$state

Short for $stack-state>.

In order to "splice" these objects back in your chain, you have to return them from the block given to rule.

BUGS

It is not fully documented yet. There are other bugs for sure, but I don't know about them. Bug reports very welcome.

Logic currently just returns the string Logic::Easy, so if you want to use the "easy" interface without importing anything, you have to say Logic::Easy->... . What a pain.

SEE ALSO

AI::Prolog

AUTHOR

Luke Palmer <luke at luqui dot org>