A User’s Guide to Picat
Version 3.0
Neng-Fa Zhou and Jonathan Fruhman
Copyright ©picat-lang.org, 2013-2020.
Last updated October 2, 2020

Preface

Picat is a general-purpose language that incorporates features from logic programming, functional programming, constraint programming, and scripting languages. The letters in the name summarize Picat’s features:

The support of unification, non-determinism, tabling, and constraints makes Picat more suitable 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 impossible 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@picat-lang.org and join the news group picat-lang@googlegroups.com.

License

The copyright of Picat is owned by picat-lang.org. 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 (http://mozilla.org/MPL/2.0/). 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 released 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 Dymchenko, 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. Special thanks to Håkan Kjellerstrand, who has been programming in Picat and blogging about Picat since May 2013. The system wouldn’t have matured so quickly without Håkan’s hundreds of programs (http://hakank.org/). Thanks also go to Bo Yuan (Bobby) Zhou, who designed the picat-lang.org web page, Sanders Hernandez, who implemented the interface to the FANN neural network library, and Domingo Alvarez Duarte, who ported Picat to MinGW (https://github.com/mingodad/picat). 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 domain 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 provides interfaces to the SAT solver MapleLCMDiscChronoBT-DL-v3 (http://sat-race-2019.ciirc.cvut.cz/), Gurobi by Gurobi Optimization, Inc, CBC by John Forrest, GLPK by Andrew Makhorin, and Z3 by Microsoft.

Contents

1 Overview
 1.1 Data Types
 1.2 Defining Predicates
 1.3 Defining Functions
 1.4 Assignments and Loops
 1.5 Tabling
 1.6 Modules
 1.7 Constraints
 1.8 Exceptions
 1.9 Higher-Order Calls
 1.10 Action Rules
 1.11 Prebuilt Maps
 1.12 Programming Exercises
2 How to Use the Picat System
 2.1 How to Use the Picat Interpreter
  2.1.1 How to Enter and Quit the Picat Interpreter
  2.1.2 How to Use the Command-line Editor
  2.1.3 How to Compile and Load Programs
  2.1.4 How to Run Programs
  2.1.5 How to Run Programs Directly
  2.1.6 Creating Standalone Executables
 2.2 How to Use the Debugger
3 Data Types, Operators, and Built-ins
 3.1 Variables
 3.2 Atoms
 3.3 Numbers
 3.4 Compound Terms
  3.4.1 Lists
  3.4.2 Strings
  3.4.3 Structures
  3.4.4 Arrays
  3.4.5 Maps
  3.4.6 Sets
  3.4.7 Heaps
 3.5 Equality Testing, Unification, and Term Comparison
  3.5.1 Numerical Equality
  3.5.2 Ordering of Terms
 3.6 Expressions
 3.7 Higher-order Predicates and Functions
 3.8 Other Built-ins in the basic Module
4 Predicates and Functions
 4.1 Predicates
 4.2 Functions
 4.3 Patterns and Pattern-Matching
 4.4 Goals
 4.5 Tail Recursion
5 Assignments and Loops
 5.1 Assignments
  5.1.1 If-Else
 5.2 Types of Loops
  5.2.1 Foreach Loops
  5.2.2 Foreach Loops with Multiple Iterators
  5.2.3 While Loops
  5.2.4 Do-while Loops
 5.3 List and Array Comprehensions
 5.4 Compilation of Loops
  5.4.1 List Comprehensions
6 Exceptions
 6.1 Built-in Exceptions
 6.2 Throwing Exceptions
 6.3 Defining Exception Handlers
7 Tabling
 7.1 Table Declarations
 7.2 The Tabling Mechanism
8 The planner Module
 8.1 Depth-Bounded Search
 8.2 Depth-Unbounded Search
 8.3 Examples
9 Modules
 9.1 Module and Import Declarations
 9.2 Binding Calls to Definitions
 9.3 Binding Higher-Order Calls
 9.4 Library Modules
10 I/O
 10.1 Opening a File
 10.2 Reading from a File
  10.2.1 End of File
 10.3 Writing to a File
 10.4 Flushing and Closing a File
 10.5 Standard File Descriptors
11 Event-Driven Actors and Action Rules
 11.1 Channels, Ports, and Events
 11.2 Action Rules
 11.3 Lazy Evaluation
 11.4 Constraint Propagators
12 Constraints
 12.1 Domain Variables
 12.2 Table constraints
 12.3 Arithmetic Constraints
 12.4 Boolean Constraints
 12.5 Global Constraints
 12.6 Solver Invocation
  12.6.1 Common Solving Options
  12.6.2 Solving Options for cp
  12.6.3 Solving Options for sat
  12.6.4 Solving Options for mip
  12.6.5 Solving Options for smt
13 The nn (Neural Networks) Module
 13.1 Create, Print, and Destroy Neural Networks
 13.2 Activation Functions
 13.3 Training Data
 13.4 Train Neural Networks
 13.5 Save and Load Neural Networks
 13.6 Run Neural Networks
14 The os Module
 14.1 The Path Parameter
 14.2 Directories
  14.2.1 The Current Working Directory
 14.3 Modifying Files and Directories
  14.3.1 Creation
  14.3.2 Deletion
 14.4 Obtaining Information about Files
 14.5 Environment Variables
A The math Module
 A.1 Constants
 A.2 Functions
  A.2.1 Sign and Absolute Value
  A.2.2 Rounding and Truncation
  A.2.3 Exponents, Roots, and Logarithms
  A.2.4 Converting Between Degrees and Radians
  A.2.5 Trigonometric Functions
  A.2.6 Hyperbolic Functions
  A.2.7 Random Numbers
  A.2.8 Other Built-ins
B The sys Module
 B.1 Compiling and Loading Programs
 B.2 Tracing Execution
  B.2.1 Debugging Commands
 B.3 Information about the Picat System
  B.3.1 Statistics
  B.3.2 Time
  B.3.3 Other System Information
 B.4 Garbage Collection
 B.5 Quitting the Picat System
C The util Module
 C.1 Utilities on Terms
 C.2 Utilities on Strings and Lists
 C.3 Utilities on Matrices
 C.4 Utilities on Lists and Sets
D The ordset Module
E The datetime Module
F Formats
 F.1 Formatted Printing
G External Language Interface with C
 G.1 Term Representation
 G.2 Fetching Arguments of Picat Calls
 G.3 Testing Picat Terms
 G.4 Converting Picat Terms into C
 G.5 Manipulating and Writing Picat Terms
 G.6 Building Picat Terms
 G.7 Registering C-defined Predicates
H Appendix: Tokens
I Appendix: Grammar
J Appendix: Operators
K Appendix: The Library Modules
Index

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.

OSPrompt 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:

OSPrompt picat File Arg1 Arg2 Argn

where File (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. 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.

1.1 Data Types

Picat is a dynamically-typed language, in which type checking occurs at runtime. A variable in Picat is a value holder. A variable name is an identifier that begins with a capital letter or the underscore. An attributed variable is a variable that has a map of attribute-value pairs attached to it. A variable is free until it is bound to a value. A value in Picat can be primitive or compound.

A primitive value can be an integer, a real number, or an atom. A character can be represented as a single-character atom. An atom name is an identifier that begins with a lower-case letter or a single-quoted sequence of characters.

A compound value can be a list in the form [t1,,tn] or a structure in the form $s(t1,,tn) where s stands for a structure name, n is called the arity of the structure, and each ti (1 i n) is a term which is a variable or a value. The preceding dollar symbol is used to distinguish a structure from a function call. Strings, arrays, maps, sets, and heaps are special compound values. A string is a list of single-character atoms. An array takes the form {t1,,tn}, which is a special 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(Name,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 expression 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> N1 = 12, N2 = 0xf3, N3 = 1.0e8  % numbers  
 
Picat> A1 = x1, A2 = ’_AB’, A3 = ’’    % atoms  
 
Picat> L = [a,b,c,d]                   % a list  
 
Picat> write("hello"++"picat")         % strings  
[h,e,l,l,o,p,i,c,a,t]  
 
Picat> print("hello"++"picat")  
hellopicat  
 
Picat> writef("%s","hello"++"picat")   % formatted write  
hellopicat  
 
Picat> writef("%-5d %5.2f",2,2.0)      % formatted write  
2      2.00  
 
Picat> S = $point(1.0,2.0)             % a structure  
 
Picat> S = new_struct(point,3)         % create a structure  
S = point(_3b0,_3b4,_3b8)  
 
Picat> A = {a,b,c,d}                   % an array  
 
Picat> A = new_array(3)                % create an array  
A = {_3b0,_3b4,_3b8}  
 
Picat> M = new_map([one=1,two=2])      % create a map  
M =  (map)[two = 2,one = 1]  
 
Picat> M = new_set([one,two,three])    % create a map set  
M = (map)[two,one,three]  
 
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]

where T is an expression, each Ei is an iterating pattern, each Di is an expression that gives a compound value, and the optional conditions Cond1,,Condn are callable terms. This list comprehension means that for every tuple of values E1 D1, , En Dn, if the conditions are true, then the value of T is added into the list.

An array comprehension takes the following form:

{T : E1 in D1, Cond1, , En in Dn, Condn}

It is the same as:

to_array([T : E1 in D1, Cond1, , En in Dn, Condn])

The predicate put(Map,Key,V al) attaches the key-value pair Key=V al to the map Map, where Key is a non-variable term, and V al is any term. The function get(Map,Key) returns V al of the key-value pair Key=V al attached to Map. The predicate has_key(Map,Key) returns true iff Map 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)  
yes  
 
Picat> X=5, var(X)  
no  
 
Picat> 5 != 2+2  
yes  
 
Picat> X = to_binary_string(5)  
X = [’1’,’0’,’1’]  
 
Picat> L = [a,b,c,d], X = L[2]  
X = b  
 
Picat> L = [(A,I) : A in [a,b], I in 1..2].  
L = [(a,1),(a,2),(b,1),(b,2)]  
 
Picat> put_attr(X,one,1), One = get_attr(X,one)  % attributed var  
One = 1  
 
Picat> S = new_struct(point,3), Name = name(S), Len = length(S)  
S = point(_3b0,_3b4,_3b8)  
Name = point  
Len = 3  
 
Picat> S = new_array(2,3), S[1,1] = 11, D2 = length(S[2])  
S = {{11,_93a0,_93a4},{_938c,_9390,_9394}}  
D2 = 3  
 
Picat> M = new_map(), put(M,one,1), One = get(M,one)  
One = 1  
 
Picat> M = new_set(), put(M,one), has_key(M,one).

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 qualifier 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.put(one,1), One = X.get(one)  
One = 1  
 
Picat> X = math.pi  
X=3.14159  
 
Picat> S = new_struct(point,3), Name = S.name, Len = S.length  
S = point(_3b0,_3b4,_3b8)  
Name = point  
Len = 3  
 
Picat> S = new_array(2,3), S[1,1] = 11, D2 = S[2].length  
S = {{11,_93a0,_93a4},{_938c,_9390,_9394}}  
D2 = 3  
 
Picat> M = new_map(), M.put(one,1), One = M.one.  
One = 1

1.2 Defining Predicates

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 statements, including conjunction (A, B), disjunction (A;B), negation (not A), if-then-else, foreach loops, and while loops.

A predicate is defined with pattern-matching rules. Picat has two types of pattern-matching rules: the non-backtrackable rule Head,Cond => Body, and the backtrackable rule Head,Cond ?=> Body. 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-then-else as follows:

fib(N,F) =>  
    if (N=0; N=1) then  
        F=1  
    elseif N>1 then  
        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 then Goal1 else Goal2 end.1 The then part 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:

membchk(X,[X|_]) => true.  
membchk(X,[_|L]) => membchk(X,L).

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.2 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:

p(V 1 , , V n ) ?=> V 1 = $t1, , V n = $tn, Body.

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

index (M11 ,,M1n) (Mm1,,Mmn)

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.

1.3 Defining Functions

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).  
 
