Canonicalizing High-Level Constructs in Picat
Neng-Fa Zhou1 and Jonathan Fruhman2
1

CUNY Brooklyn College & Graduate Center2
Independent Researcher

Abstract. Picat is a logic-based multi-paradigm dynamic language that
integrates logic programming, functional programming, constraint programming, and scripting. The Picat language is underpinned by thecore logic programming concepts, including logic variables, unification,and nondeterminism. Picat takes many constructs from other languages,
among which functions, list and array comprehensions, loops, and assignments are convenient for scripting and modeling. This paper gives
an overview of the language features of Picat, and shows how different
language constructs are compiled into a canonical form.

1

Introduction

Picat is a simple, and yet powerful, logic-based multi-paradigm dynamic language. Picat was designed with the goal of creating a logic-based general-purpose
programming language that overcomes the weaknesses of Prolog, is as powerfulas Python and Ruby for scripting, and is on a par with OPL [6] and MiniZinc[10] for modeling combinatorial problems.
Like Prolog, Picat is based on the core logic programming concepts, including logic variables, unification, and nondeterminism realized through depth-firstbacktracking search. Picat departs from Prolog in many aspects. Picat uses
pattern-matching rather than unification in the selection of rules. Unification
might be a natural choice in Horn clause resolution for theorem proving [8],but its power is rarely needed for general programming tasks. In Picat, patternmatching rules are fully indexed, while most Prolog implementations only index
clauses on one argument; therefore, Picat can be more scalable than Prolog. Unification can be considered as an equation over terms [1], and just like constraints
over finite domains, Picat supports unification as an explicit call.
Non-determinism, a powerful feature of logic programming, makes concise solutions possible for many problems, including the simulation of non-deterministic
automata, the parsing of ambiguous grammars, and search problems. In Prolog,
Horn clauses are backtrackable by default. As it is generally undecidable to detect determinism, programmers tend to excessively use the cut operator to prune
unnecessary clauses. Picat supports explicit non-determinism, which renders thecut operator unnecessary. In Picat, rules are deterministic, unless they are explicitly annotated as backtrackable.
Picat supports functions, like many other logic-based languages, such as
Curry [5] and Ciao [7]. In Prolog, a predicate defines a relation, and may succeed

multiple times. It is common for queries to fail in Prolog without the system providing any clue about the source of the failure. Functions should be used insteadof relations, unless multiple answers are required. It is more convenient to use
functions instead of predicates, because (1) functions are guaranteed to succeed
with a return value; (2) function calls can be nested; and (3) the directionalityof functions often enhances the readability.
Picat provides arrays and loops, which are probably the features that are
most unlike those of Prolog. In Prolog, in order to describe repetitions, programmers mainly rely on recursion, and occasionally rely on failure-driven loops
and higher-order extensions [15]. The lack of powerful loop constructs has arguably made Prolog less acceptable to programmers than other languages. The
extension of Prolog to support constraints has further revealed the weakness of
Prolog as a modeling language. Early attempts to introduce arrays and loops
into Prolog for modeling failed to produce a satisfactory language: most noticeably, array accesses are only treated as functions in certain contexts, and loops
require the declaration of global variables in ECLiPSe [11] and local variables in
B-Prolog [17].
Picat allows list comprehensions to be included as special functions in expressions in order to declaratively construct lists. Picat also supports the assignment
operator :=, whose original motive was to facilitate the compilation of list comprehensions. A list comprehension is easily translated into a foreach loop in
which an assignment is utilized to accumulate the constructed list. The decision to make the assignment operator available to programmers is controversial
but pragmatic. The assignment operator in Picat has earned fondness amongprogrammers for its simple semantics and convenience.
All of the language constructs, including functions, loops, comprehensions,and assignments, are provided as syntactic sugar in Picat. They are compiled
away at compile time. This paper gives an overview of the language constructs of
Picat, and shows how they are compiled into canonical-form pattern-matchingrules.

