Logic Programming in Perl 6

This is a small example of conference-driven development. I’m sitting in the board room at TPCiP – TCP in Pittsburgh surrounded by people doing both Perl 5 and Perl 6 programming, and decided to look again at Picat, working on some simple examples. I was thinking that I might be able to translate some of the simpler backtracking examples from Picat to Perl 6, and here’s a simple example.

First the Picat code:

fib(0,F) => F=1.
fib(1,F) => F=1.
fib(N,F),N>1 => fib(N-1,F1),fib(N-2,F2),F=F1+F2.

Now here’s my equivalent Perl 6 code:

multi fib( 0, $F is rw ) { $F = 1 }
multi fib( 1, $F is rw ) { $F = 1 }
multi fib( $N is rw where * > 1, $F is rw ) {
  my ( $F1, $F2 ) = 0, 0;
  my $N1 = $N - 1;
  my $N2 = $N - 2;
  fib( $N1, $F1 ) && fib( $N2, $F2 ) && $F = $F1 + $F2

The Perl 6 version is slightly larger because I need to declare some variables that Picat would ordinarily declare for me ($F1, $F2). There may be a way to work around declaring ($N1, $N2), but otherwise the two versions are identical.

How does it work?

You’ve probably guessed based on the inputs that N is index of the Fibonacci number, and F is the Fibonacci number itself. Picat doesn’t require you to declare variables, so you could ask it for the 7th Fibonacci number by calling fib(7,F) and looking at F.

my $Fib = 0;
say $Fib     # 21

Or you could do the above in Perl 6, letting the code populate $Fib for you. This code relies on the fact that Perl 6 lets you dispatch not just on signatures, not just on argument types, but on values. Look at the base case above:

multi fib( 0, $F is rw ) { ... }

fib(…) is the function signature, and this function will get called whenever the first argument is 0, like so: fib(0, $Fib). This happens even if ‘multi fib( $N, $F )’ is the one doing the calling, everything gets run through the same dispatcher each time.

So fib(2, $Fib) calls fib(1, $Fib) which calls ‘multi fib( 1, $F )’ and gives us a base case, for example. This lets the higher-order functions call our base cases, and still get the right value.

What are we missing?

Well, the Picat code can do something the Perl 6 code can’t, at least for the moment, and this is what I want to spend some time working on. In Picat, I can call ‘fib(6,F)’ and F will be 13 when the code is done. This works in Perl 6 too.

But Picat will also let you call ‘fib(N,21)’ and N will be 7 when the calculation is finished. Take some time to let that settle. Yes, you can run the calculation both forward and backward. Give N a value, and F will be the Nth Fibonacci number. Give F a value, and it will tell you what N is.

In fact, Picat will go one step further. If you don’t specify a value for either parameter but just specify variables, like ‘fib(N,F)’, then it will generate all the Fibonacci numbers and their indexes until you tell it to stop.

This is because of the backtracking engine that it uses, which I want to see if I can mimick. ‘F=F1+F2’ doesn’t mean “Assign the sum of F1 and F2 to F”. Instead, “If any values are missing, find values that satisfy the equation, and keep generating them until you run out of possibilities.”

That’s a bit of a mouthful, so let’s look at just F1. Supposing F=8 and F2=5, the backtracking engine would search all values of F1, and return just the matching value of 3. Now of course, it can’t search all values, because that means you’d be waiting forever, so there are pruning algorithms at work here.

But the same logic can work with any combination of arguments, so if both F1 and F2 were missing, then the backtracking engine would run through all possible combinations of values (pruned appropriately) until it found a combination that would work.

In this case, since in our example F=8, it would return a bunch of combinations, starting with (F1=1, F2=7), (F1=2, F2=6) and so on. But why, then, you ask, does it only return (F1=3, F2=5)? That’s because each value F1 also has to satisfy fib(N1,F1), which means that F1 has to be a Fibonacci number, as does F2.


This is the part where Perl 6 breaks down a little bit. But what I think I might be able to do is use a trick I used a while ago, relying on the fact that operators are just functions, and they dispatch just like other functions. So I should be able to start out with something crude like:

my $F = Operator.new( :lhs(3) );
my Value ($F1, $F2);
$F = $F1 + $F2;

This way both $F1 and $F2 are bound to backtracking Values, they return a Operator, and the Operator is part of the backtracking engine. This way once the Operator engine determines the range of possible combinations of $F1 and $F2 that add to 3, it can assign them concurrently to @F1.value and @F2.value.

Smooth Operators

The Operator and Value classes, along with their overloaded operators, would look something like this:

class Operator {
  has ( $.lhs, $.rhs ); }
class PlusOperator is Operator { }
class AssignmentOperator is Operator {
  method make-combinations() {...} }
class Value {
  has @.value }
multi infix:<=>( Operator $lhs, Operator $rhs ) {
  AssignmentOperator.new( :$lhs, :$rhs );
multi infix:<+>( Value $lhs, Value $rhs ) {
  PlusOperator.new( :$lhs, :$rhs );

This is purely a sketch that I haven’t tried out at all. My idea here is that once you’ve executed ‘$F = $F1 + $F2’, $F will be an AssignmentOperator instance. You should be able to call $F.make-combinations() that will solve the equation ‘3 = $F1 + $F2’ for all (constrained) values of $F1 and $F2.

That would populate @F1.values and @F2.values with (1,2) and (2,1) respectively. I’m about to play my first game of Azul, so I’ll leave the article here. The next article will hopefully implement this so you can see this all working. It won’t quite be a true backtracking engine, but it’s a start.

Dear Reader, thank you for your attention, and please feel free to add comments, questions and suggestions.