qsort([]) = L => L=[].  
qsort([H|T]) = L => L = qsort([E : E in T, E=<H]) ++ [H] ++  
                        qsort([E : E in T, E>H]).

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]).

Function facts are automatically indexed on all of the input arguments, and hence no index declaration 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 math.pi.

The fib function can also be defined as follows:

fib(N) = cond((N=0;N=1), 1, fib(N-1)+fib(N-2)).

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.

1.4 Assignments and Loops

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:

    test => X=0, X1=X+1, X2=X1+2, write(X2).

Picat supports foreach and while statements for programming repetitions. A foreach statement takes the form

foreach (E1 in D1, Cond1, , En in Dn, Condn)
Goal
end

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. 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

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 .. A.length)  
        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.  
 
sum_list(L) = Sum =>    % returns sum(L)  
    S=0,  
    foreach (X in L)  
        S:=S+X  
    end,  
    Sum=S.  
 
read_list = List =>  
    L=[],  
    E=read_int(),  
    while (E != 0)  
        L := [E|L],  
        E := read_int()  
    end,  
    List=L.

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:

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 = [].  
 
p(0,Lin,Lout) => Lout = Lin.  
p(E,Lin,Lout) =>  
    Lin = [E|Lin1],  
    NE = read_int(),  
    p(NE,Lin1,Lout).