2

The Picat Language

The name “Picat” is an acronym, and the letters in the name summarize Picat’s
features: ‘P’ for pattern-matching, ‘I’ for intuitive programming, ‘C’ for constraints, ‘A’ for action rules, and ‘T’ for tabling. This section gives an overview
of the language constructs of Picat. Some of Picat’s features, such as action rules,
tabling, and the tabling-based planner [18], are orthogonal to the language constructs, and will not be covered in this article. More details of the Picat language
can be found in [20].
2.1

Data Types

Picat is a logic-based multi-paradigm programming language for general-purpose
applications. Picat’s core is underpinned by logic programming concepts, as seen2

Fig. 1. Picat’s data types

in Prolog, including logic variables, unification, and backtracking. Logic variables,
like variables in mathematics, are value holders. A logic variable can be boundto any term, including another logic variable. Figure 1 gives the types of terms
in Picat. Picat is a dynamically-typed language, which means that type checking
occurs at runtime.
A variable name is an identifier that begins with a capital letter or the underscore; for example, X1 and abc are variable names. The underscore itself isused for anonymous variables, and each occurrence of the underscore indicatesa different variable.
An atomic value can be an atom or a number. An atom is a constant symbol.
An atom name can be either unquoted or quoted. An unquoted name is an
identifier that begins with a lower-case letter, followed by an optional string ofletters, digits, and underscores. A quoted atom is a single-quoted sequence ofarbitrary characters. For example, x1, x 1, ’ abc’, and ’a+b’ are atom names.
A number can be an integer or a real number. Picat supports big integers.
A compound value can be a list or a structure; for example, [a,b,c] is a list,
and f(a,b,c) is a structure.3 Lists are singly-linked lists. A string is a list of
characters; for example, "a+b" is the same as [a,’+’,b]. An array is a special
structure; for example, {a,b,c} is an array. A map is a special structure that
contains a set of key-value pairs, and a set is a special map that only contains
keys; both are hash tables.
Each type provides a set of built-in functions and predicates. Each of the type
names, except term and set, is a type-checking predicate. For example, list(L)tests if L is a list. Let L be a compound term. The index notation L[I] is a
special function that returns the Ith component of list L, with L[1] referringto the first element of L. An index notation can take multiple subscripts. The
cons operator [H|T ] builds a new list by adding H to the front of T . The
concatenation operator L1 ++ L2 returns the concatenated list of L1 and L2 .
3

A structure requires a preceding dollar symbol, as in $f(a,b,c), to distinguish thestructure from a function call, unless the structure is special, or it occurs in a special
context.

3

The equality test T1 == T2 is true if term T1 and term T2 are identical. The
inequality test T1 !== T2 is the same as not T1 == T2 . Note that two terms canbe identical even if they are different terms stored in different memory locations.
Also note that two terms of different types can be tested for equality, but they
are never identical. The unification T1 = T2 is true if term T1 and term T2 arealready identical, or if they can be made identical by instantiating the variablesin the terms. The built-in T1 != T2 is the same as not T1 = T2 . Note thatamong the four comparison operators ==, !==, =, and !=, only = can change thestate of the variables in the compared terms.
2.2

Predicates and Functions

In Picat, predicates and functions are defined with pattern-matching rules. Picat
has two types of rules: the non-backtrackable rule
Head, Cond => Body.
and the backtrackable rule
Head, Cond ?=> Body.
In a predicate definition, the Head takes the form p(t1 , . . . , tn ), where p is apredicate name, and n is the arity. The condition Cond, which is an optionalgoal, specifies a condition under which the rule is applicable. For a call C, if
C matches Head (i.e., there exists a substitution θ such that Headθ = C) andCond succeeds, then the rule is said to be applicable to C. When applying arule 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 thenext applicable rule will be tried on C. The backtrackable rule is semanticallyequivalent to:
Head ?=> Cond, Body.
However, in-line tests that are written to the left of ?=> will be used by thecompiler to index the rule.
The following defines the predicate member:member(X, [Y|_]) ?=> X = Y.
member(X, [_|T]) => member(X, T).

