Picat integrates several programming paradigms, including logic programming, imperative programming, functional programming, scripting, dynamic programming with tabling, and constraint programming. This section compares Picat with Prolog as a logic programming language, Haskell as a functional programming language, and Python as a scripting language.
Although Picat is a multi-paradigm language, its core is underpinned by logic programming concepts, including logic variables, unification, and backtracking.
Like in Prolog, logic variables in Picat are value holders. A logic variable can be bound to any term, including another logic variable. Logic variables are single-assignment, meaning that once a variable is bound to a value, the variable takes the identity of the value, and the variable cannot be bound again, unless the value is a variable or contains variables.
In both Prolog and Picat, unification is a basic operation, which can be utilized to unify terms. Unlike Prolog, Picat uses pattern-matching, rather than unification, to select applicable rules for a call. Consider the predicate membchk/2, which checks whether a term occurs in a list. The following are its definitions in Prolog and in Picat:
% Prolog membchk(X,[X|_]) :- !. membchk(X,[_|T]) :- membchk(X,T). % Picat membchk(X,[X|_]) => true. membchk(X,[_|T]) => membchk(X,T).
For a call membchk(X,L), if both X and L are ground, then the call has the same behavior under both the Prolog and the Picat definitions. However, if X or L is not ground, then the call may give different results in Prolog and in Picat. For example, the call membchk(a,_) and the call membchk(_,[a]) succeed in Prolog, but they fail in Picat. Pattern-matching is a simpler operation than unification. Pattern-matching rules in Picat are fully indexed, while Prolog clauses are typically indexed on one argument. Therefore, Picat can be more scalable than Prolog.
Picat, like Prolog, supports backtracking. In Prolog, every clause is implicitly backtrackable, and the cut operator ! can be utilized to control backtracking. In contrast, backtrackable rules in Picat must be explictly denoted, which renders the cut operator unnecessary. Consider the predicate member/2, as defined in Prolog and in Picat:
% Prolog member(X,[X|_]). member(X,[_|T]) :- member(X,T). % Picat member(X,[Y|_]) ?=> X = Y. member(X,[_|T]) => member(X,T).
For a call member(X,L), if L is a complete list,\footnote{A list is complete if it is empty, or if its tail is complete. For example, [a,b,c] and [X,Y,Z] are complete, but [a,b|T] is not complete if T is a variable.} then the call has the same behavior under both the Prolog and the Picat definitions. If L is incomplete, then the call can succeed an infinite number of times under the Prolog definition, because unifying L with a cons always succeeds when L is a variable. In contrast, pattern matching never changes call arguments in Picat. Therefore, the call member(X,L) can never succeed more times than the number of elements in L.
Picat also differs from Prolog in several other aspects, such as the lack of support for dynamic predicates and for user-defined operators in Picat. The most distinguishable difference between Prolog and Picat is in Picat's language constructs, including list and array comprehensions, assignable variables, loops, and functions. These language constructs, together with the built-in array and map data types, make Picat more convenient than Prolog for scripting and modeling tasks. This book is full of examples for constraint solving and planning that benefit from these constructs.
The following gives an example function in Picat, which takes two matrices, A and B, and returns the product A×B:
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.
Prolog's definition of the same function would be 10 times as long as Picat's definition. Furthermore, since the Picat compiler translates loops and list comprehensions into tail recursion, which is further converted into iteration by tail-recursion optimization, the Picat version is as fast as the Prolog version, if not faster.
Like Haskell, Picat supports function definitions with pattern-matching rules. A major difference between Haskell and Picat is that Haskell is a statically-typed language, while Picat is a dynamically-typed language. In Haskell, every variable has a known type at compile time, while in Picat, a variable is typeless until it is bound to a value. Although static typing allows the Haskell compiler to detect type errors and to optimize code generation by automatically inferring types, Picat is more flexible than Haskell.
Haskell is a pure functional language, while the core of Picat is a logic language. Haskell and Picat, as two declarative programming languages, discourage 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. For example, the sort(L) function returns a sorted copy of list L without changing L, and the remove_dups(L) function returns a copy of L that has no duplicate values. 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.
In Haskell, impure computations that have side effects are described as monads. Haskell's type system distinguishes between pure and monadic functions. In Picat, side effects can be caused by the assignment operator := and by certain built-ins, such as those that perform I/O. An assignment of the form S[I] := RHS has global side effects, since the compound term S is destructively updated, like an assignment in an imperative language. An assignment of the form X := RHS, where X is a variable, only has a side effect within the body of the rule in which the assignment occurs. Recall that the compiler introduces a new variable for X and replaces the remaining occurrences of X by the new variable. Variable assignments do not have cross-predicate or cross-function side effects.
In Haskell, using higher-order functions is a basic norm of programming. Although Picat has limited support for higher-order predicates, such as call/n, and functions, such as apply/n, map/2, and fold/3, the use of higher-order calls is discouraged, because of the overhead. Whenever possible, recursion, loops, or list and array comprehensions should be used instead.
In Picat, the unification operator = and the equality operator == can be used on any two terms. In contrast, in Haskell, the equality operator == can only be used on certain types of values. For example, consider the membchk function in Haskell:
membchk x (y:z)
| x == y = True
| otherwise = membchk x z
membchk _ [] = False
This function has the type (Eq a) => a -> [a] -> Bool, which requires type a to be an instance of a typeclass that defines the equality operator.
Haskell supports implicit lazy evaluation, meaning that the evaluation of an expression can be delayed until the value of the expression is needed. In contrast, Picat is a strict language, meaning that arguments are completely evaluated before calls are evaluated. Lazy evaluation allows for the creation of infinite lists. For example, the Haskell expression [1,2..] creates an infinite list of positive integers. In Picat, the freeze(X,Call) predicate, which delays Call until X is instantiated, can be used to simulate lazy evaluation, and infinite data can be created through the use of backtracking. For example, the following predicate generates an infinite sequence of positive integers:
gen(X) ?=> X =1. gen(X) => gen(X1), X = X1+1.
Picat is essentially a relational language. Logic variables and automatic backtracking are two features that make Picat more suitable for search problems than Haskell. The built-in predicate append is probably one of the most powerful and convenient nondeterministic predicates in Picat. The following examples illustrate several different uses of this predicate:
append(Pre,_,L) |
Checks if Pre is a prefix of L |
append(_,Suf,L) |
Checks if Suf is a suffix of L |
append(_,[Last],L) |
Retrieves the last element of L |
append(Part1,[Sep|Part2],L) |
Splits L into 2 parts separated by Sep |
Logic variables are easily extended to domain variables, which enable the natural specification of constraints. Although it is possible to simulate backtracking by using lazy evaluation in Haskell, the native support of backtracking is an advantage of Picat for relational programming.
Both Python and Picat are dynamically-typed and interpreted languages that emphasize flexibility and brevity of description more than the efficiency of programs.
Python is an imperative language and many of its built-ins have side effects. For example, the lst.sort() method destructively sorts the list lst, and the lst.remove(elm) method destructively removes elm from lst. Side effects can make code less manageable.
Lists in Picat, like lists in Prolog and Haskell, are linked lists, while lists in Python are dynamic arrays. In Picat, for a list L, the function call len(L) takes linear time in the size of L, and the list access L[I] takes I steps to reach the Ith element. In contrast, in Python, both len(L) and L[I] take constant time. Picat supports constant-time access of array elements, but Picat's arrays are not dynamic.
Python does not support tail-recursion optimization. Because of this, iteration is more often favorable than recursion for describing repetitions. For example, consider the following definition of membchk in Python:
def membchk(elm, lst):
if lst == []:
return False
else:
[head,*tail] = lst
if head == elm:
return True
else:
return membchk(elm,tail)
This definition is not efficient since: (1) the assignment [head,*tail] = lst creates a new list object, and (2) the recursive call membchk(elm,tail) creates a new frame on the stack, rather than reusing the caller's stack frame. A more efficient implementation is to use a loop to iterate over the list.
As can be seen in the membchk function shown above, Python allows patterns on the left-hand sides of assignments. While pattern-matching is a nice feature of Python, pattern-matching rules in Picat (and in Haskell) are more easily manageable and efficient. Each pattern-matching rule has its own naming scope, which enables the addition and removal of rules without affecting other rules. Pattern-matching rules are fully indexed, and in many cases pattern-directed branching is much more efficient than if-then-else.
Unlike Python, Picat does not support object-orientation. It is possible to simulate abstract data types in Picat using the module system. For example, a rectangle class can be defined in a module that provides a function named new_rect for creating a rectangle structure, functions for getting and setting the attribute values of a rectangle, and some other functions, including a function that computes a rectangle's area. Picat's dot notation makes calling a function on a structure look like calling a method on an object. For example, the following query creates a rectangle and computes its area:
R = new_rect(100,100), Area = R.area().
More syntax extensions are necessary to make Picat a full-fledged OOP language.
As a logic language, Picat has the same advantages over Python as it has over Haskell for search problems. Python has been used as a host language for constraint programming and linear programming solvers. Logic variables tend to make Picat models neater than their Python counterparts. Backtracking makes it convenient to implement some search strategies, such as branch-and-bound and iterative-deepening, for the underlying solvers.