A list comprehension is first compiled into a foreach loop, and then the loop is compiled into a call to a generated tail-recursive predicate. For example, the list comprehension

List = [(A,X) : A in [a,b], X in 1..2]

is compiled into the following loop:

List = L,  
foreach(A in [a,b], X in 1..2)  
    L = [(A,X)|T],  
    L := T  
end,  
L = [].

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.

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.3

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 declaration 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 declaration and optional import declarations. A module declaration has the form:

module Name.

where Name 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:

import Name1, , Namen.

where each Namei 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.  
 
my_sum(L) = Sum =>  
   sum_aux(L,0,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.4 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.

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 optimization 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) =>  
    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, and out_of_range. The exception interrupt(keyboard) is raised when ctrl-c is typed during a program’s execution. The built-in predicate throw Exception throws Exception.

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,Handler) 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 Handler will be executed to handle the exception.

The call call_cleanup(Goal,Cleanup) is equivalent to call(Call), except that Cleanup is called when Goal succeeds determinately (i.e., with no remaining choice point), when Goal fails, or when Goal raises an exception.

1.9 Higher-Order Calls

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 similar to call, except that apply returns a value. The function findall(Template,S) returns a list of all possible solutions of call(S) in the form of Template. Other higher-order predicates 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, time_out/3 and time2/1. 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).