Like the Prolog built-in member(X,L), this predicate can be utilized to check if
X is a member of the list L, and it can also be utilized to retrieve an element of L
through X by backtracking if X is a variable. Unlike Prolog’s member(X,L), which
can succeed an infinite number of times if L is a variable, the Picat definition
can never succeed more times than the number of elements in L, since patternmatching never changes call arguments.
4

A function is a special kind of a predicate that is defined by non-backtrackable
rules. In a function definition, the Head takes the form f (t1 , . . . , tn ) = T erm,
where f is a function name and T erm is a result to be returned. If Cond and
Body are both true, then they can be omitted together with the => arrow.
The following gives two functions for reversing a list:
naive_reverse([]) = [].
naive_reverse([H|T]) = naive_reverse(T) ++ [H].
reverse(L) = reverse_aux(L, []).
reverse_aux([], Acc) = Acc.
reverse_aux([H|T], Acc) = reverse_aux(T, [H|Acc]).

For a list, if it is empty, then naive reverse returns the empty list; otherwise,
naive reverse attaches the head H to the end of the reversed list of the tail T.
The call naive reverse(L) takes O(n2 ) time to reverse list L of length n. The
function reverse calls reverse aux, which scans the list while accumulating thereversed list in the second argument. The call reverse(L) takes linear time toreverse list L.
Picat, like functional programming languages, discourages the use of side effects in describing computations. All of the built-in functions in Picat’s basic
module are side-effect-free mathematical functions. Pure, side-effect-free functions are not dependent on the context in which they are applied. This purity
can greatly enhance the readability and maintainability of programs.
Picat’s dot notation makes calling a function look like calling a method on
an object, as in X.to string().reverse(). This uniform function call syntax 4
is convenient for chaining function calls in a readable way.
2.3

Loops and Comprehensions

Picat provides loops for describing repetitions and comprehensions for constructing lists and arrays. A foreach loop has the following general form:
foreach (E1 in D1 , Cond1 , . . ., En in Dn , Condn )Goalend
The expression Ei in Di is called an iterator, where Ei is an iterating pattern,
and Di is an expression that gives a compound value. Each Condi is an optional
condition on iterators E1 through Ei . A loop statement forms a name scope: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.
A list comprehension has the following general form:[Exp : E1 in D1 , Cond1 , . . ., En in Dn , Condn ]4

http://dlang.org/spec/function.html

5where Exp is an expression, and the iterators and conditions have the sameformat as those used in the foreach loop. A list comprehension is a special
functional notation for creating lists. It includes Exp as an element in the list foreach possible combination of values in the iterators that satisfies the conditions.
Like a loop, a list comprehension also forms a name scope.
An array comprehension has the following general form:{Exp : E1 in D1 , Cond1 , . . ., En in Dn , Condn }An array comprehension first creates a list, and then calls the function to array
to convert the list to an array.
The following gives an example that uses loops and comprehensions:matrix_multi(A, B) = C =>C = new_array(A.length, B[1].length),foreach (I in 1..A.length, J in 1..B[1].length)
C[I,J] = sum([A[I,K]*B[K,J] : K in 1..A[1].length])end.

The function matrix multi(A,B) takes two matrices, A and B, that are represented as two-dimensional arrays, and returns the product A×B. All three of thevariables A, B, and C, are non-local to the loop, because they occur before theloop. Note that, for an aggregate function, such as sum or len, that takes a list
comprehension as the argument, the compiler generates a special function thatcomputes the aggregate without actually building a list.
Loops are very convenient for scripting. The following gives an example program which recursively copies all of the files in a directory and its subdirectories
to the current directory:
import os.
main =>
WD = pwd(),
flatten_dir(WD, WD).
flatten_dir(WD, Dir) =>Fs = listdir(Dir),
foreach (F in Fs, F !== ".", F !== "..")
FullName = full_path(Dir, F),
if directory(FullName) thenflatten_dir(WD, FullName)else
cp(FullName, full_path(WD, F))
end
end.
full_path(Dir, Name) =Dir ++ [separator()] ++ Name.

