Preface

Despite the elegant concepts, new extensions (e.g., tabling and constraints), and successful applications (e.g., knowledge engineering, NLP, and search problems), Prolog has a bad reputation for being old and difficult. Many ordinary programmers find the implicit non-directionality and non-determinism of Prolog to be hard to follow, and the non-logical features, such as cuts and dynamic predicates, are prone to misuses, leading to absurd codes. The lack of language constructs (e.g., loops) and libraries for programming everyday things is also considered a big weakness of Prolog. The backward compatibility requirement has made it hopeless to remedy the language issues in current Prolog systems, and there are urgent calls for a new language.

Several successors of Prolog have been designed, including Mercury, Erlang, Oz, and Curry. The requirement of many kinds of declarations in Mercury has made the language difficult to use; Erlang’s abandonment of non-determinism in favor of concurrency has made the language unsuited for many applications despite its success in the telecom industry; Oz has never attained the popularity that the designers sought, probably due to its unfamiliar syntax and implicit laziness; Curry is considered too close to Haskell. All of these successors were designed in the 1990s, and now the time is ripe for a new logic-based language.

Picat aims to be a simple, and yet powerful, logic-based programming language for a variety of applications. Picat incorporates many declarative language features for better productivity of software development, including explicit non-determinism, explicit unification, functions, constraints, and tabling. Picat lacks Prolog’s non-logical features, such as the cut operator and dynamic predicates, making Picat more reliable than Prolog. Picat also provides imperative language constructs for programming everyday things. The system can be used for not only symbolic computations, which is a traditional application domain of declarative languages, but also for scripting and modeling tasks.

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

• Pattern-matching: A predicate defines a relation, and can have zero, one, or multiple answers. A function is a special kind of a predicate that always succeeds with one answer. Picat is a rule-based language. Predicates and functions are defined with pattern-matching rules.
• Intuitive: Picat provides assignment and loop statements for programming everyday things. An assignable variable mimics multiple logic variables, each of which holds a value at a different stage of computation. Assignments are useful for computing aggregates and are used with the foreach loop for implementing list and array comprehensions.
• Constraints: Picat supports constraint programming. Given a set of variables, each of which has a domain of possible values, and a set of constraints that limit the acceptable set of assignments of values to variables, the goal is to find an assignment of values to the variables that satisfies all of the constraints. Picat provides three solver modules: cp, sat, and mip. These three modules follow the same interface, which allows for seamless switching from one solver to another.
• Actors: Actors are event-driven calls. Picat provides action rules for describing event-driven behaviors of actors. Events are posted through channels. An actor can be attached to a channel in order to watch and to process its events.
• Tabling: Tabling can be used to store the results of certain calculations in memory, allowing the program to do a quick table lookup instead of repeatedly calculating a value. As computer memory grows, tabling is becoming increasingly important for offering dynamic programming solutions for many problems. The planner module, which is implemented by the use of tabling, has been shown to be a more efficient tool than ASP and PDDL for solving many planning problems.

The support of explicit unification, explicit non-determinism, tabling, and constraints makes Picat more suitable than functional and scripting languages for symbolic computations. Picat is arguably more expressive than Prolog for scripting and modeling. With arrays, loops, and list and array 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 also more reliable than Prolog. In addition to explicit non-determinism, explicit unification, and a simple static module system, the lack of cuts, dynamic predicates, and operator overloading also improves the reliability of the language. 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 already ready for many kinds of applications. It will also serve as a foundation for new additions, including external language interfaces with C, Java, and Python, an external language interface with MySql, threads, sockets, Web services, and language processing modules. Anybody is welcome to contribute. The C source code is available to registered developers and users. Please contact picat@picat-lang.org.

Acknowledgements

The initial design of Picat was published in December 2012, and the first alpha version was released in May 2013. The following people have contributed to the project by reviewing the ideas, the design, the implementation, and/or the documentation: 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, 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. The picat-lang.org web page was designed by Bo Yuan (Bobby) Zhou. 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; Lingeling by Armin Biere; Espresso (by Berkeley). In addition, Picat also provides interfaces to GLPK by Andrew Makhorin and Gurobi by Gurobi Optimization, Inc.

Contents

Chapter 1
Overview

Before we give an overview of the Picat language, let us briefly describe how to use the Picat system. The Picat system provides an interactive programming environment for users to load, debug, and execute programs. Users can start the Picat interpreter with the OS command picat.

Once the interpreter is started, users can type a command line after the prompt Picat>. The help command shows the usages of commands, and the halt command terminates the Picat interpreter. Users can also use the picat command to run a program directly as follows:

where 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 [t₁,…,t_n] or a structure in the form $s(t₁,…,t_n) where s stands for a structure name, n is called the arity of the structure, and each t_i (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 {t₁,…,t_n}, 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(I₁,I₂,…,I_n) returns an n-dimensional array, where each I_i 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 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, is a special function that returns a single component 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.

A list comprehension, which takes the following form, is a special functional notation for creating lists:

where T is an expression, each E_i is an iterating pattern, each D_i is an expression that gives a compound value, and the optional conditions Cond₁,…,Cond_n are callable terms. This list comprehension means that for every tuple of values E₁ ∈ D₁, …, E_n ∈ D_n, if the conditions are true, then the value of T is added into the list.

An array comprehension takes the following form:

It is the same as:

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 also allows OOP notations for calling predicates and functions. The notation A₁.f(A₂,…,A_k) is the same as f(A₁,A₂,…,A_k), unless A₁ is an atom, in which case A₁ 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

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 and A && B), disjunction (A;B and 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 rules: the non-backtrackable rule Head, Cond => Body, and the backtrackable rule Head,Cond ?=> Body. The Head takes the form p(t₁ , … , t_n ), 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

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:

An if statement takes the form if Cond then Goal₁ else Goal₂ end.¹ 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

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.

After Picat returns an answer, users can type a semicolon immediately after the answer to ask for the next answer. If users only want one answer to be returned from a call, they can use once Call to stop backtracking.

The version of member that checks if a term occurs in a list can be defined as follows:

The first rule is applicable to a call if the second argument is a list and the first argument of the call is identical to the first element of the list.

Picat allows inclusion of predicate facts in the form p(t₁,…,t_n) in predicate definitions. Facts are translated into pattern-matching rules before they are compiled. A predicate definition that consists of facts can be preceded by an index declaration in the form index (M₁₁,…,M_1n) … (M_m1,…,M_mn) where each M_ij is either + (meaning indexed) or - (meaning not indexed). For each index pattern (M_i1 , … , M_in ), the compiler generates a version of the predicate that indexes all of the + arguments.

Example

For a predicate of indexed facts, a matching version of the predicate is selected for a call. If no matching version is available, Picat throws an exception. For example, for the call edge(X,Y), if both X and Y are free, then no version of the predicate matches this call and Picat throws an exception. If predicate facts are not preceded by any index declaration, then no argument is indexed.

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(t₁ ,…,t_n) and X holds the return value. When n = 0, the parentheses can be omitted.

Example

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(t₁,…,t_n)=Exp in function definitions.

Example

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:

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

In order to handle assignments, Picat creates new variables at compile time. In the above example, at compile time, Picat creates a new variable, say X1, to hold the value of X after the assignment X:=X+1. Picat replaces X by X1 on the LHS of the assignment. It also replaces all of the occurrences of X to the right of the assignment by X1. When encountering X1:=X1+2, Picat creates another new variable, say X2, to hold the value of X1 after the assignment, and replaces the remaining occurrences of X1 by X2. When write(X2) is executed, the value held in X2, which is 3, is printed. This means that the compiler rewrites the above example as follows:

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

where each iterator, E_i in D_i, can be followed by an optional condition Cond_i. Within each iterator, E_i is an iterating pattern, and D_i is an expression that gives a compound value. The foreach statement means that Goal is executed for every possible combination of values E₁ ∈ D₁ , … , E_n ∈ D_n that satisfies the conditions Cond₁, …, Cond_n. A while statement takes the form

It repeatedly executes Goal as long as Cond succeeds. A variant of the while loop in the form of

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:

the variables I and E are local, and each iteration of the loop has its own values for these variables.

Example

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:

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:

This loop corresponds to the following sequence of recurrences:

Loop statements are compiled into tail-recursive predicates. For example, the second read_list function given above is compiled into:

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

is compiled into the following loop:

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

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

Example

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:

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:

where each Name_i 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

The predicate sum_aux is private, and is never visible outside of the module. The following shows a session that uses these modules.

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.³ 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 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 three solver modules, including cp, sat, and mip.

Example

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:

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,Arg₁,…,Arg_n), 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 Arg₁,…,Arg_n. The function apply(S,Arg₁,…,Arg_n) 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 call_cleanup/2, catch/3, count_all, freeze/2, not/1, maxof/2-3, maxof_inc/2-3, minof/2-3, minof_inc/2-3, 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

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

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:

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

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

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

For the call go, the output is:

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.

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:

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

• -g InitGoal: This option makes Picat execute a specified initial query InitGoal rather than the default main predicate.
• --help: Print out the help info.
• -log: The option -log makes the system print log information and warning messages.
• -path Directories: Directories is a semicolon-separated and double-quoted list of directories. This option sets the value of the environment variable PICATPATH before the execution of the program. The Picat system will look for PicatMainFileName and the related modules in these directories.
• -s Size: This option reserves Size words for the stack and the heap when the system is started.
• --v:
• --version: This option makes Picat print the version number.

Once the interpreter is started, users can type a query after the prompt. For example,

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:

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:

• cl(FileName): A program first needs to be compiled and loaded into the system before it can be executed. The built-in predicate cl(FileName) compiles and loads the source file named FileName.pi. Note that if the full path of the file name is not given, then the file is assumed to be in the current working directory. Also note that users do not need to give the extension name. The system compiles and loads not only the source file FileName.pi, but also all of the module files that are either directly imported or indirectly imported by the source file. The system searches for such dependent files in the directory in which FileName.pi resides or the directories that are stored in the environment variable PICATPATH. For FileName.pi, the cl command loads the generated byte-codes without creating a byte-code file. For example,
  Picat> cl("welcome")  
  Compiling:: welcome.pi  
  welcome.pi compiled in 4 milliseconds

• cl: The built-in predicate cl (with no argument) compiles and loads a program from the console, ending when the end-of-file character (ctrl-z for Windows and ctrl-d for Unix) is typed.
• compile(FileName): The built-in predicate compile(FileName) compiles the file FileName.pi and all of its dependent module files without loading the generated byte-code files. The destination directory for the byte-code file is the same as the source file’s directory. If the Picat interpreter does not have permission to write into the directory in which a source file resides, then this built-in throws an exception. For example,
  Picat> compile("welcome")  
  Compiling::welcome.pi  
  welcome.pi compiled in 4 milliseconds

• load(FileName): The built-in predicate load(FileName) loads the byte-code file FileName.qi and all of its dependent byte-code files. For FileName and its dependent file names, the system searches for a byte-code file in the directory in which FileName.qi resides or the directories that are stored in the environment variable PICATPATH. If the byte-code file FileName.qi does not exist but the source file FileName.pi exists, then this built-in compiles the source file and loads the byte codes without creating a qi file.
  Picat> load("welcome")  
  loading...welcome.qi

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,

Users can ask the system to find the next solution by typing ';' after a solution if the query has multiple solutions. For example,

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,

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:

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:

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:

Assume the program is stored in a file named myprog.pi. The following shows a trace for a query:

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

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 A₁.f(A₂,…,A_k) is the same as f(A₁ , A₂ , … , A_k ), unless A₁ is an atom, in which case A₁ 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)).

The following functions are provided for all terms:

• copy_term(Term₁) = Term₂: This function copies Term₁ into Term₂. If Term₁ is an attributed variable, then Term₂ will not contain any of the attributes.
• hash_code(Term) = Code: This function returns the hash code of Term. If Term is a variable, then the returned hash code is always 0.
• to_codes(Term) = Codes: This function returns a list of character codes of Term.
• to_fstring(Format, Args…): This function converts the arguments in the Args… parameter into a string, according to the format string Format, and returns the string. The number of arguments in Args… cannot exceed 10. Format characters are described in Chapter 10.
• to_string(Term) = String: This function returns a string representation of Term.

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:

The name _ is used for anonymous variables. In a program, different occurrences of _ are treated as different variables. So the test  _ == _ is always false.

The following two built-ins are provided to test whether a term is a free variable:

• var(Term): This predicate is true if Term is a free variable.
• nonvar(Term): This predicate is true if Term is not 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:

• attr_var(Term): This predicate is true if Term is an attributed variable.
• dvar(Term): This predicate is true if Term is an attributed domain variable.
• bool_dvar(Term): This predicate is true if Term is an attributed domain variable whose lower bound is 0 and whose upper bound is 1.
• dvar_or_int(Term): This predicate is true if Term is an attributed domain variable or an integer.
• get_attr(X, Key) = V al: This function returns the V al of the key-value pair Key=V al that is attached to X. It throws an error if X has no attribute named Key.
• get_attr(X, Key, DefaultV al) = V al: This function returns V al of the key-value pair Key=V al that is attached to X. It returns DefaultV al if X does not have the attribute named Key.
• put_attr(X, Key, V al): This predicate attaches the key-value pair Key=V al to X, where Key is a non-variable term, and V al is any term.
• put_attr(X, Key): This predicate call is the same as put_attr(X, Key,not_a_value).

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:

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:

• atom(Term): This predicate is true if Term is an atom.
• atom_chars(Atm) = String: This function returns string that contains the characters of the atom Atm. It throws an error if Atm is not an atom.
• atom_codes(Atm) = List: This function returns the list of codes of the characters of the atom Atm. It throws an error if Atm is not an atom.
• atomic(Term): This predicate is true if Term is an atom or a number.
• char(Term): This predicate is true if Term is an atom and the atom is made of one character.
• chr(Code) = Char: This function returns the UTF-8 character of the code point Code.
• digit(Term): This predicate is true if Term is an atom and the atom is made of one digit.
• len(Atom) = Len: This function returns the number of characters in Atom. Note that this function is overloaded in such a way that the argument can also be an array, a list, or a structure.
• length(Atom) = Len: This function is the same as len(Atom).
• ord(Char) = Int: This function returns the code point of the UTF-8 character Char. It throws an error if Char is not a single-character atom.

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:

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.

Table 3.2 gives the meaning of each of the numeric operators in Picat, from the operator with the highest precedence (⋆⋆) to the one with the lowest precedence (..). Except for the power operator ⋆⋆, which is right-associative, all of the arithmetic operators are left-associative.

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