A call that is passed to apply is assumed to invoke a definition in a pre-imported built-in module, the enclosing module in which apply occurs, an imported module of the enclosing module, or the global module. Due to the overhead of runtime search, the use of higher-order calls is discouraged. Whenever possible, recursion, loops, or list and array comprehensions should be used instead.

1.10 Action Rules

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:

Head, Cond, {Event}=> Body

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 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 instantiated. 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).  
 
foo(Flag) => Flag=1.

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.

1.11 Prebuilt Maps

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. 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 readability 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)) then  
       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)) then  
       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)) then  
       writef("table map t1 has key%n")  
    else  
       writef("table map t1 has no key%n")  
    end.

For the call go, the output is:

heap map h1 has no key  
global map g1 has key  
table map t1 has key

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.

1.12 Programming Exercises

Project Euler (projecteuler.net) is an excellent platform for practicing programming and problem solving skills. You can find Picat solutions to some of the problems at picat-lang.org/projects.html. Select five problems from the Project Euler problem set for which no solutions have been posted, and write a program in Picat for each of them.

Chapter 2
How to Use the Picat System

2.1 How to Use the Picat Interpreter

The Picat system is written in both C and Picat. The Picat interpreter is provided as a single standalone executable file, named picat.exe 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 terminal. 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.