This program imports the os module, from which the built-ins pwd, listdir,
directory, cp, and separator are used. The function listdir(Dir) returns
6

a list Fs of files and directories in the directory Dir. For each item F in Fs,
if F is neither "." nor "..", then the program calls full path to construct
the full name FullName of F. If FullName is a directory, then the program
recursively calls flatten dir on the directory; otherwise, it copies the file tothe WD directory.
2.4

Assignments and While Loops

Picat variables are single-assignment, meaning that once a variable is bound toa value, the variable cannot be bound again, unless the value is a variable or
the value contains variables. 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 a variable, the assignment does not actually assign thevalue of RHS to LHS. Instead, it creates a new variable for LHS to hold thevalue of RHS. After the assignment, whenever LHS is accessed in the body, thenew variable is accessed. When LHS is an access in the form X[I], the componentof X indexed I is updated. This update is undone if execution backtracks overthis assignment.
An assignment in the form X[I] := RHS has global side effects, since thecompound term that is referenced by X is destructively updated, like an assignment in an imperative language. An assignment in the form X := RHS, where
X is a variable, only has a side effect within the body of the rule in which theassignment occurs. Recall that the compiler introduces a new variable for X andreplaces the remaining occurrences of X by the new variable. Variable assignments do not have cross-predicate or cross-function side effects.
An assignment makes it possible to use a variable to hold values at different
stages during computation without inventing new variable names. With assignments, Picat is able to provide while loops that repeat under a condition. A
while loop has the form:
while (Cond)
Goal
end
As long as Cond succeeds, the loop will repeatedly execute Goal. A do-while
loop has the form:
doGoal
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. In order for a while loop to make sense, Goal
7

must contain assignments that change some variables in Cond, unless the loop
is meant to be an infinite loop.5
2.5

Constraint Modeling

Picat provides three solver modules, cp, sat, and mip, for modeling and solving constraint satisfaction and optimization problems (CSPs). As a constraint
programming language, Picat resembles CLP(FD) [3]: the operators :: andnotin are used for domain constraints, the operators #=, #!=, #>, #>=, #<,#<=, and #=< are used for arithmetic constraints, and the operators #/\ (and),#\/ (or), #^ (xor), #~ (not), #=> (if), and #<=> (iff) are used for Boolean constraints. Picat supports several global constraints, such as all different/1,
element/3, and cumulative/4. In addition to intensional constraints, Picat also
provides two predicates for expressing extensional constraints: table in/2 andtable notin/2.
The following gives a solution for the Fashion Police problem, which was usedin GCJ Round 1C 2016.6 You have brought along J different jackets (numbered
1, . . . , J), P different pairs of pants (numbered 1, . . . , P ), and S different shirts(1, . . . , S), J ≤ P ≤ S. Every day, you will pick one jacket, one pair of pants, andone shirt to wear as an outfit. You will be put into jail if you have worn the exact
same outfit twice or if you have worn the same two-garment combination morethan K times in total for some input K. Determine the maximum number of days
that you will be able to avoid being taken to jail. The problem entails finding amaximum subset of outfits that satisfies the cardinality limit. For example, for
J = 1, P = 1, S = 3, and K = 2, the answer is 2, because (1,1,1) and (1,1,2)
are possible outfits, while adding the third outfit (1,1,3) to the list will violate
the cardinality limit.
import util, sat.
main =>
T = read_line().to_int(),
foreach (TC in 1..T)[J,P,S,K] = [to_int(Token) : Token in read_line().split()],not not do_case(TC,J,P,S,K)
end.
do_case(TC,J,P,S,K) =>L = {{Ij,Ip,Is} : Ij in 1..J, Ip in 1..P, Is in 1..S},N = J * P * S,
Bs = new_array(N),Bs :: 0..1,sum(Bs) #=< J * P * K,
% pigeonhole principle
foreach (R1 in 1..N)
L[R1] = {Ij,Ip,Is},5
6

