NOPT042 Constraint programming: Tutorial 1 – Introduction to Picat¶
- See the tutorial website for program of classes, credit requirements, and a list of useful resources.
- Check out our GitHub repository for the notebooks, code examples, and solutions to some exercises (will be updated throughout the semester).
- Join our ReCodEx group for homework assignments.
What was in the lecture?¶
This tutorial does not follow the contents of the lecture. This is by design:
- In the lecture, we learn how constraint solvers work.
- In the tutorial, we learn how to create efficient constraint models, how to think in "declarative", "constraint programming" mode.
While in your future careers you are much more likely to be using an industry-grade constraint solver than to be developing one, being able to write efficient models requires sufficient understanding of the solver's inner workings.
However, at the beginning of each tutorial we will briefly review what was covered in the last lecture.
What was in Lecture 1?¶
- course overview
- history
- examples (Sudoku, map coloring, N-queens, ...)
- applications
- how CP fits within optimization
- the definition of the CSP, basic terminology
- advantages and limitations
- binarization of constraints
In this tutorial:¶
- getting started with the Picat programming language
- overview of Picat in general (not specific to constraint programming)
- a demonstration of basic constraint solving in Picat
About Picat¶
Picat is a logic-based multiparadigm general-purpose programming language.
- Pattern-matching: predicates defined with pattern-matching rules
- Intuitive: incorporates declarative language syntax, e.g. for scripting, mimics for-loops, ...
- Constraints: designed with constraint programming in mind, provides 4 solvers,
cp, sat, smt, mip - Actors: action rules for event-driven behaviour; constraint propagators are implemented as actors
- Tabling: store subresults, dynamic programming, module
planner
Why Picat?
Installation¶
You can install Picat like this (check if there's a newer version of Picat):
cd ~
wget http://picat-lang.org/download/picat37_linux64.tar.gz
tar -xf picat37_linux64.tar.gz
Then add the executable to $PATH (assuming we use bash):
echo 'export PATH="$HOME/Picat:$PATH"' >> ~/.bashrc
source ~/.bashrc
Then the command picat runs the Picat interpreter.
If you want to execute the notebooks, install Jupyter Notebook with ipicat extension (if you want to install them locally, add --user):
pip install jupyter
pip install ipicat
Then run jupyter notebook. Once the extension is loaded you can use %%picat cell magic or execute picat files: %picat -e hello-world.pi.
To view the slideshow, install the RISE extension:
pip install RISE
%load_ext ipicat
Picat version 3.7
Introductory examples¶
Hello, World!¶
%%picat
main =>
println("Hello, World!").
Hello, World!
Execute a picat file via inline magic:
%picat -e hello-world.pi
Hello, World!
Alternatively, via a shell comand:
!picat hello-world.pi
Hello, World!
Command-line arguments¶
# This doesn't work at the moment
# %picat -e hello-world.pi Alice
!picat hello-world.pi Alice
!picat hello-world.pi Alice Bob Carol Dave
Hello, Alice! I love your solution to the homework problem.
Hello, Alice and Bob and Carol and Dave! You are my favourite students.
!cat hello-world.pi
import util.
main =>
println("Hello, World!").
main([Name]) =>
printf("Hello, %s! I love your solution to the homework problem.\n", Name).
main(ARGS) =>
Names = ARGS.join(" and "),
printf("Hello, %s! You are my favourite students.\n", Names).
Example: Fibonacci sequence¶
In Jupyter, use %%picat -n predicate_name to define a predicate from a cell.
%%picat -n fib
fib(N, F) =>
if (N = 0) then
F = 0
elseif (N = 1) then
F = 1
else
fib(N - 1, F1),
fib(N - 2, F2),
F = F1 + F2
end.
Alternative syntax:
%%picat -n fib
fib(0, F) => F = 0.
fib(1, F) => F = 1.
fib(N, F), N > 1 => fib(N - 1, F1), fib(N - 2, F2), F = F1 + F2.
But of course, we should use tabling!¶
%%picat -n fib_tabled
table
fib_tabled(0, F) => F = 0.
fib_tabled(1, F) => F = 1.
fib_tabled(N, F), N > 1 => fib_tabled(N - 1, F1), fib_tabled(N - 2, F2), F = F1 + F2.
Compare the performance:
%%picat
main =>
time(fib(42, F)),
println(F),
time(fib_tabled(42, F)),
println(F).
CPU time 32.26 seconds. 267914296 CPU time 0.0 seconds. 267914296
Example: Quicksort¶
Pattern-matching rules:
%%picat -n qsort
qsort([]) = [].
qsort([H | T]) = qsort([E : E in T, E =< H]) ++ [H] ++ qsort([E : E in T, E > H]).
Alternative version:
%%picat -n qsort
qsort(L) = Lsorted =>
if L = [] then
Lsorted = []
else
L = [H | T],
Lsorted = qsort([E : E in T, E =< H]) ++ [H] ++ qsort([E : E in T, E > H]).
Try it out:
%%picat
main => L = qsort([5, 2, 6, 4, 1, 3]), println(L).
[1,2,3,4,5,6]
Source-file, with string interpolation the output:
!picat qsort/qsort.pi
For example, the list [5,2,6,4,1,3] after sorting is [1,2,3,4,5,6].
Command-line arguments:
!picat qsort/qsort.pi [5,2,6,4,1,3]
[1,2,3,4,5,6]
Reading and writing files¶
!cat qsort/assorted.lists
[2, 1] [5, 2, 6, 4, 1, 3] [44, 11, 29, 53, 59, 70, 63, 68, 16, 30, 95, 9, 55, 71, 84, 81, 64, 46, 26, 89, 15, 40, 22, 97, 39]
!picat qsort/qsort.pi qsort/assorted.lists qsort/sorted.lists
!cat qsort/sorted.lists
[1,2] [1,2,3,4,5,6] [9,11,15,16,22,26,29,30,39,40,44,46,53,55,59,63,64,68,70,71,81,84,89,95,97]
The source code:
!cat qsort/qsort.pi
qsort([]) = [].
qsort([H|T]) = qsort([E : E in T, E =< H]) ++ [H] ++ qsort([E : E in T, E > H]).
main =>
L = [5, 2, 6, 4, 1, 3],
printf("For example, the list %w after sorting is %w.\n", L, qsort(L)).
main([Lstring]) =>
L = parse_term(Lstring),
println(qsort(L)).
main([InputPath, OutputPath]) =>
Lines = read_file_lines(InputPath),
OutputFile = open(OutputPath, write),
foreach(I in 1..Lines.length)
L = parse_term(Lines[I]),
writeln(OutputFile, qsort(L))
end.
TPK algorithm¶
The TPK algorithm is an artificial problem designed by Trabb Pardo & Knuth to showcase the syntax of a given programming language (see Wikipedia):
ask for N numbers to be read into a sequence S
reverse sequence S
for each item in sequence S
call a function to do an operation
if result overflows
alert user
else
print result
The following Picat implementation is from here.
!cat tpk/tpk.pi
% TPK Algorithm in Picat
% from https://www.linuxjournal.com/content/introduction-tabled-logic-programming-picat
f(T) = sqrt(abs(T)) + 5 * T**3.
main =>
N = 4,
As = to_array([read_real() : I in 1..N]),
foreach (I in N..-1..1)
Y = f(As[I]),
if Y > 400 then
printf("%w TOO LARGE\n", I)
else
printf("%w %w\n", I, Y)
end
end.
!cat tpk/some_reals.txt
!printf "\n"
!picat tpk/tpk.pi < tpk/some_reals.txt
1.0e-2 -2.345 42.0001 -0.002
4 0.0447213 3 TOO LARGE 2 -62.9447 1 0.100005
An overview of Picat¶
Examples in this section are mostly adapted from or inspired by the Picat Book, Picat Guide, AAA2017 tutorial, and examples. For a quick overview, see pages 4–18 from Modeling and Solving AI Problems in Picat.
Data types¶
- Dynamic, runtime typing.
- Everything is a term (which can be a variable, or a value: atomic or compound)
Variables¶
- Start with capital letter or underscore:
var(X)[yes],var(_abc)[no],var(abc)[no] - A variable is free until instantiated (bound to a value).
- Single-assignment variables: after instantiation, the variable has the same identity as the value:
X=1, var(X)[no] - If execution backtracks over the binding point, the variable becomes free again.
Values¶
Primitive values:
- atom: symbolic constant, either quoted or starts with lower-case letter (incl. char)
- number: integer or real
Compound values:
- list:
L = [1, 2, 3], list comprehension:L = [X : X in 1..5] - string: a list of chars
- struct:
X = $employee(john_doe, accounting, 62150),X = new_struct(employee, 3) - array:
A = to_array(L),A = {X*X : X in 1..10} - map:
Bdays = new_map(), Bdays.put(john,oct3) - set: a map without values,
S = new_set([1,2,3]), S.has_key(2)
Other¶
- Fairly standard operators (we will introduce them as needed)
- Object-oriented notation
,is conjunction,;is disjunctionforeachandwhileloops:
foreach(E1 in D1, Cond1, ... , En in Dn, Condn)
Goal
end
while (Cond)
Goal
end
- assignment:
Var := Expchange toVar'=Exp, change occurences ofVartoVar'X[I,J] := Expdestructively updates the component (undone upon backtracking)
- Picat is not a procedural language!
Resources for learning Picat, and constraint programming in Picat:¶
- The Picat Book "Constraint Solving and Planning with Picat" (free PDF)
- The Picat Guide: "A User's guide to Picat" (in particular, Chapter 12: Constraints)
- There are several tutorials, e.g. this one.
- More resources are available here.
- Lots of Picat programs, as well as other resources, are on Hakan Kjellerstrand's Picat page.
A constraint programming example¶
For the rest of today, we will practice writing programs in "pure" Picat. We will introduce constraint modelling in Picat next tutorial. But here is one example, the N-queens problem: place N queens on an NxN chess board so that no two queens attack each other.
!picat queens/queens.pi 4
[2,4,1,3]
!cat queens/queens.pi
% adapted from picat-lang.org
import cp.
queens(N, Q) =>
Q = new_list(N),
Q :: 1..N,
all_different(Q),
all_different([$Q[I] - I : I in 1..N]),
all_different([$Q[I] + I : I in 1..N]),
solve([ff], Q).
main =>
queens(8, Q),
print(Q).
main([N]) =>
queens(N.to_int, Q),
print(Q).
Exercises¶
Exercise: count occurences¶
Write a program that counts the number of occurences of an integer in a list of integers, e.g.:
picat count-occurences.pi [1,2,4,2,3,2] 2
picat count-occurences.pi [1,2,2,1] 3
outputs 3 and 0, respectively.
Exercise: transpose¶
Write a program that transposes a given matrix (a 2D array), e.g.:
picat transpose.pi "{{1,2,3},{4,5,6}}"
outputs {{1,4},{2,5},{3,6}}. (Note that we need to put the input in quotation marks.) Inside your code define a function transpose(Matrix) = Transposed_Matrix.
Exercise: binary trees¶
Write a function that receives a binary tree encoded using the structure $node(Value,LeftChild,RightChild) and outputs the depth of the tree. For example:
picat depth.pi "node(42,nil,nil)"
picat depth.pi "node(1,node(2,nil,nil),node(3,nil,nil))"
picat depth.pi "node(1,node(2,node(3,node(4,nil,nil),node(5,nil,nil)),nil),node(6,node(7,nil,nil),node(8,nil,nil)))"
should output:
0
1
3