Luke Palmer

# 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([@_], 'peter'),
);
}
sub parent {
Logic-> any(
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 `create`d, 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.