It is possible to write an infinite loop as while (true) Goal end.
https://code.google.com/codejam/contest/4314486/dashboard#s=p2&a=2

8

if S > K thenBs[R1] #=> sum([Bs[R2] : R2 in 1..N, L[R2] = {Ij,Ip,_}]) #=< K
end,
if P > K thenBs[R1] #=> sum([Bs[R2] : R2 in 1..N, L[R2] = {Ij,_,Is}]) #=< K
end,
if J > K thenBs[R1] #=> sum([Bs[R2] : R2 in 1..N, L[R2] = {_,Ip,Is}]) #=< K
end
end,
solve([$max(sum(Bs))],Bs),
printf("Case #%w: %w\n", TC,sum(Bs)),
foreach (R in 1..N, Bs[R] == 1, L[R] = {Ij,Ip,Is})
printf("%w %w %w\n", Ij,Ip,Is)
end.

The main predicate first reads in an integer T, which is the number of test
cases. For each test case TC in 1..T, the body of the loop reads in J, P, S, andK in one line. The call do case(TC,J,P,S,K) solves the case.7
The do case predicate creates an array L of all possible outfits, computes
the number of possible outfits N, and creates an array Bs of N Boolean variables.
Each outfit is associated with one Boolean variable, which indicates whether
the outfit is in the subset. The constraint sum(Bs) #=< J * P * K encodes thepigeonhole principle.8
The foreach loop ensures that no pair of garments occurs in outfits morethan K times in the subset. For an outfit number R1, let {Ij,Ip,Is} be theoutfit. The constraintBs[R1] #=> sum([Bs[R2] : R2 in 1..N, L[R2] = {Ij,Ip,_}]) #=< K

ensures that, if the outfit {Ij,Ip,Is} is in the subset (Bs[R1] = 1), then thenumber of the jacket-pants pair {Ij,Ip} does not occur in the outfits more than
K times in the subset. This constraint is only generated if S > K, because if S
≤ K, it is impossible to have more than K pairs of {Ij,Ip}. The foreach loop
also generates cardinality constraints to ensure that the number of jacket-shirt
pairs and the number of pants-shirt pairs do not exceed the limit.
The statement solve([$max(sum(Bs))],Bs) calls the SAT solver to solve
the constraints such that the objective sum(Bs) is maximized.
GCJ problems normally require some amount of insight to solve, even forsmall datasets. This program is based on a straightforward model. Nevertheless, it solves the large dataset in 3 minutes, which is within the time limit of 8
minutes. This example demonstrates the use of Picat’s language constructs, including arrays, loops, and list comprehensions, in modeling constraint problems.
7

The double negation not not is used here to discard the generated constraints after
the case is done.
8Since J ≤ P ≤ S, min(J×P×K, P×S×K, J×S×K) equals J×P×K.

9

3

Canonicalizing the Language Constructs

The Picat implementation adopts the virtual machine TOAM [17], which is aredesign of the Warren Abstract Machine [16] for fast software emulation. TOAM
provides instructions for encoding pattern-matching rules. An extended TOAM,
which supports tabling and constraint propagation, is described in [17]. The
Picat implementation reuses codes from the B-Prolog system, except the parser,
the preprocessor, and many library built-ins. An early implementation of the
SAT compiler, which translates high-level constraints into CNF, is given in [19].
Picat translates programs into a canonical form, which is further compiled
into TOAM. This section describes the canonical form and the translation of Picat’s different language constructs into the form. The compilation of the canonical form into TOAM is detailed in [17].
3.1Canonical-form Rules

