An Introduction to Tabled Logic Programming with Picat
Picat is a new logicbased programming language. In many ways, Picat is similar to Prolog, especially BProlog, but it has functions in addition to predicates, patternmatching 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:

Patternmatching.

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 tablingbased
planner
module.
First, let's install and learn some basics of Picat. Installing Picat is easy; you can download precompiled binaries for 32 and 64bit 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) picatlang.org, 20132015.
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 doublequoted strings,
like the "Hello, World!" above, are lists of symbols):
Picat> X = a.
X = a
yes
Picat> X = 'a'.
X = a
yes
For capitalletter 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
singleassignment "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 spaceseparated 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 1based).
The loop body calculates the value of y
for every iteration and prints
the result using an "ifthenelse" 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
spaceseparated 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 arbitrarylength integers).
Effectively, with tabling, you can change the asymptotic running time from exponential to linear.
An even more useful feature is "modedirected" tabling. Using it you can instruct Picat to store the minimal or the maximal of all possible answers for a nondeterministic 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 modedirected tabling.
The planner
Module
Picat also has a tablingbased 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 mazesolver using the planner
module.
The mazesolving 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.
Sergii Dymchenko is a software developer, a programming languages enthusiast and a great believer in the importance of opensource and free software.