http://www.linuxjournal.com/content/introduction-tabled-logic-programming-picat
Picat is a new logic-based programming language. In many ways, Picat is
similar to Prolog, especially B-Prolog, but it has functions in addition
to predicates, pattern-matching instead of unification in predicate heads,
list comprehensions and optional destructive assignment.
Knowing some Prolog helps when learning Picat but is by no means required.
According to the authors of the language, Picat is an acronym for:
-
Pattern-matching.
-
Imperative.
-
Constraints.
-
Actors.
-
Tabling.
Picat has a lot of interesting features, such as constraint logic programming
support and interfaces to various solvers. In this article, I focus
on one aspect of Picat: tabling and a tabling-based
planner module.
First, let's install and learn some basics of Picat. Installing Picat
is easy; you can download precompiled binaries for 32- and 64-bit Linux
systems, as well as binaries for other platforms. If you want to compile
it yourself, C source code is available under the Mozilla Public License.
The examples here use Picat version 1.2, but newer or slightly older
versions also should work.
After the installation, you can run
picat from a command line and see
Picat's prompt:
Picat 1.2, (C) picat-lang.org, 2013-2015.
Picat>
You can run commands (queries) interactively with this interface.
Let's start with the mandatory "Hello, World":
Picat> println("Hello, World!").
Hello, World!
yes
No real surprises here. The
yes at the end means that Picat successfully
executed the query.
For the next example, let's assign 2 to a variable:
Picat> X = 2.
X = 2
yes
Note the uppercase letter for the variable name; all variable
names must start with a capital letter or an underscore (the same as in Prolog).
Next, assign symbols to the
X variable (symbols are enclosed in single
quotes; for many symbols, quotes are optional, and double-quoted strings,
like the "Hello, World!" above, are lists of symbols):
Picat> X = a.
X = a
yes
Picat> X = 'a'.
X = a
yes
For capital-letter symbols, single quotes are mandatory (otherwise it will be
treated as a variable name):
Picat> X = A.
A = X
yes
Picat> X = 'A'.
X = 'A'
yes
Note that the variable
X in different queries (separated by a full stop) are
completely independent different variables.
Lists
Next, let's work with lists:
Picat> X = [1, 2, 3, a].
X = [1,2,3,a]
yes
Lists are heterogeneous in Picat, so you can have numbers as the first three list
elements and a symbol as the last element.
You can calculate the results of arithmetic expressions like this:
Picat> X = 2 + 2.
X = 4
yes
Picat> X = [1, a, 2 + 2].
X = [1,a,4]
yes
Picat> X = 2, X = X + 1.
no
This probably is pretty surprising for you if your background is in
mainstream imperative languages. But from the logic point of view, it
makes prefect sense: X can't be equal to X + 1.
Using
:= instead of
= produces a more expected answer:
Picat> X = 2, X := X + 1.
X = 3
yes
The destructive assignment operator
:= allows you to
override Picat's usual
single-assignment "write once" policy for variables. It works in a way
you'd expect from an imperative language.
You can use the
[|] notation to get a
"head" (the first element) and a "tail"
(the rest of the elements) of a list:
Picat> X = [1, 2, 3], [Tail | Head] = X.
X = [1,2,3]
Tail = 1
Head = [2,3]
yes
You can use the same notation to add an element to the beginning of a list:
Picat> X = [1, 2, 3], Y = [0 | X].
X = [1,2,3]
Y = [0,1,2,3]
yes
Picat> X = [1, 2, 3], X := [0 | X].
X = [0,1,2,3]
yes
The first example creates a new variable
Y, and the
second example reuses
X with the assignment operator.
TPK Algorithm
Although it's handy to be able to run small queries interactively to try
different things, for larger programs, you probably will want to write the code to
a file and run it as a script.
To learn some of Picat's syntactical features, let's create a program (script)
for a TPK algorithm. TPK is an algorithm proposed by D. Knuth and
L. Pardo to show the basic syntax of a programming language beyond the
"Hello, World!" program. The algorithm asks a user to enter 11 real
numbers
(a0...a10). After that, for
i =
10...0 (in that order),
the algorithm computes the value of an arithmetic function
y =
f(ai),
and outputs a pair
(i, y), if
y <=
400 or
(i, TOO LARGE) otherwise.
Listing 1. TPK
f(T) = sqrt(abs(T)) + 5 * T**3.
main =>
N = 11,
As = to_array([read_real() : I in 1..N]),
foreach (I in N..-1..1)
Y = f(As[I]),
if Y > 400 then
printf("%w TOO LARGE\n", I)
else
printf("%w %w\n", I, Y)
end
end.
First, the code defines a function to calculate the value of
f (a
function in Picat is a special kind of a predicate that always succeeds
with a return value). The
main predicate follows
(
main is a default
name for the predicate that will be run during script execution).
The code uses list comprehension (similar to what you have in Python,
for example) to read the 11 space-separated real numbers into an array
As. The
foreach loop iterates
over the numbers in the array;
I
goes from 11 to 1 with the step -1 (in Picat, array indices are 1-based).
The loop body calculates the value of
y for every iteration and prints
the result using an "if-then-else" construct.
printf is similar to
the corresponding C language function;
%w can be seen
as a "wild card"
control sequence to output values of different types.
You can save this program to a file with the .pi extension (let's call
it tpk.pi), and then run it using the command
picat tpk.pi. Input 11
space-separated numbers and press Enter.
Tabling
Now that you have some familiarity with the Picat syntax and how to run the
scripts, let's proceed directly to tabling. Tabling is a form of
automatic caching or memoization—results of previous computations can
be stored to avoid unnecessary recomputation.
You can see the benefits of tabling by comparing two versions of a program
that calculates Fibonacci numbers with and without tabling.
Listing 2 shows a naive recursive Fibonacci implementation in Picat.
Listing 2. Naive Fibonacci
fib(0) = 1.
fib(1) = 1.
fib(N) = F =>
N > 1,
F = fib(N - 1) + fib(N - 2).
main =>
N = read_int(),
println(fib(N)).
This naive implementation works, but it has an exponential running time.
Computing the 37th Fibonacci number takes more than two seconds on my
machine:
$ time echo 37 | picat fib_naive.pi
39088169
real 0m2.604s
Computing the 100th Fibonacci number would take this program forever!
But, you can add just one line (
table) at the beginning of the
program to see a dramatic improvement in running time.
Now you can get not only 37th Fibonacci number instantly, but even the
1,337th (and the answer will not suffer from overflow, because Picat
supports arbitrary-length integers).
Effectively, with tabling, you can change the asymptotic running time from
exponential to linear.
An even more useful feature is "mode-directed" tabling. Using it you
can instruct Picat to store the minimal or the maximal of all possible
answers for a non-deterministic goal. This feature is very handy when
implementing dynamic programming algorithms.
However, that topic is beyond the scope of this article; see Picat's official documentation to learn
more about mode-directed tabling.
The planner Module
Picat also has a tabling-based
planner module, which can be used to
solve artificial intelligence planning problems. This module provides
a higher level of abstraction and declarativity.
To use the module, an application programmer has to specify
action
and
final predicates.
The
final predicate, in its simplest form, has only one parameter—the
current state—and succeeds if the state is final.
The
action predicate usually has several clauses—one for each possible
action or group of related actions. This predicate has four parameters:
current state, new state, action name and action cost.
Let's build a maze-solver using the
planner module.
The maze-solving program will read a maze map from the standard input
and output the best sequence of steps to get to the exit.
Here is an example map:
5 5
@.#..
=.#..
.##..
.#X..
.|...
The first line contains the dimensions of the maze: the number of rows
R
and columns
C.
Next,
R lines describe the rows of the maze. Here is the description of
the map symbols:
-
@ — initial hero position.
-
. — an empty cell.
-
# — a permanent wall.
-
= — a key.
-
| — a closed door.
-
X — the exit.
The hero can move up, down, left and right (no diagonals) to any open
cell (a cell without a wall or a closed door). The hero can pick up keys
and open doors. Opening a door and moving into a newly open cell is
considered one action. To open a door, the hero must have a key.
Because this is a magic maze, the key disappears after it opens a door.
All keys are identical, so opening a door basically just decreases the
number of keys the hero has by one.
The goal is to reach the exit using the minimum amount of energy.
Moving to an open cell costs one energy unit, picking up a key costs one energy
unit, and opening a door and moving to the cell previously occupied by that
door costs two energy units.
Let's represent a state for this problem as a tuple
(R, C, (ExitI,
ExitJ), Walls, Doors, Keys, K, (HeroI, HeroJ)):
-
R and C are the number of rows
and columns in the maze.
-
(ExitI, ExitJ) are the coordinates of the exit.
-
Walls is a list of the positions of all walls.
-
Doors is a list of the positions of all closed doors.
-
Keys is a list of the positions of not-yet-picked-up
keys.
-
K is the number of keys the hero has.
-
(HeroI, HeroJ) are coordinates of the hero's position.
Let's first do some boring work of translating a textual representation
of a maze to an initial state in the format defined before.
The
main predicate is an imperative procedure in
constructing an
initial state from a textual representation of a maze: you read the input
line by line, symbol by symbol, and then construct the lists of walls, doors
and keys, as well as record the coordinates of the hero and the exit.
Listing 3. Read the Maze Description
main =>
R = read_int(), C = read_int(),
Walls = [], Doors = [], Keys = [],
(ExitI, ExitJ) = (_, _),
(HeroI, HeroJ) = (_, _),
foreach (I in 1..R)
Line = read_line(),
foreach (J in 1..C)
Char = Line[J],
if Char == '@' then
HeroI := I, HeroJ := J
end,
if Char == 'X' then
ExitI := I, ExitJ := J
end,
if Char == '#' then
Walls := [(I, J) | Walls]
end,
if Char == '|' then
Doors := [(I, J) | Doors]
end,
if Char == '=' then
Keys := [(I, J) | Keys]
end
end
end,
InitState = (R, C, (ExitI, ExitJ),
Walls, Doors, Keys,
0, (HeroI, HeroJ)),
println(InitState).
Let's save this program to maze_read.pi, the maze description from above to
maze.txt, and run the program (the output is split into several lines
for clarity):
$ picat maze_read.pi < maze.txt
5,5,
(4,3),
[(4,2),(3,3),(3,2),(2,3),(1,3)],
[(5,2)],
[(2,1)],
0,1,1
So, you have the dimensions of the maze (5 by 5), the coordinates of the exit
(4, 3), the list of the coordinates of all five walls,
a one-element list of
the closed doors and a one-element list of the keys available for picking up.
The hero has 0 keys and starts in cell
(1, 1).
Now that you have your state, you can define some predicates to
solve the problem. First, the
final predicate for the
planner module:
final((_, _, (I, J), _, _, _, _, (I, J))) =>
true.
The state is final when the hero is in the cell with the same coordinates
as the exit cell. Variables with name
_ are
throw-away, "don't care"
variables that are not required to have any specific value (Picat invents
a different name for each
_ behind the scenes, so they don't have to
be equal either).
Next, describe the action to take a key if the hero is in a cell with one:
action(State, NewState, Action, Cost) ?=>
(R, C, (ExitI, ExitJ), Walls, Doors, Keys,
K, (HeroI, HeroJ)) = State,
select((HeroI, HeroJ), Keys, NewKeys),
Action = $take_key(HeroI, HeroJ),
Cost = 1,
NewState = (R, C, (ExitI, ExitJ),
Walls, Doors, NewKeys,
K + 1, (HeroI, HeroJ)).
First you decompose the state into components, and then you try to
select a key with the current coordinates of the hero
from the
Keys
list. If there is such a key, this will succeed, and the rest of the keys
will be assigned to "NewKeys"; otherwise,
select fails, and Picat will
break the execution of this action clause.
The name of the action is
take_key, with the coordinates of the event in
the parentheses (the
$ instructs Picat to treat it literally, like a string,
and not to try to execute as a function), and the cost is one energy unit.
The new state is almost the same as the old state, except that the number
of keys the hero has is increased by one, and the current key no longer
is available to pick up.
Besides picking up keys, there are two more possible actions: moving to an
empty cell and moving to a cell with a door after opening it. It's a
good idea to combine both these actions into one clause, because they
share a lot of code used to select a new hero position and check whether
it's within the maze boundary:
action(State, NewState, Action, Cost) =>
(R, C, (ExitI, ExitJ), Walls, Doors, Keys,
K, (HeroI, HeroJ)) = State,
(
Di = 0, Dj = 1
;
Di = 0, Dj = -1
;
Di = 1, Dj = 0
;
Di = -1, Dj = 0
),
NewHeroI = HeroI + Di,
NewHeroJ = HeroJ + Dj,
NewHeroI >= 1, NewHeroI <= R,
NewHeroJ >= 1, NewHeroJ <= C,
(
% move to open cell
not membchk((NewHeroI, NewHeroJ), Walls),
not membchk((NewHeroI, NewHeroJ), Doors),
Action = $move(NewHeroI, NewHeroJ),
Cost = 1,
NewState = (R, C, (ExitI, ExitJ),
Walls, Doors, Keys,
K, (NewHeroI, NewHeroJ))
;
% open a door and move to that cell
K > 0,
select((NewHeroI, NewHeroJ), Doors, NewDoors),
Action = $open(NewHeroI, NewHeroJ),
Cost = 2,
NewState = (R, C, (ExitI, ExitJ),
Walls, NewDoors, Keys,
K - 1, (NewHeroI, NewHeroJ))
).
Again, first you decompose the state into the components. Next, you try
all possible new positions for the hero with non-deterministic disjunction:
;.
A position must be within the maze boundaries:
I must
be from 1 to
R,
and
J must be from 1 to
C. After that, there are two possibilities:
move to an open cell, or open a door and move to that cell.
Moving to an open cell is possible only if there isn't a wall or a
closed door at the desired position. Two
not membchk lines verify
this condition. If the condition is met, the action name is
move,
and the cost is one energy unit. The only change in the state is the hero's position.
Opening an door is possible if there is a door at the position and
the hero has at least one key. The
select line here is similar to the
line for the
take action, but now you select a door instead of a key.
If the conditions are met, the action name is
open,
and the cost is two
energy units. The new state is almost the same as the old state, but
the door is removed from the list of doors, the number of keys the
hero has is decreased by one, and the hero has moved to a new position.
To use the defined
final and
action predicates
and find the plan, you need to change
println(InitState) to
best_plan_unbounded(InitState, Plan), println(Plan) in
the
main
from the maze_read.pi program. (Note:
best_plan_unbounded is one of the
predicates of the
planner module for finding best
plans. This particular
version uses memory to avoid re-exploring states, converting tree search
in the space of all possible plans to graph search.)
Listing 4 shows the complete maze program.
Listing 4. Full Maze Program
import planner.
action(State, NewState, Action, Cost) ?=>
(R, C, (ExitI, ExitJ), Walls, Doors, Keys,
K, (HeroI, HeroJ)) = State,
select((HeroI, HeroJ), Keys, NewKeys),
Action = $take_key(HeroI, HeroJ),
Cost = 1,
NewState = (R, C, (ExitI, ExitJ),
Walls, Doors, NewKeys,
K + 1, (HeroI, HeroJ)).
action(State, NewState, Action, Cost) =>
(R, C, (ExitI, ExitJ), Walls, Doors, Keys,
K, (HeroI, HeroJ)) = State,
(
Di = 0, Dj = 1
;
Di = 0, Dj = -1
;
Di = 1, Dj = 0
;
Di = -1, Dj = 0
),
NewHeroI = HeroI + Di,
NewHeroJ = HeroJ + Dj,
NewHeroI >= 1, NewHeroI <= R,
NewHeroJ >= 1, NewHeroJ <= C,
(
% move to open cell
not membchk((NewHeroI, NewHeroJ), Walls),
not membchk((NewHeroI, NewHeroJ), Doors),
Action = $move(NewHeroI, NewHeroJ),
Cost = 1,
NewState = (R, C, (ExitI, ExitJ),
Walls, Doors, Keys,
K, (NewHeroI, NewHeroJ))
;
% open a door and move to that cell
K > 0,
select((NewHeroI, NewHeroJ), Doors, NewDoors),
Action = $open(NewHeroI, NewHeroJ),
Cost = 2,
NewState = (R, C, (ExitI, ExitJ),
Walls, NewDoors, Keys,
K - 1, (NewHeroI, NewHeroJ))
).
final((_, _, (I, J), _, _, _, _, (I, J))) =>
true.
main =>
R = read_int(), C = read_int(),
Walls = [], Doors = [], Keys = [],
(ExitI, ExitJ) = (_, _),
(HeroI, HeroJ) = (_, _),
foreach (I in 1..R)
Line = read_line(),
foreach (J in 1..C)
Char = Line[J],
if Char == '@' then
HeroI := I, HeroJ := J
end,
if Char == 'X' then
ExitI := I, ExitJ := J
end,
if Char == '#' then
Walls := [(I, J) | Walls]
end,
if Char == '|' then
Doors := [(I, J) | Doors]
end,
if Char == '=' then
Keys := [(I, J) | Keys]
end
end
end,
InitState = (R, C, (ExitI, ExitJ),
Walls, Doors, Keys,
0, (HeroI, HeroJ)),
best_plan_unbounded(InitState, Plan),
println(Plan).
After running it for the maze used above, you get an optimal plan (list of
actions) to solve the maze (the output is split into several lines for
clarity):
$ picat maze.pi < maze.txt
[
move(2,1),
take_key(2,1),
move(3,1),
move(4,1),
move(5,1),
open(5,2),
move(5,3),move(4,3)
]
You can try to run this program with inputs of various sizes and with
different features. For example, this input requires the hero to take
a key to the right, then go left to get more keys, and then go right
again to the exit:
1 10 ==|=|@=||X
Of course, you can improve the maze program in many different ways:
-
Better user interface: currently, the output is not very easy to read,
and the program exits with an error if the maze is not solvable.
-
Sets or hash tables instead of lists: looking for a key or wall in a
list requires linear time, while with a more appropriate data structure,
it will be constant.
-
Adding a heuristic: the search could be improved with a heuristic to
make it a variant of an IDA* algorithm.
-
New maze features: you could implement different kinds of keys, weapons,
treasure and monsters.
Overall, Picat looks like a really good starting point for a journey into
the realm of logic-based programming languages. It provides many of
the goodies Prolog has, such as non-determinism and built-in depths-first
search with backtracking, and at the same time, Picat allows you to fall back to
convenient imperative concepts like destructive assignments and loops.
Higher-level features, like tabling and the
planner
module, provide ways
to write concise, declarative and efficient programs.
Resources
Picat:
http://picat-lang.org
"Artificial intelligence planning with Picat" by Sergii
Dymchenko:
http://sdymchenko.com/blog/2015/01/31/ai-planning-picat
Hakan Kjellerstrand's Picat Page:
http://www.hakank.org/picat
"Declaratively solving Google Code Jam problems with Picat" by
Sergii Dymchenko and Mariia Mykhailova:
http://arxiv.org/abs/1504.00977
"Combinatorial Search with Picat" by Neng-Fa Zhou:
http://arxiv.org/abs/1405.2538 