A canonical-form rule takes one of the following forms:
Head, Cond => Body.
Head, Cond ?=> Body.
A canonical-form rule is different from the source-language rule in that Condand Body do not include functions, comprehensions, loops, or assignments; allof these constructs are compiled away by Picat’s preprocessor.
3.2

Transformation of Functions

Picat replaces a function call f (t1 , . . . , tn ) by a new variable V , and inserts a new
predicate call p(t1 , . . . , tn , V ) before the goal in which the function call occurs.
For a rule in the definition of f /n
f (t1 , . . . , tn ) = Exp, Cond => Body.
Picat translates it into the following predicate rule:p(t1 , . . . , tn , V ), Cond => Body, V = Exp.
Picat employs an optimization to generate a tail-recursive rule if Exp is a list.
Consider, for example, the following function conc, which concatenates twolists:
conc([], Ys) = Ys.
conc([X|Xs], Ys) = [X | conc(Xs, Ys)].

Picat translates it into the following predicate:conc_p([], Ys, Zs) => Zs = Ys.
conc_p([X|Xs], Ys, Zs) =>Zs = [X|Zs1],
conc_p(Xs, Ys, Zs1).

The Picat compiler incorporates the tail-recursion optimization, which translates tail-recursive deterministic predicates into iteration. A call to conc p only
allocates one frame on the stack, no matter how long the list is.
10

3.3

Transformation of Comprehensions

Picat translates a list comprehension into a foreach loop that uses := to accumulate values. The list comprehension[Exp : E1 in D1 , Cond1 , . . ., En in Dn , Condn ]is replaced by a new variable L, and the following statements are inserted into
the context:
L = Tail,
foreach (E1 in D1 , Cond1 , . . ., En in Dn , Condn )Tail = [Exp|NewVar],
Tail := NewVar,
end,
Tail = []Initially, Tail is a free variable. In the body of the loop, the call
Tail = [Exp|NewVar]
binds Tail to the term [Exp|NewVar], and the assignment Tail := NewVarlets Tail reference the new tail. After the loop, the call Tail = [] binds Tailto [], completing the list. An alternative translation is possible, which begins
with an empty list, and attaches each value to the end of the list. However, thistranslation is not efficient, since it takes linear time to add a value to the end of
a list.
List comprehensions that occur in aggregate functions, including sum(L),min(L), max(L), and len(L), are compiled in such a way that an aggregate
value is computed, rather than a list. For example, the function callsum([f(I) : I in 1..100])is replaced by a new variable Sum, and the following statements are inserted into
the context:
S = 0,
foreach (I in 1..100)
S := S + f(I)end,
Sum = S

3.4

Transformation of Pure foreach Loops

Picat translates loops into tail-recursive predicates. Consider pure foreach loops
that do not contain assignments. Without loss of generality, consider a foreachloop that has only one iterator:
foreach (E in D)
Goal
end
11

The general form of the foreach loop can be converted into this form by introducing if-then statements and nested loops into the loop goal. For a loop
statement that has nested loops, the inner-most loop is transformed first.
Let V1 , V2 , . . ., Vn be the global variables in Goal, i.e., variables that occur
before the loop in the context. If D is a list, then the loop is replaced by apredicate call in the form p(V1 ,V1 ,. . .,Vn ,D), where p is a newly generated
predicate:p(V1 ,V1 ,. . .,Vn ,[]) => true.
p(V1 ,V1 ,. . .,Vn ,[E|T ]) => Goal, p(V1 ,V1 ,. . .,Vn ,T ).
Note that local variables in Goal are not passed to predicate p, and are naturally
localized. If D is an array or a range in the form LB..Step..UB, then the generated predicate takes extra arguments for iterating over the array or the range
using recursion.
3.5

Transformation of Assignments