2.1.1 How to Enter and Quit the Picat Interpreter

The Picat interpreter is started with the OS command picat.

OSPrompt picat

where OSPrompt 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:

picat Opts PicatMainFileName A1 A2 An

where PicatMainFileName can have the extension .pi and can contain a path of directories, and Opts is a sequence of options of the following:

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.

2.1.2 How to Use the Command-line Editor

The Picat interpreter uses the getline program written by Chris Thewalt. The getline program memorizes up to 100 of the most recent queries that the users have typed, and allows users to recall past queries and edit the current query by using Emacs editing commands. The following gives the editing commands:

ctrl-fMove the cursor one position forward.
ctrl-bMove the cursor one position backward.
ctrl-aMove the cursor to the beginning of the line.
ctrl-eMove the cursor to the end of the line.
ctrl-d Delete the character under the cursor.
ctrl-hDelete the character to the left of the cursor.
ctrl-kDelete the characters to the right of the cursor.
ctrl-uDelete the whole line.
ctrl-pLoad the previous query in the buffer.
ctrl-nLoad the next query in the buffer.

Note that the command ctrl-d terminates the interpreter if the line is empty and the cursor is located in the beginning of the line.

2.1.3 How to Compile and Load Programs

A Picat program is stored in one or more text files with the extension name pi. A file name is a string of characters. Picat treats both ’/’ and ’' ’ as file name separators. Nevertheless, since ’' ’ is used as the escape character in quoted strings, two consecutive backslashes must be used, as in "c:' ' work' ' myfile.pi", if ’' ’ is used as the separator.

For the sake of demonstration we assume the existence of a file named welcome.pi in the current working directory that stores the following program:

    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.

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:: welcome.pi  
welcome.pi 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.

2.1.5 How to Run Programs Directly

Programs that define the main/0 predicate or the main/1 predicate can be run directly as a OS command. For example,

$ 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 (picat.exe for Windows), and the environment variable PICATPATH has been set to contain the directory of the welcome.pi file or the file is in the current working directory.

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 welcome.exe for Linux:

#!/bin/bash  
picat welcome.pi  
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:

$ welcome.exe  
 Welcome to PICAT’s world!  
 Finished!

2.2 How to Use the Debugger

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 myprog.pi. The following shows a trace for a query:

 Picat> debug  
 
 {Trace mode}  
 Picat> cl(myprog)  
 
 {Trace mode}  
 Picat> p(X),q(Y)  
    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 $Name/N

to set the functor Name/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 Name 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.

Chapter 3
Data Types, Operators, and Built-ins

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 Functions. 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 A.Attr, where Attr does not have the form f(), is the same as the function call get(A,Attr). For example, the expression S.name returns the name, and the expression S.arity 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)).


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)



The following functions are provided for all terms:

Other built-ins on terms are given in Sections 3.5 and 3.8.

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:

An attributed variable is a variable that has a map of attribute-value pairs attached to it. The following built-ins are provided for attributed variables:

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 characters. 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:

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.


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


From .. Step .. To A range (list) of numbers with a step


From .. To A range (list) of numbers with step 1


X =:= Y pretty much (numerically) equal



In addition to the numeric operators, the basic module also provides the following built-ins for numbers:

The math module provides more numeric functions. See Appendix A.

3.4 Compound Terms

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(Term) is true if Term 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 L.length, 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).