• between(From, To, X) (nondet): If X is bound to an integer, then this predicate determines whether X is between From and To. Otherwise, if X is unbound, then this predicate nondeterministically selects X from the integers that are between From and To. It is the same as member(X, From..To).
• float(Term): This predicate is true if Term is a real number.
• int(Term): This predicate is true if Term is an integer.
• integer(Term): The same as int(Term).
• max(X, Y ) = V al: This function returns the maximum of X and Y , where X and Y are terms.
• maxint_small() = Int: This function returns the maximum integer that is represented in one word. All integers that are greater than this integer are represented as big integers.
• min(X, Y ) = V al: This function returns the minimum of X and Y , where X and Y are terms.
• minint_small() = Int: This function returns the minimum integer that is represented in one word. All integers that are smaller than this integer are represented as big integers.
• number(Term): This predicate is true if Term is a number.
• number_chars(Num) = String: This function returns a list of characters of Num. This function is the same as to_fstring("%d",Num) if Num is an integer, and the same as to_fstring("%f",Num) if Num is a real number.
• number_codes(Num) = List: This function returns a list of codes of the characters of Num. It is the same as number_chars(Num).to_codes().
• real(Term): This predicate is the same as float(Term).
• to_binary_string(Int) = String: This function returns the binary representation of the integer Int as a string.
• to_float(NS) = Real: This function is the same as NS⋆1.0 if NS is a number, and the same as parse_term(NS) if NS is a string of digits.
• to_hex_string(Int) = String: This function returns the hexadecimal representation of the integer Int as a string.
• to_int(ANS) = Int: This function is the same as truncate(ANS) in the math module if ANS is a number, the same as ord(ANS)-ord('0') if ANS is a digit character, and the same as parse_term(ANS) if ANS is a string.
• to_integer(ANS) = Int: This function is the same as to_int(ANS).
• to_number(ANS) = Num: This function is the same as ANS if ANS is a number, the same as ord(ANS)-ord('0') if ANS is a digit character, and the same as parse_term(ANS) if ANS is a string.
• to_oct_string(Int) = String: This function returns the octal representation of the integer Int as a string.
• to_radix_string(Int,Base) = String: This function returns the representation of the integer Int of the numeral Base as a string, where Base must be greater than 1 and less than 37. The call to_oct_string(Int) is the same as to_radix_string(Int,8).
• to_real(NS) = Real: This function is the same as to_float(NS).

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, 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 [t₁,…,t_n], where each t_i (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 [A₁ ,A₂ ,… ,A_n |T] is a shorthand for [A₁|[A₂|…[A_n|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).

• List₁ ++ List₂ = List: This function returns the concatenated list of List₁ and List₂.
• append(X, Y , Z) (nondet): This predicate is true if appending Y to X can create Z. This predicate may backtrack if X is not a complete list.¹
• append(W, X, Y , Z) (nondet): This predicate is defined as:
      append(W,X,Y,Z) => append(W,X,WX), append(WX,Y,Z).

• avg(List) = V al: This function returns the average of all the elements in List. This function throws an exception if List is not a list or any of the elements is not a number.
• delete(List, X) = ResList: This function deletes the first occurrence of X from List, returning the result in ResList. The built-in !=/2 is used to test if two terms are different. No variables in List or X will be bound after this function call.
• delete_all(List, X) = ResList: This function deletes all occurrences of X from List, returning the result in ResList. The built-in !=/2 is used to test if two terms are different.
• first(List) = Term: This function returns the first element of List.
• flatten(List) = ResList: This function flattens a list of nested lists into a list. For example, flatten([[1],[2,[3]]]) returns [1,2,3].
• head(List) = Term: This function returns the head of the list List. For example, head([1,2,3]) returns 1.
• insert(List, Index, Elm) = ResList: This function inserts Elm into List at the index Index, returning the result in ResList. After insertion, the original List is not changed, and ResList is the same as
  List.slice(1, Index-1)++[Elm|List.slice(Index, List.length)].
• insert_all(List, Index, AList) = ResList: This function inserts all of the elements in AList into List at the index Index, returning the result in ResList. After insertion, the original List is not changed, and ResList is the same as
  List.slice(1, Index-1)++AList++List.slice(Index, List.length).
• insert_ordered(List,Term): This function inserts Term into the ordered list List, such that the resulting list remains sorted.
• insert_ordered_down(List,Term): This function inserts Term into the descendantly ordered list List, such that the resulting list remains sorted down.
• last(List) = Term: This function returns the last element of List.
• len(List) = Len: This function returns the number of elements in List. Note that this function is overloaded in such a way that the argument can also be an atom, an array, or a structure.
• length(List) = Len: This function is the same as len(List).
• list(Term): This predicate is true if Term is a list.
• max(List) = V al: This function returns the maximum value that is in List, where List is a list of terms.
• membchk(Term, List): This predicate is true if Term is an element of List.
• member(Term, List) (nondet): This predicate is true if Term is an element of List. When Term is a variable, this predicate may backtrack, instantiating Term to different elements of List.
• min(List) = V al: This function returns the minimum value that is in List, where List is a list or an array of terms.
• new_list(N) = List: This function creates a new list that has N free variable arguments.
• new_list(N,InitV al) = List: This function creates a new list that has N arguments all initialized to InitV al.
• nth(Index, List, Elem) (nondet): This predicate is true when Elem is the Index’th element of List. Counting starts at 1. When Index is a variable, this predicate may backtrack, instantiating Index to a different integer between 1 and len(List).
• prod(List) = V al: This function returns the product of all of the values in List.
• remove_dups(List) = ResList: This function removes all duplicate values from List, retaining only the first occurrence of each value. The result is returned in ResList. Note that an O(n²) algorithm is used in the implementation. If List is large, then sort_remove_dups(List) may be faster than this function.
• reverse(List) = ResList: This function reverses the order of the elements in List, returning the result in ResList.
• select(X, List, ResList) (nondet): This predicate nondeterministically selects an element X from List, and binds ResList to the list after X is removed. On backtracking, it selects the next element.
• sort(List) = SList: This function sorts the elements of List in ascending order, returning the result in SList.
• sort(List,KeyIndex) = SList: This function sorts the elements of List by the key index KeyIndex in ascending order, returning the result in SList. The elements of List must be compound values and KeyIndex must be a positive integer that does not exceed the length of any of the elements of List. This function is defined as follows:
      sort(List,KeyIndex) = SList =>  
          List1 = [(E[KeyIndex],E) : E in List],  
          List2 = sort(List1),  
          SList = [E : (_,E) in List2].

• sort_remove_dups(List) = SList: This function is the same as the following, but is faster.

  sort(List).remove_dups()

• sort_remove_dups(List,KeyIndex) = SList: This function is the same as the following, but is faster.

  sort(List,KeyIndex).remove_dups()

• sort_down(List) = SList: This function sorts the elements of List in descending order, returning the result in SList.
• sort_down(List,KeyIndex) = SList: This function sorts the elements of List by the key index KeyIndex in descending order, returning the result in SList.
• sort_down_remove_dups(List) = SList: This function is the same as the following, but is faster.

  sort_down(List).remove_dups()

• sort_down_remove_dups(List,KeyIndex) = SList: This function is the same as the following, but is faster.

  sort_down(List,KeyIndex).remove_dups()

• slice(List,From,To) = SList: This function returns the sliced list of List from index From through index To. From must not be less than 1.
• slice(List,From) = SList: This function is the same as the following.

  slice(List,From,List.length)

• sum(List) = V al: This function returns the sum of all of the values in List.
• tail(List) = Term: This function returns the tail of the list List. For example, the call tail([1,2,3]) returns [2,3].
• to_array(List) = Array: This function converts the list List to an array. The elements of the array are in the same order as the elements of the list.
• zip(List₁, List₂, …, List_n) = List: This function makes a list of array tuples. The jth tuple in the list takes the form {E_1j,…,E_nj}, where E_ij is the jth element in List_i. In the current implementation, n can be 2, 3, or 4.

3.4.2 Strings

A string is represented as a list of single-character atoms. For example, the string "hello" is the same as the list [h,e,l,l,o]. In addition to the built-ins on lists, the following built-ins are provided for strings:

• string(Term): This predicate is true if Term is a string.
• to_lowercase(String) = LString: This function converts all uppercase alphabetic characters into lowercase characters, returning the result in LString.
• to_uppercase(String) = UString: This function converts all lowercase alphabetic characters into uppercase characters, returning the result in UString.

3.4.3 Structures

A structure takes the form $s(t₁,…,t_n), where s is an atom, and n is called the arity of the structure. The dollar symbol is used to distinguish a structure from a function call. The functor of a structure comprises the name and the arity of the structure.

The following types of structures can never denote functions, meaning that they do not need to be preceded by a $ symbol.

Picat disallows creation of the following types of structures:

The compiler will report a syntax error when it encounters any of these expressions within a term constructor.

The following built-ins are provided for structures:

• arity(Struct) = Arity: This function returns the arity of Struct, which must be a structure.
• len(Struct) = Arity: This function is the same as arity(Struct).
• name(Struct) = Name: This function returns the name of Struct.
• new_struct(Name, IntOrList) = Struct: This function creates a structure that has the name Name. If IntOrList is an integer, N, then the structure has N free variable arguments. Otherwise, if IntOrList is a list, then the structure contains the elements in the list.
• struct(Term): This predicate is true if Term is a structure.
• to_list(Struct) = List: This function returns a list of the components of the structure Struct.

3.4.4 Arrays

An array takes the form {t₁,…,t_n}, which is a special structure with the name '{}' and arity n. Note that, unlike a list, an array always has its length stored in memory, so the function length(Array) always takes constant time. Also note that Picat supports constant-time access of array elements, so the index notation A[I] takes constant time.

In addition to the built-ins for structures, the following built-ins are provided for arrays:

• array(Term): This predicate is true if Term is an array.
• new_array(D₁, …, D_n) = Arr: This function creates an n-dimensional array, where each D_i is an integer expression that specifies the size of a dimension. In the current implementation, n cannot exceed 10.

The following built-ins, which are originally provided for lists (see 3.4.1), are overloaded for arrays:

• Array₁ ++ Array₂ = Array
• avg(Array) = V al
• first(Array) = Term
• last(Array) = Term
• len(Array) = Len
• length(Array) = Len
• max(Array) = V al
• min(Array) = V al
• nth(Index, List, Elem) (nondet)
• reverse(Array) = ResArray
• slice(Array,From,To) = SArray
• slice(Array,From) = SArray
• sum(Array) = V al
• sort(Array) = SArray
• sort(Array,KeyIndex) = SArray
• sort_remove_dups(Array) = SArray
• sort_remove_dups(Array,KeyIndex) = SArray
• sort_down(Array) = SArray
• sort_down(Array,KeyIndex) = SArray
• sort_down_remove_dups(Array) = SArray
• sort_down_remove_dups(Array,KeyIndex) = SArray

Note that many of the overloaded built-ins for arrays are not implemented efficiently, but are provided for convenience. For example, sort(Array) is implemented as follows:

3.4.5 Maps

A map is a hash-table that is represented as a structure that contains a set of key-value pairs. The functor of the structure that is used for a map is not important. An implementation may ban access to the name and the arity of the structure of a map. Maps must be created with the built-in function new_map, unless they are prebuilt (see Section 1.11). In addition to the built-ins for structures, the following built-ins are provided for maps:

• clear(Map): This predicate clears the map Map. It throws an error if Map is not a map.
• get(Map, Key) = V al: This function returns V al of the key-value pair Key=V al in Map. It throws an error if Map does not contain the key Key.
• get(Map, Key, DefaultV al) = V al: This function returns V al of the key-value pair Key=V al in Map. It returns DefaultV al if Map does not contain Key.
• has_key(Map, Key): This predicate is true if Map contains a pair with Key.
• keys(X) = List: This function returns the list of keys of the pairs in Map.
• map(Term): This predicate is true if Term is a map.
• map_to_list(Map) = PairsList: This function returns a list of Key=V al pairs that constitute Map.
• new_map(IntOrPairsList) = Map: This function creates a map with an initial capacity or an initial list of pairs.
• new_map(N, PairsList) = Map: This function creates a map with the initial capacity N, the initial list of pairs PairsList, where each pair has the form Key=V al.
• put(Map, Key, V al): This predicate attaches the key-value pair Key=V al to Map, where Key is a non-variable term, and V al is any term.
• put(Map, Key): This predicate is the same as put(Map, Key, not_a_value).
• values(Map) = List: This function returns the list of values of the pairs in Map.
• size(Map) = Size: This function returns the number of pairs in Map.

Most of the built-ins are overloaded for attributed variables.

3.4.6 Sets

A set is a map where every key is associated with the atom not_a_value. All of the built-ins for maps can be applied to sets. For example, the built-in predicate has_key(Set,Elm) tests if Elm is in Set. In addition to the built-ins on maps, the following built-ins are provided for sets:

• new_set(IntOrKeysList) = Set: This function creates a set with an initial capacity or an initial list of keys.
• new_set(N,KeysList) = Set: This function creates a set with the initial capacity N and the initial list of keys KeysList.

3.4.7 Heaps

A heap² is a complete binary tree represented as an array. A heap can be a min-heap or a max-heap. In a min-heap, the value at the root of each subtree is the minimum among all the values in the subtree. In a max-heap, the value at the root of each subtree is the maximum among all the values in the subtree.

• heap_is_empty(Heap): This predicate is true if Heap is empty.
• heap_pop(Heap) = Elm: This function removes the root element from the heap, and returns the element. As the function updates the heap, it is not pure. The update will be undone when execution backtracks over the call.
• heap_push(Heap, Elm): This predicate pushes Elm into Heap in a way that maintains the heap property. The update to Heap will be undone when execution backtracks over the call.
• heap_size(Heap) = Size: This function returns the size of Heap.
• heap_to_list(Heap) = List: This function returns a list of the elements in Heap.
• heap_top(Heap) = Elm: This function returns the element at the root of the heap. If Heap is a min-heap, then the element is guaranteed to be the minimum, and if Heap is a max-heap, then the element is guaranteed to be the maximum.
• new_max_heap(IntOrList) = Heap: This function creates a max-heap. If IntOrList is an integer, then it indicates the capacity. Otherwise, if IntOrList is a list, then the max-heap contains the elements in the list in an order that maintains the heap property.
• new_min_heap(IntOrList) = Heap: This function creates a min-heap. If IntOrList is an integer, then it indicates the capacity. Otherwise, if IntOrList is a list, then the min-heap contains the elements in the list in an order that maintains the heap property.

Example

3.5 Equality Testing, Unification, and Term Comparison

The equality test T₁ == T₂ is true if term T₁ and term T₂ are identical. Two variables are identical if they are aliases. Two primitive values are identical if they have the same type and the same internal representation. Two lists are identical if the cars are identical and the cdrs are identical. Two structures are identical if their functors are the same and their components are pairwise identical. The inequality test T₁ !== T₂ is the same as not T₁ == T₂. Note that two terms can be identical even if they are stored in different memory locations. Also note that it takes linear time in the worst case to test whether two terms are identical, unlike in C-family languages, in which the equality test operator == only compares addresses.

The unification T₁ = T₂ is true if term T₁ and term T₂ are already identical, or if they can be made identical by instantiating the variables in the terms. The built-in T₁ != T₂ is true if term T₁ and term T₂ are not unifiable. The predicate bind_vars(Term,V al) binds all of the variables in Term to V al.

Example

The last query illustrates the occurs-check problem. When binding X to f(X), Picat does not check if X occurs in f(X) for the sake of efficiency. This unification creates a cyclic term, which can never be printed.

When a unification’s operands contain attributed variables, the implementation is more complex. When a plain variable is unified with an attributed variable, the plain variable is bound to the attributed variable. When two attributed variables, say Y and O, where Y is younger than O, are unified, Y is bound to O, but Y ’s attributes are not copied to O. Since garbage collection does not preserve the seniority of terms, the result of the unification of two attributed variables is normally unpredictable.

3.5.1 Numerical Equality

The numerical equality test T₁ =:= T₂ is true if term T₁ and term T₂ are pretty much the same numerical value. This means that T1 and T2 must both be numbers. Whereas the test T₁ == T₂ fails if one number is an integer and one number is a real number, the test T₁ =:= T₂ may succeed. Consider the following examples.

Example

In the first query, 1 is an integer, while 1.0 is a real number, so the equality test fails. However, the second query, which is a numerical equality test, succeeds.

3.5.2 Ordering of Terms

Picat orders terms in the following way:

Variables are ordered by their addresses. Note that the ordering of variables may change after garbage collection. Numbers are ordered by their numerical values. Atoms are ordered lexicographically. Structures are first ordered lexicographically by their names; if their names are the same, then they are ordered by their components. Arrays are ordered as structures with the special name ’{}’. Lists and strings are ordered by their elements.

• Term1 @< Term2: The term Term1 precedes the term Term2 in the standard order. For example, a @< b succeeds.
• Term1 @=< Term2: The term Term1 either precedes, or is identical to, the term Term2 in the standard order. For example, a @=< b succeeds.
• Term1 @<= Term2: This is the same as Term1 @=< Term2.
• Term1 @> Term2: The term Term1 follows the term Term2 in the standard order.
• Term1 @>= Term2: The term Term1 either follows, or is identical to, the term Term2 in the standard order.

3.6 Expressions

Expressions are made from variables, values, operators, and function calls. Expressions differ from terms in the following ways:

• An expression can contain dot notations, such as math.pi.
• An expression can contain index notations, such as X[I].
• An expression can contain ranges, such as 1..2..100.
• An expression can contain list comprehensions, such as [X : X in 1..100].
• An expression can contain array comprehensions, such as {X : X in 1..100}.

A conditional expression, which takes the form cond(Cond,Exp₁,Exp₂), is a special kind of function call that returns the value of Exp₁ if the condition Cond is true and the value of Exp₂ if Cond is false.

Note that, except for conditional expressions in which the conditions are made of predicates, no expressions can contain predicates. A predicate is true or false, but never returns any value.

3.7 Higher-order Predicates and Functions

A predicate or function is said to be higher-order if it takes calls as arguments. The basic module has the following higher-order predicates and functions.

• apply(S, Arg₁, …, Arg_n) = V al: S is an atom or a structure. This function calls the function that is named by S with the arguments that are specified in S, together with extra arguments Arg₁, …, Arg_n. This function returns the value that S returns.
• call(S, Arg₁, …, Arg_n): S is an atom or a structure. This predicate calls the predicate that is named by S with the arguments that are specified in S, together with extra arguments Arg₁, …, Arg_n.
• call_cleanup(Call, Cleanup): This predicate is the same as call(Call), except that Cleanup is called when Call succeeds determinately (i.e., with no remaining choice point), when Call fails, or when Call raises an exception.
• catch(Call, Exception, Handler): This predicate is the same as Call, except when an exception that matches Exception is raised during the execution of Call. When such an exception is raised, all of the bindings that have been performed on variables in Call will be undone, and Handler will be executed to handle the exception.
• count_all(Call) = Count: This function returns the number of all possible instances of call(Call) that are true. For example, count_all(member(X,[1,2,3])) returns 3.
• findall(Template, Call) = Answers: This function returns a list of all possible instances of call(Call) that are true in the form of Template. Note that Template is assumed to be a term without function calls, and that Call is assumed to be a predicate call whose arguments can contain function calls. Also note that, like a loop, findall forms a name scope. For example, in findall(f(X),p(X,g(Y))), f(X) is a term even though it is not preceded with $; g(Y) is a function call; the variables X and Y are assumed to be local to findall if they do not occur before in the outer scope.
• find_all(Template, Call) = Answers: This function is the same as the above function.
• freeze(X, Call): This predicate delays the evaluation of Call until X becomes a non-variable term.
• map(FuncOrList, ListOrFunc) = ResList: This function applies a given function to every element of a given list and returns a list of the results. One of the arguments is a function, and the other is a list. The order of the arguments is not important.
• map(Func, List1, List2) = ResList: Let List1 be [A₁,…,A_n] and List2 be [B₁ ,… ,B_n]. This function applies the function Func to every pair of elements (A_i,B_i) by calling apply(Func,A_i,B_i), and returns a list of the results.
• maxof(Call, Objective): This predicate finds a satisfiable instance of Call, such that Objective has the maximum value. Here, Call is used as a generator, and Objective is an expression to be maximized. For every satisfiable instance of Call, Objective must be a ground expression. For maxof, search is restarted with a new bound each time that a better answer is found.
• maxof(Call, Objective, ReportCall): This is the same as maxof(Call,Objective), except that call(ReportCall) is executed each time that an answer is found.
• maxof_inc(Call, Objective): This is the same as maxof(Call,Objective), except that search continues rather than being restarted each time that a better solution is found.
• maxof_inc(Call, Objective, ReportCall): This is the same as the previous predicate, except that call(ReportCall) is executed each time that an answer is found.
• minof(Call, Objective): This predicate finds a satisfiable instance of Call, such that Objective has the minimum value.
• minof(Call, Objective, ReportCall): This is the same as minof(Call,Objective), except that call(ReportCall) is executed each time that an answer is found.
• minof_inc(Call, Objective): This predicate is the same as minof(Call,Objective), except that search continues rather than being restarted each time that a better solution is found.
• minof_inc(Call, Objective, ReportCall): This predicate is the same as the previous one, except that call(ReportCall) is executed each time that an answer is found.
• reduce(Func, List) = Res: If List is a list that contains only one element, this function returns the element. If List contains at least two elements, then the first two elements A₁ and A₂ are replaced with apply(Func,A₁,A₂). This step is repeatedly applied to the list until the list contains a single element, which is the final value to be returned. The order of the arguments is not important, meaning that the first argument can be a list and the second one can be a function.
• reduce(Func, List, InitV al) = Res: This function is the same as
  reduce(Func,[InitV al|List]).

3.8 Other Built-ins in the basic Module

• acyclic_term(Term): This predicate is true if Term is acyclic, meaning that Term does not contain itself.
• and_to_list(Conj) = List: This function converts Conj in the form (a₁,…,a_n) into a list in the form [a₁,…,a_n].
• compare_terms(Term₁, Term₂) = Res: This function compares Term₁ and Term₂ . If Term₁ < Term₂, then this function returns -1. If Term₁ == Term₂, then this function returns 0. Otherwise, Term₁ > Term₂, and this function returns 1.
• different_terms(Term₁, Term₂): This constraint ensures that Term₁ and Term₂ are different. This constraint is suspended when the arguments are not sufficiently instantiated.
• get_global_map() = Map: This function returns the global map, which is shared by all threads.
• get_heap_map() = Map: This function returns the current thread’s heap map. Each thread has its own heap map.
• get_table_map() = Map: This function returns the current thread’s table map. Each thread has its own table map. The table map is stored in the table area and both keys and values are hash-consed (i.e., common sub-terms are shared).
• ground(Term): This predicate is true if Term is ground. A ground term does not contain any variables.
• list_to_and(List) = Conj: This function converts List in the form [a₁,…,a_n] into a term in the form (a₁,…,a_n).
• number_vars(Term, N₀) = N₁: This function numbers the variables in Term by using the integers starting from N₀. N₁ is the next integer that is available after Term is numbered. Different variables receive different numberings, and the occurrences of the same variable all receive the same numbering.
• parse_radix_string(String, Base) = Int: This function converts a radix String of Base into a decimal integer Int, where Base must be greater than 1 and less than 37. For example, parse_radix_string("101",2) returns 5, which is the same as parse_term("0b101").
• parse_term(String, Term, V ars): This predicate uses the Picat parser to extract a term Term from String. V ars is a list of pairs, where each pair has the form Name=V ar.
• parse_term(String) = Term: This function converts String to a term.
• second(Compound) = Term: This function returns the second argument of the compound term Compound.
• subsumes(Term₁, Term₂): This predicate is true if Term₁ subsumes Term₂.
• variant(Term₁, Term₂): This predicate is true if Term₂ is a variant of Term₁.
• vars(Term) = V ars: This function returns a list of variables that occur in Term.

Chapter 4
Predicates and Functions

In Picat, predicates and functions are defined with pattern-matching rules. Picat has two types of rules: the non-backtrackable rule

and the backtrackable rule

Each rule is terminated by a dot (.) followed by a white space.

4.1 Predicates

A predicate defines a relation, and can have zero, one, or multiple answers. Within a predicate, the Head is a pattern in the form p(t₁,…,t_n), where p is called the predicate name, and n is called the arity. When n = 0, the parentheses can be omitted. The condition Cond, which is an optional goal, specifies a condition under which the rule is applicable. Cond cannot succeed more than once. The compiler converts Cond to once Cond if would otherwise be possible for Cond to succeed more than once.

For a call C, if C matches the pattern p(t₁,…,t_n) and Cond is true, then the rule is said to be applicable to C. When applying a rule to call C, Picat rewrites C into Body. If the used rule is non-backtrackable, then the rewriting is a commitment, and the program can never backtrack to C. However, if the used rule is backtrackable, then the program will backtrack to C once Body fails, meaning that Body will be rewritten back to C, and the next applicable rule will be tried on C.

A predicate is said to be deterministic if it is defined with non-backtrackable rules only, non-deterministic if at least one of its rules is backtrackable, and globally deterministic if it is deterministic and all of the predicates in the bodies of the predicate’s rules are also globally deterministic. A deterministic predicate that is not globally deterministic can still have more than one answer.

Example

The predicate append(Xs,Ys,Zs) is true if the concatenation of Xs and Ys is Zs. It defines a relation among the three arguments, and does not assume directionality of any of the arguments. For example, this predicate can be used to concatenate two lists, as in the call

this predicate can also be used to split a list nondeterministically into two sublists, as in the call append(L1,L2,[a,b,c,d]); this predicate can even be called with three free variables, as in the call append(L1,L2,L3).

The predicate min_max(L,Min,Max) returns two answers through its arguments. It binds Min to the minimum of list L, and binds Max to the maximum of list L. This predicate does not backtrack. Note that a call fails if the first argument is not a list. Also note that this predicate consumes linear space. A tail-recursive version of this predicate that consumes constant space will be given below.

4.2 Functions

A function is a special kind of a predicate that always succeeds with one answer. Within a function, the Head is an equation p(t₁,…,t_n)=X, where p is called the function name, and X is an expression that gives the return value. Functions are defined with non-backtrackable rules only.

For a call C, if C matches the pattern p(t₁,…,t_n) and Cond is true, then the rule is said to be applicable to C. When applying a rule to call C, Picat rewrites the equation C=X′ into (Body, X′=X), where X′ is a newly introduced variable that holds the return value of C.

Picat allows inclusion of function facts in the form p(t₁,…,t_n)=Exp in function definitions. The function fact p(t₁,…,t_n)=Exp is shorthand for the rule:

where X is a new variable.

Although all functions can be defined as predicates, it is preferable to define them as functions for two reasons. Firstly, functions often lead to more compact expressions than predicates, because arguments of function calls can be other function calls. Secondly, functions are easier to debug than predicates, because functions never fail and never return more than one answer.

Example

The function qequation(A,B,C) returns the pair of roots of A⋆X²+B⋆X+C=0. If the discriminant B⋆B-4⋆A⋆C is negative, then an exception will be thrown.

The function rev(L) returns the reversed list of L. Note that the function rev(L) takes quadratic time and space in the length of L. A tail-recursive version that consumes linear time and space will be given below.

4.3 Patterns and Pattern-Matching

The pattern p(t₁ ,…,t_n) in the head of a rule takes the same form as a structure. Function calls are not allowed in patterns. Also, patterns cannot contain index notations, dot notations, ranges, array comprehensions, or list comprehensions. Pattern matching is used to decide whether a rule is applicable to a call. For a pattern P and a term T , term T matches pattern P if P is identical to T , or if P can be made identical to T by instantiating P ’s variables. Note that variables in the term do not get instantiated after the pattern matching. If term T is more general than pattern P , then the pattern matching can never succeed.

Unlike calls in many committed-choice languages, calls in Picat are never suspended if they are more general than the head patterns of the rules. A predicate call fails if it does not match the head pattern of any of the rules in the predicate. A function call throws an exception if it does not match the head pattern of any of the rules in the function. For example, for the function call rev(L), where L is a variable, Picat will throw the following exception:

A pattern can contain as-patterns in the form V @Pattern, where V is a new variable in the rule, and Pattern is a non-variable term. The as-pattern V @Pattern is the same as Pattern in pattern matching, but after pattern matching succeeds, V is made to reference the term that matched Pattern. As-patterns can avoid re-constructing existing terms.

Example

In the third rule, the as-pattern Ys@[Y|_] binds two variables: Ys references the second argument, and Y references the car of the argument. The rule can be rewritten as follows without using any as-pattern:

Nevertheless, this version is less efficient, because the cons [Y|Ys] needs to be re-constructed.

4.4 Goals

In a rule, both the condition and the body are goals. Queries that the users give to the interpreter are also goals. A goal can take one of the following forms:

• true: This goal is always true.
• fail: This goal is always false. When fail occurs in a condition, the condition is false, and the rule is never applicable. When fail occurs in a body, it causes execution to backtrack.
• false: This goal is the same as fail.
• p(t₁ , … , t_n ): This goal is a predicate call. The arguments t₁,…,t_n are evaluated in the given order, and the resulting call is resolved using the rules in the predicate p∕n. If the call succeeds, then variables in the call may get instantiated. Many built-in predicates are written in infix notation. For example, X=Y is the same as '='(X,Y).
• P, Q: This goal is a conjunction of goal P and goal Q. It is resolved by first resolving P, and then resolving Q. The goal is true if both P and Q are true. Note that the order is important: (P , Q) is in general not the same as (Q, P ).
• P && Q: This is the same as (P, Q).
• P; Q: This goal is a disjunction of goal P and goal Q. It is resolved by first resolving P . If P is true, then the disjunction is true. If P is false, then Q is resolved. The disjunction is true if Q is true. The disjunction is false if both P and Q are false. Note that a disjunction can succeed more than once. Note also that the order is important: (P ; Q) is generally not the same as (Q; P ).
• P || Q: This is the same as (P; Q).
• not P: This goal is the negation of P . It is false if P is true, and true if P is false. Note a negation goal can never succeed more than once. Also note that no variables can get instantiated, no matter whether the goal is true or false.
• once P: This goal is the same as P , but can never succeed more than once.
• repeat: This predicate is defined as follows:
      repeat ?=> true.  
      repeat => repeat.

  The repeat predicate is often used to describe failure-driven loops. For example, the query

        repeat,writeln(a),fail

  repeatedly outputs 'a' until ctrl-c is typed.

• if-then: An if-then statement takes the form

  if Cond1 then

  Goal1

  elseif Cond2 then

  Goal2

  elseif Condn then

  Goaln

  else

  Goalelse

  end

  where the elseif and else clauses are optional. If the else clause is missing, then the else goal is assumed to be true. For the if-then statement, Picat finds the first condition Cond_i that is true. If such a condition is found, then the truth value of the if-then statement is the same as Goal_i. If none of the conditions is true, then the truth value of the if-then statement is the same as Goal_else. Note that no condition can succeed more than once.

• throw Exception: This predicate throws the term Exception. This predicate will be detailed in Chapter 6 on Exceptions.
• Loops: Picat has three types of loop statements: foreach, while, and do-while. A loop statement is true if and only if every iteration of the loop is true. The details of loops are given in Chapter 5.

4.5 Predicate Facts

For an extensional relation that contains a large number of tuples, it is tedious to define such a relation as a predicate with pattern-matching rules. It is worse if the relation has multiple keys. In order to facilitate the definition of extensional relations, Picat allows the inclusion of predicate facts in the form p(t₁ ,… ,t_n ) in predicate definitions. Facts and rules cannot co-exist in predicate definitions and facts must be ground. A predicate definition that consists of facts must be preceded by an index declaration in the form

where each M_ij is either + (meaning indexed) or - (meaning not indexed). Facts are translated into pattern-matching rules before they are compiled.

Example

The predicate edge is translated into the following rules:

4.6 Tail Recursion

A rule is said to be tail-recursive if the last call of the body is the same predicate as the head. The last-call optimization enables last calls to reuse the stack frame of the head predicate if the frame is not protected by any choice points. This optimization is especially effective for tail recursion, because it converts recursion into iteration. Tail recursion runs faster and consumes less memory than non-tail recursion.

The trick to convert a predicate (or a function) into tail recursion is to define a helper that uses an accumulator parameter to accumulate the result. When the base case is reached, the accumulator is returned. At each iteration, the accumulator is updated. Initially, the original predicate (or function) calls the helper with an initial value for the accumulator parameter.

Example

In the helper predicate min_max_helper(L,CMin,Min,CMax,Max), CMin and CMax are accumulators: CMin is the current minimum value, and CMax is the current maximum value. When L is empty, the accumulators are returned by the unification calls Min=CMin and Max=CMax. When L is a cons [H|T], the accumulators are updated: CMin changes to min(CMin,H), and CMax changes to max(CMax,H). The helper function rev_helper(L,R) follows the same idea: it uses an accumulator list to hold, in reverse order, the elements that have been scanned. When L is empty, the accumulator is returned. When L is the cons [X|Xs], the accumulator R changes to [X|R].

Chapter 5
Assignments and Loops

This chapter discusses variable assignments, loop constructs, and list and array comprehensions in Picat. It describes the scope of an assigned variable, indicating where the variable is defined, and where it is not defined. Finally, it shows how assignments, loops, and list comprehensions are related, and how they are compiled.

5.1 Assignments

Picat variables are single-assignment, meaning that once a variable is bound to a value, the variable cannot be bound again. In order to simulate imperative language variables, Picat provides the assignment operator :=. An assignment takes the form LHS:=RHS, where LHS is either a variable or an access of a compound value in the form X[…]. When LHS is an access in the form X[I], the component of X indexed I is updated. This update is undone if execution backtracks over this assignment.

Example

The compiler needs to give special consideration to the scope of a variable. The scope of a variable refers to the parts of a program where a variable occurs.

Consider the test example. This example binds X to 0. Then, the example tries to bind X to X + 1. However, X is still in scope, meaning that X is already bound to 0. Since X cannot be bound again, the compiler must perform extra operations in order to manage assignments that use the := operator.

In order to handle assignments, Picat creates new variables at compile time. In the test example, at compile time, Picat creates a new variable, say X1, to hold the value of X after the assignment X := X + 1. Picat replaces X by X1 on the LHS of the assignment. All occurrences of X after the assignment are replaced by X1. When encountering X1 := X1 + 2, Picat creates another new variable, say X2, to hold the value of X1 after the assignment, and replaces the remaining occurrences of X1 by X2. When write(X2) is executed, the value held in X2, which is 3, is printed. This means that the compiler rewrites the above example as follows:

5.1.1 If-Else

This leads to the question: what does the compiler do if the code branches? Consider the following code skeleton.

Example