An assignment that updates a compound value is transformed into a built-in
predicate called segarg. This subsection shows how to transform assigned variables.
For an assignment LHS := RHS that occurs in a conjunction of goals, Picat
introduces a new variable for LHS that holds the value of RHS. For example,
consider the following rule:
test => X = 0, X := X + 1,

X := X + 2, write(X).

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 is printed. After preprocessing, the rule is translated into the following:
test => X = 0, X1 = X + 1, X2 = X1 + 2, write(X2).

For an assignment that occurs in if-then-else, Picat introduces a new predicate. Consider the following example:go(Z) =>
X = 1, Y = 2,
if Z > 0 thenX := X * Zelse
Y := Y + Z
end,println([X,Y]).

Picat translates the program into the following:12

go(Z) =>X = 1, Y = 2,
p(X, Xout, Y, Yout, Z),
println([Xout,Yout]).
p(Xin, Xout, Yin, Yout, Z), Z > 0 =>Xout = Xin * Z,
Yout = Yin.
p(Xin, Xout, Yin, Yout, Z) =>Xout = Xin,
Yout = Yin + Z.

One rule is generated for each branch of the if-then-else statement. For eachvariable V that occurs on the LHS of an assignment that is inside of the if-thenelse 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. Therefore, predicate
p is passed the parameters Xin, Xout, Yin, and Yout.
Similarly, for an assignment that occurs in a loop, Picat passes two variables
to the predicate for the loop: one variable holds the value before the loop goal is
executed, and the other holds the value after the loop goal is executed. Consider
the following example:
sum_list(L, Sum) =>S = 0,
foreach (E in L)
S := S + E
end,
Sum = S.

Picat translates the program into the following:
sum_list(L, Sum) =>S = 0,p(L, S, Sout),
Sum = Sout.
p([], Sin, Sout) =>Sout = Sin.
p([E|T], Sin, Sout) =>St = Sin + E,
p(T, St, Sout).

In addition to the list L, Picat passes arguments S and Sout to predicate p. Notethat only the global variables that occur within the loop are passed to p.

4

Related Work

The canonical-form language that is used in the Picat compiler is called matchingclauses in B-Prolog [17]. This canonical form narrows the gap between the highlevel constructs and the underlying virtual machine.
13

Functions are naturally a basic notion in functional logic languages, such as
Curry [5]. Picat, like other logic programming languages, such as Mercury [9] andCiao [7], provides functions as a syntax extension. Picat has limited support forhigher-order predicates and functions, and does not support lambda expressions.
The use of higher-order calls in Picat is discouraged because of the overhead.
Classic functional and logic languages rely on recursion and higher-order facilities to describe repetitions. Many modern languages, such as F#9 and OCaml10 ,provide looping constructs. Picat’s foreach loop is similar to B-Prolog’s foreachloop [17], which was inspired by logical loops in ECLiPSe [12]. In ECLiPSe, variables are assumed to be local to each iteration, unless they are declared global. In
B-Prolog, variables are assumed to be global to all of the iterations, unless they
are declared local. In contrast, Picat adopts a simple and clean scoping rule forvariables, which renders the declaration of local or global variables unnecessary.
The list comprehension, which can be traced back to SETL [13], was madepopular by Haskell. The optimization that computes a value instead of creating
a list when a comprehension is immediately fed into an aggregate function, suchas sum, is a special application of the idea of deforestation [14]. The same idea
is employed in compiling loops whose iterators contain the range .. and thezip function. The Picat compiler does not apply deforestation to user-defined
functions or built-in functions in other contexts.
It is rare for declarative languages to provide assignments. An assignment of
the form S[I] := RHS is similar to the setarg built-in in Prolog. An assignmentof the form X := RHS, where X is a variable, is translated into unification at compile time. The transformation rules that eliminate assignments are employed inbuilding the static single assignment form (SSA) for imperative programs, whichsimplifies program analysis and compilation [2]. The Picat compiler introduces
a new predicate for every branching statement that contains assignments, evenfor if-then-else, which could be compiled inline. This makes it unnecessary to
introduce a phi function [2] when branches merge.
There are abundant examples that demonstrate the usefulness and convenience of Picat’s language constructs for modeling. In [4], several examples are
given for GCJ problems.

