Picat Guide
Picat Guide
Version 3.9 #4
Picat is a general-purpose language that incorporates features from logic programming, functional
programming, constraint programming, and scripting languages. The letters in the name summa-
rize Picat’s features:
• Pattern-matching: A predicate defines a relation, and can have zero, one, or multiple an-
swers. A function is a special kind of a predicate that always succeeds with one answer.
Picat is a rule-based language. Predicates and functions are defined with pattern-matching
rules. Since version 3.0, Picat also supports Prolog-style Horn clauses and Definite Clause
Grammar (DCG) rules.
• Intuitive: Picat provides assignment and loop statements for programming everyday things.
An assignable variable mimics multiple logic variables, each of which holds a value at a
different stage of computation. Assignments are useful for computing aggregates and are
used with the foreach loop for implementing list and array comprehensions.
• Constraints: Picat supports constraint programming. Given a set of variables, each of which
has a domain of possible values, and a set of constraints that limit the acceptable set of
assignments of values to variables, the goal is to find an assignment of values to the variables
that satisfies all of the constraints. Picat provides four solver modules: cp, sat, smt, and
mip. These four modules follow the same interface, which allows for seamless switching
from one solver to another.
• Actors: Actors are event-driven calls. Picat provides action rules for describing event-
driven behaviors of actors. Events are posted through channels. An actor can be attached
to a channel in order to watch and to process its events. All the propagators used in cp are
implemented as actors.
• Tabling: Tabling can be used to store the results of certain calculations in memory, allow-
ing the program to do a quick table lookup instead of repeatedly calculating a value. As
computer memory grows, tabling is becoming increasingly important for offering dynamic
programming solutions for many problems. The planner module, which is implemented
by the use of tabling, has been shown to be an efficient tool for solving planning problems.
The support of unification, non-determinism, tabling, and constraints makes Picat more suit-
able than functional and scripting languages for symbolic computations. Picat is more convenient
than Prolog for scripting and modeling. With arrays, loops, and comprehensions, it is not rare to
find problems for which Picat requires an order of magnitude fewer lines of code to describe than
Prolog. Picat is more scalable than Prolog. The use of pattern-matching rather than unification
facilitates indexing of rules. Picat is not as powerful as Prolog for metaprogramming and it’s im-
possible to write a meta-interpreter for Picat in Picat itself. Nevertheless, this weakness can be
remedied with library modules for implementing domain-specific languages.
The Picat implementation is based on the B-Prolog engine. The current implementation is
ready for many kinds of applications. It also serves as a foundation for new additions. The project
is open, and you are welcome to join as a developer, a sponsor, a user, or a reviewer. Please contact
picat@[Link] and join the news group [Link]
picat-lang.
i
License
The copyright of Picat is owned by [Link]. Picat is provided, free of charge, for
any purposes, including commercial ones. The C source files of Picat are covered by the Mozilla
Public License, v. 2.0 ([Link] In essence, anyone is allowed
to build works, including proprietary ones, based on Picat, as long as the Source Code Form is
retained. The copyright holders, developers, and distributors will not be held liable for any direct
or indirect damages.
Acknowledgements
The initial design of Picat was published in December 2012, and the first alpha version was re-
leased in May 2013. Many people have contributed to the project by reviewing the ideas, the
design, the implementation, and/or the documentation, including Roman Barták, Nikhil Barthwal,
Mike Bionchik, Lei Chen, Veronica Dahl, Claudio Cesar de Sá, Agostino Dovier, Sergii Dym-
chenko, Julio Di Egidio, Christian Theil Have, Håkan Kjellerstrand, Annie Liu, Nuno Lopes,
Marcio Minicz, Richard O’Keefe, Lorenz Schiffmann, Paul Tarau, and Jan Wielemaker. Spe-
cial thanks to Håkan Kjellerstrand, who has been programming in Picat and blogging about Pi-
cat since May 2013. The system wouldn’t have matured so quickly without Håkan’s hundreds
of programs ([Link] Thanks also go to Bo Yuan (Bobby) Zhou, who de-
signed the [Link] web page, Sanders Hernandez, who implemented the interface
to the FANN neural network library, and Domingo Alvarez Duarte, who ported Picat to MinGW
([Link] The Picat project was supported in part by the
NSF under grant numbers CCF1018006 and CCF1618046.
The Picat implementation is based on the B-Prolog engine. It uses the following public do-
main modules: token.c by Richard O’Keefe; getline.c by Chris Thewalt; bigint.c by
Matt McCutchen; Espresso (by Berkeley); FANN by Steffen Nissen. In addition, Picat also pro-
vides interfaces to the SAT solver Kissat ([Link]
Gurobi by Gurobi Optimization, Inc, CBC by John Forrest, GLPK by Andrew Makhorin, SCIP
by the Zuse Institute, and Z3 by Microsoft.
ii
Contents
1 Overview 1
1.1 Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Defining Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Defining Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Assignments and Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Tabling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6 Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.8 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.9 Higher-Order Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.10 Action Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.11 Prebuilt Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.12 Programming Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
iii
3.6 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.7 Higher-order Predicates and Functions . . . . . . . . . . . . . . . . . . . . . . . 41
3.8 Other Built-ins in the basic Module . . . . . . . . . . . . . . . . . . . . . . . 42
6 Exceptions 59
6.1 Built-in Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.2 Throwing Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.3 Defining Exception Handlers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
7 Tabling 61
7.1 Table Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
7.2 The Tabling Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
9 Modules 72
9.1 Module and Import Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . 72
9.2 Binding Calls to Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
9.3 Binding Higher-Order Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
9.4 Library Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
10 I/O 75
10.1 Opening a File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
10.2 Reading from a File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
10.2.1 End of File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
10.3 Writing to a File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
10.4 Flushing and Closing a File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
iv
10.5 Standard File Descriptors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
12 Constraints 87
12.1 Domain Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
12.2 Table constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
12.3 Arithmetic Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
12.4 Boolean Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
12.5 Global Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
12.6 Bit-Vector Constraints (sat only) . . . . . . . . . . . . . . . . . . . . . . . . . . 99
12.7 Solver Invocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
12.7.1 Common Solving Options . . . . . . . . . . . . . . . . . . . . . . . . . 101
12.7.2 Solving Options for cp . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
12.7.3 Solving Options for sat . . . . . . . . . . . . . . . . . . . . . . . . . . 102
12.7.4 Solving Options for mip . . . . . . . . . . . . . . . . . . . . . . . . . . 102
12.7.5 Solving Options for smt . . . . . . . . . . . . . . . . . . . . . . . . . . 103
v
A.2.8 Other Built-ins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
F Formats 131
F.1 Formatted Printing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
Index 153
vi
Chapter 1
Overview
Before we give an overview of the Picat language, let us briefly describe how to use the Picat
system. The Picat system provides an interactive programming environment for users to load,
debug, and execute programs. Users can start the Picat interpreter with the OS command picat.
Once the interpreter is started, users can type a command line after the prompt Picat>. The
help command shows the usages of commands, and the halt command terminates the Picat
interpreter. Users can also use the picat command to run a program directly as follows:
where F ile (with or without the extension .pi) is the main file name of the program. The program
must define a predicate named main/0 or main/1.1 If the command line contains arguments
after the file name, then main/1 is executed. Otherwise, if the file name is not followed by any
arguments, then main/0 is executed. When main/1 executed, all of the arguments after the file
name are passed to the predicate as a list of strings.
The picat command accepts several options, which specify an initial setting for the inter-
preter. For example, the option -d starts the interpreter in debug mode, enabling tracing:
1
structure with the name ’{}’. A map is a hash-table represented as a structure that contains a set
of key-value pairs. A set is a special map where only keys are used. A heap is a complete binary
tree represented as an array. A heap can be a min-heap or a max-heap.
The function new_struct(N ame, IntOrList) returns a structure. The function new_map(S)
returns a map that initially contains the pairs in list S, where each pair has the form Key = V al.
The function new_set(S) returns a map set that initially contains the elements in list S. A
map-set is a map in which every key is mapped to the atom not_a_value. The function
new_array(I1 , I2 , . . . , In ) returns an n-dimensional array, where each Ii is an integer expres-
sion specifying the size of a dimension. An n-dimensional array is a one-dimensional array where
the arguments are (n-1)-dimensional arrays.
Example
Picat> V1 = X1, V2 = _ab, V3 = _ % variables
Picat> print("hello"++"picat")
hellopicat
2
Picat> X = 1..2..10 % ranges
X = [1,3,5,7,9]
Picat> X = 1..5
X = [1,2,3,4,5]
Picat allows function calls in arguments. For this reason, it requires structures to be preceded
with a dollar symbol in order for them to be treated as data. Without the dollar symbol, the
command S = point(1.0,2.0) would call the function point(1.0,2.0) and bind S to
its return value. In order to ensure safe interpretation of meta-terms in higher-order calls, Picat
forbids the creation of terms that contain structures with the name ’.’, index notations, array
comprehensions, list comprehensions, and loops.
For each type, Picat provides a set of built-in functions and predicates. The index notation
X[I], where X references a compound value and I is an integer expression or a range in the
form l..u, is a special function that returns a single component (when I is an integer) or a list of
components (when I is a range) of X. The index of the first element of a list or a structure is 1. In
order to facilitate type checking at compile time, Picat does not overload arithmetic operators for
other purposes, and requires an index expression to be an integer or an integer range.
A list comprehension, which takes the following form, is a special functional notation for
creating lists:
[T : E1 in D1 , Cond1 , . . ., En in Dn , Condn ]
{T : E1 in D1 , Cond1 , . . ., En in Dn , Condn }
The predicate put(M ap, Key, V al) attaches the key-value pair Key=V al to the map M ap,
where Key is a non-variable term, and V al is any term. The function get(M ap, Key) returns
V al of the key-value pair Key=V al attached to M ap. The predicate has_key(M ap, Key)
returns true iff M ap contains a pair with the given key.
An attributed variable has a map attached to it. The predicate put_attr(X, Key, V al)
attaches the key-value pair Key=V al to X. The function get_attr(X, Key) returns V al of
the key-value pair Key=V al attached to X.
Example
Picat> integer(5)
yes
Picat> real(5)
no
Picat> var(X)
3
yes
Picat> X = 5, var(X)
no
Picat> 5 != 2+2
yes
Picat> X = to_binary_string(5)
X = [’1’,’0’,’1’]
Picat also allows OOP notations for calling predicates and functions. The notation A1 .f (A2 , . . . , Ak )
is the same as f (A1 , A2 , . . . , Ak ), unless A1 is an atom, in which case A1 must be a module qual-
ifier for f . The notation A.f , where f is an atom, is the same as the call A.f ().
Example
Picat> X = 5.to_binary_string()
X = [’1’,’0’,’1’]
Picat> X = 5.to_binary_string().length
X = 3
Picat> X = [Link]
4
X = 3.14159
A predicate call either succeeds or fails, unless an exception occurs. A predicate call can return
multiple answers through backtracking. The built-in predicate true always succeeds, and the
built-in predicate fail (or false) always fails. A goal is made from predicate calls and state-
ments, including conjunction (A, B), disjunction (A; B), negation (not A), if statement, foreach
loops, and while loops.
A predicate is defined with pattern-matching rules. Picat has two types of pattern-matching
rules:
The Head takes the form p(t1 , . . . , tn ), where p is called the predicate name, and n is called the
arity. When n = 0, the parentheses can be omitted. The condition Cond, which is an optional
goal, specifies a condition under which the rule is applicable. For a call C, if C matches Head and
Cond succeeds, meaning that the condition evaluates to true, the rule is said to be applicable to C.
When applying a rule to call C, Picat rewrites C into Body. If the used rule is non-backtrackable,
then the rewriting is a commitment, and the program can never backtrack to C. If the used rule
is backtrackable, however, the program will backtrack to C once Body fails, meaning that Body
will be rewritten back to C, and the next applicable rule will be tried on C.
Example
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.
fib(N,F) => throw $error(wrong_argument,fib,N).
A call matches the head fib(0,F) if the first argument is 0. The second argument can
be anything. For example, for the call fib(0,2), the first rule is applied, since fib(0, 2)
matches its head. However, when the body is executed, the call 2 = 1 fails.
The predicate fib/2 can also be defined using if-statement as follows:
fib(N,F) =>
if (N = 0; N = 1)
5
F = 1
elseif (N > 1)
fib(N-1,F1), fib(N-2,F2), F = F1+F2
else
throw $error(wrong_argument,fib,N)
end.
An if statement takes the form if (Cond) Goal1 else Goal2 end.2 The goal Goal1 can
contain one or more elseif clauses. The else part can be omitted. In that case the else part is
assumed to be else true. The built-in throw E throws term E as an exception.
Example
member(X,[Y|_]) ?=> X = Y.
member(X,[_|L]) => member(X,L).
The pattern [Y|_] matches any list. The backtrackable rule makes a call nondeterministic,
and the predicate can be used to retrieve elements from a list one at a time through backtracking.
Picat> member(X,[1,2,3])
X = 1;
X = 2;
X =
3;
no
After Picat returns an answer, users can type a semicolon immediately after the answer to ask for
the next answer. If users only want one answer to be returned from a call, they can use once
Call to stop backtracking.
The version of member that checks if a term occurs in a list can be defined as follows:
The first rule is applicable to a call if the second argument is a list and the first argument of the call
is identical to the first element of the list.
Horn Clauses
Picat supports Prolog-style Horn clauses.3 A Horn clause takes the form Head :- Body. When
Body is true, the clause can be written as Head. Let Head be p(t1 , . . . , tn ). The Horn clause
can be translated equivalently to the following pattern-matching rule:
where the dollar symbols indicate that all of the ti ’s are terms, rather than function calls.
A predicate definition that consists of Horn clauses can be preceded by an index declaration
in the form
6
where each Mij is either + (meaning indexed) or − (meaning not indexed). When a predicate
defined by Horn clauses is not preceded by an index declaration, Picat automatically generates one
for the predicate. For each index pattern (Mi1 , . . . , Min ), the compiler generates a version of the
predicate that indexes all of the + arguments. An index declaration only affects the efficiency, but
not the behavior of the predicate. It is assumed that there is a default version of the predicate that
has none of its arguments indexed.
Example
index (+,-) (-,+)
edge(a,b).
edge(a,c).
edge(b,c).
edge(c,b).
For a predicate of Horn clauses, a matching version of the predicate is selected for a call. If no
matching version is available, Picat uses the default version. For example, for the call edge(X,Y),
if both X and Y are free, then the default version is used.
A function call always succeeds with a return value if no exception occurs. Functions are defined
with non-backtrackable rules in which the head is an equation F =X, where F is the function
pattern in the form f (t1 , . . . , tn ) and X holds the return value. When n = 0, the parentheses can
be omitted.
Example
fib(0) = F => F = 1.
fib(1) = F => F = 1.
fib(N) = F, N > 1 => F = fib(N-1)+fib(N-2).
A function call never fails and never succeeds more than once. For function calls such as fib(-1)
or fib(X), Picat raises an exception.
Picat allows inclusion of function facts in the form f (t1 ,. . .,tn )=Exp in function definitions.
Example
fib(0) = 1.
fib(1) = 1.
fib(N) = F, N > 1 => F = fib(N-1)+fib(N-2).
qsort([]) = [].
qsort([H|T]) =
qsort([E : E in T, E =< H]) ++ [H] ++ qsort([E : E in T, E > H]).
7
Function facts are automatically indexed on all of the input arguments, and hence no index decla-
ration is necessary. Note that while a predicate call with no argument does not need parentheses, a
function call with no argument must be followed with parentheses, unless the function is module-
quantified, as in [Link].
The fib function can also be defined as follows:
The conditional expression returns 1 if the condition (N = 0; N = 1) is true, and the value of
fib(N-1)+fib(N-2) if the condition is false.
Picat allows assignments in rule bodies. An assignment takes the form LHS:=RHS, where LHS
is either a variable or an access of a compound value in the form X[...]. When LHS is an
access in the form X[I], the component of X indexed I is updated. This update is undone if
execution backtracks over this assignment.
Example
test => X = 0, X := X+1, X := X+2, write(X).
In order to handle assignments, Picat creates new variables at compile time. In the above
example, at compile time, Picat creates a new variable, say X1, to hold the value of X after the
assignment X := X+1. Picat replaces X by X1 on the LHS of the assignment. It also replaces all
of the occurrences of X to the right of the assignment by X1. When encountering X1 := X1+2,
Picat creates another new variable, say X2, to hold the value of X1 after the assignment, and
replaces the remaining occurrences of X1 by X2. When write(X2) is executed, the value held
in X2, which is 3, is printed. This means that the compiler rewrites the above example as follows:
Picat supports foreach and while statements for programming repetitions. A foreach
statement takes the form
where each iterator, Ei in Di , can be followed by an optional condition Condi . Within each
iterator, Ei is an iterating pattern, and Di is an expression that gives a compound value. The
foreach statement means that Goal is executed for every possible combination of values E1 ∈
D1 , . . ., En ∈ Dn that satisfies the conditions Cond1 , . . ., Condn .4
A while statement takes the form
while (Cond)
Goal
end
It repeatedly executes Goal as long as Cond succeeds. A variant of the while loop in the form of
4
The condition break(Cond) terminates the loop when Cond is true.
8
do
Goal
while (Cond)
executes Goal one time before testing Cond.
A loop statement forms a name scope. Variables that occur only in a loop, but do not occur
before the loop in the outer scope, are local to each iteration of the loop. For example, in the
following rule:
p(A) =>
foreach (I in 1 .. [Link])
E = A[I],
writeln(E)
end.
the variables I and E are local, and each iteration of the loop has its own values for these variables.
Example
write_map(Map) =>
foreach ((Key = Value) in Map)
writef("%w = %w\n",Key,Value)
end.
The function read_list reads a sequence of integers into a list, terminating when 0 is read. The
loop corresponds to the following sequence of recurrences:
L=[]
L1 =[e1 |L]
L2 =[e2 |L1 ]
...
Ln =[en |Ln−1 ]
List=Ln
Note that the list of integers is in reversed order. If users want a list in the same order as the input,
then the following loop can be used:
9
read_list = List =>
List = L,
E = read_int(),
while (E != 0)
L = [E|T],
L := T,
E := read_int()
end,
L = [].
This loop corresponds to the following sequence of recurrences:
L=[e1 |L1 ]
L1 =[e2 |L2 ]
...
Ln−1 =[en |Ln ]
Ln =[]
Loop statements are compiled into tail-recursive predicates. For example, the second read_list
function given above is compiled into:
read_list = List =>
List = L,
E = read_int(),
p(E,L,Lout),
Lout = [].
1.5 Tabling
A predicate defines a relation where the set of facts is implicitly generated by the rules. The
process of generating the facts may never end and/or may contain a lot of redundancy. Tabling
can prevent infinite loops and redundancy by memorizing calls and their answers. In order to have
all calls and answers of a predicate or function tabled, users just need to add the keyword table
before the first rule.
10
Example
table
fib(0) = 1.
fib(1) = 1.
fib(N) = fib(N-1)+fib(N-2).
When not tabled, the function call fib(N) takes exponential time in N. When tabled, however, it
takes only linear time.
Users can also give table modes to instruct the system on what answers to table. Mode-directed
tabling is especially useful for dynamic programming problems. In mode-directed tabling, a plus-
sign (+) indicates input, a minus-sign (-) indicates output, max indicates that the corresponding
variable should be maximized, min indicates that the corresponding variable should be minimized,
and nt indicates that the corresponding argument is not tabled.5
Example
table(+,+,min)
edit([],[],D) => D = 0.
edit([X|Xs],[X|Ys],D) =>
edit(Xs,Ys,D).
edit(Xs,[Y|Ys],D) ?=> % insert
edit(Xs,Ys,D1),
D = D1+1.
edit([X|Xs],Ys,D) => % delete
edit(Xs,Ys,D1),
D = D1+1.
For a call edit(L1,L2,D), where L1 and L2 are given lists and D is a variable, the rules can
generate all facts, each of which contains a different editing distance between the two lists. The
table mode table(+,+,min) tells the system to keep a fact with the minimal editing distance.
A tabled predicate can be preceded by both a table declaration and at most one index declara-
tion if it contains facts. The order of these declarations is not important.
1.6 Modules
A module is a source file with the extension .pi. A module begins with a module name declara-
tion and optional import declarations. A module declaration has the form:
module N ame.
where N ame must be the same as the main file name. A file that does not begin with a module
declaration is assumed to belong to the global module, and all of the predicates and functions that
are defined in such a file are visible to all modules as well as the top-level of the interpreter.
An import declaration takes the form:
11
where each N amei is a module name. When a module is imported, all of its public predicates and
functions will be visible to the importing module. A public predicate or function in a module can
also be accessed by preceding it with a module qualifier, as in m.p(), but the module still must
be imported.
Atoms and structure names do not belong to any module, and are globally visible. In a module,
predicates and functions are assumed to be visible both inside and outside of the module, unless
their definitions are preceded by the keyword private.
Example
% in file my_sum.pi
module my_sum.
private
sum_aux([],Sum0,Sum) => Sum = Sum0.
sum_aux([X|L],Sum0,Sum) => sum_aux(L,X+Sum0,Sum).
% in file test_my_sum.pi
module test_my_sum.
import my_sum.
go =>
writeln(my_sum([1,2,3,4])).
The predicate sum_aux is private, and is never visible outside of the module. The following
shows a session that uses these modules.
Picat> load("test_my_sum")
Picat> go
10
The command load(File) loads a module file into the system. If the file has not been compiled,
then the load command compiles the file before loading it. If this module is dependent on other
modules, then the other modules are loaded automatically if they are not yet in the system.6 When
a module is loaded, all of its public predicates and functions become visible to the interpreter.
The Picat module system is static, meaning that the binding of normal calls to their definitions
takes place at compile time. For higher-order calls, however, Picat may need to search for their
definitions at runtime. Several built-in modules are imported by default, including basic, io,
math, and sys. For a normal call that is not higher-order in a module, the Picat compiler searches
modules for a definition in the following order:
1. The implicitly imported built-in modules in the order from basic, math, io to sys.
2. The enclosing module of the call.
3. The explicitly imported modules in the order that they were imported.
4. The global module.
6
Dependent modules must be in a path that is specified by the environment variable PICATPATH.
12
1.7 Constraints
Picat can be used as a modeling and solving language for constraint satisfaction and optimization
problems. A constraint program normally poses a problem in three steps: (1) generate variables;
(2) generate constraints over the variables; and (3) call solve to find a valuation for the variables
that satisfies the constraints, and possibly optimizes an objective function. Picat provides four
solver modules, including cp, sat, smt, and mip.
Example
import cp.
go =>
Vars = [S,E,N,D,M,O,R,Y], % generate variables
Vars :: 0..9,
all_different(Vars), % generate constraints
S #!= 0,
M #!= 0,
1000*S+100*E+10*N+D+1000*M+100*O+10*R+E
#= 10000*M+1000*O+100*N+10*E+Y,
solve(Vars), % search
writeln(Vars).
In arithmetic constraints, expressions are treated as data, and it is unnecessary to enclose them
with dollar-signs.
The loops provided by Picat facilitate modeling of many constraint satisfaction and optimiza-
tion problems. The following program solves a Sudoku puzzle:
import cp.
sudoku =>
instance(N,A),
A :: 1..N,
foreach (Row in 1..N)
all_different(A[Row])
end,
foreach (Col in 1..N)
all_different([A[Row,Col] : Row in 1..N])
end,
M = floor(sqrt(N)),
foreach (Row in 1..M, Col in 1..M)
Square = [A[Row1,Col1] :
Row1 in (Row-1)*M+1..Row*M,
Col1 in (Col-1)*M+1..Col*M],
all_different(Square)
end,
solve(A),
foreach (I in 1..N) writeln(A[I]) end.
instance(N,A) =>
13
N = 9,
A = {{2,_,_,6,7,_,_,_,_},
{_,_,6,_,_,_,2,_,1},
{4,_,_,_,_,_,8,_,_},
{5,_,_,_,_,9,3,_,_},
{_,3,_,_,_,_,_,5,_},
{_,_,2,8,_,_,_,_,7},
{_,_,1,_,_,_,_,_,4},
{7,_,8,_,_,_,6,_,_},
{_,_,_,_,5,3,_,_,8}}.
Recall that variables that occur within a loop, and do not occur before the loop in the outer scope,
are local to each iteration of the loop. For example, in the third foreach statement of the
sudoku predicate, the variables Row, Col, and Square are local, and each iteration of the
loop has its own values for these variables.
1.8 Exceptions
An exception is an event that occurs during the execution of a program that requires a special
treatment. In Picat, an exception is just a term. Example exceptions thrown by the system include:
• divide_by_zero
• file_not_found
• number_expected
• interrupt
• out_of_range
A predicate or function is said to be higher-order if it takes calls as arguments. The built-ins call,
apply, and find_all are higher-order. The predicate call(S,Arg1 ,. . .,Argn ), where S
is an atom or a structure, calls the predicate named by S with the arguments that are specified in S
together with extra arguments Arg1 ,. . .,Argn . The function apply(S,Arg1 ,. . .,Argn ) is sim-
ilar to call, except that apply returns a value. The function findall(T emplate,S) returns
a list of all possible solutions of call(S) in the form of T emplate. Other higher-order predi-
cates include \+/1, call_cleanup/2, catch/3, count_all, freeze/2, maxof/2-3,
maxof_inc/2-3, minof/2-3, minof_inc/2-3, not/1, once/1, time/1, time2/1,
14
and time_out/3. All of these higher-order predicates are defined in the basic module, except
for time/1, time2/1, and time_out/3, which are defined in the sys module. Higher-order
calls cannot contain assignments or loops.
Example
Picat> S = $member(X), call(S,[1,2,3])
X = 1;
X = 2;
X = 3;
no
Picat> L = findall(X,member(X,[1,2,3])).
L = [1,2,3]
Picat> Z = apply(’+’,1,2)
Z = 3
Among the higher-order built-ins, findall is special in that it forms a name scope like a
loop. Local variables that occur in a findall call are not visible to subsequent calls in the body
or query.
The meta-call apply never returns a partially evaluated function. If the number of arguments
does not match the required number, then it throws an exception.
Example
map(_F,[]) = [].
map(F,[X|Xs]) = [apply(F,X)|map(F,Xs)].
map2(_F,[],[]) = [].
map2(F,[X|Xs],[Y|Ys]) = [apply(F,X,Y)|map2(F,Xs,Ys)].
fold(_F,Acc,[]) = Acc.
fold(F,Acc,[H|T]) = fold(F, apply(F,H,Acc),T).
Picat provides action rules for describing event-driven actors. An actor is a predicate call that can
be delayed, and can be activated later by events. Each time an actor is activated, an action can be
executed. A predicate for actors contains at least one action rule in the form:
where Head is an actor pattern, Cond is an optional condition, Event is a non-empty set of event
patterns separated by ’,’, and Body is an action. For an actor and an event, an action rule is
15
said to be applicable if the actor matches Head and Cond is true. A predicate for actors cannot
contain backtrackable rules.
An event channel is an attributed variable to which actors can be attached, and through which
events can be posted to actors. A channel has four ports: ins, bound, dom, and any. An event
pattern in Event specifies the port to which the actor is attached. The event pattern ins(X)
attaches the actor to the ins-port of channel X, and the actor will be activated when X is instan-
tiated. The event pattern event(X,T ) attaches the actor to the dom-port of channel X. The
built-in post_event(X,T ) posts an event term T to the dom-port of channel X. After an
event is posted to a port of a channel, the actors attached to that port are activated. For an activated
actor, the system searches for an applicable rule and executes the rule body if it finds one. After
execution, the actor is suspended, waiting to be activated again by other events. Picat does not
provide a built-in for detaching actors from channels. An actor fails if no rule is applicable to it
when it is activated or the body of the applied rule fails. An actor becomes a normal call once a
normal non-backtrackable rule is applied to it.
Example
echo(X,Flag), var(Flag), {event(X,T)} => writeln(T).
echo(_X,_Flag) => writeln(done).
When a call echo(X,Flag) is executed, where Flag is a variable, it is attached to the dom-port
of X as an actor. The actor is then suspended, waiting for events posted to the dom-port. For this
actor definition, the command
echo(X,Flag), post_event(X,hello), post_event(X,picat).
prints out hello followed by picat. If the call foo(Flag) is inserted before the second call
to post_event, then var(Flag) fails when the actor is activated the second time, causing the
second rule to be applied to the actor. Then, the output will be hello followed by done. Note
that events are not handled until a non-inline call is executed. Replacing foo(Flag) by Flag
= 1 will result in a different behavior because Flag = 1 is an inline call.
Picat has three kinds of prebuilt maps: heap maps, global maps, and table maps. Prebuilt heap
maps are created on the heap immediately after the system is started. The built-in function
get_heap_map(ID) returns the heap map that is associated with ID, where ID must be a
ground term. If no heap map is associated with ID, then this function establishes an association
between ID and an unused heap map, and returns the map. A heap map is like a normal map.
Users use put to add key-value pairs into the map. Users use get to retrieve a value that is
associated with a key in the map. Changes to a heap map up to a choice point are undone when
execution backtracks to that choice point. The built-in function get_heap_map() returns the
heap map that is associated with a system-generated default identifier. There are an unlimited
number of prebuilt heap maps.
Global maps are created in the global area when the Picat system is started. The built-in
function get_global_map(ID) returns the global map that is associated with ID, where ID
must be a ground term. If no global map is associated with ID, then this function establishes an
association between ID and an unused global map, and returns the map. A big difference between
a global map and a heap map is that changes to the global map are not undone upon backtracking.
16
When a key-value pair is added into the global map, the variables in the value term are numbered
before they are copied to the global area. If the value term contains attributed variables, then the
attributes of the variables are not copied, and are therefore lost. When retrieving a value that is
associated with a key, the value term in the global area is copied back to the heap after all of the
numbered variables are unnumbered. The built-in function get_global_map() returns the
global map that is associated with a system-generated default identifier. The number of prebuilt
global maps is 97, and the system halts if a program requests more than 97 global maps.
Table maps are created in the table area when the Picat system is started. The built-in function
get_table_map(ID) returns the table map that is associated with ID, where ID must be a
ground term. If no table map is associated with ID, then this function establishes an association
between ID and an unused table map, and returns the map. Like the global map, changes to a
table map are not undone upon backtracking. Unlike the global map, however, keys and values are
hash-consed so that common ground sub-terms are not replicated in the table area. The built-in
function get_table_map() returns the table map that is associated with a system-generated
default identifier. The number of prebuilt table maps is 97, and the system halts if a program
requests more than 97 table maps.
The advantage of using prebuilt maps is that data can be accessed everywhere without being
passed as arguments, and the disadvantage is that it affects locality of data and thus the readabil-
ity of programs. In tabled programs, using prebuilt maps is discouraged because it may cause
unanticipated effects.
Example
go ?=>
get_heap_map(h1).put(one,1),
get_global_map(g1).put(one,1),
get_table_map(t1).put(one,1),
fail.
go =>
if (get_heap_map(h1).has_key(one))
writef("heap map h1 has key%n")
else
writef("heap map h1 has no key%n")
end,
if (get_global_map(g1).has_key(one))
writef("global map g1 has key%n")
else
writef("global map g1 has no key%n")
end,
if (get_table_map(t1).has_key(one))
writef("table map t1 has key%n")
else
writef("table map t1 has no key%n")
end.
17
The fail call in the first rule causes execution to backtrack to the second rule. After backtracking,
the pair added to the heap map by the first rule is lost, but the pair added to the global map and the
pair added to the table map remain.
18
Chapter 2
The Picat system is written in both C and Picat. The Picat interpreter is provided as a single
standalone executable file, named [Link] for Windows and picat for Unix. The Picat
interpreter provides an interactive programming environment for users to compile, load, debug,
and execute programs. In order to start the Picat interpreter, users first need to open an OS ter-
minal. In Windows, this can be done by selecting Start -> Run and typing cmd or selecting
Start -> Programs -> Accessories -> Command Prompt. In order to start the
Picat interpreter in any working directory, the environment variable path must be properly set to
contain the directory where the executable is located.
where OSP rompt is the OS prompt. After the interpreter is started, it responds with the prompt
Picat>, and is ready to accept queries.
In general, the picat command takes the following form:
where P icatM ainF ileN ame can have the extension .pi and can contain a path of directories,
and Opts is a sequence of options of the following:
• -d: This option puts Picat in debug mode after Picat is started. In debug mode, execution
can be traced, and the stack trace is printed once an error occurs.
• -g InitGoal: This option makes Picat execute a specified initial query InitGoal rather
than the default main predicate.
• -log: The option -log makes the system print log information and warning messages.
19
• -s Size: This option reserves Size words for the stack and the heap when the system is
started.
• -v:
Once the interpreter is started, users can type a query after the prompt. For example,
Picat> X = 1+1
X = 2
Picat> printf("hello"++" picat")
hello picat
The halt predicate, or the exit predicate, terminates the Picat interpreter. An alternative
way to terminate the interpreter is to enter ctrl-d (control-d) when the cursor is located at the
beginning of an empty line.
include N ame.
The include directive causes the content of the file named N ame to be copied verbatim to
where the directive occurs.
For the sake of demonstration we assume the existence of a file named [Link] in the
current working directory that stores the following program:
20
main =>
print(" Welcome to PICAT’s world! \n ").
main(Args) =>
print(" Welcome to PICAT’s world! \n"),
foreach (Arg in Args)
printf("%s\n", Arg)
end.
• cl(F ileN ame): A program first needs to be compiled and loaded into the system be-
fore it can be executed. The built-in predicate cl(F ileN ame) compiles and loads the
source file named F ileN [Link]. Note that if the full path of the file name is not given,
then the file is assumed to be in the current working directory. Also note that users do not
need to give the extension name. The system compiles and loads not only the source file
F ileN [Link], but also all of the module files that are either directly imported or indirectly
imported by the source file. The system searches for such dependent files in the directory
in which F ileN [Link] resides or the directories that are stored in the environment vari-
able PICATPATH. For F ileN [Link], the cl command loads the generated byte-codes
without creating a byte-code file. For example,
Picat> cl("welcome")
Compiling:: [Link]
[Link] compiled in 4 milliseconds
• cl: The built-in predicate cl (with no argument) compiles and loads a program from the
console, ending when the end-of-file character (ctrl-z for Windows and ctrl-d for
Unix) is typed.
• compile(F ileN ame): The built-in predicate compile(F ileN ame) compiles the file
F ileN [Link] and all of its dependent module files without loading the generated byte-
code files. The destination directory for the byte-code file is the same as the source file’s
directory. If the Picat interpreter does not have permission to write into the directory in
which a source file resides, then this built-in throws an exception. For example,
Picat> compile("welcome")
Compiling::[Link]
[Link] compiled in 4 milliseconds
• load(F ileN ame): The built-in predicate load(F ileN ame) loads the byte-code file
F ileN [Link] and all of its dependent byte-code files. For F ileN ame and its dependent
file names, the system searches for a byte-code file in the directory in which F ileN [Link]
resides or the directories that are stored in the environment variable PICATPATH. If the
byte-code file F ileN [Link] does not exist but the source file F ileN [Link] exists, then
this built-in compiles the source file and loads the byte codes without creating a qi file.
Picat> load("welcome")
loading...[Link]
21
2.1.4 How to Run Programs
After a program is loaded, users can query the program. For each query, the system executes
the program, and reports yes when the query succeeds and no when the query fails. When a
query that contains variables succeeds, the system also reports the bindings for the variables. For
example,
Picat> cl("welcome")
Compiling:: [Link]
[Link] compiled in 4 milliseconds
loading...
yes
Picat> main
Welcome to PICAT’s world!
yes
Users can ask the system to find the next solution by typing ’;’ after a solution if the query
has multiple solutions. For example,
Picat> member(X,[1,2,3])
X = 1;
X = 2;
X = 3;
no
Users can force a program to terminate by typing ctrl-c, or by letting it execute the built-
in predicate abort. Note that when the system is engaged in certain tasks, such as garbage
collection, users may need to wait for a while in order to see the termination after they type
ctrl-c.
$ picat welcome
Welcome to PICAT’s world!
$ picat welcome a b c
Welcome to PICAT’s world!
a
b
c
The ’$’ sign is the prompt of the OS. It is assumed that the environment variable PATH has
been set to contain the directory of the executable picat ([Link] for Windows), and the
environment variable PICATPATH has been set to contain the directory of the [Link] file
or the file is in the current working directory.
22
2.1.6 Creating Standalone Executables
It is possible to create a script that can be run as a standalone executable. For example, consider
the following script [Link] for Linux:
#!/bin/bash
picat [Link]
echo " Finished!"
Once the environment variables PATH and PICATPATH are set properly, and the script is set to
have the execution permission, it can be executed as follows:
$ [Link]
Welcome to PICAT’s world!
Finished!
The Picat system has three execution modes: non-trace mode, trace mode, and spy mode. In trace
mode, it is possible to trace the execution of a program, showing every call in every possible stage.
In order to trace the execution, the program must be recompiled while the system is in trace mode.
In spy mode, it is possible to trace the execution of individual functions and predicates that are spy
points. When the Picat interpreter is started, it runs in non-trace mode. The predicate debug or
trace changes the mode to trace. The predicate nodebug or notrace changes the mode to
non-trace.
In trace mode, the debugger displays execution traces of queries. An execution trace consists
of a sequence of call traces. Each call trace is a line that consists of a stage, the number of the call,
and the information about the call itself. For a function call, there are two possible stages: Call,
meaning the time at which the function is entered, and Exit, meaning the time at which the call
is completed with an answer. For a predicate call, there are two additional possible stages: Redo,
meaning a time at which execution backtracks to the call, and Fail, meaning the time at which
the call is completed with a failure. The information about a call includes the name of the call, and
the arguments. If the call is a function, then the call is followed by = and ? at the Call stage, and
followed by = V alue at the Exit stage, where V alue is the return value of the call.
Consider, for example, the following program:
p(X) ?=> X = a.
p(X) => X = b.
q(X) ?=> X = 1.
q(X) => X = 2.
Assume the program is stored in a file named [Link]. The following shows a trace for a
query:
Picat> debug
{Trace mode}
Picat> cl(myprog)
{Trace mode}
Picat> p(X), q(Y)
23
Call: (1) p(_328) ?
Exit: (1) p(a)
Call: (2) q(_378) ?
Exit: (2) q(1)
X = a
Y = 1 ?;
Redo: (2) q(1) ?
Exit: (2) q(2)
X = a
Y = 2 ?;
Redo: (1) p(a) ?
Exit: (1) p(b)
Call: (3) q(_378) ?
Exit: (3) q(1)
X = b
Y = 1 ?;
Redo: (3) q(1) ?
Exit: (3) q(2)
X = b
Y = 2 ?;
no
In trace mode, the debugger displays every call in every possible stage. Users can set spy points
so that the debugger only shows information about calls of the symbols that users are spying. Users
can use the predicate
spy $N ame/N
to set the functor N ame/N as a spy point, where the arity N is optional. If the functor is defined
in multiple loaded modules, then all these definitions will be treated as spy points. If no arity is
given, then any functor of N ame is treated as a spy point, regardless of the arity.
After displaying a call trace, if the trace is for stage Call or stage Redo, then the debugger
waits for a command from the users. A command is either a single letter followed by a carriage-
return, or just a carriage-return. See Appendix B for the debugging commands.
24
Chapter 3
Picat is a dynamically-typed language, in which type checking occurs at runtime. A variable gets a
type once it is bound to a value. In Picat, variables and values are terms. A value can be primitive
or compound. A primitive value can be an integer, a real number, or an atom. A compound value
can be a list or a structure. Strings, arrays, maps, sets, and heaps are special compound values.
This chapter describes the data types and the built-ins for each data type that are provided by the
basic module.
Many of the built-ins are given as operators. Table 3.1 shows all of the operators that are
provided by Picat. Unless the table specifies otherwise, the operators are left-associative. The
as-pattern operator (@) and the operators for composing goals, including not, once, conjunction
(, and &&), and disjunction (; and ||), will be described in Chapter 4 on Predicates and Func-
tions. The constraint operators (the ones that begin with #) will be described in Chapter 12 on
Constraints. In Picat, no new operators can be defined, and none of the existing operators can be
redefined.
The dot operator (.) is used in OOP notations for calling predicates and functions. It is
also used to qualify calls with a module name. The notation A1 .f (A2 , . . . , Ak ) is the same as
f (A1 , A2 , . . . , Ak ), unless A1 is an atom, in which case A1 must be a module qualifier for f . If
an atom needs to be passed as the first argument to a function or a predicate, then this notation
cannot be used. The notation [Link], where Attr does not have the form f(. . .), is the same
as the function call get(A, Attr). For example, the expression [Link] returns the name, and
the expression [Link] returns the arity of S if S is a structure. Note that the dot operator is
left-associative. For example, the expression X.f().g() is the same as g(f(X)). Also note
that functions in dot notation are always evaluated eagerly, and therefore should not be used in
term constructs or constraint expressions.
The following functions are provided for all terms:
• copy_term(T erm1 ) = T erm2 : This function copies T erm1 into T erm2 . If T erm1
is an attributed variable, then T erm2 will not contain any of the attributes.
• hash_code(T erm) = Code: This function returns the hash code of T erm. If T erm is
a variable, then the returned hash code is always 0.
• to_codes(T erm) = Codes: This function returns a list of character codes of T erm.
25
Table 3.1: Operators in Picat
Precedence Operators
Highest ., @
** (right-associative)
unary +, unary -, ~
* , /, //, /<, />, div, mod, rem
binary +, binary -
>>, <<
/\
^
\/
..
++ (right-associative)
=, !=, :=, ==, !==, =:=, <, =<, <=, >, >=, ::, in, notin, =..
#=, #!=, #<, #=<, #<=, #>, #>=, @<, @=<, @<=, @>, @>=
#~
#/\
#^
#\/
#=> (right-associative)
#<=>
not, once, \+
, (right-associative), && (right-associative)
Lowest ; (right-associative), || (right-associative)
26
• to_fstring(F ormat,Args . . .): This function converts the arguments in the Args . . .
parameter into a string, according to the format string F ormat, and returns the string. The
number of arguments in Args . . . cannot exceed 10. Format characters are described in
Chapter 10.
3.1 Variables
Variables in Picat, like variables in mathematics, are value holders. Unlike variables in imperative
languages, Picat variables are not symbolic addresses of memory locations. A variable is said to
be free if it does not hold any value. A variable is instantiated when it is bound to a value. Picat
variables are single-assignment, which means that after a variable is instantiated to a value, the
variable will have the same identity as the value. After execution backtracks over a point where a
binding took place, the value that was assigned to a variable will be dropped, and the variable will
be turned back into a free variable.
A variable name is an identifier that begins with a capital letter or the underscore. For example,
the following are valid variable names:
X1 _ _ab
The name _ is used for anonymous variables. In a program, different occurrences of _ are treated
as different variables. So the test _ == _ is always false.
The following two built-ins are provided to test whether a term is a free variable:
• var(T erm): This predicate is true if T erm is a free variable.
• get_attr(X,Key) = V al: This function returns the V al of the key-value pair Key=V al
that is attached to X. It throws an error if X has no attribute named Key.
27
3.2 Atoms
An atom is a symbolic constant. An atom name can either be quoted or unquoted. An unquoted
name is an identifier that begins with a lower-case letter, followed by an optional string of letters,
digits, and underscores. A quoted name is a single-quoted sequence of arbitrary characters. A
character can be represented as a single-character atom. For example, the following are valid atom
names:
x x_1 ’_’ ’\\’ ’a\’b\n’ ’_ab’ ’$%’
No atom name can last more than one line. An atom name cannot contain more than 1000 char-
acters. The backslash character ’\’ is used as the escape character. So, the name ’a\’b\n’
contains four characters: a, ’, b, and \n.
The following built-ins are provided for atoms:
• ascii_alpha(T erm): This predicate is true if T erm is an atom and the atom is made
of one letter.
• ascii_alpha_digit(T erm): This predicate is true if T erm is an atom and the atom
is made of one letter or one digit.
• ascii_digit(T erm): This predicate is true if T erm is an atom and the atom is made
of one digit.
• ascii_lowercase(T erm): This predicate is true if T erm is an atom and the atom is
made of one lowercase letter.
• ascii_uppercase(T erm): This predicate is true if T erm is an atom and the atom is
made of one uppercase letter.
• atom_chars(Atm) = String: This function returns string that contains the characters
of the atom Atm. It throws an error if Atm is not an atom.
• atom_codes(Atm) = List: This function returns the list of codes of the characters of
the atom Atm. It throws an error if Atm is not an atom.
• char(T erm): This predicate is true if T erm is an atom and the atom is made of one
character.
• chr(Code) = Char: This function returns the UTF-8 character of the code point Code.
• digit(T erm): This predicate is true if T erm is an atom and the atom is made of one
digit.
• len(Atom) = Len: This function returns the number of characters in Atom. Note that
this function is overloaded in such a way that the argument can also be an array, a list, or a
structure.
• ord(Char) = Int: This function returns the code point of the UTF-8 character Char. It
throws an error if Char is not a single-character atom.
28
Table 3.2: Arithmetic Operators
X ** Y power
+X same as X
-X sign reversal
~X bitwise complement
X * Y multiplication
X / Y division
X // Y integer division, truncated
X /> Y integer division (ceiling(X / Y ))
X /< Y integer division (floor(X / Y ))
X div Y integer division, floored
X mod Y modulo, same as X - floor(X div Y ) * Y
X rem Y remainder (X - (X // Y ) * Y )
X + Y addition
X - Y subtraction
X » Y right shift
X « Y left shift
X /\ Y bitwise and
X ^ Y bitwise xor
X \/ Y bitwise or
F rom .. Step .. T o A range (list) of numbers with a step
F rom .. T o A range (list) of numbers with step 1
X =:= Y pretty much (numerically) equal
3.3 Numbers
A number can be an integer or a real number. An integer can be a decimal numeral, a binary
numeral, an octal numeral, or a hexadecimal numeral. In a numeral, digits can be separated by
underscores, but underscore separators are ignored by the tokenizer. For example, the following
are valid integers:
12_345 a decimal numeral
0b100 4 in binary notation
0o73 59 in octal notation
0xf7 247 in hexadecimal notation
A real number consists of an optional integer part, an optional decimal fraction preceded by
a decimal point, and an optional exponent. If an integer part exists, then it must be followed by
either a fraction or an exponent in order to distinguish the real number from an integer literal. For
example, the following are valid real numbers.
12.345 0.123 12-e10 0.12E10
Table 3.2 gives the meaning of each of the numeric operators in Picat, from the operator with
the highest precedence (**) to the one with the lowest precedence (..). Except for the power
operator **, which is right-associative, all of the arithmetic operators are left-associative.
In addition to the numeric operators, the basic module also provides the following built-ins
for numbers:
29
• between(F rom,T o,X) (nondet): If X is bound to a number, then this predicate deter-
mines whether X is between F rom and T o. Otherwise, if X is unbound, then this predicate
nondeterministically selects X from the numbers that are between F rom and T o with step
1. It is the same as member(X,[E : E in F rom..T o]), but it does not create
the list.
• max(X,Y ) = V al: This function returns the maximum of X and Y , where X and Y are
terms.
• maxint_small() = Int: This function returns the maximum integer that is represented
in one word. All integers that are greater than this integer are represented as big integers.
• min(X,Y ) = V al: This function returns the minimum of X and Y , where X and Y are
terms.
• minint_small() = Int: This function returns the minimum integer that is represented
in one word. All integers that are smaller than this integer are represented as big integers.
• number_codes(N um) = List: This function returns a list of codes of the characters
of N um. It is the same as number_chars(N um).to_codes().
30
• to_number(AN S) = N um: This function is the same as AN S if AN S is a num-
ber, the same as ord(AN S)-ord(’0’) if AN S is a digit character, and the same as
parse_term(AN S) if AN S is a string.
A compound term can be a list or a structure. Components of compound terms can be accessed
with subscripts. Let X be a variable that references a compound value, and let I be an integer
expression that represents a subscript. The index notation X[I] is a special function that returns
the Ith component of X if I is an integer or a list of components if I is a range in the form of l..u,
counting from the beginning. Subscripts begin at 1, meaning that X[1] is the first component of
X. An index notation can take multiple subscripts. For example, the expression X[1,2] is the
same as T[2], where T is a temporary variable that references the component that is returned by
X[1]. The predicate compound(T erm) is true if T erm is a compound term.
3.4.1 Lists
A list takes the form [t1 ,. . .,tn ], where each ti (1 ≤ i ≤ n) is a term. Let L be a list. The
expression [Link], which is the same as the functions get(L,length) and length(L),
returns the length of L. Note that a list is represented internally as a singly-linked list. Also note
that the length of a list is not stored in memory; instead, it is recomputed each time that the function
length is called.
The symbol ’|’ is not an operator, but a separator that separates the first element (so-called
car) from the rest of the list (so-called cdr). The cons notation [H|T ] can occur in a pattern or
in an expression. When it occurs in a pattern, it matches any list in which H matches the car and
T matches the cdr. When it occurs in an expression, it builds a list from H and T . The notation
[A1 ,A2 ,. . .,An |T ] is a shorthand for [A1 |[A2 |. . .[An |T ]. . .]. So [a,b,c] is the same
as [a|[b|[c|[]]]].
The basic module provides the following built-ins on lists, most of which are overloaded for
strings (3.4.2) and arrays (see 3.4.4).
• List1 ++ List2 = List: This function returns the concatenated list of List1 and List2 .
31
• avg(List) = V al: This function returns the average of all the elements in List. This
function throws an exception if List is not a list or any of the elements is not a number.
• flatten(List) = ResList: This function flattens a list of nested lists into a list. For
example, flatten([[1],[2,[3]]]) returns [1,2,3].
• head(List) = T erm: This function returns the head of the list List. For example,
head([1,2,3]) returns 1.
• insert(List,Index,Elm) = ResList: This function inserts Elm into List at the in-
dex Index, returning the result in ResList. After insertion, the original List is not changed,
and ResList is the same as
[Link](1,Index-1)++[Elm|[Link](Index,[Link])].
• insert_ordered(List,T erm): This function inserts T erm into the ordered list List,
such that the resulting list remains sorted.
• len(List) = Len: This function returns the number of elements in List. Note that this
function is overloaded in such a way that the argument can also be an atom, an array, or a
structure.
• max(List) = V al: This function returns the maximum value that is in List, where List
is a list of terms.
• min(List) = V al: This function returns the minimum value that is in List, where List
is a list or an array of terms.
32
• new_list(N ) = List: This function creates a new list that has N free variable argu-
ments.
• new_list(N ,InitV al) = List: This function creates a new list that has N arguments
all initialized to InitV al.
• nth(Index,List,Elem) (nondet): This predicate is true when Elem is the Index’th el-
ement of List. Counting starts at 1. When Index is a variable, this predicate may backtrack,
instantiating Index to a different integer between 1 and len(List).
• prod(List) = V al: This function returns the product of all of the values in List.
• remove_dups(List) = ResList: This function removes all duplicate values from List,
retaining only the first occurrence of each value. The result is returned in ResList. Note that
an O(n2 ) algorithm is used in the implementation. For long lists, sort_remove_dups
is faster than this function.
• reverse(List) = ResList: This function reverses the order of the elements in List,
returning the result in ResList.
• sort(List) = SList: This function sorts the elements of List in ascending order, re-
turning the result in SList.
• sort(List,KeyIndex) = SList: This function sorts the elements of List by the key
index KeyIndex in ascending order, returning the result in SList. The elements of List
must be compound values and KeyIndex must be a positive integer that does not exceed the
length of any of the elements of List. In particular, if an element is a list, then KeyIndex
must be either 1 or 2. This function is defined as follows:
sort(List).remove_dups()
sort(List,KeyIndex).remove_dups()
33
• sort_down_remove_dups(List) = SList: This function is the same as the follow-
ing, but is faster.
sort_down(List).remove_dups()
sort_down(List,KeyIndex).remove_dups()
• slice(List,F rom,T o) = SList: This function returns the sliced list of List from
index F rom through index T o. F rom must not be less than 1. It is the same as the index
notation List[F rom..T o].
slice(List,F rom,[Link])
• sum(List) = V al: This function returns the sum of all of the values in List.
• tail(List) = T erm: This function returns the tail of the list List. For example, the call
tail([1,2,3]) returns [2,3].
• to_array(List) = Array: This function converts the list List to an array. The ele-
ments of the array are in the same order as the elements of the list.
• zip(List1 ,List2 ,. . .,Listn ) = List: This function makes a list of array tuples. The
jth tuple in the list takes the form {E1j , . . . , Enj }, where Eij is the jth element in Listi .
In the current implementation, n can be 2, 3, or 4.
3.4.2 Strings
A string is represented as a list of single-character atoms. For example, the string "hello" is the
same as the list [h,e,l,l,o]. In addition to the built-ins on lists, the following built-ins are
provided for strings:
3.4.3 Structures
A structure takes the form $s(t1 ,. . .,tn ), where s is an atom, and n is called the arity of the
structure. The dollar symbol is used to distinguish a structure from a function call. The functor of
a structure comprises the name and the arity of the structure.
The following types of structures can never denote functions, meaning that they do not need
to be preceded by a $ symbol.
34
Goals: (a,b), (a;b), not a, X = Y, X != 100, X > 1
Constraints: X+Y #= 100, X #!= 1
Arrays: {2,3,4}, {P1,P2,P3}
The compiler will report a syntax error when it encounters any of these expressions within a term
constructor.
The following built-ins are provided for structures:
• T =.. L: The name and the arguments of T comprise the list L. This predicate extracts
the name and arguments of T when T is instantiated, and constructs T from the list L when
L is instantiated.
• arg(I,T ,A): The Ith argument of the term T is A. This predicate is the equivalent to:
X = T , A = X[I], except when I is 0 or T is a list. When I is 0, the call fails. When T is a
list, only two indices, namely 1 and 2, are acceptable. For I = 1, A is unified with the car of
the list, and for I = 2, A is unified with the cdr of the list.
• arity(Struct) = Arity: This function returns the arity of Struct, which must be a
structure.
• functor(T ,F ,N ): The principal functor of the term T has the name F and the arity N .
This predicate extracts the functor F/N of T when T is instantiated, and constructs a term
T of the given functor F/N when T is a variable.
• to_list(Struct) = List: This function returns a list of the components of the structure
Struct.
35
3.4.4 Arrays
An array takes the form {t1 ,. . .,tn }, which is a special structure with the name ’{}’ and ar-
ity n. Note that, unlike a list, an array always has its length stored in memory, so the function
length(Array) always takes constant time. Also note that Picat supports constant-time access
of array elements, so the index notation A[I] takes constant time when I is an integer.
In addition to the built-ins for structures, the following built-ins are provided for arrays:
The following built-ins, which are originally provided for lists (see 3.4.1), are overloaded for
arrays:
• avg(Array) = V al
• first(Array) = T erm
• last(Array) = T erm
• len(Array) = Len
• length(Array) = Len
• max(Array) = V al
• min(Array) = V al
• nth(Index,List,Elem) (nondet)
• prod(Array) = V al
• reverse(Array) = ResArray
• sum(Array) = V al
• sort(Array) = SArray
• sort(Array,KeyIndex) = SArray
• sort_remove_dups(Array) = SArray
• sort_remove_dups(Array,KeyIndex) = SArray
• sort_down(Array) = SArray
• sort_down(Array,KeyIndex) = SArray
• sort_down_remove_dups(Array) = SArray
36
• sort_down_remove_dups(Array,KeyIndex) = SArray
Note that many of the overloaded built-ins for arrays are not implemented efficiently, but are
provided for convenience. For example, sort(Array) is implemented as follows:
sort(Array) = Array.to_list().sort().to_array().
3.4.5 Maps
A map is a hash-table that is represented as a structure that contains a set of key-value pairs. The
functor of the structure that is used for a map is not important. An implementation may ban access
to the name and the arity of the structure of a map. Maps must be created with the built-in function
new_map, unless they are prebuilt (see Section 1.11). In addition to the built-ins for structures,
the following built-ins are provided for maps:
• clear(M ap): This predicate clears the map M ap. It throws an error if M ap is not a map.
• del(M ap,Key): This predicate deletes from M ap the pair that has the key Key. It
throws an error if M ap is not a map. It does nothing if M ap does not contain a pair with
Key.
• get(M ap,Key) = V al: This function returns V al of the key-value pair Key=V al in
M ap. It throws an error if M ap does not contain the key Key.
• get(M ap,Key,Def aultV al) = V al: This function returns V al of the key-value pair
Key=V al in M ap. It returns Def aultV al if M ap does not contain Key.
• keys(X) = List: This function returns the list of keys of the pairs in M ap.
• map_to_list(M ap) = P airsList: This function returns a list of Key=V al pairs that
constitute M ap.
• new_map(IntOrP airsList) = M ap: This function creates a map with an initial capac-
ity or an initial list of pairs.
• new_map(N ,P airsList) = M ap: This function creates a map with the initial capacity
N , the initial list of pairs P airsList, where each pair has the form Key=V al.
• put(M ap,Key,V al): This predicate attaches the key-value pair Key=V al to M ap,
where Key is a non-variable term, and V al is any term.
• values(M ap) = List: This function returns the list of values of the pairs in M ap.
• size(M ap) = Size: This function returns the number of pairs in M ap.
37
3.4.6 Sets
A set is a map where every key is associated with the atom not_a_value. All of the built-ins
for maps can be applied to sets. For example, the built-in predicate has_key(Set,Elm) tests
if Elm is in Set. In addition to the built-ins on maps, the following built-ins are provided for sets:
• new_set(IntOrKeysList) = Set: This function creates a set with an initial capacity
or an initial list of keys.
• new_set(N ,KeysList) = Set: This function creates a set with the initial capacity N
and the initial list of keys KeysList.
3.4.7 Heaps
A heap2 is a complete binary tree represented as an array. A heap can be a min-heap or a max-
heap. In a min-heap, the value at the root of each subtree is the minimum among all the values in
the subtree. In a max-heap, the value at the root of each subtree is the maximum among all the
values in the subtree.
• heap_is_empty(Heap): This predicate is true if Heap is empty.
• heap_pop(Heap) = Elm: This function removes the root element from the heap, and
returns the element. As the function updates the heap, it is not pure. The update will be
undone when execution backtracks over the call.
• heap_push(Heap,Elm): This predicate pushes Elm into Heap in a way that maintains
the heap property. The update to Heap will be undone when execution backtracks over the
call.
• heap_top(Heap) = Elm: This function returns the element at the root of the heap. If
Heap is a min-heap, then the element is guaranteed to be the minimum, and if Heap is a
max-heap, then the element is guaranteed to be the maximum.
Example
main =>
L = [1,3,2,4,5,3,6],
H = new_min_heap(L),
N = H.heap_size(),
S = [H.heap_pop() : _ in 1..N],
println(S).
2
Note that a heap, as a data structure, is different from the heap area, in which data, including heap maps, are stored.
38
3.5 Equality Testing, Unification, and Term Comparison
The equality test T1 == T2 is true if term T1 and term T2 are identical. Two variables are identi-
cal if they are aliases. Two primitive values are identical if they have the same type and the same
internal representation. Two lists are identical if the cars are identical and the cdrs are identical.
Two structures are identical if their functors are the same and their components are pairwise iden-
tical. The inequality test T1 !== T2 is the same as not T1 == T2 . Note that two terms can be
identical even if they are stored in different memory locations. Also note that it takes linear time
in the worst case to test whether two terms are identical, unlike in C-family languages, in which
the equality test operator == only compares addresses.
The unification T1 = T2 is true if term T1 and term T2 are already identical, or if they can be
made identical by instantiating the variables in the terms. The built-in T1 != T2 is true if term T1
and term T2 are not unifiable. The predicate bind_vars(T erm,V al) binds all of the variables
in T erm to V al.
Example
Picat> X = 1
X = 1
Picat> $f(a,b) = $f(a,b)
yes
Picat> [H|T] = [a,b,c]
H = a
T = [b,c]
Picat> $f(X,b) = $f(a,Y)
X = a
Y = b
Picat> bind_vars({X,Y,Z},a)
Picat> X = $f(X)
The last query illustrates the occurs-check problem. When binding X to f(X), Picat does not
check if X occurs in f(X) for the sake of efficiency. This unification creates a cyclic term, which
can never be printed.
When a unification’s operands contain attributed variables, the implementation is more com-
plex. When a plain variable is unified with an attributed variable, the plain variable is bound to the
attributed variable. When two attributed variables, say Y and O, where Y is younger than O, are
unified, Y is bound to O, but Y ’s attributes are not copied to O. Since garbage collection does not
preserve the seniority of terms, the result of the unification of two attributed variables is normally
unpredictable.
Example
39
Picat> 1 == 1.0
no
In the first query, 1 is an integer, while 1.0 is a real number, so the equality test fails. However, the
second query, which is a numerical equality test, succeeds.
• T1 is T2 : If T1 is a variable, then the call binds the variable to the result of T2 , which must
be a number after evaluation. If T1 is a non-variable expression, then the call is equivalent
to T1 =:= T2 .
var < number < atom < structure and array < list and string
Variables are ordered by their addresses. Note that the ordering of variables may change after
garbage collection. Numbers are ordered by their numerical values. Atoms are ordered lexico-
graphically. Structures are first ordered lexicographically by their names; if their names are the
same, then they are ordered by their components. Arrays are ordered as structures with the special
name ’{}’. Lists and strings are ordered by their elements.
• T erm1 @< T erm2: The term T erm1 precedes the term T erm2 in the standard order.
For example, a @< b succeeds.
• T erm1 @=< T erm2: The term T erm1 either precedes, or is identical to, the term T erm2
in the standard order. For example, a @=< b succeeds.
• T erm1 @> T erm2: The term T erm1 follows the term T erm2 in the standard order.
• T erm1 @>= T erm2: The term T erm1 either follows, or is identical to, the term T erm2
in the standard order.
3.6 Expressions
Expressions are made from variables, values, operators, and function calls. Expressions differ
from terms in the following ways:
40
A conditional expression, which takes the form cond(Cond,Exp1 ,Exp2 ), is a special kind
of function call that returns the value of Exp1 if the condition Cond is true and the value of Exp2
if Cond is false.
Note that, except for conditional expressions in which the conditions are made of predicates,
no expressions can contain predicates. A predicate is true or false, but never returns any value.
A predicate or function is said to be higher-order if it takes calls as arguments. The basic module
has the following higher-order predicates and functions.
• count_all(Call) = Count: This function returns the number of all possible instances
of call(Call) that are true. For example, count_all(member(X,[1,2,3])) re-
turns 3.
• findall(T emplate,Call) = Answers: This function returns a list of all possible in-
stances of call(Call) that are true in the form of T emplate. Note that T emplate is
assumed to be a term without function calls, and that Call is assumed to be a predicate call
whose arguments can contain function calls. Also note that, like a loop, findall forms
a name scope. For example, in findall(f(X),p(X,g(Y))), f(X) is a term even
though it is not preceded with $; g(Y) is a function call; the variables X and Y are assumed
to be local to findall if they do not occur before in the outer scope.
• find_all(T emplate,Call) = Answers: This function is the same as the above func-
tion.
• freeze(X,Call): This predicate delays the evaluation of Call until X becomes a non-
variable term.
41
This function applies the function F unc to every pair of elements (Ai , Bi ) by calling
apply(F unc,Ai ,Bi ), and returns a list of the results.
• reduce(F unc,List) = Res: If List is a list that contains only one element, this func-
tion returns the element. If List contains at least two elements, then the first two elements
A1 and A2 are replaced with apply(F unc,A1 ,A2 ). This step is repeatedly applied to
the list until the list contains a single element, which is the final value to be returned. The
order of the arguments is not important, meaning that the first argument can be a list and the
second one can be a function.
• acyclic_term(T erm): This predicate is true if T erm is acyclic, meaning that T erm
does not contain itself.
• and_to_list(Conj) = List: This function converts Conj in the form (a1 ,. . .,an )
into a list in the form [a1 ,. . .,an ].
• compare_terms(T erm1 ,T erm2 ) = Res: This function compares T erm1 and T erm2 .
If T erm1 < T erm2 , then this function returns −1. If T erm1 == T erm2 , then this func-
tion returns 0. Otherwise, T erm1 > T erm2 , and this function returns 1.
42
• different_terms(T erm1 ,T erm2 ): This constraint ensures that T erm1 and T erm2
are different. This constraint is suspended when the arguments are not sufficiently instanti-
ated.
• get_global_map(ID) = M ap: This function returns the global map with the identi-
fier ID, which must be a ground term.
• get_heap_map(ID) = M ap: This function returns the heap map with the identifier
ID, which must be ground term.
• get_table_map() = M ap: This function returns the default table map. The table map
is stored in the table area and both keys and values are hash-consed (i.e., common sub-terms
are shared).
• get_table_map(ID) = M ap: This function returns the table map with the identifier
ID, which must be a ground term.
• ground(T erm): This predicate is true if T erm is ground. A ground term does not contain
any variables.
• list_to_and(List) = Conj: This function converts List in the form [a1 ,. . .,an ]
into a term in the form (a1 ,. . .,an ).
• number_vars(T erm): This predicate numbers the variables in T erm by using the inte-
gers starting from 0. Different variables receive different numberings, and the occurrences
of the same variable all receive the same numbering.
• parse_term(String,T erm,V ars): This predicate uses the Picat parser to extract a
term T erm from String. V ars is a list of pairs, where each pair has the form N ame=V ar.
• second(Compound) = T erm: This function returns the second argument of the com-
pound term Compound.
• vars(T erm) = V ars: This function returns a list of variables that occur in T erm.
43
Chapter 4
In Picat, predicates and functions are defined with rules. Each rule is terminated by a dot (.)
followed by a white space or the newline character.
Picat has two types of pattern-matching rules: the non-backtrackable rule
Head, Cond => Body.
and the backtrackable rule
Head, Cond ?=> Body.
Picat also supports Prolog-style Horn clauses and Definite Clause Grammar (DCG) rules for
predicate definitions. A Horn clause takes the form:
Head :- Body.
which can be written as Head if Body is true. A DCG rule takes the form:
Head --> Body.
A predicate definition that consists of Horn clauses can be preceded by an index declaration, as
described in Section 1.2. Picat converts Horn clauses and DCG rules into pattern-matching rules.
4.1 Predicates
A predicate defines a relation, and can have zero, one, or multiple answers. Within a predicate, the
Head is a pattern in the form p(t1 , . . . , tn ), where p is called the predicate name, and n is called
the arity. When n = 0, the parentheses can be omitted. The condition Cond, which is an optional
goal, specifies a condition under which the rule is applicable. Cond cannot succeed more than
once. The compiler converts Cond to once Cond if would otherwise be possible for Cond to
succeed more than once.
For a call C, if C matches the pattern p(t1 , . . . , tn ) and Cond is true, then the rule is said to
be applicable to C. When applying a rule to call C, Picat rewrites C into Body. If the used rule
is non-backtrackable, then the rewriting is a commitment, and the program can never backtrack to
C. However, if the used rule is backtrackable, then the program will backtrack to C once Body
fails, meaning that Body will be rewritten back to C, and the next applicable rule will be tried on
C.
A predicate is said to be deterministic if it is defined with non-backtrackable rules only, non-
deterministic if at least one of its rules is backtrackable, and globally deterministic if it is determin-
istic and all of the predicates in the bodies of the predicate’s rules are also globally deterministic.
A deterministic predicate that is not globally deterministic can still have more than one answer.
44
Example
append(Xs,Ys,Zs) ?=> Xs = [], Ys = Zs.
append(Xs,Ys,Zs) =>
Xs = [X|XsR],
Zs = [X|ZsR],
append(XsR,Ys,ZsR).
4.2 Functions
A function is a special kind of a predicate that always succeeds with one answer. Within a function,
the Head is an equation p(t1 , . . . , tn )=X, where p is called the function name, and X is an
expression that gives the return value. Functions are defined with non-backtrackable rules only.
For a call C, if C matches the pattern p(t1 , . . . , tn ) and Cond is true, then the rule is said to be
applicable to C. When applying a rule to call C, Picat rewrites the equation C=X ′ into (Body,
X ′ =X), where X ′ is a newly introduced variable that holds the return value of C.
Picat allows inclusion of function facts in the form p(t1 ,. . .,tn )=Exp in function definitions.
The function fact p(t1 ,. . .,tn )=Exp is shorthand for the rule:
p(t1 ,. . .,tn )=X => X=Exp.
where X is a new variable.
Although all functions can be defined as predicates, it is preferable to define them as functions
for two reasons. Firstly, functions often lead to more compact expressions than predicates, because
arguments of function calls can be other function calls. Secondly, functions are easier to debug
than predicates, because functions never fail and never return more than one answer.
Example
qequation(A,B,C) = (R1,R2),
D = B*B-4*A*C,
45
D >= 0
=>
NTwoC = -2*C,
R1 = NTwoC/(B+sqrt(D)),
R2 = NTwoC/(B-sqrt(D)).
rev([]) = [].
rev([X|Xs]) = rev(Xs)++[X].
The function qequation(A,B,C) returns the pair of roots of A*X2 +B*X+C = 0. If the dis-
criminant B*B-4*A*C is negative, then an exception will be thrown.
The function rev(L) returns the reversed list of L. Note that the function rev(L) takes
quadratic time and space in the length of L. A tail-recursive version that consumes linear time and
space will be given below.
The pattern p(t1 , . . . , tn ) in the head of a rule takes the same form as a structure. Function calls
are not allowed in patterns. Also, patterns cannot contain index notations, dot notations, ranges,
array comprehensions, or list comprehensions. Pattern matching is used to decide whether a rule
is applicable to a call. For a pattern P and a term T , term T matches pattern P if P is identical
to T , or if P can be made identical to T by instantiating P ’s variables. Note that variables in the
term do not get instantiated after the pattern matching. If term T is more general than pattern P ,
then the pattern matching can never succeed.
Unlike calls in many committed-choice languages, calls in Picat are never suspended if they
are more general than the head patterns of the rules. A predicate call fails if it does not match the
head pattern of any of the rules in the predicate. A function call throws an exception if it does
not match the head pattern of any of the rules in the function. For example, for the function call
rev(L), where L is a variable, Picat will throw the following exception:
unresolved_function_call(rev(L)).
A pattern can contain as-patterns in the form V @P attern, where V is a new variable in the
rule, and P attern is a non-variable term. The as-pattern V @P attern is the same as P attern
in pattern matching, but after pattern matching succeeds, V is made to reference the term that
matched P attern. As-patterns can avoid re-constructing existing terms.
Example
merge([],Ys) = Ys.
merge(Xs,[]) = Xs.
merge([X|Xs],Ys@[Y|_]) = [X|Zs], X < Y => Zs = merge(Xs,Ys).
merge(Xs,[Y|Ys]) = [Y|merge(Xs,Ys)].
In the third rule, the as-pattern Ys@[Y|_] binds two variables: Ys references the second argu-
ment, and Y references the car of the argument. The rule can be rewritten as follows without using
any as-pattern:
Nevertheless, this version is less efficient, because the cons [Y|Ys] needs to be re-constructed.
46
4.4 Goals
In a rule, both the condition and the body are goals. Queries that the users give to the interpreter
are also goals. A goal can take one of the following forms:
• fail: This goal is always false. When fail occurs in a condition, the condition is false,
and the rule is never applicable. When fail occurs in a body, it causes execution to back-
track.
• p(t1 , . . . , tn ): This goal is a predicate call. The arguments t1 , . . . , tn are evaluated in the
given order, and the resulting call is resolved using the rules in the predicate p/n. If the
call succeeds, then variables in the call may get instantiated. Many built-in predicates are
written in infix notation. For example, X = Y is the same as ’=’(X,Y).
• not P : This goal is the negation of P . It is false if P is true, and true if P is false. Note
a negation goal can never succeed more than once. Also note that no variables can get
instantiated, no matter whether the goal is true or false.
• once P : This goal is the same as P , but can never succeed more than once.
The repeat predicate is often used to describe failure-driven loops. For example, the query
47
if (Cond1 )
Goal1
elseif (Cond2 )
Goal2
..
.
elseif (Condn )
Goaln
else
Goalelse
end
where the elseif and else clauses are optional. If the else clause is missing, then the
else goal is assumed to be true. For the if statement, Picat finds the first condition Condi
that is true. If such a condition is found, then the truth value of the if statement is the same
as Goali . If none of the conditions is true, then the truth value of the if statement is the same
as Goalelse . Note that no condition can succeed more than once.1
• throw Exception: This predicate throws the term Exception. This predicate will be
detailed in Chapter 6 on Exceptions.
• !: This special predicate, called a cut, is provided for controlling backtracking. A cut in the
body of a rule has the effect of removing the choice points, or alternative rules, of the goals
to the left of the cut.
• Loops: Picat has three types of loop statements: foreach, while, and do-while. A loop
statement is true if and only if every iteration of the loop is true. The details of loops are
given in Chapter 5.
A rule is said to be tail-recursive if the last call of the body is the same predicate as the head. The
last-call optimization enables last calls to reuse the stack frame of the head predicate if the frame
is not protected by any choice points. This optimization is especially effective for tail recursion,
because it converts recursion into iteration. Tail recursion runs faster and consumes less memory
than non-tail recursion.
The trick to convert a predicate (or a function) into tail recursion is to define a helper that
uses an accumulator parameter to accumulate the result. When the base case is reached, the
accumulator is returned. At each iteration, the accumulator is updated. Initially, the original
predicate (or function) calls the helper with an initial value for the accumulator parameter.
Example
min_max([H|T],Min,Max) =>
min_max_helper([H|T],H,Min,H,Max).
1
If Condi is not enclosed in parentheses, then it must be followed by the keyword then.
48
rev([]) = [].
rev([X|Xs]) = rev_helper(Xs,[X]).
rev_helper([],R) = R.
rev_helper([X|Xs],R) = rev_helper(Xs,[X|R]).
49
Chapter 5
This chapter discusses variable assignments, loop constructs, and list and array comprehensions
in Picat. It describes the scope of an assigned variable, indicating where the variable is defined,
and where it is not defined. Finally, it shows how assignments, loops, and list comprehensions are
related, and how they are compiled.
5.1 Assignments
Picat variables are single-assignment, meaning that once a variable is bound to a value, the variable
cannot be bound again. In order to simulate imperative language variables, Picat provides the
assignment operator :=. An assignment takes the form LHS:=RHS, where LHS is either a
variable or an access of a compound value in the form X[...]. When LHS is an access in
the form X[I], the component of X indexed I is updated. This update is undone if execution
backtracks over this assignment.
Example
test => X = 0, X := X + 1, X := X + 2, write(X).
The compiler needs to give special consideration to the scope of a variable. The scope of a
variable refers to the parts of a program where a variable occurs.
Consider the test example. This example binds X to 0. Then, the example tries to bind X
to X + 1. However, X is still in scope, meaning that X is already bound to 0. Since X cannot be
bound again, the compiler must perform extra operations in order to manage assignments that use
the := operator.
In order to handle assignments, Picat creates new variables at compile time. In the test
example, at compile time, Picat creates a new variable, say X1, to hold the value of X after the
assignment X := X + 1. Picat replaces X by X1 on the LHS of the assignment. All occurrences
of X after the assignment are replaced by X1. When encountering X1 := X1 + 2, Picat creates
another new variable, say X2, to hold the value of X1 after the assignment, and replaces the
remaining occurrences of X1 by X2. When write(X2) is executed, the value held in X2, which
is 3, is printed. This means that the compiler rewrites the above example as follows:
test => X = 0, X1 = X + 1, X2 = X1 + 2, write(X2).
5.1.1 If-Else
This leads to the question: what does the compiler do if the code branches? Consider the following
code skeleton.
50
Example
if_ex(Z) =>
X = 1, Y = 2,
if (Z > 0)
X := X * Z
else
Y := Y + Z
end,
println([X,Y]).
The if_ex example performs exactly one assignment. At compilation time, the compiler
does not know whether or not Z>0 evaluates to true. Therefore, the compiler does not know
whether to introduce a new variable for X or for Y.
Therefore, when an if-else statement contains an assignment, the compiler rewrites the if-else
statement as a predicate. For example, the compiler rewrites the above example as follows:
if_ex(Z) =>
X = 1, Y = 2,
p(X, Xout, Y, Yout, Z),
println([Xout,Yout]).
One rule is generated for each branch of the if-else statement. For each variable V that occurs on
the LHS of an assignment statement that is inside of the if-else statement, predicate p is passed
two arguments, Vin and Vout. In the above example, X and Y each occur on the LHS of an
assignment statement. Therefore, predicate p is passed the parameters Xin, Xout, Yin, and
Yout.
Picat has three types of loop statements for programming repetitions: foreach, while, and
do-while.
Each Ei is an iterating pattern. Each Di is an expression that gives a compound value. Each
Condi is an optional condition on iterators E1 through Ei .
Foreach loops can be used to iterate through compound values, as in the following examples.
51
Example
loop_ex1 =>
L = [17, 3, 41, 25, 8, 1, 6, 40],
foreach (E in L)
println(E)
end.
loop_ex2(Map) =>
foreach ((Key = Value) in Map)
writef("%w = %w\n", Key, Value)
end.
The loop_ex1 example iterates through a list. The loop_ex2 example iterates through a
map, where Key = Value is the iterating pattern.
The loop_ex1 example can also be written, using a failure-driven loop, as follows.
Example
loop_ex1 =>
L = [17, 3, 41, 25, 8, 1, 6, 40],
( member(E, L),
println(E),
fail
;
true
).
Recall that the range Start..Step..End stands for a list of numbers. Ranges can be used as
compound values in iterators.
Example
loop_ex3 =>
foreach (E in 1 .. 2 .. 9)
println(E)
end.
Also recall that the function zip(List1 ,List2 ,. . .,Listn ) returns a list of tuples. This
function can be used to simultaneously iterate over multiple lists.
Example:
loop_ex_parallel =>
foreach (Pair in zip(1..2, [a,b]))
println(Pair)
end.
52
Example:
loop_ex4 =>
L = [2, 3, 5, 10],
foreach (I in L, J in 1 .. 10, J mod I != 0)
printf("%d is not a multiple of %d%n", J, I)
end.
If a foreach loop has multiple iterators, then it is compiled into a series of nested foreach
loops in which each nested loop has a single iterator. In other words, a foreach loop with multiple
iterators executes its goal once for every possible combination of values in the iterators.
The foreach loop in loop_ex4 is the same as the nested loop:
loop_ex5 =>
L = [2, 3, 5, 10],
foreach (I in L)
foreach (J in 1..10)
if (J mod I != 0)
printf("%d is not a multiple of %d%n", J, I)
end
end
end.
loop_ex6 =>
A = {2, 3, 5, 0, 10, 4},
foreach (I in 1..len(A), break(A[I] == 0))
println(A[I])
end.
while (Cond)
Goal
end
Example:
loop_ex7 =>
I = 1,
while (I <= 9)
println(I),
53
I := I + 2
end.
loop_ex8 =>
J = 6,
while (J <= 5)
println(J),
J := J + 1
end.
loop_ex9 =>
E = read_int(),
while (E mod 2 == 0; E mod 5 == 0)
println(E),
E := read_int()
end.
loop_ex10 =>
E = read_int(),
while (E mod 2 == 0, E mod 5 == 0)
println(E),
E := read_int()
end.
The while loop in loop_ex7 prints all of the odd numbers between 1 and 9. It is similar to
the foreach loop
foreach (I in 1 .. 2 .. 9)
println(I)
end.
The while loop in loop_ex8 never executes its goal. J begins at 6, so the condition J <=
5 is never true, meaning that the body of the loop does not execute.
The while loop in loop_ex9 demonstrates a compound condition. The loop executes as long
as the value that is read into E is either a multiple of 2 or a multiple of 5.
The while loop in loop_ex10 also demonstrates a compound condition. Unlike in loop_ex9,
in which either condition must be true, in loop_ex10, both conditions must be true. The loop
executes as long as the value that is read into E is both a multiple of 2 and a multiple of 5.
do
Goal
while (Cond)
A do-while loop is similar to a while loop, except that a do-while loop executes Goal one time
before testing Cond. The following example demonstrates the similarities and differences between
do-while loops and while loops.
54
Example
loop_ex11 =>
J = 6,
do
println(J),
J := J + 1
while (J <= 5).
Unlike loop_ex8, loop_ex11 executes its body once. Although J begins at 6, the do-
while loop prints J, and increments J before evaluating the condition J <= 5.
A list comprehension is a special functional notation for creating lists. List comprehensions have
a similar format to foreach loops.
[T : E1 in D1 , Cond1 , . . ., En in Dn , Condn ]
{T : E1 in D1 , Cond1 , . . ., En in Dn , Condn }
Example
picat> L = [(A, I) : A in [a, b], I in 1 .. 2].
L = [(a , 1),(a , 2),(b , 1),(b , 2)]
Variables that occur in a loop, but do not occur before the loop in the outer scope, are local to each
iteration of the loop. For example, in the rule
p(A) =>
foreach (I in 1 .. [Link])
E = A[I],
println(E)
end.
the variables I and E are local, and each iteration of the loop has its own values for these variables.
Consider the example:
55
Example
while_test(N) =>
I = 1,
while (I <= N)
I := I + 1,
println(I)
end.
In this example, the while loop contains an assignment statement. As mentioned above, at compi-
lation time, Picat creates new variables in order to handle assignments. One new variable is created
for each assignment. However, when this example is compiled, the compiler does not know the
number of times that the body of the while loop can be executed. This means that the compiler
does not know how many times the assignment I := I + 1 will occur, and the compiler is
unable to create new variables for this assignment. In order to solve this problem, the compiler
compiles while loops into tail-recursive predicates.
In the while_test example, the while loop is compiled into:
while_test(N) =>
I = 1,
p(I, N).
Example
min_max([H|T], Min, Max) =>
LMin = H,
LMax = H,
foreach (E in T)
LMin := min(LMin, E),
LMax := max(LMax, E)
end,
Min = LMin,
Max = LMax.
This loop finds the minimum and maximum values of a list. The loop is compiled to:
56
min_max([H|T], Min, Max) =>
LMin = H,
LMax = H,
p(T, LMin, LMin1, LMax, LMax1),
Min = LMin1,
Max = LMax1.
Nested Loops
As mentioned above, variables that only occur within a loop are local to each iteration of the loop.
In nested loops, variables that are local to the outer loop are global to the inner loop. In other
words, if a variable occurs in the outer loop, then the variable is also visible in the inner loop.
However, variables that are local to the inner loop are not visiable to the outer loop.
For example, consider the nested loops:
nested =>
foreach (I in 1 .. 10)
printf("Numbers between %d and %d ", I, I * I),
foreach (J in I .. I * I)
printf("%d ", J)
end,
nl
end.
Variable I is local to the outer foreach loop, and is global to the inner foreach loop. Therefore,
iterator J is able to iterate from I to I * I in the inner foreach loop. Iterator J is local to the
inner loop, and does not occur in the outer loop.
Since a foreach loop with N iterators is converted into N nested foreach loops, the order of the
iterators matters.
Example
comp_ex =>
L = [(A, X) : A in [a, b], X in 1 .. 2].
57
This list comprehension is compiled to:
comp_ex =>
List = L,
foreach (A in [a, b], X in 1 .. 2)
L = [(A, X) | T],
L := T
end,
L = [].
Example
make_list1 =>
L = [Y : X in 1..5],
write(L).
make_list2 =>
Y = Y,
L = [Y : X in 1..5],
write(L).
Suppose that a user would like to create a list [Y, Y, Y, Y, Y]. The make_list1 predicate
incorrectly attempts to make this list; instead, it outputs a list of 5 different variables since Y is
local. In order to make all five variables the same, make_list2 makes variable Y global, by
adding the line Y = Y to globalize Y.
58
Chapter 6
Exceptions
An exception is an event that occurs during the execution of a program. An exception requires a
special treatment. In Picat, an exception is just a term. A built-in exception is a structure, where
the name denotes the type of the exception, and the arguments provide other information about the
exception, such as the source, which is the goal or function that raised the exception.
Picat throws many types of exceptions. The following are some of the built-in exceptions:1
• zero_divisor(Source): Source divides a number by zero.
• io_error(EN o,EM sg,Source): An I/O error with the number EN o and message
EM sg occurs in Source.
• load_error(F N ame,Source): An error occurs while loading the byte-code file named
F N ame. This error is caused by the malformatted byte-code file.
• out_of_memory(Area): The system runs out of memory while expanding Area, which
can be: stack_heap, trail, program, table, or findall.
59
• Type_expected(EArg,Source): The argument EArg in Source is not an expected
type or value, where T ype can be var, nonvar, dvar, atom, integer, real, number,
list, map, etc.
The built-in predicate throw(Exception) throws Exception. After an exception is thrown, the
system searches for a handler for the exception. If none is found, then the system displays the
exception and aborts the execution of the current query. It also prints the backtrace of the stack
if it is in debug mode. For example, for the function call open("[Link]"), the following
message will be displayed if there is no file that is named "[Link]".
*** error(existence_error(source_sink,[Link]),open)
All exceptions, including those raised by built-ins and interruptions, can be caught by catchers. A
catcher is a call in the form:
catch(Goal,Exception,RecoverGoal)
which is equivalent to Goal, except when an exception is raised during the execution of Goal
that unifies Exception. When such an exception is raised, all of the bindings that have been
performed on variables in Goal will be undone, and RecoverGoal will be executed to handle
the exception. Note that Exception is unified with a renamed copy of the exception before
RecoverGoal is executed. Also note that only exceptions that are raised by a descendant call of
Goal can be caught.
The call call_cleanup(Call,Cleanup) is equivalent to call(Call), except that
Cleanup is called when Call succeeds determinately (i.e., with no remaining choice point),
when Call fails, or when Call raises an exception.
60
Chapter 7
Tabling
The Picat system is a term-rewriting system. For a predicate call, Picat selects a matching rule
and rewrites the call into the body of the rule. For a function call C, Picat rewrites the equation
C = X where X is a variable that holds the return value of C. Due to the existence of recursion in
programs, the term-rewriting process may never terminate. Consider, for example, the following
program:
where the predicate edge defines a relation, and the predicate reach defines the transitive closure
of the relation. For a query such as reach(a,X), the program never terminates due to the
existence of left-recursion in the second rule. Even if the rule is converted to right-recursion, the
query may still not terminate if the graph that is represented by the relation contains cycles.
Another issue with recursion is redundancy. Consider the following problem: Starting in the
top left corner of a N × N grid, one can either go rightward or downward. How many routes are
there through the grid to the bottom right corner? The following gives a program in Picat for the
problem:
route(N,N,_Col) = 1.
route(N,_Row,N) = 1.
route(N,Row,Col) = route(N,Row+1,Col)+route(N,Row,Col+1).
The function call route(20,1,1) returns the number of routes through a 20×20 grid. The
function call route(N,1,1) takes exponential time in N, because the same function calls are
repeatedly spawned during the execution, and are repeatedly resolved each time that they are
spawned.
Tabling is a memoization technique that can prevent infinite loops and redundancy. The idea
of tabling is to memorize the answers to subgoals and use the answers to resolve their variant
descendants. In Picat, in order to have all of the calls and answers of a predicate or function
tabled, users just need to add the keyword table before the first rule.
Example
table
reach(X,Y) ?=> edge(X,Y).
61
reach(X,Y) => reach(X,Z), edge(Z,Y).
table
route(N,N,_Col) = 1.
route(N,_Row,N) = 1.
route(N,Row,Col) = route(N,Row+1,Col)+route(N,Row,Col+1).
With tabling, all queries to the reach predicate are guaranteed to terminate, and the function call
route(N,1,1) takes only N2 time.
For some problems, such as planning problems, it is infeasible to table all answers, because
there may be an infinite number of answers. For some other problems, such as those that require
the computation of aggregates, it is a waste to table non-contributing answers. Picat allows users
to provide table modes to instruct the system about which answers to table. For a tabled predicate,
users can give a table mode declaration in the form (M1 , M2 , . . . , Mn ), where each Mi is one of
the following:
• + : indicates input
• - : indicates output
• max: indicates that the corresponding variable should be maximized (only the first best
answer is tabled).
• min indicates that the corresponding variable should be minimized (only the first best an-
swer is tabled).
• mmax: indicates that the corresponding variable should be maximized (all best answers are
tabled).
• mmin indicates that the corresponding variable should be minimized (all best answers are
tabled).
The last mode Mn can be nt, which indicates that the argument is not tabled. Two types of data
can be passed to a tabled predicate as an nt argument: (1) global data that are the same to all the
calls of the predicate, and (2) data that are functionally dependent on the input arguments.
An argument with the mode max, min, mmax or mmin is called an objective argument. Only
one argument can be an objective to be optimized. As an objective argument can be a compound
value, this limit is not essential, and users can still specify multiple objective variables to be op-
timized. When the table mode max or min is provided, Picat tables only one optimal answer
for the same input arguments. When the table mode mmax or mmin is provided, Picat tables all
optimal answers for the same input arguments. Input arguments are assumed to be ground. Output
arguments, including objective arguments, are assumed to be variables.
Example
table(+,+,-,min)
sp(X,Y,Path,W) ?=>
Path = [(X,Y)],
edge(X,Y,W).
sp(X,Y,Path,W) =>
Path = [(X,Z)|Path1],
edge(X,Z,Wxz),
62
sp(Z,Y,Path1,W1),
W = Wxz+W1.
The predicate edge(X,Y,W) specifies a weighted directed graph, where W is the weight of the
edge between node X and node Y. The predicate sp(X,Y,Path,W) states that Path is a path
from X to Y with the minimum weight W. Note that whenever the predicate sp/4 is called, the
first two arguments must always be instantiated. For each pair, the system stores only one path
with the minimum weight. When the mode min is replaced with mmin, the system stores all paths
with the minimum weight.
The following program finds a shortest path among those with the minimum weight for each
pair of nodes:
table (+,+,-,min).
sp(X,Y,Path,WL) ?=>
Path = [(X,Y)],
WL = (Wxy,1),
edge(X,Y,Wxy).
sp(X,Y,Path,WL) =>
Path = [(X,Z)|Path1],
edge(X,Z,Wxz),
sp(Z,Y,Path1,WL1),
WL1 = (Wzy,Len1),
WL = (Wxz+Wzy,Len1+1).
For each pair of nodes, the pair of variables (W,Len) is minimized, where W is the weight, and
Len is the length of a path. The built-in function compare_terms(T1 ,T2 ) is used to compare
answers. Note that the order is important. If the term would be (Len,W), then the program would
find a shortest path, breaking a tie by selecting one with the minimum weight.
The tabling system is useful for offering dynamic programming solutions for planning prob-
lems. The following shows a tabled program for general planning problems:
table (+,-,min)
plan(S,Plan,Len), final(S) => Plan = [], Len = 0.
plan(S,Plan,Len) =>
action(Action,S,S1),
plan(S1,Plan1,Len1),
Plan = [Action|Plan1],
Len = Len1+1.
The predicate action(Action,S,S1) selects an action and performs the action on state S
to generate another state, S1. Again, by replacing min with mmin, the predicate plan can be
employed to generate all optimal plans.
Example
The program shown in Figure 7.1 solves the Farmer’s problem: The farmer wants to get his goat,
wolf, and cabbage to the other side of the river. His boat isn’t very big, and it can only carry him
and either his goat, his wolf, or his cabbage. If he leaves the goat alone with the cabbage, then
the goat will gobble up the cabbage. If he leaves the wolf alone with the goat, then the wolf will
gobble up the goat. When the farmer is present, the goat and cabbage are safe from being gobbled
up by their predators.
63
go =>
S0 = [s,s,s,s],
plan(S0,Plan,_),
writeln([Link]()).
table (+,-,min)
plan([n,n,n,n],Plan,Len) => Plan = [], Len = 0.
plan(S,Plan,Len) =>
Plan = [Action|Plan1],
action(S,S1,Action),
plan(S1,Plan1,Len1),
Len = Len1+1.
action([F,F,G,C],S1,Action) ?=>
Action = farmer_wolf,
opposite(F,F1),
S1 = [F1,F1,G,C],
not unsafe(S1).
action([F,W,F,C],S1,Action) ?=>
Action = farmer_goat,
opposite(F,F1),
S1 = [F1,W,F1,C],
not unsafe(S1).
action([F,W,G,F],S1,Action) ?=>
Action = farmer_cabbage,
opposite(F,F1),
S1 = [F1,W,G,F1],
not unsafe(S1).
action([F,W,G,C],S1,Action) ?=>
Action = farmer_alone,
opposite(F,F1),
S1 = [F1,W,G,C],
not unsafe(S1).
64
7.2 The Tabling Mechanism
The Picat tabling system employs the so-called linear tabling mechanism, which computes fix-
points by iteratively evaluating looping subgoals. The system uses a data area, called the table
area, to store tabled subgoals and their answers. The tabling area can be initialized with the fol-
lowing built-in predicate:
This predicate clears up the table area. It’s the user’s responsibility to ensure that no data in the
table area are referenced by any part of the application.
Linear tabling relies on the following three primitive operations to access and update the table
area.
Subgoal lookup and registration: This operation is used when a tabled subgoal is encountered
during execution. It looks up the subgoal table to see if there is a variant of the subgoal.
If not, it inserts the subgoal (termed a pioneer or generator) into the subgoal table. It also
allocates an answer table for the subgoal and its variants. Initially, the answer table is empty.
If the lookup finds that there already is a variant of the subgoal in the table, then the record
that is stored in the table is used for the subgoal (called a consumer). Generators and con-
sumers are handled differently. In linear tabling, a generator is resolved using rules, and a
consumer is resolved using answers; a generator is iterated until the fixed point is reached,
and a consumer fails after it exhausts all of the existing answers.
Answer lookup and registration: This operation is executed when a rule succeeds in generating
an answer for a tabled subgoal. If a variant of the answer already exists in the table, then
it does nothing; otherwise, it inserts the answer into the answer table for the subgoal, or
it tables the answer according to the mode declaration. Picat uses the lazy consumption
strategy (also called the local strategy). After an answer is processed, the system backtracks
to produce the next answer.
65
Chapter 8
The planner module provides several predicates for solving planning problems. Given an initial
state, a final state, and a set of possible actions, a planning problem is to find a plan that transforms
the initial state to the final state. In order to use the planner module to solve a planning problem,
users have to provide the condition for the final states and the state transition diagram through the
following global predicates:
• final(S,P lan,Cost): A final state can be reached from S by the action sequence in
P lan with Cost. If this predicate is not given, then the system assumes the following
definition:
A state is normally a ground term. As all states are tabled during search, it is of paramount
importance to find a good representation for states such that terms among states can be shared as
much as possible.
In addition to the two required predicates given above, users can optionally provide the fol-
lowing global procedures to assist Picat in searching for plans:
• sequence(P ,Action): This predicate binds Action to a viable action form based on the
current partial plan P . Note that the actions in list P are in reversed order, with the most
recent action occurring first in the list, and the first action occurring last in the list. The
planner calls sequence/2 to find an action for expanding the current state before calling
action/4. For example,
66
sequence([move(R,_,_)|_], Action) ?=> Action = $jump(R).
sequence([move(R,_,_)|_], Action) => Action = $wait(R).
sequence(_, _) => true.
These sequence rules ban robots from moving in an interleaving fashion; a robot must con-
tinue to move until it takes the action jump or wait before another robot can start moving.
The last rule sequence(_, _) => true is necessary; it permits any action to be taken
if the partial plan is empty, or if the most recent action in the partial plan is not move.
Depth-bounded search amounts to exploring the search space, taking into account the current
available resource amount. A new state is only explored if the available resource amount is non-
negative. When depth-bounded search is used, the function current_resource() can be
used to retrieve the current resource amount. If the heuristic estimate of the cost to travel from the
current state to the final state is greater than the available resource amount, then the current state
fails.
67
• best_plan_bb(S,P lan,Cost): If the second argument is a variable, then this predi-
cate is the same as the best_plan_bb/4 predicate, except that the limit is assumed to be
268435455.
• current_plan()=P lan: This function returns the current plan that has transformed the
initial state to the current state. If the current execution path was not initiated by one of the
calls that performs resource-bounded search, then [] is returned.
• is_tabled_state(S): This predicate succeeds if the state S has been explored before
and has been tabled.
In contrast to depth-bounded search, depth-unbounded search does not take into account the avail-
able resource amount. A new state can be explored even if no resource is available for the explo-
ration. The advantage of depth-unbounded search is that failed states are never re-explored.
68
• best_plan_nondet(S,Limit,P lan): If the second argument is an integer, then this
predicate is the same as the best_plan_nondet/4 predicate, except that the plan’s cost
is not returned.
• plan_unbounded(S,P lan): This predicate is the same as the above predicate, except
that the limit is assumed to be 268435455.
8.3 Examples
The program shown in Figure 8.1 solves the Farmer’s problem by using the planner module.
Figure 8.2 gives a program for the 15-puzzle problem. A state is represented as a list of
sixteen locations, each of which takes the form (Ri ,Ci ), where Ri is a row number and Ci is
a column number. The first element in the list gives the position of the empty square, and the
remaining elements in the list give the positions of the numbered tiles from 1 to 15. The function
heuristic(Tiles) returns the Manhattan distance between the current state and the final
state.
69
import planner.
go =>
S0 = [s,s,s,s],
best_plan(S0,Plan),
writeln(Plan).
action([F,F,G,C],S1,Action,ActionCost) ?=>
Action = farmer_wolf,
ActionCost = 1,
opposite(F,F1),
S1 = [F1,F1,G,C],
not unsafe(S1).
action([F,W,F,C],S1,Action,ActionCost) ?=>
Action = farmer_goat,
ActionCost = 1,
opposite(F,F1),
S1 = [F1,W,F1,C],
not unsafe(S1).
action([F,W,G,F],S1,Action,ActionCost) ?=>
Action = farmer_cabbage,
ActionCost = 1,
opposite(F,F1),
S1 = [F1,W,G,F1],
not unsafe(S1).
action([F,W,G,C],S1,Action,ActionCost) =>
Action = farmer_alone,
ActionCost = 1,
opposite(F,F1),
S1 = [F1,W,G,C],
not unsafe(S1).
70
import planner.
main =>
InitS = [(1,2),(2,2),(4,4),(1,3),
(1,1),(3,2),(1,4),(2,4),
(4,2),(3,1),(3,3),(2,3),
(2,1),(4,1),(4,3),(3,4)],
best_plan(InitS,Plan),
foreach (Action in Plan)
println(Action)
end.
action([P0@(R0,C0)|Tiles],NextS,Action,Cost) =>
Cost = 1,
(R1 = R0-1, R1 >= 1, C1 = C0, Action = up;
R1 = R0+1, R1 =< 4, C1 = C0, Action = down;
R1 = R0, C1 = C0-1, C1 >= 1, Action = left;
R1 = R0, C1 = C0+1, C1 =< 4, Action = right),
P1 = (R1,C1),
slide(P0,P1,Tiles,NTiles),
NextS = [P1|NTiles].
71
Chapter 9
Modules
A module is a bundle of predicate and function definitions that are stored in one file. A module
forms a name space. Two definitions can have the same name if they reside in different modules.
Because modules avoid name clashes, they are very useful for managing source files of large
programs.
In Picat, source files must have the extension name ".pi". A module is a source file that begins
with a module name declaration in the form:
module N ame.
where N ame must be the same as the main file name. A file that does not begin with a module
declaration is assumed to belong to the default global module. The following names are reserved
for system modules and should not be used to name user modules: basic, bp, cp, datetime,
glb, io, math, mip, nn, ordset, os, planner, sat, smt, sys, and util.
In order to use symbols that are defined in another module, users must explicitly import them
with an import declaration in the form:
where each imported N amei is a module name. For each imported module, the compiler first
searches for it in the search path that is specified by the environment variable PICATPATH. If no
module is found, the compiler gives an error message. Several modules are imported by default,
including basic, io, math, and sys.
The import relation is not transitive. Suppose that there are three modules: A, B, and C. If A
imports B and B imports C, then A still needs to import C in order to reference C’s symbols.
The built-in command cl("xxx") compiles the file [Link] and loads the generated code
into the interpreter. The built-in command load("xxx") loads the bytecode file [Link]. It
compiles the source file [Link] only when necessary. The load command also imports the
public symbols defined in the module to the interpreter. This allows users to use these symbols on
the command line without explicitly importing the symbols. If the file [Link] imports modules,
those module files will be compiled and loaded when necessary.
A program file can contain include directives of the form:
include N ame.
72
where N ame is a string indicating a file name relative to the program file. The include directive
causes the content of the file named N ame to be copied verbatim to where the directive occurs.
The include directive allows users to split a large program into several source files. Note that
the included source files cannot contain module or import declarations, and no definitions can span
multiple files.
The Picat system has a global symbol table for atoms, a global symbol table for structure names,
and a global symbol table for modules. For each module, Picat maintains a symbol table for the
public predicate and function symbols defined in the module. Private symbols that are defined in a
module are compiled away, and are never stored in the symbol table. While predicate and function
symbols can be local to a module, atoms and structures are always global.
The Picat module system is static, meaning that the binding of normal (or non-higher-order)
calls to their definitions takes place at compile time. For each call, the compiler first searches
the default modules for a definition that has the same name as the call. If no definition is found,
then the compiler searches for a definition in the enclosing module. If no definition is found, the
compiler searches the imported modules in the order that they were imported. If no definition is
found in any of these modules, then the compiler will issue an warning1 , assuming the symbol is
defined in the global module.
It is possible for two imported modules to contain different definitions that have the same name.
When multiple names match a call, the order of the imported items determines which definition is
used. Picat allows users to use qualified names to explicitly select a definition. A module-qualified
call is a call preceded by a module name and ’.’ without intervening whitespace.
Example
% [Link]
module qsort.
sort([]) = [].
sort([H|T]) =
sort([E : E in T, E =< H]) ++ [H] ++ sort([E : E in T, E > H]).
% [Link]
module isort.
sort([]) = [].
sort([H|T]) = insert(H,sort(T)).
private
insert(X,[]) = [X].
insert(X,Ys@[Y|_]) = Zs, X =< Y => Zs = [X|Ys].
insert(X,[Y|Ys]) = [Y|insert(X,Ys)].
The module [Link] defines a function named sort using quick sort, and the module isort
defines a function of the same name using insertion sort. In the following session, both modules
are used.
1
A warning is issued instead of an error. This allows users to test incomplete programs with missing definitions.
73
picat> load("qsort")
picat> load("isort")
picat> L = sort([2,1,3])
L = [1,2,3]
picat> L = [Link]([2,1,3])
L = [1,2,3]
picat> L = [Link]([2,1,3])
L = [1,2,3]
As sort is also defined in the basic module, which is preloaded, that function is used for the
command L = sort([2,1,3]).
Module names are just atoms. Consequently, it is possible to bind a variable to a module name.
Nevertheless, in a module-qualified call M.C, the module name can never be a variable. Recall
that the dot notation is also used to access attributes and to call predicates and functions. The
notation M.C is treated as a call or an attribute if M is not an atom.
Suppose that users want to define a function named generic_sort(M,L) that sorts list L
using the sort function defined in module M. Users cannot just call [Link](L), since M is a
variable. Users can, however, select a function based on the value held in M by using function facts
as follows:
generic_sort(qsort,L) = [Link](L).
generic_sort(isort,L) = [Link](L).
Because Picat forbids variable module qualifiers and terms in dot notations, it is impossible to
create module-qualified higher-order terms. For a higher-order call, if the compiler knows the
name of the higher-order term, as in findall(X,member(X, L)), then it searches for a def-
inition for the name, just like it does for a normal call. However, if the name is unknown, as in
apply(F,X,Y), then the compiler generates code to search for a definition. For a higher-order
call to call/N or apply/N, the runtime system searches modules in the following order:
1. The implicitly imported built-in modules basic, io, math, and sys.
2. The current list of loaded modules that is returned by the built-in function call loaded_modules(),
excluding the pre-imported built-in modules.
As private symbols are compiled away at compile time, higher-order terms can never reference
private symbols. Due to the overhead of runtime search, the use of higher-order calls is discour-
aged.
Picat comes with a library of standard modules, described in separate chapters. The function
sys.loaded_modules() returns a list of modules that are currently in the system.
74
Chapter 10
I/O
Picat has an io module for reading input from files and writing output to files. The io module is
imported by default.
The io module contains functions and predicates that read from a file, write to a file, reposition
the read/write pointer within a file, redirect input and output, and create temporary files and pipes.
The io module uses file descriptors to read input from files, and to write output to files. A
file descriptor is a structure that encodes file descriptor data, including an index in a file descriptor
table that stores information about opened files. The following example reads data from one file,
and writes the data into another file.
Example
rw =>
Reader = open("input_file.txt"),
Writer = open("output_file.txt", write),
L = read_line(Reader),
while (L != end_of_file)
println(Writer, L),
flush(Writer),
L := read_line(Reader)
end,
close(Reader),
close(Writer).
There are two functions for opening a file. Both of them are used in the previous example.
• open(N ame,M ode) = F D: The M ode parameter is one of the four atoms: read,
write, or append. The read atom is used for reading from a file; if the file does not
exist, or the program tries to write to the file, then the program will throw an error. The
write atom is used for reading from a file and writing to a file; if the file already exists,
then the file will be overwritten. The append atom is similar to the write atom; however, if
the file already exists, then data will be appended at the end of the pre-existing file.
75
10.2 Reading from a File
The io module has at least one function for reading data into each primitive data type. It also has
functions for reading characters, tokens, strings, and bytes. Recall that strings are stored as lists of
single-character atoms.
The read functions in the io module take a file descriptor as the first parameter. This file
descriptor is the same descriptor that the open function returns. The parameter can be omitted if
it is the standard input file stdin.
• read_int(F D) = Int: This function reads a single integer from the file that is repre-
sented by F D. It throws an input_mismatch exception if F D is at the end of the file or
the next token at F D is not an integer.
• read_real(F D) = Real: This function reads a single real number from the file that is
represented by F D. It throws an input_mismatch exception if F D is at the end of the
file or the next token at F D is not a number.
• read_char(F D) = V al: This function reads a single UTF-8 character from the file
that is represented by F D. It returns end_of_file if F D is at the end of the file.
• read_char_code(F D) = V al: This function reads a single UTF-8 character from the
file that is represented by F D and returns its code point. It returns -1 if F D is at the end of
the file.
• read_picat_token(F D,T okenT ype,T okenV alue): This predicate reads a single
Picat token from the file that is represented by F D. T okenT ype is the type and T okenV alue
is the value of the token. T okenT ype is one of the following: atom, end_of_file,
end_of_rule, integer, punctuation, real, string, underscore, and var.
• read_picat_token(T okenT ype,T okenV alue): This predicate reads a token from
stdin.
• read_picat_token() = T okenV alue: This function is the same as the above, except
that it reads from stdin.
76
• read_term(F D) = T erm: This function reads a single Picat term from the file that is
represented by F D. The term must be followed by a dot ‘.’ and at least one whitespace
character. This function consumes the dot symbol. The whitespace character is not stored
in the returned string.
• read_line(F D) = String: This function reads a string from the file that is repre-
sented by F D, stopping when either a newline (‘\r\n’ on Windows, and ‘\n’ on Unix)
is read, or the end_of_file atom is returned. The newline is not stored in the returned
string.
• read_byte(F D) = V al: This function reads a single byte from the file that is repre-
sented by F D.
• read_byte(F D,N ) = List: This function reads up to N bytes from the file that is
represented by F D. It returns the list of bytes that were read.
• read_file_bytes(F ile) = List: This function reads an entire byte file into a list.
• read_file_bytes() = List: This function reads an entire byte file from the console
into a list.
• read_file_chars(F ile) = String: This function reads an entire character file into
a string.
• read_file_chars() = String: This function reads an entire character file from the
console into a string.
• read_file_codes(F ile) = List: This function reads UTF-8 codes of an entire char-
acter file into a list.
• read_file_lines(F ile) = Lines: This function reads an entire character file into a
list of line strings.
• read_file_lines() = Lines: This function reads an entire character file from the
console into a list of line strings.
• read_file_terms(F ile) = Lines: This function reads an entire text file into a list of
terms. In the file, each term must be terminated by ‘.’ followed by at least one white space.
• read_file_terms() = Lines: This function reads an entire text file from the console
into a list of terms.
77
There are cases when the read_char(F D,N ), and read_byte(F D,N ) functions will
read fewer than N values. One case occurs when the end of the file is encountered. Another case
occurs when reading from a pipe. If a pipe is empty, then the read functions wait until data
is written to the pipe. As soon as the pipe has data, the read functions read the data. If a
pipe has fewer than N values when a read occurs, then these three functions will return a string
that contains all of the values that are currently in the pipe, without waiting for more values. In
order to determine the actual number of elements that were read, after the functions return, use
length(List) to check the length of the list that was returned.
The io module also has functions that peek at the next value in the file without changing the
current file location. This means that the next read or peek function will return the same value,
unless the read/write pointer is repositioned or the file is modified.
• peek_char(F D) = V al
• peek_byte(F D) = V al
Example
rw =>
Reader = open("[Link]"),
Writer = open("[Link]", write),
while (not at_end_of_stream(Reader))
L := read_line(Reader),
println(Writer, L),
flush(Writer)
end,
close(Reader),
close(Writer).
The advantage of using the at_end_of_stream predicate instead of using the end_of_file
atom is that at_end_of_stream immediately indicates that the end of the file was reached,
even if the last read function read values into a list. In the first example in this chapter, which
used the end_of_file atom, an extra read_line function was needed before the end of the
file was detected. In the above example, which used at_end_of_stream, read_line was
only called if there was data remaining to be read.
78
10.3 Writing to a File
The write and print predicates take a file descriptor as the first parameter. The file descriptor
is the same descriptor that the open function returns. If the file descriptor is stdout, then the
parameter can be omitted.
• write(F D,T erm): This predicate writes T erm to a file. Single-character lists are
treated as strings. Strings are double-quoted, and atoms are single-quoted when necessary.
This predicate does not print a newline, meaning that the next write will begin on the same
line.
• write_byte(F D,Bytes): This predicate writes a single byte or a list of bytes to a file.
• writeln(F D,T erm): This predicate writes T erm and a newline, meaning that the next
write will begin on the next line.
• writef(F D,F ormat,Args . . .): This predicate is used for formatted writing, where
the F ormat parameter contains format characters that indicate how to print each of the
arguments in the Args parameter. The number of arguments in Args . . . cannot exceed 16.
Note that these predicates write both primitive values and compound values.
The writef predicate includes a parameter that specifies the string that is to be formatted.
The F ormat parameter is a string that contains format characters. Format characters take the form
%[flags][width][.precision]specifier. Only the percent sign and the specifier are
mandatory. Flags can be used for justification and padding. The width is the minimum number of
characters that are to be printed. The precision is the number of characters that are to be printed
after the number’s radix point. Note that the width includes all characters, including the radix
point and the characters that follow it. The specifier indicates the type of data that is to be written.
A specifier can be one of the C format specifiers %%, %c,1 %d, %e, %E, %f, %g, %G, %i, %o, %s,
%u, %x, and %X. In addition, Picat uses the specifier %n for newlines, and uses %w for terms. For
details, see Appendix F.
1
The specifier %c can only be used to print ASCII characters. Use the specifier %w to print UTF-8 characters.
79
Example
formatted_print =>
FD = open("[Link]",write),
Format1 = "Hello, %s. Happy birthday! ",
Format2 = "You are %d years old today. ",
Format3 = "That is %.2f%% older than you were last year.",
writef(FD, Format1, "Bob"),
writef(FD, Format2, 7),
writef(FD, Format3, ((7.0 - 6.0) / 6.0) * 100),
close(FD).
This writes, “Hello, Bob. Happy birthday! You are 7 years old today.
That is 16.67% older than you were last year.”
The io module also has the three print predicates.
• print(F D,T erm): This predicate prints T erm to a file. Unlike the write predicates,
the print predicates do not place quotes around strings and atoms.
• printf(F D,F ormat,Args . . .): This predicate is the same as writef, except that
printf uses print to display the arguments in the Args parameter, while writef
uses write to display the arguments in the Args parameter. The number of arguments
in Args . . . cannot exceed 16.
The following example demonstrates the differences between the write and print predi-
cates.
Example
picat> write("abc")
[a,b,c]
picat> write([a,b,c])
[a,b,c]
picat> write(’a@b’)
’a@b’
picat> writef("%w %s%n",[a,b,c],"abc")
[a,b,c] abc
picat> print("abc")
abc
picat> print([a,b,c])
abc
picat> print(’a@b’)
a@b
picat> printf("%w %s%n",[a,b,c],"abc")
abc abc
80
10.4 Flushing and Closing a File
The io module has one predicate to flush a file stream, and one predicate to close a file stream.
• flush(F D): This predicate causes all buffered data to be written without delay.
• close(F D): This predicate causes the file to be closed, releasing the file’s resources, and
removing the file from the file descriptor table. Any further attempts to write to the file
descriptor without calling open will cause an error to be thrown.
The atoms stdin, stdout, and stderr represent the file descriptors for standard input, stan-
dard output, and standard error. These atoms allow the program to use the input and output func-
tions of the io module to read from and to write to the three standard streams.
81
Chapter 11
Many applications require event-driven computing. For example, an interactive GUI system needs
to react to UI events such as mouse clicks on UI components; a Web service provider needs to
respond to service requests; a constraint propagator for a constraint needs to react to updates to the
domains of the variables in the constraint. Picat provides action rules for describing event-driven
actors. An actor is a predicate call that can be delayed and can be activated later by events. Actors
communicate with each other through event channels.
An event channel is an attributed variable to which actors can be attached, and through which
events can be posted to actors. A channel has four ports, named ins, bound, dom, and any,
respectively. Many built-ins in Picat post events. When an attributed variable is instantiated,
an event is posted to the ins-port of the variable. When the lower bound or upper bound of a
variable’s domain changes, an event is posted to the bound-port of the variable. When an inner
element E, which is neither the lower or upper bound, is excluded from the domain of a variable,
E is posted to the dom-port of the variable. When an arbitrary element E, which can be the lower
or upper bound or an inner element, is excluded from the domain of a variable, E is posted to the
any-port of the variable. The division of a channel into ports facilitates speedy handling of events.
For better performance, the system posts an event to a port only when there are actors attached to
the port. For example, if no actor is attached to a domain variable to handle exclusions of domain
elements, then these events will never be posted.
The built-in post_event(X,T ) posts the event term T to the dom-port of the channel
variable X.
The following built-ins are used to post events to one of a channel’s four ports:
The call post_event(X,T ) is the same as post_event_dom(X,T ). This means that the
dom-port of a finite domain variable has two uses: posting exclusions of inner elements from the
domain, and posting general term events.
82
11.2 Action Rules
Picat provides action rules for describing the behaviors of actors. An action rule takes the follow-
ing form:
where Head is an actor pattern, Cond is an optional condition, Event is a non-empty set of event
patterns separated by ’,’, and Body is an action. For an actor that is activated by an event, an
action rule is said to be applicable if the actor matches Head and Cond is true. A predicate for
actors is defined with action rules and non-backtrackable rules. It cannot contain backtrackable
rules.
Unlike rules for a normal predicate or function, in which the conditions can contain any pred-
icates, the conditions of the rules in a predicate for actors must be conjunctions of inline test
predicates, such as type-checking built-ins (e.g., integer(X) and var(X)) and comparison
built-ins (e.g., equality test X == Y , disequality test X !== Y , and arithmetic comparison X
> Y ). This restriction ensures that no variables in an actor can be changed while the condition is
executed.
For an actor that is activated by an event, the system searches the definition sequentially from
the top for an applicable rule. If no applicable rule is found, then the actor fails. If an applicable
rule is found, the system executes the body of the rule. If the body fails, then the actor also
fails. The body cannot succeed more than once. The system enforces this by converting Body
into ‘once Body’ if Body contains calls to nondeterministic predicates. If the applied rule is
an action rule, then the actor is suspended after the body is executed, meaning that the actor is
waiting to be activated again. If the applied rule is a normal non-backtrackable rule, then the actor
vanishes after the body is executed. For each activation, only the first applicable rule is applied.
For a call and an action rule ‘Head, Cond, {Event} => Body’, the call is registered as an
actor if the call matches Head and Cond evaluates to true. The event pattern Event implicitly
specifies the ports to which the actor is attached, and the events that the actor watches. The
following event patterns are allowed in Event:
• event(X,T ): This is the general event pattern. The actor is attached to the dom-ports of
the variables in X. The actor will be activated by events posted to the dom-ports. T must
be a variable that does not occur before event(X,T ) in the rule.
• ins(X): The actor is attached to the ins-ports of the variables in X. The actor will be
activated when a variable in X is instantiated.
• bound(X): The actor is attached to the bound-ports of the variables in X. The actor will
be activated when the lower bound or upper bound of the domain of a variable in X changes.
• dom(X): The actor is attached to the dom-ports of the variables in X. The actor will be
activated when an inner value is excluded from the domain of a variable in X. The actor is
not interested in what value is actually excluded.
• dom(X,E): This is the same as dom(X), except the actor is interested in the value E
that is excluded. E must be a variable that does not occur before dom(X,E) in the rule.
• dom_any(X): The actor is attached to the any-ports of the variables in X. The actor will
be activated when an arbitrary value, including the lower bound value and the upper bound
value, is excluded from the domain of a variable in X. The actor is not interested in what
value is actually excluded.
83
• dom_any(X,E): This is the same as dom_any(X), except the actor is interested in
the value E that is actually excluded. E must be a variable that does not occur before
dom_any(X,E) in the rule.
In an action rule, multiple event patterns can be specified. After a call is registered as an actor
on the channels, it will be suspended, waiting for events, unless the atom generated occurs in
Event, in which case the actor will be suspended after Body is executed.
The system has an event queue. After events are posted, they are added into the queue. Events
are not handled until execution enters or exits a non-inline predicate or function. In other words,
only non-inline predicates and functions can be interrupted, and inline predicates, such as X =
Y , and inline functions, such as X + Y , are never interrupted by events.
Example
Consider the following action rule:
p(X), {event(X,T)} => writeln(T).
The following gives a query and its output:
Picat> p(X), X.post_event(ping), X.post_event(pong)
ping
pong
The call p(X) is an actor. After X.post_event(ping), the actor is activated and the body of
the action rule is executed, giving the output ping. After X.post_event(pong), the actor is
activated again, outputting pong.
There is no primitive for killing actors or explicitly detaching actors from channels. As de-
scribed above, an actor never disappears as long as action rules are applied to it. An actor vanishes
only when a normal rule is applied to it. Consider the following example.
p(X,Flag),
var(Flag),
{event(X,T)}
=>
writeln(T),
Flag = 1.
p(_,_) => true.
An actor defined here can only handle one event posting. After it handles an event, it binds the
variable Flag. When a second event is posted, the action rule is no longer applicable, causing the
second rule to be selected.
One question arises here: what happens if a second event is never posted to X? In this case, the
actor will stay forever. If users want to immediately kill the actor after it is activated once, then
users have to define it as follows:
p(X,Flag),
var(Flag),
{event(X,O),ins(Flag)},
=>
write(O),
Flag = 1.
p(_,_) => true.
84
In this way, the actor will be activated again after Flag is bound to 1, and will be killed after the
second rule is applied to it.
The built-in predicate freeze(X,Goal) is equivalent to ‘once Goal’, but its evaluation is
delayed until X is bound to a non-variable term. The predicate is defined as follows:
For the call freeze(X,Goal), if X is a variable, then X is registered as an actor on the ins-port
of X, and X is then suspended. Whenever X is bound, the event ins is posted to the ins-port of
X, which activates the actor freeze(X,Goal). The condition var(X) is checked. If true, the
actor is suspended again; otherwise, the second rule is executed, causing the actor to vanish after
it is rewritten into once Goal.
The built-in predicate different_terms(T1 ,T2 ) is a disequality constraint on terms T1
and T2 . The constraint fails if the two terms are identical; it succeeds whenever the two terms are
found to be different; it is delayed if no decision can be made because the terms are not sufficiently
instantiated. The predicate is defined as follows:
import cp.
different_terms(X,Y) =>
different_terms(X,Y,1).
85
then they are different if the functor is different, or if any pair of arguments of the structures is
different.
A constraint propagator is an actor that reacts to updates of the domains of the variables in a
constraint. The following predicate defines a propagator for maintaining arc consistency on X for
the constraint X+Y #= C:
import cp.
Whenever an inner element Ey is excluded from the domain of Y, this propagator is triggered to
exclude C-Ey, which is the support of Ey, from the domain of X. For the constraint X+Y #= C,
users need to generate two propagators, namely,
to maintain the arc consistency. Note that in addition to these two propagators, users also need
to generate propagators for maintaining interval consistency, because dom(Y,Ey) only captures
exclusions of inner elements, and does not capture bounds. The following propagator maintains
interval consistency for the constraint:
import cp.
86
Chapter 12
Constraints
Picat provides four solver modules, including cp, sat, smt, and mip, for modeling and solv-
ing constraint satisfaction and optimization problems (CSPs). All four of these modules imple-
ment the same set of constraints on integer-domain variables. The mip module also supports
real-domain variables. In order to use a solver, users must first import the module. In order
to make the symbols defined in a module available to the top level of the interpreter, users can
use the built-in import to import the module. The mip module requires Gurobi (https://
[Link]/), Cbc ([Link] or GLPK (https:
//[Link]/software/glpk/). The smt module requires Z3 ([Link]
com/Z3Prover/z3/) or CVC4 ([Link] Users can specify, as a
solving option, a solver to be used if the module is mip or smt.
As the four modules have the same interface, this chapter describes the four modules together.
Figure 12.1 shows the constraint operators that are provided by Picat. Unless it is explicitly spec-
ified otherwise, the built-ins that are described in this chapter appear in all four modules. In the
built-ins that are presented in this chapter, an integer-domain variable can also be an integer, unless
it is explicitly specified to only be a variable.
Precedence Operators
Highest ::, notin, #=, #!=, #<, #=<, #<=, #>, #>=
#~
#/\
#^
#\/
#=>
Lowest #<=>
A constraint program normally poses a problem in three steps: (1) generate variables; (2)
generate constraints over the variables; and (3) call solve to find a valuation for the variables
that satisfies the constraints and possibly optimizes an objective function.
Example
This program in Figure 12.1 imports the cp module in order to solve the N -queens problem. The
same program runs with the SAT solver if sat is imported, runs with the SMT solver if smt is
87
import cp.
queens(N) =>
Qs = new_array(N),
Qs :: 1..N,
foreach (I in 1..N-1, J in I+1..N)
Qs[I] #!= Qs[J],
abs(Qs[I]-Qs[J]) #!= J-I
end,
solve(Qs),
writeln(Qs).
imported, and runs with the LP/MIP solver if mip is imported. The predicate Qs :: 1..N
declares the domains of the variables. The operator #!= is used for inequality constraints. In
arithmetic constraints, expressions are treated as terms, and it is unnecessary to enclose them with
dollar-signs. The predicate solve(Qs) calls the solver in order to solve the array of variables
Qs. For cp, solve([ff],Qs), which always selects a variable that has the smallest domain
(the so-called first-fail principle), can be more efficient than solve(Qs).
A domain variable is an attributed variable that has a domain attribute. The Boolean domain
is treated as a special integer domain where 1 denotes true and 0 denotes false. Domain
variables are declared with the built-in predicate V ars :: Exp.
• V ars :: Exp: This predicate restricts the domain or domains of V ars to Exp. V ars
can be either a single variable or a collection of variables.1 For integer-domain variables,
Exp must result in a list of integer values. For real-domain variables for the mip module,
Exp must be an interval in the form L..U , where L and U are real values.
Domain variables, when being created, are usually represented internally by using intervals.
An interval turns to a bit vector when a hole occurs in the interval. The following built-in predicate
can be used to reset the range or access the current range.
• fd_vector_min_max(M in,M ax): When the arguments are integers, this predicate
specifies the range of bit vectors; when the arguments are variables, this predicate binds
them to the current bounds of the range. The default range is -3200..3200.
• V ars notin Exp: This predicate excludes values Exp from the domain or domains of
V ars, where V ars and Exp are the same as in V ars :: Exp. This constraint cannot
be applied to real-domain variables.
• fd_degree(F DV ar) = Degree: This function returns the number of propagators that
are attached to F DV ar. This built-in is only provided by cp.
1
A collection can be either a list or an array, where elements can be collections.
88
• fd_disjoint(F DV ar1,F DV ar2): This predicate is true if F DV ar1’s domain and
F DV ar2’s domain are disjoint.
• fd_dom(F DV ar) = List: This function returns the domain of F DV ar as a list, where
F DV ar is an integer-domain variable. If F DV ar is an integer, then the returned list con-
tains the integer itself.
• fd_false(F DV ar,Elm): This predicate is true if the integer Elm is not an element in
the domain of F DV ar.
• fd_max(F DV ar) = M ax: This function returns the upper bound of the domain of
F DV ar, where F DV ar is an integer-domain variable.
• fd_min(F DV ar) = M in: This function returns the lower bound of the domain of
F DV ar, where F DV ar is an integer-domain variable.
• fd_min_max(F DV ar,M in,M ax): This predicate binds M in to the lower bound of
the domain of F DV ar, and binds M ax to the upper bound of the domain of F DV ar,
where F DV ar is an integer-domain variable.
• fd_next(F DV ar,Elm) = N extElm: This function returns the next element of Elm
in F DV ar’s domain. It throws an exception if Elm has no next element in F DV ar’s
domain.
• fd_set_false(F DV ar,Elm): This predicate excludes the element Elm from the
domain of F DV ar. If this operation results in a hole in the domain, then the domain
changes from an interval representation into a bit-vector representation, no matter how big
the domain is. This built-in is only provided by cp.
• fd_size(F DV ar) = Size: This function returns the size of the domain of F DV ar,
where F DV ar is an integer-domain variable.
• fd_true(F DV ar,Elm): This predicate is true if the integer Elm is an element in the
domain of F DV ar.
• new_dvar() = F DV ar: This function creates a new domain variable with the default
domain, which has the bounds -72057594037927935..72057594037927935 on
64-bit computers and -268435455..268435455 on 32-bit computers.2
A table constraint, or an extensional constraint, over a tuple of variables specifies a set of tuples
that are allowed (called positive) or disallowed (called negative) for the variables. A positive
constraint takes the form table_in(DV ars,R), where DV ars is either a tuple of variables
{X1 , . . . , Xn } or a list of tuples of variables, and R is a list of tuples in which each tuple takes the
form {a1 , . . . , an }, where ai is an integer or the don’t-care symbol ∗. A negative constraint takes
the form table_notin(DV ars,R).
2
Note that incorrect results may be caused by overflows or underflows.
89
Example
The following example solves a toy crossword puzzle. One variable is used for each cell in the
grid, so each slot corresponds to a tuple of variables. Each word is represented as a tuple of
integers, and each slot takes on a set of words of the same length as the slot. Recall that the
function ord(Char) returns the code of Char, and that the function chr(Code) returns the
character of Code.
import cp.
crossword(Vars) =>
Vars = [X1,X2,X3,X4,X5,X6,X7],
Words2 = [{ord(’I’),ord(’N’)},
{ord(’I’),ord(’F’)},
{ord(’A’),ord(’S’)},
{ord(’G’),ord(’O’)},
{ord(’T’),ord(’O’)}],
Words3 = [{ord(’F’),ord(’U’),ord(’N’)},
{ord(’T’),ord(’A’),ord(’D’)},
{ord(’N’),ord(’A’),ord(’G’)},
{ord(’S’),ord(’A’),ord(’G’)}],
table_in([{X1,X2},{X1,X3},{X5,X7},{X6,X7}], Words2),
table_in([{X3,X4,X5},{X2,X4,X6}], Words3),
solve(Vars),
writeln([chr(Code) : Code in Vars]).
90
• max(Collection): The maximum of Collection, where Collection is a nested collection
of domain variables.
Example
import mip.
go =>
M = {{0,3,2,3,0,0,0,0},
{0,0,0,0,0,0,5,0},
{0,1,0,0,0,1,0,0},
{0,0,2,0,2,0,0,0},
{0,0,0,0,0,0,0,5},
{0,4,0,0,2,0,0,1},
{0,0,0,0,0,2,0,3},
{0,0,0,0,0,0,0,0}},
maxflow(M,1,8).
maxflow(M,Source,Sink) =>
N = [Link],
X = new_array(N,N),
foreach (I in 1..N, J in 1..N)
X[I,J] :: 0..M[I,J]
end,
foreach (I in 1..N, I != Source, I != Sink)
sum([X[J,I] : J in 1..N]) #= sum([X[I,J] : J in 1..N])
end,
Total #= sum([X[Source,I] : I in 1..N]),
Total #= sum([X[I,Sink] : I in 1..N]),
solve([$max(Total)],X),
writeln(Total),
writeln(X).
This program uses MIP to solve the maximum integer flow problem. Given the capacity matrix
M of a directed graph, the start vertex Source, and the destination vertex Sink, the predicate
maxflow(M,Source,Sink) finds a maximum flow from Source to Sink over the graph.
91
When two vertices are not connected by an arc, the capacity is given as 0. The first foreach loop
specifies the domains of the variables. For each variable X[I,J], the domain is restricted to
integers between 0 and the capacity, M[I,J]. If the capacity is 0, then the variable is immediately
instantiated to 0. The next foreach loop posts the conservation constraints. For each vertex I, if it
is neither the source nor the sink, then its total incoming flow amount
sum([X[J,I] : J in 1..N])
is equal to the total outgoing flow amount
sum([X[I,J] : J in 1..N]).
The total flow amount is the total outgoing amount from the source, which is the same as the total
incoming amount to the sink.
BoolExp is either a Boolean constant (0 or 1), a Boolean variable (an integer-domain variable
with the domain [0,1]), an arithmetic constraint, a domain constraint (in the form of V ar ::
Domain or V ar notin Domain), or a Boolean constraint. As shown in Table 12.1, the oper-
ator #~ has the highest precedence, and the operator #<=> has the lowest precedence. Note that
the Boolean constraint operators have lower precedence than the arithmetic constraint operators.
So the constraint
X #!= 3 #/\ X#!= 5 #<=> B
is interpreted as
((X #!= 3) #/\ (X#!= 5)) #<=> B.
The Boolean constraint operators are defined as follows.
• #~ BoolExp: This constraint is 1 iff BoolExp is equal to 0.
• BoolExp1 #/\ BoolExp2: This constraint is 1 iff both BoolExp1 and BoolExp2 are
1.
• BoolExp1 #^ BoolExp2: This constraint is 1 iff exactly one of BoolExp1 and BoolExp2
is 1.
• BoolExp1 #<=> BoolExp2: This constraint is 1 iff BoolExp1 and BoolExp2 are equiv-
alent.
92
12.5 Global Constraints
A global constraint is a constraint over multiple variables. A global constraint can normally be
translated into a set of smaller constraints, such as arithmetic and Boolean constraints. If the cp
module is used, then global constraints are not translated into smaller constraints; rather, they are
compiled into special propagators that maintain a certain level of consistency for the constraints.
In Picat, constraint propagators are encoded as action rules. If the sat module is used, then global
constraints are translated into smaller constraints before being translated further into conjunctive
normal form. If the mip module is used, then global constraints are decomposed into equality and
disequality constraints.
Picat provides the following global constraints.
• acyclic(V s,Es): This constraint ensures that the undirected graph represented by V s
and Es contains no cycles, where V s is a list of pairs of the form {V, B} and Es is a list of
triplets of the form {V1 , V2 , B}. A pair {V, B} in V s, where V is a ground term and B is a
Boolean variable, denotes that V is in the graph if and only if B = 1. A triplet {V1 , V2 , B}
denotes that V1 is connected with V2 by an edge in the graph if and only if B = 1 and
both V1 and V2 are in the graph. Note that the graph to be constructed is assumed to be
undirected. If there exists a triplet {V1 , V2 , B} in Es, then the triplet {V2 , V1 , B} will be
added to Es if it is not specified.
• acyclic_d(V s,Es): This constraint ensures that the directed graph represented by V s
and Es contains no cycles, where V s and Es are the same as those in acyclic(V s,Es),
except that the graph is directed.
• all_different(F DV ars): This constraint ensures that each pair of variables in the
list or array F DV ars is different. This constraint is compiled into a set of inequality con-
straints. For each pair of variables V 1 and V 2 in F DV ars, all_different(F DV ars)
generates the constraint V 1 #!= V 2.
assignment(Xs,Ys) =>
N = [Link],
(var(Ys) -> Ys = new_list(N); true),
Xs :: 1..N,
Ys :: 1..N,
foreach (I in 1..N, J in 1..N)
X[I] #= J #<=> Y[J] #= I
end.
93
• at_least(N ,L,V ): This constraint succeeds if there are at least N elements in L that
are equal to V , where N and V must be integer-domain variables, and L must be a list of
integer-domain variables.
• at_most(N ,L,V ): This constraint succeeds if there are at most N elements in L that
are equal to V , where N and V must be integer-domain variables, and L must be a list of
integer-domain variables.
circuit([X1,X2,X3,X4])
[3,4,2,1] is a solution, but [2,1,4,3] is not, because the graph 1 -> 2, 2 ->
1, 3 -> 4, 4 -> 3 contains two sub-cycles.
count(V,L,Rel,N) =>
sum([V #= E : E in L]) #= Count,
call(Rel,Count,N).
• disjunctive_tasks(T asks): T asks is a list of terms. Each term has the form
disj_tasks(S1 ,D1 ,S2 ,D2 ), where S1 and S2 are two integer-domain variables, and
94
D1 and D2 are two positive integers. This constraint is equivalent to posting the disjunc-
tive constraint S1 +D1 #=< S2 #\/ S2 +D2 #=< S1 for each term in T asks; however the
constraint may be more efficient, because it converts the disjunctive tasks into global con-
straints.
• element(I,List,V ): This constraint is true if the Ith element of List is V , where I and
V are integer-domain variables, and List is a list of integer-domain variables.
• exactly(N ,L,V ): This constraint succeeds if there are exactly N elements in L that
are equal to V , where N and V must be integer-domain variables, and L must be a list of
integer-domain variables.
global_cardinality(List,Pairs) =>
foreach ($Key-V in Pairs)
sum([B : E in List, B#<=>(E#=Key)]) #= V
end.
• hcp(V s,Es): This constraint ensures that the directed graph represented by V s and Es
forms a Hamiltonian cycle, where V s is a list of pairs of the form {V, B}, and Es is a list of
triplets of the form {V1 , V2 , B}. A pair {V, B} in V s, where V is a ground term and B is a
Boolean variable, denotes that V is in the graph if and only if B = 1. A triplet {V1 , V2 , B}
denotes that V1 is connected to V2 by an edge in the graph if and only if B = 1. The
circuit and subcircuit constraints can be implemented as follows by using hcp:
circuit(L) =>
N = len(L),
L :: 1..N,
Vs = [{I,1} : I in 1..N],
Es = [{I,J,B} : I in 1..N,
J in fd_dom(L[I]),
J !== I,
B #<=> L[I] #= J],
hcp(Vs,Es).
subcircuit(L) =>
N = len(L),
L :: 1..N,
Vs = [{I,B} : I in 1..N,
B #<=> L[I] #!= I],
Es = [{I,J,B} : I in 1..N,
J in fd_dom(L[I]),
J !== I,
95
B #<=> L[I] #= J],
hcp(Vs,Es).
• hcp(V s,Es,K): This constraint is the same as hcp(V s,Es), except that it also con-
strains the number of vertices in the graph to be K.
• hcp_grid(A): This constraint ensures that the grid graph represented by A, which is
a two-dimensional array of Boolean (0/1) variables, forms a Hamiltonian cycle. In a grid
graph, each cell is directly connected horizontally and vertically, but not diagonally, to its
neighbors. Only cells labeled 1 are considered as vertices of the graph. This constraint is
implemented as follows by using hcp:
hcp_grid(A) =>
NRows = len(A),
NCols = len(A[1]),
Vs = [{(R,C), A[R,C]} :
R in 1..NRows,
C in 1..NCols],
Es = [{(R,C), (R1,C1), _} :
R in 1..NRows,
C in 1..NCols,
(R1,C1) in neibs(A,NRows,NCols,R,C)],
hcp(Vs,Es).
neibs(A,NRows,NCols,R,C) =
[(R1,C1) : (R1,C1) in [(R-1,C), (R+1,C),
(R,C-1), (R,C+1)],
R1 >= 1, R1 =< NRows,
C1 >= 1, C1 =< NCols,
A[R1,C1] !== 0].
• lex_le(L1 ,L2 ): The sequence (an array or a list) L1 is lexicographically less than or
equal to L2 .
• lex_lt(L1 ,L2 ): The sequence (an array or a list) L1 is lexicographically less than L2 .
96
• matrix_element(M atrix,I,J,V ): This constraint is true if the entry at <I,J> in
M atrix is V , where I, J, and V are integer-domain variables, and M atrix is an two-
dimensional array of integer-domain variables.
• neqs(N eqList): N eqList is a list of inequality constraints of the form X #!= Y , where
X and Y are integer-domain variables. This constraint is equivalent to the conjunction of
the inequality constraints in N eqList, but it extracts all_distinct constraints from the
inequality constraints.
• nvalue(N ,List): The number of distinct values in List is N , where List is a list of
integer-domain variables.
• path(V s,Es,Src,Dest): This constraint ensures that the undirected graph represented
by V s and Es is a path from Src to Dest, where V s is a list of pairs of the form {V, B},
Es is a list of triplets of the form {V1 , V2 , B}, Src is a vertex, and Dest is a vertex or a list
of vertices. A pair {V, B} in V s, where V is a ground term representing a vertex and B is a
Boolean variable, denotes that V is in the graph if and only if B = 1. A triplet {V1 , V2 , B}
denotes that V1 is connected with V2 by an edge in the graph if and only if B = 1 and
both V1 and V2 are in the graph. Note that the graph to be constructed is assumed to be
undirected. If there exists a triplet {V1 , V2 , B} in Es, then the triplet {V2 , V1 , B} will be
added to Es if it is not specified.
• path_d(V s,Es,Src,Dest): This constraint ensures that the directed graph represented
by V s and Es is a path from Src to Dest, where V s and Es are the same as those in
path(V s,Es,Src,Dest), except that the graph is directed.
• scc(V s,Es): This constraint ensures that the undirected graph represented by V s and
Es is strongly connected, where V s is a list of pairs of the form {V, B}, and Es is a list of
triplets of the form {V1 , V2 , B}. A pair {V, B} in V s, where V is a ground term and B is a
Boolean variable, denotes that V is in the graph if and only if B = 1. A triplet {V1 , V2 , B}
denotes that V1 is connected with V2 by an edge in the graph if and only if B = 1 and
both V1 and V2 are in the graph. Note that the graph to be constructed is assumed to be
undirected. If there exists a triplet {V1 , V2 , B} in Es, then the triplet {V2 , V1 , B} will be
added to Es if it is not specified.
97
• scc(V s,Es,K): This constraint is the same as scc(V s,Es), except that it also con-
strains the number of vertices in the graph to be K.
• scc_grid(A): This constraint ensures that the grid graph represented by A, which is a
two-dimensional array of Boolean variables, forms a strongly connected undirected graph.
In a grid graph, each cell is directly connected horizontally and vertically, but not diagonally,
to its neighbors. Only cells labeled 1 are considered as vertices of the graph. This constraint
is implemented as follows by using scc:
scc_grid(A) =>
NRows = len(A),
NCols = len(A[1]),
Vs = [{(R,C), A[R,C]} :
R in 1..NRows,
C in 1..NCols],
Es = [{(R,C), (R1,C1), _} :
R in 1..NRows,
C in 1..NCols,
(R1,C1) in neibs(A,NRows,NCols,R,C),
(R,C) @< (R1,C1)],
scc(Vs,Es).
neibs(A,NRows,NCols,R,C) =
[(R1,C1) : (R1,C1) in [(R-1,C), (R+1,C),
(R,C-1), (R,C+1)],
R1 >= 1, R1 =< NRows,
C1 >= 1, C1 =< NCols,
A[R1,C1] !== 0].
Note that there is an edge between each pair of neighboring cells in the resulting graph as
long as the cells are in the graph.
• scc_d(V s,Es): This constraint ensures that the directed graph represented by V s and
Es is strongly connected, where V s and Es are the same as those in scc(V s,Es), except
that the graph is directed.
• scc_d(V s,Es,K): This constraint is the same as scc_d(V s,Es), except that it also
constrains the number of vertices in the graph to be K.
98
• subcircuit_grid(A): This constraint ensures that the grid graph represented by A,
which is a two-dimensional array of Boolean (0/1) variables, forms a Hamiltonian cycle. In
a grid graph, each cell is directly connected horizontally and vertically, but not diagonally,
to its neighbors. Only non-zero cells are considered as vertices of the graph.
• tree(V s,Es): This constraint ensures that the undirected graph represented by V s and
Es is a tree, where V s is a list of pairs of the form {V, B}, and Es is a list of triplets of
the form {V1 , V2 , B}. A pair {V, B} in V s, where V is a ground term and B is a Boolean
variable, denotes that V is in the tree if and only if B = 1. A triplet {V1 , V2 , B} denotes
that V1 is connected with V2 by an edge in the tree if and only if B = 1 and both V1 and V2
are in the tree. Note that the graph to be constructed is assumed to be undirected. If there
exists a triplet {V1 , V2 , B} in Es, then the triplet {V2 , V1 , B} will be added to Es if it is not
specified.
• tree(V s,Es,K): This constraint is the same as tree(V s,Es), except that it also
constrains the number of vertices in the tree to be K.
The sat module supports bit-vector constraints, which enhance modeling capabilities, improve
solving performance, and support large integers that exceed the bounds of domain values. A bit
vector is an array representing the binary form of an unsigned integer. Let V be a bit vector
of length N . The bit V [1] corresponds to the least significant bit, while V [N ] represents the
most significant bit. In a bit-vector constraint, a bit-vector argument may also be a non-negative
integer. If the argument is a non-negative integer, Picat automatically converts it to its binary
representation.
• bv_drop(A,N ): Returns a bit vector containing the remaining bits of bit-vector A after
dropping the lowest N bits.
99
• bv_or(A,B,C): Forces bit-vector C to be the bitwise or of bit-vectors A and B.
• solve(Opts,V ars): This predicate calls the imported solver to label the variables V ars
with values, where Opts is a list of options for the solver. The options will be detailed
below. This predicate can backtrack in order to find multiple solutions. The cp module
allows incremental labeling of variables, and some variables that occur in constraints but
are not passed to solve may remain uninstantiated after a call to solve. The user is
responsible for having all the variables that need to be instantiated passed to solve. In
constrast, the sat and mip modules do not support incremental labeling of variables.
• indomain(V ar): This predicate is only accepted by cp. It is the same as solve([],
[V ar]).
• solve_all(Opts,V ars) = Solutions: This function returns all the solutions that sat-
isfy the constraints.
100
12.7.1 Common Solving Options
The following options are accepted by all four of the solvers.5
• $limit(N ): Search up to N solutions.
• $max(V ar): Maximize the variable V ar.
• $min(V ar): Minimize the variable V ar.
• $report(Call): Execute Call each time a better answer is found while searching for an
optimal answer. This option cannot be used if the mip module is used.
101
12.7.3 Solving Options for sat
• dump: Dump the CNF code to stdout.
where SolF ile is a file for the solution, and T mpF ile is a file that stores the CPLEX-format
constraints. Picat throws existence_error if the command cbc is not available.
• glpk: Instruct Picat to use the GLPK MIP solver. Picat uses the following command to call
the GLPK solver:
where SolF ile is a solution file, and T mpF ile is a file that stores the CPLEX-format con-
straints. Picat throws existence_error if the command glpsol is not available.
• gurobi: Instruct Picat to use the Gurobi MIP solver. Picat uses the following command to
call the Gurobi solver:
where SolF ile is a file for the solution, and T mpF ile is a file that stores the CPLEX-
format constraints. Picat throws existence_error if the command gurobi_cl is not
available.
• scip: Instruct Picat to use the SCIP MIP solver. Picat provides an internal interface to the
SCIP solver through the C language.6 Note that, unlike other linear programming solvers,
SCIP only returns integer solutions although it allows real coefficients and contiguous-
domain variables.
6
The SCIP interface is not included in the pre-made binary executables, and users must build an executable from the
source code following the installation instructions.
102
12.7.5 Solving Options for smt
• cvc4: Instruct Picat to use the CVC4 SMT solver. Picat uses the following command to
call the CVC4 solver:
where T mpF ile is a file that stores the SMT-LIB2-format constraints, and SolF ile is a
solution file. Picat throws existence_error if the command cvc4 is not available in
the path.
• logic(Logic): Instruct the SMT solver to use Logic in the solving, where Logic must be
an atom or a string, and the specified logic must be available in the SMT solver. The default
logic for Z3 is “LIA”, and the default logic for CVC4 is “NIA”.
• tmp(F ile): Dump the SMT-LIB2 format to F ile rather than the default file “__tmp.smt2”,
before calling the smt solver. The name F ile must be a string or an atom that has the
extension name “.smt2”. When this file name is specified, the smt solver will save the
solution into a file name that has the same main name as F ile but the extension name “.sol”.
• z3: Instruct Picat to use the z3 SMT solver. When no SMT solver is specified, Picat first
searches for the command z3, and when z3 cannot be found it continues to search for the
command cvc4.
103
Chapter 13
The nn module provides a high-level interface between Picat and the FANN1 neural networks
library, which implements feedforward neural networks.2 A feedforward neural network consists
of neurons organized in layers from an input layer to an output layer, possibly with a number of
hidden layers. A feedforward network represents a function from input to output. Neurons in a
layer (except for the input layer) are connected to neurons in the previous layer. The connections
have weights. The neurons in the input layer receive the input. The information is propagated
forward through the layers until it reaches the output layer, where the output is returned. The in-
formation that a neuron receives is determined by the connected predecessor neurons, the weights
of the connections, and an activation function. The connection weights of a neural network are
normally adjusted through training on a given set of input-output pairs, called training data. Once
a neural network is trained, it can be used to predict the output for a given input.
The following gives an example program which creates a neural network for the xor function,
and trains it on a set of data stored in a file:
import nn.
main =>
NN = new_nn({2,3,1}),
nn_train(NN,"[Link]"),
nn_save(NN,"[Link]"),
nn_destroy_all.
The function new_nn({2,3,1}) returns a neural network with three layers, where the input
layer has 2 neurons, the hidden layer has 3 neurons, and the output layer has 1 neuron. The program
does not specify any activation functions used between layers, entailing that the default activation
function, which is sym_sigmoid, will be used. The predicate nn_train(NN,"[Link]")
trains the neural network with the training data stored in the file "[Link]". The user is able
to specify an algorithm to be used in the training and several parameters that affect the behavior
of the algorithm, such as the maximum number of iterations (called epochs), the learning rate, and
the error function. This example does not specify a training algorithm or any of the training param-
eters, entailing that the default algorithm, which is rprop, is used with the default setting. The
predicate nn_save saves the trained neural network into a file named "[Link]". The pred-
icate nn_destroy_all clears the neural network and the internal data structures used during
training.
The text file "[Link]" contains the following training data:
1
[Link]
2
The Picat-FANN interface was implemented by Sanders Hernandez.
104
4 2 1
-1 -1
-1
-1 1
1
1 -1
1
1 1
-1
The three integers in the first line state, respectively, that the number of input-output pairs is 4, the
number of input values is 2, and the number of output values is 1. The remaining lines give the
input-output pairs.
The following program performs the same task as the above program, except that it trains the
neural network with internal data:
import nn.
main =>
NN = new_nn({2,3,1}),
nn_train(NN,[({-1,-1}, -1),
({-1,1}, 1),
({1,-1}, 1),
({1,1}, -1)]),
nn_save(NN,"[Link]"),
nn_destroy_all.
The predicate nn_train is overloaded. When the second argument is a file name, Picat reads
training data from the file. Otherwise, Picat expects a collection (a list or an array) of input-output
pairs.
The following example program illustrates how to use a trained network:
import nn.
main =>
NN = nn_load("[Link]"),
printf("xor(-1,1) = %w\n",nn_run(NN,{-1,1})),
nn_destroy_all.
The function nn_load loads a neural network. The function nn_run uses the network to predict
the output for an input.
105
• new_sparse_nn(Layers,Rate) = N N : This function creates a sparse neural net-
work that has the structure Layers and the connection rate Rate. The connection rate de-
termines the sparseness of the network, with 1 indicating that the network is fully connected,
and 0 indicating that the network is not connected at all.
• nn_print(N N ): This predicate prints the attributes of the neural network N N , includ-
ing the connections, the weights, the activation functions, and some other parameters.
• nn_destroy_all: This predicate destroys all the neural networks and the internal data
structures.
An activation function for a neuron determines how information is propagated to it from its pre-
decessor neurons. When a new neural network is created, it uses the default activation function
sym_sigmoid for all of its non-input neurons. The following predicates can be utilized to set
activation functions.
– linear
– threshold
– sym_threshold: symmetric threshold.
– sigmoid
– step_sigmoid: stepped sigmoid
– sym_sigmoid: symmetric sigmoid
– elliot: an alternative for sigmoid
– sym_elliot: symmetric elliot
– gaussian
– sym_gaussian: symmetric Gaussian
– linear_piece
– sym_linear_piece: symmetric linear piece
– sin
– sym_sin: symmetric sin
– cos
– sym_cos: symmetric cos
The detault activation function is sym_sigmoid. Each of these functions has a corre-
sponding name in FANN. Please refer to the FANN documentation for a more detailed
description of these functions.
106
• nn_set_activation_function_hidden(N N ,F unc): This predicate sets the ac-
tivation function to F unc for all of the hidden layers in the neural network N N .
A training dataset can be supplied to FANN either through a text file or a Picat collection. A
training dataset file must have the following format:
A training dataset stored in a Picat collection must be either a list or an array of input-output pairs.
An input-output pair has the form (Input,Output), where Input is an array of numbers or a
single number, and so is Output.
107
13.4 Train Neural Networks
• nn_train(N N ,Data,Opts): This predicate trains the neural network N N using the
dataset Data under the control of training options Opts. The following training options are
supported:
• nn_save(N N ,F ile): This predicate saves the neural network N N to a file named F ile.
• nn_load(F ile) = N N : This function creates a neural network from a FANN neural
network file named F ile.
108
13.6 Run Neural Networks
109
Chapter 14
The os Module
Picat has an os module for manipulating files and directories. In order to use any of the functions
or predicates, users must import the module.
Many of the functions and predicates in this module have a P ath parameter. This parameter is
a string or an atom, representing the path of a file or directory. This path can be an absolute
path, from the system’s root directory, or a relative path, from the current file location. Different
systems use different separator characters to separate directories in different levels of the directory
hierarchy. For example, Windows uses ‘\’ and Unix uses ‘/’. The following function outputs a
single character, representing the character that the current system uses as a file separator.
• separator() = V al
14.2 Directories
The os module includes functions for reading and modifying directories. The following example
shows how to list all of the files in a directory tree, using a depth-first directory traversal.
Example
import os.
110
• listdir(P ath) = List: This function returns a list of all of the files and directories
that are contained inside the directory specified by P ath. If P ath is not a directory, then
an error is thrown. The returned list contains strings, each of which is the name of a file or
directory.
The above example also uses the directory predicate, which will be discussed in Section 14.4.
14.3.1 Creation
The os module contains a number of predicates for creating new files and directories:
• mkdir(P ath): This predicate creates a new directory at location P ath. The directory will
be created with a default permission list of [rwu, rwg, ro]. If the program does not
have permission to write to the parent directory of P ath, this predicate will throw an error.
An error will also occur if the parent directory does not exist.
• rename(Old,N ew): This renames a file or a directory from Old to N ew. This predicate
will throw an error if Old does not exist. An error will also occur if the program does not
have permission to write to Old or N ew.
• cp(F romP ath,T oP ath): This copies a file from F romP ath to T oP ath. This predicate
will throw an error if F romP ath does not exist or F romP ath is a directory. An error will
also occur if the program does not have permission to read from F romP ath, or if it does
not have permission to write to T oP ath.
14.3.2 Deletion
The os module contains a number of predicates for deleting files and directories.
• rm(P ath): This deletes a file. An error will be thrown if the file does not exist, if the
program does not have permission to delete the file, or if P ath refers to a directory, a hard
link, a symbolic link, or a special file type.
• rmdir(P ath): This deletes a directory. An error will be thrown if the directory does
not exist, the program does not have permission to delete the directory, the directory is not
empty, or if P ath does not refer to a directory.
111
14.4 Obtaining Information about Files
The os module contains a number of functions that retrieve file status information, and predicates
that test the type of a file. These predicates will all throw an error if the program does not have
permission to read from P ath.
• size(P ath) = Int: If P ath is not a symbolic link, then this function returns the number
of bytes contained in the file to which P ath refers. If P ath is a symbolic link, then this
function returns the path size of the symbolic link. Because the function size/1 is defined
in the basic module for returning the size of a map, this function requires an explicit
module qualifier [Link](P ath).
• file_base_name(P ath) = List: This function returns a string containing the base
name of P ath. For example, the base name of “a/b/[Link]" is “[Link]".
• file(P ath): Does P ath refer to a regular file? This predicate is true if P ath is neither a
directory nor a special file, such as a socket or a pipe.
• file_exists(P ath): This tests whether P ath exists, and, if it exists, whether P ath
refers to a regular file.
Example
import os.
test_file(Path) =>
if (not exists(Path))
printf("%s does not exist %n",Path)
elseif (directory(Path))
println("Directory")
elseif (file(Path))
println("File")
else
println("Unknown")
end.
112
14.5 Environment Variables
• getenv(N ame) = String: This function returns the value of the environment variable
N ame as a string. This function will throw an error if the environment variable N ame does
not exist.
113
Appendix A
Picat provides a math module, which has common mathematical constants and functions. The
math module is imported by default.
A.1 Constants
• e = 2.71828182845904523536
• pi = 3.14159265358979323846
A.2 Functions
The math module contains mathematical functions that serve a number of different purposes.
Note that the arguments must all be numbers. If the arguments are not numbers, then Picat will
throw an error.
• abs(X) = V al: This function returns the absolute value of X. If X ≥ 0, then this
function returns X. Otherwise, this function returns −X.
Example
Picat> Val1 = sign(3), Val2 = sign(-3), Val3 = sign(0)
Val1 = 1
Val2 = -1
Val3 = 0
Picat> Val = abs(-3)
Val = 3
114
A.2.2 Rounding and Truncation
The math module includes the following functions for converting a real number into the integers
that are closest to the number.
• ceiling(X) = V al: This function returns the closest integer that is greater than or
equal to X.
• floor(X) = V al: This function returns the closest integer that is less than or equal to
X.
• truncate(X) = V al: This function removes the fractional part from a real number.
• modf(X) = (IntV al,F ractV al): This function splits a real number into its integer
part and its fractional part.
Example
Picat> Val1 = ceiling(-3.2), Val2 = ceiling(3)
Val1 = -3
Val2 = 3
Picat> Val1 = floor(-3.2), Val2 = floor(3)
Val1 = -4
Val2 = 3
Picat> Val1 = round(-3.2), Val2 = round(-3.5), Val3 = round(3.5)
Val1 = -3
Val2 = -4
Val3 = 4
Picat> Val1 = truncate(-3.2), Val2 = truncate(3)
Val1 = -3
Val2 = 3
Picat> IF = modf(3.2)
IF = (3.0 , 0.2)
• pow_mod(X,Y ,Z) = V al: This function returns X Y mod Z. All of the arguments
must be integers, and Y must not be negative.
• sqrt(X) = V al: This function returns the square root of X. Note that the math module
does not support imaginary numbers. Therefore, if X < 0, this function throws an error.
115
• log2(X) = V al: This function returns log2 (X).
Example
Picat> P1 = pow(2, 5), P2 = exp(2)
P1 = 32
P2 = 7.38906
Picat> S = sqrt(1)
S = 1.0
Picat> E = log(7), T = log10(7), T2 = log2(7), B = log(7, 7)
E = 1.94591
T = 0.845098
T2 = 2.80735
B = 1.0
Example
Picat> R = to_radians(180)
R = 3.14159
Picat> D = to_degrees(pi)
D = 180.0
• sin(X) = V al: This function returns the sine of X, where X is given in radians.
• cos(X) = V al: This function returns the cosine of X, where X is given in radians.
• tan(X) = V al: This function returns the tangent of X, where X is given in radians.
• sec(X) = V al: This function returns the secant of X, where X is given in radians. If
cos(X) is 0, then this function throws an error.
• csc(X) = V al: This function returns the cosecant of X, where X is given in radians. If
sin(X) is 0, then this function throws an error.
• cot(X) = V al: This function returns the cotangent of X, where X is given in radians.
If tan(X) is 0, then this function throws an error.
• asin(X) = V al: This function returns the arc sine of X, in radians. The returned value
is in the range [-pi / 2, pi / 2]. X must be in the range [−1, 1]; otherwise, this
function throws an error.
116
• acos(X) = V al: This function returns the arc cosine of X, in radians. The returned
value is in the range [0, pi]. X must be in the range [−1, 1]; otherwise, this function
throws an error.
• atan(X) = V al: This function returns the arc tangent of X, in radians. The returned
value is in the range [-pi / 2, pi / 2].
• atan2(X,Y ) = V al: This function returns the arc tangent of Y / X, in radians. X and
Y are coordinates. The returned value is in the range [-pi, pi].
• asec(X) = V al: This function returns the arc secant of X, in radians. The returned
value is in the range [0, pi]. X must be in the range (−∞, −1] or [1, ∞); otherwise, this
function throws an error.
• acsc(X) = V al: This function returns the arc cosecant of X, in radians. The returned
value is in the range [-pi / 2, pi / 2]. X must be in the range (−∞, −1] or [1, ∞);
otherwise, this function throws an error.
• acot(X) = V al: This function returns the arc cotangent of X, in radians. The returned
value is in the range [-pi / 2, pi / 2].
Example
Picat> S = sin(pi), C = cos(pi), T = tan(pi)
S = 0.0
C = -1.0
T = 0.0
Picat> S = asin(0), C = acos(0), T = atan(0), T2 = atan2(-10, 10)
S = 0.0
C = 1.5708
T = 0.0
T2 = -0.785398
Picat> S = sec(pi / 4), C = csc(pi / 4), T = cot(pi / 4)
S = 1.41421
C = 1.41421
T = 1.0
Picat> S = asec(2), C = acsc(2), T = acot(0)
S = 1.0472
C = 0.5236
T = 1.5708
117
• csch(X) = V al: This function returns the hyperbolic cosecant of X. If X is 0, then this
function throws an error.
• acosh(X) = V al: This function returns the arc hyperbolic cosine of X. If X < 1, then
this function throws an error.
• atanh(X) = V al: This function returns the arc hyperbolic tangent of X. X must be in
the range (−1, 1); otherwise, this function throws an error.
• asech(X) = V al: This function returns the arc hyperbolic secant of X. X must be in
the range (0, 1]; otherwise, this function throws an error.
• acoth(X) = V al: This function returns the arc hyperbolic cotangent of X. X must be
in the range (−∞, −1) or (1, ∞); otherwise, this function throws an error.
Example
Picat> S = sinh(pi), C = cosh(pi), T = tanh(pi)
S = 11.54874
C = 11.59195
T = 0.99627
Picat> S = sech(pi / 4), C = csch(pi / 4), T = coth(pi / 4)
S = 0.75494
C = 1.15118
T = 1.52487
Picat> S = asinh(0), C = acosh(1), T = atanh(0)
S = 0.0
C = 0.0
T = 0.0
• random(Seed) = V al: This function returns a random integer. At the same time, it
changes the seed of the random number generator.
• random(Low,High) = V al: This function returns a random integer in the range Low..High.
118
• frand() = V al: This function returns a random real number between 0.0 and 1.0, inclu-
sive.
• frand(Low,High) = V al: This function returns a random real number between Low
and High, inclusive.
• gcd(A,B): This function returns the greatest common divisor of integer A and integer B.
• primes(N ) = List: This function returns a list of prime numbers that are less than or
equal to N .
119
Appendix B
The sys module, which is imported by default, contains built-ins that are relevant to the Picat
system. The built-ins in the sys module perform operations that include compiling programs,
tracing execution, and displaying statistics and information about the Picat system.
The sys module includes a number of built-ins for compiling programs and loading them into
memory.
• compile(F ileN ame): This predicate compiles the file F ileN [Link] and all of its de-
pendent files without loading the generated byte-code files. The destination directory for the
byte-code file is the same as the source file’s directory. If the Picat interpreter does not have
permission to write into the directory in which a source file resides, then this built-in throws
an exception. If F ileN [Link] imports modules, then these module files are also com-
piled. The system searches for these module files in the directory in which F ileN [Link]
resides or the directories that are stored in the environment variable PICATPATH.
• compile_bp(F ileN ame): This predicate translates the Picat file F ileN [Link] into
a B-Prolog file F ileN [Link]. If the file is dependent on other Picat files, then those files
are compiled using compile/1. The destination directory for the B-Prolog file is the same
as the source file’s directory. If the Picat interpreter does not have permission to write into
the directory in which a source file resides, then this built-in throws an exception.
• load(F ileN ame): This predicate loads the byte-code file F ileN [Link] and all of
its dependent byte-code files into the system for execution. For F ileN ame, the system
searches for a byte-code file in the directory specified by F ileN ame or the directories
that are stored in the environment variable PICATPATH. For the dependent file names, the
system searches for a byte-code file in the directory in which F ileN [Link] resides or the
directories that are stored in the environment variable PICATPATH. If the byte-code file
F ileN [Link] does not exist, but the source file F ileN [Link] exists, then this built-in
compiles the source file and loads the byte codes without creating a qi file. Note that, for
the dependent files, if the byte-code file does not exist, but the source file exists, then the
source file will be compiled.
• cl(F ileN ame): This predicate compiles and loads the source file named F ileN [Link].
Note that the extension .pi does not need to be given. The system also compiles and loads
all of the module files that are either directly imported or indirectly imported by the source
120
file. The system searches for such dependent files in the directory in which F ileN [Link]
resides or the directories that are stored in the environment variable PICATPATH.
• cl: This predicate compiles and loads a program from the console, ending when the end-
of-file character (ctrl-z for Windows and ctrl-d for Unix) is typed.
• cl_facts(F acts): This predicate compiles and loads facts into the system. The argu-
ment F acts is a list of ground facts.
• cl_facts(F acts,IndexInf o): This predicate compiles and loads facts into the system.
The argument F acts is a list of ground facts. The argument IndexInf o is a list of indexing
information in the form p(M1 ,M2 ,...,Mn ). Each Mi can either be +, which indicates
that the argument is input, or -, which indicates that the argument is output.
• cl_facts_table(F acts): This predicate is the same as cl_facts/1, except that the
facts are all tabled.
The Picat system has three execution modes: non-trace mode, trace mode, and spy mode. In
trace mode, it is possible to trace the execution of a program, showing every call in every possible
stage. In order to trace the execution, the program must be recompiled while the system is in trace
mode. In spy mode, it is possible to trace the execution of individual functions and predicates. The
following predicates are used to switch between non-trace mode and trace mode.
• spy(P oint): This predicate places a spy point on P oint, which is a function or a predicate,
optionally followed by an arity. The creation of a spy point switches the Picat system to spy
mode.
• nospy: This predicate removes all spy points, and switches the execution mode to non-trace
mode.
• abort: This predicate terminates the current program. This can be used in all three execu-
tion modes.
121
• - : remove a spy point.
• <cr> : A carriage return causes the system to show the next call trace.
• n : nodebug, prevent the system from displaying debugging messages for the remainder of
the program.
• t i : backtrace, show the backtrace from the call numbered i to the current call.
• u : undo what has been done to the current call and redo it.
• u i : undo what has been done to the call numbered i and redo it.
The sys module contains a number of built-ins that display information about the Picat system.
This information includes statistics about the system, including the memory that is used, and the
amount of time that it takes to perform a goal.
B.3.1 Statistics
The following built-ins display statistics about the memory that Picat system uses.
• statistics: This predicate displays the number of bytes that are allocated to each data
area, and the number of bytes that are already in use.
• statistics(Key,V alue): The statistics concerning Key are V alue. This predicate
gives multiple solutions upon backtracking. Keys include runtime, program, heap,
control, trail, table, gc, backtracks, and gc_time. The values for most of
the keys are lists of two elements. For the key runtime, the first element denotes the
amount of time in milliseconds that has elapsed since Picat started, and the second element
denotes the amount of time that has elapsed since the previous call to statistics/2
was executed. For the key gc, the number indicates the number of times that the garbage
collector has been invoked. For the key backtracks, the number indicates the number
of backtracks that have been done during the labeling of finite domain variables since Picat
was started. For all other keys, the first element denotes the size of memory in use, and the
122
second element denotes the size of memory that is still available in the corresponding data
area.
• statistics_all() = List: This function returns a list of lists that are in the form
[Key, Value]. The list contains all of the keys that statistics/2 can display, to-
gether with their corresponding values.
Example
Picat> statistics
Stack+Heap: 8,000,000 bytes
Stack in use: 1,156 bytes
Heap in use: 28,592 bytes
Memory manager:
GC: Call(0), Time(0 ms)
Expansions: Stack+Heap(0), Program(0), Trail(0), Table(0)
Key = program
Value = [1451656,6548344]?;
Key = heap
Value = [34112,7964524]?;
Key = control
Value = [1360,7964524]?;
Key = trail
Value = [1496,3998504]?;
Key = table
Value = [0,4000000]?;
Key = table_blocks
Value = 1?;
key = gc
Value = 0?;
123
Key = backtracks
V = 0 ?;
Key = gc_time
Value = 0
Picat> L = statistics_all()
L = [[runtime, [359947,66060]], [program, [1451656,6548344]],
[heap, [34112,7964524]], [control, [1360,7964524]],
[trail, [1496,3998504]], [table, [0,4000000]],
[table_blocks,1],[gc, 0], [backtracks, 0], [gc_time, 0]]
B.3.2 Time
The following predicates display the amount of CPU time that it takes to perform a goal.
• time(Goal): This predicate calls Goal, and reports the number of seconds of CPU time
that were consumed by the execution.
• time2(Goal): This predicate calls Goal, and reports the number of seconds of CPU
time that were consumed by the execution, and the number of backtracks that have been
performed in labeling finite-domain variables during the execution of Goal.
• loaded_modules() = List: This function returns a list of the modules that are cur-
rently loaded in the Picat system. This list includes library modules and user-defined mod-
ules. By default, this function returns [basic,sys,io,math].
• picat_path() = P ath: This function returns the directories that are stored in the en-
vironment variable PICATPATH. If the environment variable PICATPATH does not exist,
then this function throws an error.
• command(String) = Int: This function sends the command String to the OS and re-
turns the status that is returned from the OS.
Picat incorporates an incremental garbage collector for the control stack and the heap. The garbage
collector is active by default. The sys module includes the following predicates for garbage
collection.
124
• garbage_collect: This predicate starts the garbage collector.
• garbage_collect(Size): This predicate calls the garbage collector. If there are less
than Size words on the control stack and heap after garbage collection, then it invokes the
memory manager to expand the stack and heap so that there are Size words on the control
stack and heap.
• exit
• halt
125
Appendix C
The util module provides general useful utility functions and predicates. This module is ex-
pected to be expanded in the future. This module must be imported before use.
• replace(T erm,Old,N ew) = N ewT erm: This function returns a copy of T erm,
replacing all of the occurrences of Old in T erm by N ew.
• replace_at(T erm,Index,N ew) = N ewT erm: This function returns a copy of T erm,
replacing the argument at Index by N ew. T erm must be a compound term.
• find_first_of(T erm,P attern) = Index: This function returns the first index at
which the argument unifies with P attern. If there is no argument that unifies with P attern,
then this function returns -1. T erm must be either a list or a structure.
• find_last_of(T erm,P attern) = Index: This function returns the last index at
which the argument unifies with P attern. If there is no argument that unifies with P attern,
then this function returns -1. T erm must be either a list or a structure.
• chunks_of(List,K) = ListOf Lists: This function splits List into chunks, each of
which has length K, and returns the list of the chunks. The last chunk may have less than
K elements if the length of List is not a multiple of K.
• drop(List,K) = List: This function returns the suffix of List after the first K elements
are dropped, or [] if K is greater than the length of List.
• join(T okens) = String: This function is the same as join(T okens," " ).
126
• lstrip(List) = List: This function is the same as lstrip(List," \t\n\r").
• lstrip(List,Elms) = List: This function returns a copy of List with leading ele-
ments in Elms removed.
• rstrip(List,Elms) = List: This function returns a copy of List with trailing ele-
ments in Elms removed.
• strip(List,Elms) = List: This function returns a copy of List with leading and trail-
ing elements in Elms removed.
• take(List,K) = List: This function returns the prefix of List of length K, or List
itself if K is greater than the length of List.
An array matrix is a two-dimensional array. The first dimension gives the number of the rows and
the second dimension gives the number of the columns. A list matrix represents a matrix as a list
of lists.
• rows(A) = List: This function returns the rows of the matrix A as a list.
• columns(A) = List: This function returns the columns of the matrix A as a list.
• diagonal1(A) = List: This function returns primary diagonal of the matrix A as a list.
127
C.4 Utilities on Lists and Sets
128
Appendix D
An ordered set is represented as a sorted list that does not contain duplicates. The ordset module
provides useful utility functions and predicates on ordered sets. This module must be imported
before use.
• delete(OSet,Elm) = OSet1 : This function returns of a copy of OSet that does not
contain the element Elm.
• disjoint(OSet1 ,OSet2 ): This predicate is true when OSet1 and OSet2 have no ele-
ment in common.
• insert(OSet,Elm) = OSet1 : This function returns a copy of OSet with the element
Elm inserted.
• intersection(OSet1 ,OSet2 )=OSet3 : This function returns an ordered set that con-
tains elements which are in both OSet1 and OSet2 .
• new_ordset(List) = OSet: This function returns an ordered set that contains the ele-
ments of List.
• subtract(OSet1 ,OSet2 )=OSet3 : This function returns an ordered set that contains all
of the elements of OSet1 which are not in OSet2 .
• union(OSet1 ,OSet2 )=OSet3 : This function returns an ordered set that contains all of
the elements which are present in either OSet1 or OSet2 .
129
Appendix E
Picat’s datetime module provides built-ins for retrieving the date and time. This module must
be imported before use.
• current_datetime() = DateT ime: This function returns the current date and time
as a structure in the form
where the arguments are all integers, and have the following meanings and ranges.
In the M onth argument, 0 represents January, and 11 represents December. In the Hour
argument, 0 represents 12 AM, and 23 represents 11 PM. In the Second argument, the value
60 represents a leap second.
• current_date() = Date: This function returns the current date as a structure in the
form date(Y ear,M onth,Day), where the arguments have the meanings and ranges that
are defined above.
• current_day() = W Day: This function returns the number of days since Sunday, in
the range 0 to 6.
130
Appendix F
Formats
The following table shows the specifiers that can be used in formats for the writef, printf,
and to_fstring.
Specifier Output
%% Percent Sign
%c Character
%d Signed Decimal Integer
%e Scientific Notation, with Lowercase e
%E Scientific Notation, with Uppercase E
%f Decimal Real Number
%g Shorter of %e and %f
%G Shorter of %E and %f
%i Signed Decimal Integer
%n Platform-independent Newline
%o Unsigned Octal Integer
%s String
%u Unsigned Decimal Integer
%w Term
%x Unsigned Lowercase Hexadecimal Integer
%X Unsigned Uppercase Hexadecimal Integer
131
Appendix G
Picat has an interface with C, through which Picat programs can call deterministic predicates that
are written as functions in C. C programs that use this interface must include the file "picat.h"
in the directory Picat/Emulator. In order to make C-defined predicates available to Picat,
users have to re-compile Picat’s C source code together with the newly-added C functions.
Picat’s C interface provides functions for accessing, manipulating, and building Picat terms. In
order to understand these functions, users need to know how terms are represented in Picat’s
virtual machine.
A term is represented by a word that contains a value and a tag. A word has 32 bits or 64 bits,
depending on the underlying CPU and OS. The tag in a word distinguishes the type of the term.
The value of a term is an address, except when the term is an integer (in which case, the value
represents the integer itself). The location to which the address points is dependent on the type
of the term. In a reference, the address points to the referenced term. An unbound variable is
represented by a self-referencing pointer. In an atom, the address points to the record for the atom
symbol in the symbol table. In a structure, f (t1 , . . . , tn ), the address points to a block of n + 1
consecutive words, where the first word points to the record for the functor, f/n, in the symbol
table, and the remaining n words store the components of the structure. Arrays, floating-point
numbers, and big integers are represented as special structures. Picat lists are singly-linked lists.
In a list, [H|T], the address points to a block of two consecutive words, where the first word stores
the car, H, and the second word stores the cdr, T.
A C function that defines a Picat predicate should not take any argument. The following function
is used in order to fetch arguments in the current Picat call.
The following functions are provided for testing Picat terms. They return PICAT_TRUE when
they succeed and PICAT_FALSE when they fail.
132
• int picat_is_var(TERM t): Term t is a variable.
• int picat_is_nil(TERM t): Term t is nil, i.e., the empty list [].
The following functions convert Picat terms to C. If a Picat term does not have the expected type,
then the global C variable exception, which is of type Term, is assigned a term. A C program
that uses these functions must check exception in order to see whether data are converted
correctly. The converted data are only correct when exception is (TERM)NULL.
• long picat_get_integer(TERM t): Convert the Picat integer t into C. The term
t must be an integer; otherwise exception is set to integer_expected and 0 is
returned. Note that precision may be lost if t is a big integer.
• double picat_get_float(TERM t): Convert the Picat float t into C. The term t
must be a floating-point number; otherwise exception is set to number_expected,
and 0.0 is returned.
133
• (char *) picat_get_struct_name(TERM t): Return a pointer to the string that
is the name of structure t. The term t must be a structure; otherwise, exception is set to
structure_expected, and NULL is returned.
• int picat_unify(TERM t1,TERM t2): Unify two Picat terms t1 and t2. The
result is PICAT_TRUE if the unification succeeds, and PICAT_FALSE if the unification
fails.
• TERM picat_get_arg(int i,TERM t): Return the ith argument of term t. The
term t must be compound, and i must be an integer that is between 1 and the arity of
t; otherwise, exception is set to compound_expected, and the Picat integer 0 is
returned.
• TERM picat_get_car(TERM t): Return the car of the list t. The term t must be a
non-empty list; otherwise exception is set to list_expected, and the Picat integer 0
is returned.
• TERM picat_get_cdr(TERM t): Return the cdr of the list t. The term t must be a
non-empty list; otherwise exception is set to list_expected, and the Picat integer 0
is returned.
• TERM picat_build_list(): Return a Picat list whose car and cdr are free variables.
• TERM picat_build_array(int n): Return a Picat array whose size is n. The ar-
ray’s arguments are all free variables.
134
G.7 Registering C-defined Predicates
The first argument is the predicate name, the second argument is the arity, and the third argument is
the name of the function that defines the predicate. The function that defines the predicate cannot
take any argument. As described above, picat_get_call_arg(i,arity) is used to fetch
arguments from the Picat call.
For example, the following registers a predicate whose name is "p", and whose arity is 2.
The C function’s name does not need to be the same as the predicate name.
Predicates that are defined in C should be registered after the Picat engine is initialized, and
before any call is executed. One good place for registering predicates is the Cboot() function
in the file cpreds.c, which registers all of the C-defined built-ins of Picat. After registration,
the predicate can be called. All C-defined predicates must be explicitly called with the module
qualifier bp, as in bp.p(a,X).
Example
where the first argument is given and the second is unknown. The following steps show how to
define this predicate in C, and how to make it callable from Picat.
Step 1 . Write a C function to implement the predicate. The following shows a sample:
#include "picat.h"
p(){
TERM a1, a2, a, b, c, f1, l1, f12;
char *name_ptr;
135
f12 = picat_build_float(1.2); /* 1.2 */
Step 3 . Modify the make file, if necessary, and recompile the system. Now, p/2 is in the group
of built-ins in Picat.
picat> bp.p(a,X)
X = f(a)
136
Appendix H
Appendix: Tokens
Tokens to be returned:
Token-type lexeme
=====================
ATOM a string of chars of the atom name
VARIABLE a string of chars of the variable name
INTEGER an integer literal
FLOAT a float literal
STRING a string of chars
OPERATOR a string of chars in the operator
SEPARATOR one of "(" ")" "{" "}" "[" "]"
*/
line_terminator ->
the LF character, also known as "newline"
the CR character, also known as "return"
the CR character followed by the LF character
input_char ->
utf8_char but not CR or LF
comment ->
traditional_comment
end_of_line_comment
traditional_comment ->
"/*" comment_tail
comment_tail ->
"*" comment_tail_star
not_star comment_tail
comment_tail_star ->
"/"
"*" comment_tail_star
not_star_not_slash comment_tail
not_star ->
input_char but not "*"
line_terminator
not_star_not_slash ->
input_char but not "*" or "/"
line_terminator
end_of_line_comment ->
"%" {input_char} line_terminator
137
white_space ->
the SP character, also known as "space"
the HT character, also known as "horizontal tab"
the FF character, also known as "form feed"
line_terminator
token ->
atom_token
variable_token
integer_literal
real_literal
string_literal
operator_token
separator_token
atom_token ->
small_letter {alphanumeric_char}
single_quoted_token
variable_token ->
anonymous_variable
named_variable
named_variable ->
"_" alphanumeric {alphanumeric}
capital_letter {alphanumeric}
alphanumeric ->
alpha_char
decimal_digit
alpha_char ->
underscore_char
letter
letter ->
small_letter
capital_letter
single_quoted_token ->
"’" {string_char} "’"
string_literal ->
"\"" {string_char} "\""
string_char ->
input_char
escape_sequence
integer_literal ->
decimal_numeral
hex_numeral
octal_numeral
binary_numeral
decimal_numeral ->
decimal_digit [decimal_digits_and_underscores]
decimal_digits_and_underscores ->
decimal_digit_or_underscore
decimal_digits_and_underscores decimal_digit_or_underscore
decimal_digit_or_underscore ->
decimal_digit
"_"
138
hex_numeral ->
"0x" hex_digits
"0X" hex_digits
hex_digits ->
hex_digit [hex_digits_and_underscores]
hex_digits_and_underscores ->
hex_digit_or_underscore
hex_digits_and_underscores hex_digit_or_underscore
hex_digit_or_underscore ->
hex_digit
"_"
octal_numeral ->
"0O" octal_digits
"0o" octal_digits
octal_digits ->
octal_digit [octal_digits_and_underscores]
octal_digits_and_underscores ->
octal_digit_or_underscore
octal_digits_and_underscores octal_digit_or_underscore
octal_digit_or_underscore ->
octal_digit
"_"
binary_numeral ->
"0b" binary_digits
"0B" binary_digits
binary_digits:
binary_digit [binary_digits_and_underscores]
binary_digits_and_underscores ->
binary_digit_or_underscore
binary_digits_and_underscores binary_digit_or_underscore
binary_digit_or_underscore:
binary_digit
"_"
real_literal ->
decimal_numeral "." decimal_numeral [exponent_part]
exponent_part ->
exponent_indicator signed_integer
exponent_indicator ->
"e"
"E"
signed_integer ->
[sign] decimal_numeral
sign ->
"+"
"-"
separator ->
one of "(" ")" "{" "}" "[" "]"
operator ->
one of
"=" "!=" ">" ">=" "<" "<=" "=<" ".." "!"
"," ";" ":" "::" "." ". " (dot-whitespace)
"=>" "?=>" "==" "!==" ":=" "|" "$" "@"
139
"/\" "\/" "~" "^" "<<" ">>"
"+" "-" "*" "**" "/" "/>" "/<" "^"
"#=" "#!=" "#>" "#>=" "#<" "#<=" "#=<"
"#/\" "#\/" "#~" "#^" "#=>" "#<=>"
"@>" "@>=" "@<" "@<=" "@=<"
small_letter ->
one of "a" "b" ... "z"
capital_letter ->
one of "A" "B" ... "Z"
decimal_digit ->
one of "0" "1" "2" "3" "4" "5" "6" "7" "8" "9"
hd ->
hex_digit
hex_digit ->
one of
"0" "1" "2" "3" "4" "5" "6" "7" "8" "9"
"a" "b" "c" "d" "e" "f" "A" "B" "C" "D" "E" "F"
octal_digit ->
one of "0" "1" "2" "3" "4" "5" "6" "7"
binary_digit ->
one of "0" "1"
escape_sequence ->
"\"" /* double quote " */
"\’" /* single quote ’ */
"\\" /* backslash \ */
"\‘" /* back quote ‘ */
"\a" /* alarm */
"\b" /* backspace */
"\f" /* form feed */
"\n" /* line feed */
"\r" /* carriage return */
"\t" /* horizontal tab */
"\uhh...h" /* unicode (utf-8) code point */
"\v" /* vertical tab */
140
Appendix I
Appendix: Grammar
program_body ->
{predicate_definition | function_definition | actor_definition}
module_declaration ->
"module" atom eor
import_declaration ->
import import_item {"," import_item} eor
import_item ->
atom
predicate_definition ->
{predicate_directive} predicate_rule_or_fact {predicate_rule_or_fact}
function_definition ->
{function_directive} function_rule_or_fact {function_rule_or_fact}
actor_definition ->
["private"] action_rule {(action_rule
| nonbacktrackable_predicate_rule)}
function_directive ->
"private"
"table"
predicate_directive ->
"private"
"table" ["(" table_mode {"," table_mode} ")" ]
"index" index_declaration {"," index_declaration}
index_declaration ->
141
"(" index_mode {"," index_mode} ")"
index_mode ->
"+"
"-"
table_mode ->
"+"
"-"
"min"
"max"
"nt"
predicate_rule_or_fact ->
predicate_rule
predicate_fact
function_rule_or_fact ->
function_rule
function_fact
predicate_rule ->
head ["," condition] ("=>" | "?=>") body eor
head (":-" | "-->") body eor
nonbacktrackable_predicate_rule ->
head ["," condition] "=>" body eor
predicate_fact ->
head eor
head ->
atom ["(" [term {"," term}] ")"]
function_rule ->
head "=" expression ["," condition] "=>" body eor
function_fact ->
head "=" argument eor
action_rule ->
head ["," condition] "," "{" event_pattern "}" => body eor
event_pattern ->
term {’,’ term}
argument ->
negative_goal
goal ->
disjunctive_goal
disjunctive_goal ->
disjunctive_goal ";" conjunctive_goal
conjunctive_goal
conjunctive_goal ->
conjunctive_goal "," negative_goal
negative_goal
negative_goal ->
"not" negative_goal
equiv_constr
equiv_constr ->
equiv_constr "#<=>" impl_constr
142
impl_constr
impl_constr ->
impl_constr "#=>" or_constr
or_constr
or_constr ->
or_constr "#\/" xor_constr
xor_constr
xor_constr ->
xor_constr "#^" and_constr
and_constr
and_constr ->
and_constr "#/\" not_constr
not_constr
not_constr ->
"#~" not_constr
enclosed_goal
enclosed_goal ->
"if" if_cond goal {"elseif" if_cond goal} "else" goal "end"
"foreach" "(" iterator {"," (iterator | condition)} ")" goal "end"
"while" "(" goal ")" ["do"] goal "end"
"do" goal "while" "(" goal ")"
expression {bin_rel_op expression}
bin_rel_op ->
"="
"!="
":="
"=="
"!=="
">"
">="
"<"
"=<"
"<="
"::"
"in"
"notin"
"#="
"#!="
"#>"
"#>="
"#<"
"#=<"
"#<="
"@>"
"@>="
"@<"
"@=<"
"@<="
expression ->
concat_expression
concat_expression ->
range_expression ["++" concat_expression]
range_expression ->
or_expression [".." or_expression [".." or_expression]]
or_expression ->
xor_expression
143
or_expression "\/" xor_expression
xor_expression ->
and_expression
xor_expression "^" and_expression % bit-wise xor
and_expression ->
shift_expression
and_expression "/\" shift_expression
shift_expression ->
additive_expression
shift_expr ( "<<" | ">>" ) additive_expression
additive_expression ->
multiplicative_expression
additive_expression "+" multiplicative_expression
additive_expression "-" multiplicative_expression
multiplicative_expression ->
unary_expression
multiplicative_expression "*" unary_expression
multiplicative_expression "/" unary_expression
multiplicative_expression "//" unary_expression
multiplicative_expression "/>" unary_expression
multiplicative_expression "/<" unary_expression
multiplicative_expression "div" unary_expression
multiplicative_expression "mod" unary_expression
multiplicative_expression "rem" unary_expression
unary_expression ->
power_expression
"+" unary_expression
"-" unary_expression
"~" unary_expression % bit-wise complement
power_expression ->
primary_expression ["**" unary_expression]
primary_expression ->
"(" goal ")"
variable "[" argument ["," argument] "]" % subscript notation
variable "@" term ["@"] % as-pattern
variable
integer
float
atom_or_call
list_expression
array_expression
function_call
term_constructor
primary_expression "." atom_or_call % dot-notation
atom_or_call ->
atom ["(" [argument {"," argument}] ")"]
list_expression ->
"[]"
"[" argument list_expression_suffix "]"
list_expression_suffix ->
":" iterator {"," (iterator | condition)} % list comprehension
{"," argument} ["|" argument]
array_expression ->
"{}"
"{" argument array_expression_suffix "}"
array_expression_suffix ->
144
":" iterator {"," (iterator | condition)} % array comprehension
{"," argument}
function_call ->
[primary_expression "."] atom "(" [argument {"," argument}] ")"
variable_list ->
"[" [variable {"," variable}] "]"
term_constructor ->
"$" goal ["$"]
/* a term has the same form as a goal except that it cannot contain loops
or if statements. Note that subscript notations, range expressions, dot
notations, and list comprehensions are still treated as functions in
term constructors */
145
Appendix J
Appendix: Operators
Precedence Operators
Highest ., @
** (right-associative)
unary +, unary -, ~
*, /, //, /<, />, div, mod, rem
binary +, binary -
>>, <<
/\
^
\/
..
++ (right-associative)
=, !=, :=, ==, !==, =:=, <, =<, <=, >, >=, ::, in, notin, =..
#=, #!=, #<, #=<, #<=, #>, #>=, @<, @=<, @<=, @>, @>=
#~
#/\
#^
#\/
#=> (right-associative)
#<=>
not, once, \+
, (right-associative), && (right-associative)
Lowest ; (right-associative), || (right-associative)
146
Appendix K
147
• findall(T emplate,Call) = List • minof(Call,Objective)
• first(Compound) = T erm • minof(Call,Objective,ReportCall)
• flatten(List1) = List2 • minof_inc(Call,Objective)
• float(T erm) • minof_inc(Call,Objective,ReportCall)
• fold(F ,ACC,List) = Res • name(Struct) = N ame
• freeze(X,Goal) • new_array(D1 ,. . .,Dn ) = Arr
• functor(T ,F ,N ) • new_list(N ) = List
• get(M ap,Key) = V al • new_list(N ,InitV al) = List
• get(M ap,Key,Def aultV al)=V al • new_map(Int,P airsList) = M ap
• get_attr(AttrV ar,Key) = V al • new_map(IntOrP airsList) = M ap
• get_attr(AttrV ar,Key,Def aultV al)=V al • new_max_heap(IntOrList) = Heap
• get_global_map(ID) = M ap • new_min_heap(IntOrList) = Heap
• get_global_map() = M ap • new_set(Int,ElmsList) = M ap
• get_heap_map(ID) = M ap • new_set(IntOrElmsList) = M ap
• get_heap_map() = M ap • new_struct(N ame,IntOrList) = Struct
• get_table_map(ID) = M ap • nonvar(T erm)
• get_table_map() = M ap • not Call
• ground(T erm) • nth(I,ListOrArray,V al) (nondet)
• handle_exception(T erm,T erm) • number(T erm)
• has_key(M ap,Key) • number_chars(N um) = String
• number_codes(N um) = List
• hash_code(T erm) = Int
• number_vars(T erm)
• head(List) = T erm
• number_vars(T erm,N0 ) = N1
• heap_is_empty(Heap)
• once Call
• heap_pop(Heap) = Elm
• ord(Char) = Int
• heap_push(Heap,Elm)
• parse_radix_string(String,Base) = Int
• heap_size(Heap) = Size
• parse_term(String) = T erm
• heap_to_list(Heap) = List
• parse_term(String,T erm,V ars)
• heap_top(Heap) = Elm
• post_event(X,Event)
• insert(List,Index,Elm) = ResList • post_event_any(X,Event)
• insert_all(List,Index,AList) = ResList • post_event_bound(X)
• insert_ordered(List,T erm) = R • post_event_dom(X,Event)
• insert_ordered_down(List,T erm) = R • post_event_ins(X)
• int(T erm) • prod(Collection) = V al
• integer(T erm)
• put(M ap,Key)
• is(T1 ,T2 )
• put(M ap,Key,V al)
• keys(M ap) = List
• put_attr(V ar,Key)
• last(Compound) = T erm
• put_attr(V ar,Key,V al)
• len(T erm) = Len
• real(T erm)
• length(T erm) = Len
• reduce(F unc,List) = Res
• list(T erm) • reduce(F unc,List,InitV al) = Res
• list_to_and(List) = Conj • remove_dups(ListOrArray) = ResList
• lowercase(Char) • repeat (nondet)
• map(F unc,List1,List2) = ResList • reverse(ListOrArray) = Res
• map(F uncOrList,ListOrF unc) = ResList
• second(Compound) = T erm
• map(T erm)
• select(X,List,ResList) (nondet)
• map_to_list(M ap) = List
• size(M ap) = Size
• max(ListOrArray) = V al • slice(ListOrArray,F rom)
• max(X,Y ) = V al • slice(ListOrArray,F rom,T o)
• maxint_small() = Int
• sort(ListOrArray) = Sorted
• maxof(Call,Objective)
• sort(ListOrArray,KeyIndex) = Sorted
• maxof(Call,Objective,ReportCall)
• sort_down(ListOrArray) = Sorted
• maxof_inc(Call,Objective)
• sort_down(ListOrArray,KeyIndex) = Sorted
• maxof_inc(Call,Objective,ReportCall)
• sort_down_remove_dups(ListOrArray) = Sorted
• membchk(T erm,List)
• sort_down_remove_dups(ListOrArray,KeyIndex) =
• member(T erm,List) (nondet) Sorted
• min(ListOrArray) = V al • sort_remove_dups(ListOrArray) = Sorted
• min(X,Y ) = V al • sort_remove_dups(ListOrArray,KeyIndex) = Sorted
• minint_small() = Int • sorted(ListOrArray)
148
• sorted_down(ListOrArray) • floor(X) = V al
• string(T erm) • frand() = V al
• struct(T erm) • frand(Low,High) = V al
• subsumes(T erm1 ,T erm2 ) • gcd(A,B) = V al
• sum(Collection) = V al • log(X) = V al
• tail(List) = T erm • log(B,X) = V al
• throw(E) • log10(X) = V al
• to_array(List) = Array • log2(X) = V al
• to_atom(String) = Atom • modf(X) = (IntV al,F ractV al)
• to_binary_string(Int) = String • odd(Int)
• to_codes(T erm) = List • pi() = 3.14159265358979323846
• to_fstring(F ormat,Args . . .) = String • pow(X,Y ) = V al
• to_hex_string(Int) = String • pow_mod(X,Y ,Z) = V al
• prime(Int)
• to_int(N umOrCharOrStr) = Int
• primes(Int) = List
• to_integer(N umOrCharOrStr) = Int
• rand_max() = V al
• to_list(Struct) = List
• random = V al
• to_lowercase(String) = LString
• random(Low,High) = V al
• to_number(N umOrCharOrStr) = N umber
• random(Seed) = V al
• to_oct_string(Int) = String
• random2() = Int
• to_radix_string(Int,Base) = String
• round(X) = V al
• to_real(N umOrStr) = Real • sec(X) = V al
• to_string(T erm) = String • sech(X) = V al
• to_uppercase(String) = U String • sign(X) = V al
• true • sin(X) = V al
• uppercase(Char) • sinh(X) = V al
• values(M ap) = List • sqrt(X) = V al
• var(T erm) • tan(X) = V al
• variant(T erm1 ,T erm2 ) • tanh(X) = V al
• vars(T erm) = V ars • to_degrees(Radian) = Degree
• zip(List1 ,List2 ) = List • to_radians(Degree) = Radian
• zip(List1 ,List2 ,List3 ) = List • truncate(X) = V al
• zip(List1 ,List2 ,List3 ,List4 ) = List
149
• read_char_code() = V al Module os
• read_file_bytes(F ile) = List
• cd(P ath)
• read_file_bytes() = List • chdir(P ath)
• read_file_chars(F ile) = String • cp(F romP ath,T oP ath)
• cwd() = P ath
• read_file_chars() = String • directory(P ath)
• read_file_codes(F ile) = List • dir
• env_exists(N ame)
• read_file_codes() = List • executable(P ath)
• read_file_lines(F ile) = List • exists(P ath)
• read_file_lines() = List • file(P ath)
• file_base_name(P ath) = String
• read_file_terms(F ile) = List • file_directory_name(P ath) = String
• read_file_terms() = List • file_exists(P ath)
• read_int(F D) = Int • getenv(EnvString) = String
• listdir(P ath) = List
• read_int() = Int • ls
• read_line(F D) = String • mkdir(P ath)
• pwd() = P ath
• read_line() = String • readable(P ath)
• read_number(F D) = N umber • rename(Old,N ew)
• rm(P ath)
• read_number() = N umber
• rmdir(P ath)
• read_picat_token(F D) = T okenV alue • separator() = V al
• read_picat_token(F D,T okenT ype,T okenV alue) • size(P ath) = Int
• writable(P ath)
• read_picat_token(T okenT ype,T okenV alue)
• read_picat_token() = T okenV alue
Modules cp, mip, sat, and smt
• read_real(F D) = Real
• read_real() = Real • #~X
• X #!= Y
• read_term(F D) = T erm • X #/\ Y
• read_term() = T erm • X #< Y
• X #<= Y
• readln(F D) = String • X #<=> Y
• readln() = String • X #= Y
• X #=< Y
• write(F D,T erm) • X #=> Y
• write(T erm) • X #> Y
• X #>= Y
• write_byte(Bytes) • X #\/ Y
• write_byte(F D,Bytes) • X #^ Y
• V ars :: Exp
• write_char(Chars) • V ars notin Exp
• write_char(F D,Chars) • acyclic(V s,Es)
• write_char_code(Codes) • acyclic_d(V s,Es)
• all_different(F DV ars)
• write_char_code(F D,Codes) • all_different_except_0(F DV ars)
• writef(F D,F ormat,Args . . .) • all_distinct(F DV ars)
• assignment(F DV ars1,F DV ars2)
• writeln(F D,T erm)
• at_least(N ,L,V )
• writeln(T erm) • at_most(N ,L,V )
• bv_add(A,B,C) (sat only)
• bv_and(A,B,C) (sat only)
Module ordset • bv_div(A,B,C) (sat only)
• bv_drop(A,N ) (sat only)
• delete(OSet,Elm) = OSet1 • bv_eq(A,B) (sat only)
• disjoint(OSet1,OSet2) • bv_ge(A,B) (sat only)
• bv_gt(A,B) (sat only)
• insert(OSet,Elm) = OSet1
• bv_mod(A,B,C) (sat only)
• intersection(OSet1,OSet2)=OSet3 • bv_mul(A,B,C) (sat only)
• new_ordset(List) • bv_neq(A,B) (sat only)
• ordset(T erm) • bv_or(A,B,C) (sat only)
• bv_pow(A,B,C) (sat only)
• subset(OSet1,OSet2)
• bv_sum(As,B) (sat only)
• subtract(OSet1,OSet2)=OSet3 • bv_take(A,N ) (sat only)
• union(OSet1,OSet2)=OSet3 • bv_to_int(A) (sat only)
150
• bv_xor(A,B,C) (sat only) • solve_all(V ars) = List
• circuit(F DV ars) • solve_suspended(Opt) (cp only)
• count(V ,F DV ars,N )
• count(V ,F DV ars,Rel,N ) • solve_suspended (cp only)
• cumulative(Ss,Ds,Rs,Limit) • subcircuit(F DV ars)
• decreasing(L)
• subcircuit_grid(A)
• decreasing_strict(L)
• diffn(RectangleList) • subcircuit_grid(A,K)
• disjunctive_tasks(T asks) (cp only) • table_in(DV ars,R)
• element(I,List,V ) • table_notin(DV ars,R)
• element0(I,List,V )
• tree(V s,Es)
• exactly(N ,L,V )
• fd_degree(F DV ar) = Degree (cp only) • tree(V s,Es,K)
• fd_disjoint(DV ar1,DV ar2)
• fd_dom(F DV ar) = List
• fd_false(F DV ar,Elm) Module planner
• fd_max(F DV ar) = M ax
• fd_min(F DV ar) = M in • best_plan(S,Limit,P lan)
• fd_min_max(F DV ar,M in,M ax)
• best_plan(S,Limit,P lan,Cost)
• fd_next(F DV ar,Elm) = N extElm
• fd_prev(F DV ar,Elm) = P revElm • best_plan(S,P lan)
• fd_set_false(F DV ar,Elm) (cp only) • best_plan(S,P lan,Cost)
• fd_size(F DV ar) = Size • best_plan_bb(S,Limit,P lan)
• fd_true(F DV ar,Elm)
• fd_vector_min_max(M in,M ax) • best_plan_bb(S,Limit,P lan,Cost)
• global_cardinality(List,P airs) • best_plan_bb(S,P lan)
• hcp(V s,Es)
• best_plan_bb(S,P lan,Cost)
• hcp(V s,Es,K)
• hcp_grid(A) • best_plan_bin(S,Limit,P lan)
• hcp_grid(A,Es) • best_plan_bin(S,Limit,P lan,Cost)
• hcp_grid(A,Es,K) • best_plan_bin(S,P lan)
• increasing(L)
• increasing_strict(L) • best_plan_bin(S,P lan,Cost)
• indomain(V ar) (nondet) (cp only) • best_plan_nondet(S,Limit,P lan) (nondet)
• indomain_down(V ar) (nondet) (cp only) • best_plan_nondet(S,Limit,P lan,Cost) (nondet)
• int_to_bv(C) (sat only)
• best_plan_nondet(S,P lan) (nondet)
• lex_le(L1 ,L2 )
• lex_lt(L1 ,L2 ) • best_plan_nondet(S,P lan,Cost) (nondet)
• matrix_element(M atrix,I,J,V ) • best_plan_unbounded(S,Limit,P lan)
• matrix_element0(M atrix,I,J,V )
• best_plan_unbounded(S,Limit,P lan,Cost)
• neqs(N eqList) (cp only)
• new_bv(N ) (sat only) • best_plan_unbounded(S,P lan)
• new_dvar() = F DV ar • best_plan_unbounded(S,P lan,Cost)
• new_fd_var() = F DV ar
• current_plan()=P lan
• path(V s,Es,Src,Dest)
• path_d(V s,Es,Src,Dest) • current_resource()=Amount
• regular(X, Q, S, D, Q0, F ) • current_resource_plan_cost(Amount,P lan,Cost)
• scalar_product(A,X,P roduct) • is_tabled_state(S)
• scalar_product(A,X,Rel,P roduct)
• plan(S,Limit,P lan)
• scc(V s,Es)
• scc(V s,Es,K) • plan(S,Limit,P lan,Cost)
• scc_d(V s,Es)
• plan(S,P lan)
• scc_d(V s,Es,K)
• scc_grid(A) • plan(S,P lan,Cost)
• scc_grid(A,K) • plan_unbounded(S,Limit,P lan)
• serialized(Starts,Durations)
• plan_unbounded(S,Limit,P lan,Cost)
• solve(Opts,V ars) (nondet)
• solve(V ars) (nondet) • plan_unbounded(S,P lan)
• solve_all(Opts,V ars) = List • plan_unbounded(S,P lan,Cost)
151
Module nn (Neural Networks) • garbage_collect
• garbage_collect(Size)
• new_nn(Layers) = N N • halt
• new_sparse_nn(Layers) = N N • initialize_table
• new_sparse_nn(Layers,Rate) = N N • load(F ile)
• new_standard_nn(Layers) = N N • loaded_modules()
• nn_destroy(N N ) • nodebug
• nn_destroy_all • nospy
• nn_load(F ile) = N N • notrace
• nn_print(N N ) • spy F unctor
• nn_run(N N ,Input) = Output • statistics
• statistics(N ame,V alue) (nondet)
• nn_run(N N ,Input,Opts) = Output
• statistics_all() = List
• nn_save(N N ,F ile)
• time(Goal)
• nn_set_activation_function_hidden(N N ,F unc)
• time2(Goal)
• nn_set_activation_function_layer(N N ,F unc,Layer)
• time_out(Goal,Limit,Res)
• nn_set_activation_function_output(N N ,F unc)
• trace
• nn_set_activation_steepness_hidden(N N ,Steepness)
• nn_set_activation_steepness_layer(N N ,Steepness,Layer)
• nn_set_activation_steepness_output(N N ,Steepness)
Module util
• nn_train(N N ,Data) • array_matrix_to_list(M atrix) = List
• nn_train(N N ,Data,Opts) • array_matrix_to_list_matrix(AM atrix) = LM atrix
• nn_train_data_get(Data,I) = P air • chunks_of(List,K) = ListOf Lists
• nn_train_data_load(F ile) = Data • find(String,SubString,F rom,T o) (nondet)
• nn_train_data_save(Data,F ile) • find_first_of(T erm,P attern) = Index
• nn_train_data_size(Data) = Size • find_ignore_case(String,SubString,F rom,T o) (nondet)
• find_last_of(T erm,P attern) = Index
Module datetime • join(W ords) = String
• join(W ords,Separator) = String
• current_datetime() = DateT ime
• list_matrix_to_array_matrix(LM atrix) = AM atrix
• current_day() = W Day
• lstrip(List) = List
• current_date() = Date
• lstrip(List,Elms) = List
• current_time() = T ime
• matrix_multi(M atrixA,M atrixB) = M atrixC
• permutation(List,P erm) (nondet)
Module sys (imported by default) • permutations(List) = Lists
• power_set(List) = Lists
• abort
• cl • replace(T erm,Old,N ew) = N ewT erm
• cl(F ile) • replace_at(T erm,Index,N ew) = N ewT erm
• cl_facts(F acts) • rstrip(List) = List
• cl_facts(F acts,IndexInf o) • rstrip(List,Elms) = List
• cl_facts_table(F acts) • split(List) = W ords
• cl_facts_table(F acts,IndexInf o) • split(List,Separators) = W ords
• command(String) • strip(List) = List
• compile(F ile) • strip(List,Elms) = List
• debug • take(List,K) = List
• exit • transpose(M atrix) = T ransposed
152
Index
153
bv_to_int/1, 100 debug/0, 23, 121
bv_xor/3, 100 decreasing/1, 94
call_cleanup/2, 14, 41, 60 decreasing_strict/1, 94
call, 14, 41 del/2, 37
catch/3, 14, 41, 60 delete/2, 32, 129
cbc, 102 delete_all/2, 32
cd/1, 111 diagonal1/1, 127
ceiling/1, 115 diagonal2/1, 127
char/1, 28 different_terms/2, 43, 85
chdir/1, 111 diffn/1, 94
chr/1, 28, 90 digit/1, 28
chunks_of/2, 126 directory/1, 111, 112
circuit/1, 94, 98 disjoint/2, 129
cl/0, 21, 121 disjunctive_tasks/1, 94
cl/1, 21, 72, 120 dom-port, 16, 82, 83
cl_facts/1, 121 drop/2, 126
cl_facts/2, 121 dvar/1, 27
cl_facts_table/1, 121 dvar_or_int/1, 27
cl_facts_table/2, 121 element/3, 95
clear/1, 37 element0/3, 95
close/1, 81 end_of_file, 78
command/1, 124 env_exists/1, 113
compare_terms/2, 42 even/1, 119
compile/1, 21, 120 exactly/3, 95
compile_bp/1, 120 executable/1, 112
compound/1, 31 exists/1, 112
cond, 8, 41 exit/0, 20, 125
copy_term/1, 25 exp/1, 115
copy_term_shallow/1, 25 e, 114
cos/1, 116 fail, 5, 18, 47
cosh/1, 117 false, 5, 47
cot/1, 116 fd_degree/1, 88
coth/1, 118 fd_disjoint/2, 89
count/3, 94 fd_dom/1, 89
count/4, 94 fd_false/2, 89
count_all/2, 14, 41 fd_max/1, 89
cp/2, 111 fd_min/1, 89
csc/1, 116 fd_min_max/3, 89
csch/1, 118 fd_next/2, 89
cumulative/4, 94, 98 fd_prev/2, 89
current_date/0, 130 fd_set_false/2, 89
current_datetime/0, 130 fd_size/1, 89
current_day/0, 130 fd_true/2, 89
current_plan/0, 68 fd_vector_min_max/2, 88
current_resource/0, 68 file/1, 112
current_resource_plan_cost/3, 69 file_base_name/1, 112
current_time/0, 130 file_directory_name/1, 112
cvc3, 103 file_exists/1, 112
cwd/0, 111 final/1, 66
154
final/3, 66 heap_top/1, 38
find/4, 126 help/0, 1, 124
find_all/2, 14, 41 heuristic/1, 66
find_first_of/2, 126 import, 11, 72
find_ignore_case/4, 126 include directive, 20, 72
find_last_of/2, 126 increasing/1, 96
findall/2, 14, 15, 41 increasing_strict/1, 96
findall, 74 index, 6
first/1, 32, 36 indomain/1, 100
flatten/1, 32 indomain_down/1, 100
float/1, 30 initialize_table/0, 65
floor/1, 115 insert/2, 129
flush/1, 81 insert/3, 32
frand/0, 119 insert_all/3, 32
frand/2, 119 insert_ordered/2, 32
freeze/2, 14, 41, 85 insert_ordered_down/2, 32
functor/3, 35 ins-port, 16, 82, 83, 85
garbage_collect/0, 125 int/1, 30
garbage_collect/1, 125 int_to_bv/1, 100
gcd/2, 119 integer/1, 30, 83
get/2, 3, 16, 25, 31, 37 intersection/2, 129
get/3, 37 is/2, 40
get_attr/2, 3, 27 is_tabled_state/1, 69
get_attr/3, 27 join/1, 126
get_global_map/0, 17, 43 join/2, 126
get_global_map/1, 16, 43 keys/1, 37
get_heap_map/0, 16, 43 last/1, 32, 36
get_heap_map/1, 16, 43 len/1, 28, 32, 35, 36
get_table_map/0, 17, 43 length/1, 28, 31, 32, 36, 78
get_table_map/1, 17, 43 lex_le/2, 96
getenv/1, 113 lex_lt/2, 96
global_cardinality/2, 95 list/1, 32
glpk, 102 list_to_and/1, 43
ground/1, 43 listdir/1, 111
gurobi, 102 load/1, 12, 21, 72, 120
halt/0, 1, 20, 125 loaded_modules/0, 74, 124
has_key/2, 3, 37 log/1, 115
hash_code/1, 25 log/2, 116
hcp/2, 95 log10/1, 115
hcp/3, 96 log2/1, 116
hcp_grid/1, 96 lstrip/1, 127
hcp_grid/2, 96 lstrip/2, 127
hcp_grid/3, 96 map/1, 37
head/1, 32 map/2, 41
heap_is_empty/1, 38 map/3, 41
heap_pop/1, 38 map_to_list/1, 37
heap_push/2, 38 matrix_element/4, 97
heap_size/1, 38 matrix_element0/4, 97
heap_to_list/1, 38 matrix_multi/2, 127
155
max/1, 32, 36 nn_save/2, 108
max/2, 30, 49 nn_set_activation_.../2, 107
maxint_small/0, 30 nn_set_activation_.../3, 106, 107
maxof/2, 14, 42 nn_train/2, 108
maxof/3, 14, 42 nn_train/3, 108
maxof_inc/2, 14, 42 nn_train_data_get/2, 107
maxof_inc/3, 14, 42 nn_train_data_load/1, 107
max, 62 nn_train_data_save/2, 107
membchk/2, 32 nn_train_data_size/1, 107
member/2, 6, 32, 74 nodebug/0, 23, 121
min/1, 32, 36 nolog/0, 124
min/2, 30, 49 nonvar/1, 27
minint_small/0, 30 nospy/0, 121
minof/2, 14, 42 not/1, 14, 25, 47
minof/3, 14, 42 notrace/0, 23, 121
minof_inc/2, 14, 42 nth/3, 33, 36
minof_inc/3, 14, 42 number/1, 30
min, 62 number_chars/1, 30
mkdir/1, 111 number_codes/1, 30
mmax, 62 number_vars/1, 43
mmin, 62 number_vars/2, 43
modf/1, 115 nvalue/2, 97
module, 11, 72 odd/1, 119
name/1, 25, 35 once/1, 6, 14, 25, 44, 47, 83, 85, 124
neqs/1, 97 open/1, 60, 75, 76, 79, 81
new_array, 2, 36 open/2, 75, 76, 79, 81
new_bv/1, 100 ord/1, 28, 90
new_dvar/0, 89 ordset/1, 129
new_list/1, 33 parse_radix_string/2, 43
new_list/2, 33 parse_term/1, 43
new_map/1, 2, 37 parse_term/3, 43
new_map/2, 37 path/4, 97
new_max_heap/1, 38 path_d/4, 97
new_min_heap/1, 38 peek_byte/1, 78
new_nn/1, 105 peek_char/1, 78
new_ordset/1, 129 permutation/2, 128
new_set/1, 2, 38 permutations/1, 128
new_set/2, 38 picat_path/0, 124
new_sparse_nn/1, 106 picat, 1, 19
new_sparse_nn/2, 106 pi, 114
new_standard_nn/1, 105 plan/2, 67
new_struct/2, 2, 35 plan/3, 67
nextto/3, 128 plan/4, 67
nn_destroy/1, 106 plan_unbounded/2, 69
nn_destroy_all/0, 106 plan_unbounded/3, 69
nn_load/1, 108 plan_unbounded/4, 69
nn_print/1, 106 post_event/2, 16, 82
nn_run/2, 109 post_event_any/2, 82
nn_run/3, 109 post_event_bound/1, 82
156
post_event_dom/2, 82 read_real/1, 76
post_event_ins/1, 82 read_term/0, 77
pow/2, 115 read_term/1, 77
pow_mod/3, 115 readable/1, 112
prime/1, 119 readln/0, 77
primes/1, 119 readln/1, 77
print/1, 80 real/1, 30
print/2, 80 reduce/2, 42
printf, 80, 131 reduce/3, 42
println/1, 80 regular/6, 97
println/2, 80 remove_dups/1, 33
prod/1, 33, 36 rename/2, 111
put/2, 27, 37 repeat/0, 47
put/3, 3, 16, 37 replace/3, 126
put_attr/3, 3, 27 replace_at/3, 126
pwd/0, 111 reverse/1, 33, 36
rand_max/0, 118 rm/1, 111
random/0, 118 rmdir/1, 111
random/1, 118 round/1, 115
random/2, 118 rows/1, 127
random2/0, 118 rstrip/1, 127
read_byte/0, 77 rstrip/2, 127
read_byte/1, 77 scalar_product/3, 97
read_byte/2, 77, 78 scalar_product/4, 97
read_char/0, 76 scc/2, 97
read_char/1, 76 scc/3, 98
read_char/2, 76, 78 scc_d/2, 98
read_char_code/0, 76 scc_d/3, 98
read_char_code/1, 76 scc_grid/1, 98
read_char_code/2, 76 scc_grid/2, 98
read_file_bytes/0, 77 scip, 102
read_file_bytes/1, 77 sec/1, 116
read_file_chars/0, 77 sech/1, 117
read_file_chars/1, 77 second/1, 43
read_file_codes/0, 77 select/3, 33
read_file_codes/1, 77 separator/0, 110
read_file_lines/0, 77 sequence/2, 66
read_file_lines/1, 77 serialized/2, 98
read_file_terms/0, 77 sign/1, 114
read_file_terms/1, 77 sin/1, 116
read_int/0, 59, 76 sinh/1, 117
read_int/1, 76 size/1, 37, 112
read_line/0, 77 slice/2, 34, 36
read_line/1, 77, 78 slice/3, 34, 36
read_picat_token/0, 76 solve/1, 13, 87, 88, 100
read_picat_token/1, 76 solve/2, 13, 87, 88, 100
read_picat_token/2, 76 solve_all/1, 100
read_picat_token/3, 76 solve_all/2, 100
read_real/0, 76 solve_suspended/0, 100
157
solve_suspended/1, 100 to_lowercase/1, 34
sort/1, 33, 36 to_number/1, 31
sort/2, 33, 36 to_oct_string/1, 31
sort_down/1, 33, 36 to_radians/1, 116
sort_down_remove_dups/1, 34, 36, 37 to_radix_string/2, 31
sort_remove_dups/1, 33, 36 to_real/1, 31
sort_remove_dups/2, 33, 36 to_string/1, 27
split/1, 127 to_uppercase/1, 34
split/2, 127 trace/0, 23, 121
spy/1, 24, 121 transpose/1, 127
sqrt/1, 115 tree/2, 99
statistics/0, 122 tree/3, 99
statistics/2, 122, 123 true, 5, 47, 51, 56
statistics_all/0, 123 truncate/1, 30, 115
stderr, 81 union/2, 129
stdin, 81 values/1, 37
stdout, 81 var/1, 16, 27, 83, 85
string/1, 34 variant/2, 43
strip/1, 127 vars/1, 43
strip/2, 127 writable/1, 112
struct/1, 35 write/1, 8, 50, 79, 80
subcircuit/1, 98 write/2, 79, 80
subcircuit_grid/1, 99 write_byte/1, 79
subcircuit_grid/2, 99 write_byte/2, 79
subset/2, 129 write_char/1, 79
subsumes/2, 43 write_char/2, 79
subtract/2, 129 write_char_code/1, 79
sum/1, 34 write_char_code/2, 79
table_in/2, 89 writef, 79, 80, 131
table_notin/2, 89 writeln/1, 79
table, 10, 11, 61 writeln/2, 79
tail/1, 34 z3, 103
take/2, 127 zip, 34, 52
tan/1, 116 =../2, 35
tanh/1, 117 =/2, 39
throw/1, 6, 14, 48, 60 =:=/2, 39
time/1, 14, 124 ==/2, 39
time2/1, 124 =\=/2, 40
time_out/3, 15, 124 \+/1, 14, 47
to_array/1, 34
to_binary_string/1, 30 accumulator, 48, 49, 56, 57
to_codes/1, 25, 30 action rule, 15, 16, 82–85, 93
to_degrees/1, 116 activation function, 104
to_float/1, 30 anonymous variable, 27
to_fstring, 27, 30, 131 append mode, 75
to_hex_string/1, 30 arity, 1, 5, 25, 34, 36, 37, 44
to_int/1, 30 array, 1, 2, 25, 34, 36
to_integer/1, 30 array comprehension, 3, 55
to_list/1, 35 as-pattern, 46
158
assignment, 8, 50, 51, 56 heap map, 16
atom, 1, 12, 14, 25, 28, 34 higher-order call, 3, 12, 14, 41, 74
attributed variable, 1, 3, 16, 25, 27, 37, 39 Horn clause, 6, 44
159
symbolic link, 111, 112
table constraint, 89
table map, 17
tabling, 10, 11, 17, 61, 62, 65
tail recursion, 10, 45, 46, 48, 56
term, 1, 3, 6, 14, 16
trace mode, 23, 24, 121
160