• Week by week (official edt | unofficial eirb'elec)
• Library including
• TD exercises and solutions
• CLP final test 25 April 2007 new! last year: CLP final test 23 May 2006
• Getting started with CHIP
• CHIP online documentation
• Project [Team Work]
• Evaluation [pdf | xls] marks proposed to the jury
• Prolog and Constraint Industry [CUC2006]

Week by week

• Week 1 : Wednesday 24 January 2007
• Week 2 : Wednesday 31 January 2007
• Week 3 : Wednesday 7 February 2007 - Dr. Idir Gouachi, from Cosytec
• Week 4 : Wednesday 14 February 2007
• Week 5 : Wednesday 28 February 2007
• Week 6 : Wednesday 7 March 2007
• Week 7 : Wednesday 14 March 2007
• Week 8 : Wednesday 21 March 2007
• Week 9 : Wednesday 28 March 2007
• Week 10: Wednesday 4 April 2007

Week 1 : Wednesday 24 January 2007

Lecture 1: Introduction to the module. Presentation of web information (Library, Prolog and Constraint Industry). [Printed version of Slides and Exercise list is available from Ms Marie-Josèphe de Gasquet, computer science secretary: these are old versions, but very close to Library documents.]

Evaluation: 2 hour final test (30%) + mini-project (70%) OR 2 hour final test (70%) + mini-project (30%). Mini-project soon available.

Motivation: Sudoku problem.

Beginning of: LP, introduction, functional versus relational programming, first order logic syntax and semantics, validity of formulas,

lp.html slides 1--12.

Week 2 : Wednesday 31 January 2007

• Write only true things!
• Write enough!
• Do not write to much (avoid redundancy)!
  

• A pure Prolog program is a finite representation of a (possibly infinite) set of ground facts. Queries are means of extracting facts.
• Theory available from lp.html slides 24--46.
  

Week 3 : Wednesday 7 February 2007

Presentation by Dr. Idir Gouachi, from Cosytec:

• Part 0: Presentation of Cosytec;
• Part 1: CHIP, syntactic constraints, global constraints, with application examples;
• Part 2:  industrial applications with demonstrations.

Week 4 : Wednesday 14 February 2007

• color the map of Yougoslavia: copy yugoslavia.pl to your Chip directory [this is exercise XI from sheet (pdf | doc)];
• DON'T look at solution;
• SEND+MORE=MONEY: copy money.pl to your Chip directory [this is exercise XV from sheet (pdf | doc)];
• DON'T look at solution;
• 4-queen puzzle, then, generalization to N-queen puzzle, using Prolog to generate constraints [exercise  XVIII from sheet (pdf | doc)];
• Not done!
• DON'T look at solution;

Lecture 4: Very brief overview of CHIP constraints (or builtin predicates needed for the N-queen puzzle):

• length(L, N): L is a list of length N;
• CLP(FD), Finite Domain constraints (::, #=, #\=, #>, #<, ...)
• X::1..N :  X is declared as a FD variable whose domain consists of the natural number interval [1, N],
• X #\= Y :  X and Y have different values; note that X and Y must have been declared as a FD variable;
• X #\= Y+n :  The values of X and Y+n are different; this extends the previous syntax: n must be a natural number;
• X #\= Y+N:  The values of X and Y+N are different; this generalizes previous syntax: N must be a rational variable which has been instantiated to some natural number;
• Remark: N could also be a FD variable already bound to some natural number, or a tree-domain variable bound to some natural number;
• 3*X + 4*Y #= 5*Z + U + 45, FD-equality (linear expressions, more tolerant syntax than for #\=);
• indomain(X): instantiate X in its domain (value generation); note that "indomain" may take and additional parameter to specify domain value selection ordering;
• labeling(Variables, 0, most_constrained, indomain): generalization of "indomain" to a list of FD variables: third and fourth argument respectively allow heuristic control over variable selection order and domain value selection order;
• CLP(Q), linear rational constraints ( ^=, ^\=, ^>, ^<, ...)
• 3*X + 4*Y ^= 5*Z + U + 45,
• X+1 ^= Y.
• useful for parameterizing a FD problem;
• CLP(trees), equivalent to pure Prolog;
• f(X, a) = f(b, Y),
• X = f(X, a)   has a solution in CHIP! see blackboard on photo at top of page (Infinite regular trees);
• These constraint languages communicate to some (weak) extent..

Week 5 : Wednesday 28 February 2007

• 4-queen puzzle, then, generalization to N-queen puzzle, using Prolog + CLP(Q) to generate constraints [exercise  XVIII from sheet (pdf | doc)];
• DON'T look at solution;

Week 6 : Wednesday 7 March 2007

• Operational semantics of LP (Pure Prolog): resolution, unification, search trees, see lp.htm slides 12--29, 47--50;
• According to its declarative semantics, a Prolog program is a finite representation of a potentially infinite set of facts (ground atoms): they can be explained mathematically, independantly from "how it works in the machine";
• Operational semantics tell you what happens in the machine when you enter a query (after "reconsulting" a Prolog program). The explanation is based upon the notion of search tree, which summarizes all the possible proofs in the form of branches:
• nodes are labeled with lists of atoms: the root is labeled with the initial query;
• a non empty node has as many successors as there are applicable clauses in the Prolog program, for erasing the first atom;
• a finite branch corresponds to a success, yielding an answer, if nothing is left to be proved, or a finite failure otherwise;
• infinite branches correspond to non termination of a proof: because Prolog systems use a "depth first, left to right" strategy, they never meet more than one infinite branch: everything to the right is out of reach (including finite solutions or failures);
• The basic (and unique) inference rule used for the construction of a node in a search tree is the "erase" rule (based on SLD-resolution) using the "unification algorithm":
• parent node: l₁, ..., l_n ;
• clause variant (all variables distinct from those in parent node):  c :- h₁, ..., h_k (written "c." if k=0);
• most general unifier sigma of l₁ and c: sigma(l₁) = sigma(c);
• successor node: sigma(h₁), ..., sigma(h_k), sigma(l₂), ..., sigma(l_n);
• Answers to the initial query are produced along a success branch by composing substitutions performed along the branch, and projecting the result on the query variables.
• Operational semantics of CLP:  search trees, CLP efficiency vs LP inefficiency, see clp.htm, slides 3--7;

TD 6: Mystery exercise:

• read exercise V from sheet (pdf | doc); we use "m" for "mystery", "c" for "cons", "n" for "nil", and "a", "b" instead of "1", "2";
• dont'look at the search tree of the "m(X, c(a, c(b, n)))" until you have drawn it yourself! 
• SLD resolution snapshots are also available (but SLD resolution proofs were not done in class this year).

• read and understand the problem;
• read CHIP Reference manual documentation on the "diffn" global constraint;
• first try to solve the specific "enseirb_info_data.pl" timetable problem only. The idea is: look at the file, and write the constraints;
• some ideas and questions:
• each task involves 3 resources: time, professor, group of students;
• a task may correspond to a course, a TD, a lunch break, a night of sleep, ...;
• how do we map tasks into "diffn" constraints?
• what is the dimension of a rectangle in a "diffn"?
• units of time correspond to 15 minutes (in the above example) or 10 minutes (in a second example to be provided): there is no correspondence between a "unit" and an "ENSEIRB créneau"!
• durations specified by "module" clauses cannot be broken into pieces: for example, "psycho" module requires 12 units (3 hours in a row) for the lecture, and there is only one lecture per week.

Week 7 : Wednesday 14 March 2006

• concerning the dimension of rectangles in "diffn" constraints, have a look at dimension_choice.pl program and test it;
• a second input data file (enseirb_info_data2.pl) will be supplied, using actual ENSEIRB data, based on 5--9 February 2007 week, for Info (I1 and I2):
• ENSEIRBtt5_9feb2007_i1.pdf (.xls),
• ENSEIRBtt5_9feb2007_i2.pdf (.xls).

Back to Week by Week or Top

Week 8 : Wednesday 21 March 2007

• Question: How can I collect information from enseirb_info_data.pl, for instance, a list of all modules, or a list of all professors?
• Answer: You now want to solve the class of planning problems, not just the specific instance enseirb_info_data.pl. The best way is to use CHIP findall predicate. You can collect all solutions to a given query in a list. This is not pure Prolog, but there is no other method, because of the data representation in the form of a Datalog program. In theory, we could have used a big list to represent all the data, and there would be no need for findall, but it would have been less readable.
• Complement: I have implemented a variant of findall, named findall_once, see findall.pl.
• Question: Is it possible to have more than one free time period in a week?
• Answer: It is not clear from the subject. The "freetime" semantics do not forbid more than one period of free time; I actually implicitely made this assumption, but it is unnecessary. One could easily handle any number of free time breaks.
• Question: Given two natural numbers A and B, such that B is a divisor of A, how can I compute the quotient?
• Answer: If A and B are constants, and you know that B is a divisor of A, you can use rational linear constraints:
      B*Q ^= A
  This constraint is linear because in the product B*Q, B is a constant.
• Complement: If B is not necessarily a divisor of A, you cannot use a rational constraint such as
      B*Q + R ^= A
  because this might yield non natural rational numbers for Q and R. You can solve the euclidian division problem in natural numbers, using finite domains, see euclid.pl. [Do not use  "is" which is an old and obsolete construction, resembling ":=" assignment statement in imperative programming].

Back to Week by Week or Top

Week 9 : Wednesday 28 March 2007

• Question: How can I collect information from enseirb_info_data.pl, for instance, a list of all modules, or a list of all professors?
• Answer: Use "findall" CHIP predicate (see same question, last week).

• ~gloess/chip/clp/solutions/nth.pl :vector and matrix access, may be useful for display purposes (converting professor numbers into professor names, ...);
• ~gloess/chip/clp/solutions/coloring.pl : generic coloring (for any given map, not just Yugoslavia!), an example of contraint generator (from a specific problem instance solver to a generic problem solver).

Back to Week by Week or Top

Week 10 : Wednesday 4 April 2007

• Explanations on the compiler:
• the technique used is now called "DCG" for "Definite Clause Grammars" rather than "metamorphosis grammars" as suggested in the CHIP compiler.pl program. Each terminal or non terminal in the original grammar is turned into a predicate. Predicates corresponding to terminals ("a", "b", "c", "+", "*", "(", ")" in the exemple under consideration) are defined using one clause only; predicates corresponding to non terminals are defined using as many clauses as there are in the grammar, for each one of them. The predicates take 3 arguments: the first two arguments are syntactic; the third one is semantic and represents the compiled code.
• Assuming p is a predicate corresponding to a terminal or non terminal p in the grammar, then:
• p(X, Y, P) means that:
• X and Y are lists of words (terminals),
• Y is a tail of X,
• the difference X-Y (that is, the list Z such that append(Z, Y, X) holds, note that it is a prefix of X) has the syntactic class p,
• P is the compiled code (we also say, translation, or semantic translation) corresponding to the source text X-Y.
• In other words, p(X, Y, P) means that X starts with a text of syntactic class p, which compiles into P, and ends with Y.
• It is easy to encode each terminal into a Prolog clause, e.g.:
• a([a | Y], Y, a).      % The sentence [a | Y] starts with terminal a and ends with Y; the translation is simply a itself, here.
• For non terminals, it is easy to encode each rule of the grammar into a Prolog clause, at least if one ignores the semantic translation (third argument), in a first approach, which we will assume here. The key idea is to use as many intermediate syntactic variables (-1) as there are elements in the right member of the rule.  Then the Chasle relation applies, e.g., X-Z = X-Y + Y-Z.
• For instance, the rule
      sumSequence ::=   + factor sumSequence
  will be turned into the Prolog clause:
• sumSequence(X, W) :- +(X, Y), factor(Y, Z), sumSequence(Z, W).
• A rule with empty right member, such as
      sumSequence ::= epsilon
  becomes a fact, here:
• sumSequence(X, X).  % X-X, the empty text [] has the syntactic class sumSequence.

Recall some useful CHIP programs or examples.

Back to Week by Week or Top

Library

* Use ghostview with Landscape orientation and letter format.

Acrobat Reader: for easy access through your navigator, edit your preferences and associate "acroread %s" handler with "Portable Document Format" application.

Back to Top

---

Project

• Build a general size sudoku solver 
• + a general size sudoku generator
• with graphic and web interface
• ... and on line payment by credit card!
• see Week 4, Week6, Week 7, Week 8, Week 9 for more information on project.

Student teams and work.

Deliverable see additional ".htaccess" request 16 May 2006!

• Each team will notify me by e-mail (cc to all team members) of the address (URL) of the project directory, which should be under the "public_html" of one of the team member; no later than Monday 15 May 2006, 11:59pm;
• The project directory should contain:
• an "index.html" file with links to a report (html or pdf) and CHIP and/or Java implementation;
• a "report" directory containing the report;
  
• a "chip" directory containing all the source CHIP files, together with a ".htaccess" file containing the lines (added May 16, 2006):
      RemoveHandler .pl
      AddType text/plain   pl PL
• some other directories if needed (for example if there is a Java development);
• The report may be short (2 or 4 pages, for instance). It should:
• clearly identify the team members;
• start with a brief introduction;
• describe the state of achievement: is the general size sudoku solver operational? What other features have been provided among the suggested ones (generator, graphic and/or interface, ...) and what is the state of achievement of each such feature;
• give the essential ideas underlying the implementation of each feature (for those who have used XGIP or GAELL for graphics, some explanation of what has been used, and some comparison with other known tools, is welcome);
• describe the purpose of each CHIP file (and its main predicates);
• give some assessment of the efficiency of your tool: size of the sudokus you can solve or generate (dimension and number of blank boxes in the sudoku grids you can generate, time needed for solving or generating sudokus, ...);
• not give the detail of each predicate;
• end with some conclusion and perspective.
• The CHIP source code should consist of one or more ".pl" files located in the "chip" directory. Each file should be composed of
• A banner identifying the authors (the team members), their school (ENSEIRB), ..., the date, the general purpose of the file;
• The predicate definitions. For each predicate p of arity N, there should be
• A comment explaining the precise meaning of the predicate, in the form:
• /*   p(X1, ..., XN)
        --------------
            means that  <some sentence referring to X1, ..., XN>
  */
• Note that X1, ..., XN should be well chosen (meaningful) distinct symbols;
• The name of the predicate should also be meaningful;
• the clauses defining the predicate p of arity N. [It is usually not necessary to include comments with clauses; variable names should be carefully chosen, and compatible with those used in the comment defining the predicate meaning.].
• A commented zone containing queries:
• Each query should start with a brief comment related to the query;
• Each query should be runnable as the first one in a CHIP session (do not assume that anything has been "reconsulted" prior to the query).
• If you have used Java or other programming languages, you know the rules better than I do ...;
• I intend to save your directories on this CHIP 2005-2006 page. Bon courage!

Public defence

• 20 minutes per team, mostly for a demo (prepare a demo on a terminal); whiteboard will be available for a brief explanation of the work (if necessary): no slide presentation is required;
• teams will defend their project in the order of the list;
• teams are not requested to attend other team defence; teams should prepare their demo ahead of time on a terminal;
• as always, there may be some delay ... so that you may have to wait!
• See you!

Back to Top

Prolog and Constraint Industry

• Cosytec [CUC2006]
• ILog
• PROLOGIA
• AFPLC (association)
• ALP (association)

© Copyright 1999-3000 Paul Y Gloess