5

Conclusion

This paper has presented the Picat language, and has shown how to compile Picat’s high-level language constructs into canonical-form pattern-matching rules.
The high-level language constructs give Picat flexibility and brevity needed for
scripting. Picat provides a comprehensive box of tools for describing and solving
combinatorial search problems. The high-level constructs also facilitate modelingwith these tools.
910

http://fsharp.org/
http://ocaml.org/

14

Acknowledgement
Neng-Fa Zhou is supported in part by the NSF under the grant number CCF1618046.

References
1. Alain Colmerauer. Equations and inequations on finite and infinite trees. In
Proceedings of FGCS, pages 85–99. ICOT, 1984.
2. Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently computing static single assignment form and the control
dependence graph. ACM Transactions on Programming Languages and Systems,
13(4):451–490, 1991.
3. Mehmet Dincbas, Pascal Van Hentenryck, Helmut Simonis, Abderrahmane Aggoun, Thomas Graf, and Françoise Berthier. The constraint logic programming
language CHIP. In FGCS, pages 693–702, 1988.
4. Sergii Dymchenko and Mariia Mykhailova. Declaratively solving Google Code Jam
problems with Picat. In PADL, pages 50–57, 2015.
5. Michael Hanus. Functional logic programming: From theory to Curry. In Programming Logics, pages 123–168, 2013.
6. Pascal Van Hentenryck. Constraint and integer programming in OPL. INFORMS
Journal on Computing, 14:2002, 2002.
7. Manuel V. Hermenegildo, Francisco Bueno, Manuel Carro, Pedro López-Garcı́a,
Edison Mera, José F. Morales, and Germán Puebla. An overview of Ciao and its
design philosophy. Theory and Practice of Logic Programming, 12(1-2):219–252,
2012.
8. Robert Kowalski and Donald Kuehner. Linear resolution with selection function.
Artificial Intelligence, 2(3–4):227–260, 1971.
9. Mercury. http://www.mercurylang.org/.
10. Nicholas Nethercote, Peter J. Stuckey, Ralph Becket, Sebastian Brand, Gregory J.
Duck, and Guido Tack. MiniZinc: Towards a standard CP modelling language. In
Principles and Practice of Constraint Programming, pages 529–543, 2007.
11. Joachim Schimpf. Logical loops. In ICLP, pages 224–238, 2002.
12. Joachim Schimpf and Kish Shen. Eclipse-from LP to CLP. Theory and Practiceof Logic Programming, 12(1-2):127–156, 2012.
13. Jacob T. Schwartz, Robert B. K. Dewar, Ed Dubinsky, and Edith Schonberg.
Programming with Sets - An Introduction to SETL. Springer, 1986.
14. Philip Wadler. Deforestation: Transforming programs to eliminate trees. Theoretical Computer Science, 73(2):231–248, 1990.
15. David H. D. Warren. High-order extensions to Prolog – are they needed? MachineIntelligence, 10:441–454, 1982.
16. David H. D. Warren. An abstract Prolog instruction set. Technical note 309, SRI
International, 1983.
17. Neng-Fa Zhou. The language features and architecture of B-Prolog. Theory andPractice of Logic Programming, 12(1-2):189–218, 2012.
18. Neng-Fa Zhou, Roman Barták, and Agostino Dovier. Planning as tabled logic
programming. In Theory and Practice of Logic Programming, 2015.
19. Neng-Fa Zhou and Håkan Kjellerstrand. The Picat-SAT compiler. In PADL, pages
48–62, 2016.
20. Neng-Fa Zhou, Håkan Kjellerstrand, and Jonathan Fruhman. Constraint Solving
and Planning with Picat. Springer, 2015.

15