*From Logic Programming to Prolog*

by Krzystof Apt

(available in the library and on web)

*Logic Programming and Negation: A survey*

by Krzystof Apt and Roland Bol

(available in the library and on web)

Some slides, also used in the past, are available here:

- Introduction

- Unification
- Procedural Interpretation
- Declarative Interpretation
- Pure Prolog
- Common Use of CUT
- Negation -- Procedural Interpretation
- Negation -- Declarative Interpretation
- Termination of Programs

Exam: 7 February 2012, starting at 10:00am, duration 120 min, room E5 (and E6 should E5 not be sufficient).

On 25 January we will meet at 14:30 in room E005 to complete the tutorial of the morning (allow max 20 mins), and after this the FLP course is considered closed.

No FLP lectures on the week starting on 30/1.

Lecture and tutorial on 24 and 25 January will be swapped.

The lecture on 18/1 is cancelled.

An extra tutorial is planned on 19/12/2011 at DS6 in room 2026.

An extra tutorial is planned on 19/12/2011 at DS1.

Christmas break: last day of teaching period is 21/12/2011, lectures resume on 4/1/2012

The lecture on 16/11/2011 is cancelled for national calendar holiday (Buss- und Bettag); it will be recovered on Friday 18/11/2011 at DS1 and it will be a mixed tutorial/lecture session (more tutorial than lecture).

The lecture on 2/11 is cancelled and anticipated to 18/10 DS4.

The lecture on 9/11 is cancelled and anticipated to 24/10 DS1.

The tutorials on 18/10 and 1/11 (this latter, held by Amin) will take place as planned.

*12.10.11—Lecture 1*Introduction to the course and module; slides 1 have been presented in full. Notions of rule, fact, list, occur-check, termination, success, failure have been discussed through examples; comparison of programs in the declarative and imperative programming languages, as well as some pros and cons of declarative (Prolog) programs have been discussed.

- Before the next lecture, revise the concepts and try the Exercise List 1. You may use any Prolog compiler (Sicstus and SWI being the most common ones); be aware there might be slight differences in some built-in predicates.

*18.10.11—Tutorial 1 *Solutions and discussion on some of the proposed exercises in the List 1 (be aware, there is a typo in the mult predicate, which is supposed to be a ternary predicate). Recursion and tail-recursion; use of accumulators; use of Prolog libraries for arithmetics.

*18.10.11—Lecture 2 *Unification (slides 2, up to page 16). Terms, substitutions, application of subtitutions to a term, composition of substitutions, substitutions ordering, unifiers, most general unifier, Martelli-Montanari algorithm.

- Before the next lecture, revise the concepts and definitions presented so far.

*19.10.11—Lecture 3 *Unification (continuation of slides 2). Relations, partial orders, lexicographic orders, Martelli-Montanari algorithm: proofs of correctness, completeness, termination. Presentation of solutions of further exercises from List 1.

- Before the next lecture, revise the concepts, definitions, proofs. Exercise List 2 is available.

*24.10.11—Lecture 4 *Procedural Interpretation (slides 3, up to page 28). Terminology, SLD-Derivation step, Resolvent, Standardization apart, Computed Answer Substitution, some elements of arbitrarity, Resolution and propagation, similarity of SLD-derivations, answer substitutions and variants, selection rule, switching lemma, independence from the selection rule.

- Before the next lecture, revise the concepts, definitions, proofs.

*26.10.11—Lecture 5 *Procedural Interpretation (termination of slides 3) and Declarative Interpretation (slides 4, up to p.13). Interpretation and models: terminology, algebras, notions of interpretation, model, state, logical consequence,definition of Herbrand universe and Herbrand Base; examples.

- Before the next lecture, revise the concepts and definitions; the Exercise List 3 is now available.

*01.11.11—Tutorial 2 *Solutions and discussion on some of the proposed exercises in the List 2 (up to 2.6b), held by Amin.

- Before the next lecture, revise the concepts, definitions, proofs.

*15.11.11—Tutorial 3 *Solutions and discussion of the remaining exercises in List 2.

- Before the next lecture, please revise the basic algebraic concepts and terminology related to functions and functions composition; on the coming Friday we will start discussing solutions of the List 3.

*18.11.11—Tutorial 4 *Solutions and discussion of the exercises in List 3, up to 3.3 included.

- Before the next lecture, please revise the basic algebraic concepts and terminology related to functions and function composition as well as the material presented in lecture 5. The (small) Exercise List 4 is available, to help you revise lecture 5.

*23.11.11—Lecture 6 *Declarative interpretation (up to slide 30 included): term model, Herbrand model, Implication tree, correct answer vs computer answer, soundness and completeness of SLD-resolution.

- Before the next lecture, please revise the proofs of all technical results presented so far (redo them, trying to understand each formal step). The (small) Exercise List 5 is available, to help you revise lecture 6. As usual, you are strongly advised to try and solve the exercises.

*29.11.11—Tutorial 5 *Solutions and discussions of the remaining exercises in the List 3 (exercise 3.6: there is a typo in the text, the query is ?-double(s(0),Y), double(Y, s(s(s(s(0))))). Solutions and discussion of the List 4 (for the part c, only the interpretation I_1 has been presented).

- Before the next lecture, please revise all proofs of all technical results presented so far.

*30.11.11—Lecture 7 (and tutorial 6) *Declarative interpretation (completion of the group 4 of slides). Least Herbrand Model; Partially ordered sets, notions of lower/upper bound, least upper bound; operators on cpo's: monotonicity, finitarity, continuity; pre-fixed point,fixed point, and least fixed point (lfp); characterisation of the least Herbrand Model in terms of lfp(T_P). Examples. Sketch of solution of the exercise 3.6 and hints on how to proceed.

- Before the next lecture, please revise all proofs of all technical results presented so far. Notions about partial ordered sets and continuos, monotonic transformations on them are available (among the others) in John Lloyd: Foundation of Logic Programming (Springer Verlag, 1987). The Exercise List 6 is available.

*07.12.11—Lecture 8 *Pure Prolog (group 5 of slides) and extension with cut. Common uses of cut (group 6 of slides). Negation--Procedural interpretation (above, is the item 7 among the slides): preliminary definitions up to p. 7.

- For negation you might consider referring to the excellent survey by Apt and Bol.

*13.12.11—Tutorial 7 *Correction of the List 5 of exercises (up to 5.3 included).

*14.12.11—Lecture 9 *Negation--Procedural interpretation (above, is the item 7 among the slides, up to p. 28): (pre-)SLDNF-trees/derivations/resultants; notions of success, failure, floundering; problems with non-ground negative literals in queries; safe selection rule; allowed programs and queries; Prolog's choices.

- The Exercise List 7 is available. Please consider that the absence of a list of exercises about Pure Prolog is only motivated by the presence of the course LPE.

*19.12.11—Tutorial 8 *Correction of the List 5 of exercises (the remaining exercises); correction of the List 6 (up to Ex 6.2 included).

- Another tutorial has been agreed with the students in class; by lack of better time slots we have agreed to have another session today, at DS6, in room 2026.

*19.12.11—Tutorial 9 *Correction of the List 6 (the remaining exercises) and List 7.

*21.12.11—Lecture 10 *Negation--Procedural interpretation (presentation of the slides has been completed). Negation -- Declarative Interpretation: preliminary definitions, completion of a program, examples, dependency graph of a program, notions of hierarchy, strictness, even/odd dependency, stratification of program/query. Correspondence between SLDNF-computed answer and correct answers wrt to completion for ground and allowed queries/programs (up to page 20 included).

- The Exercise List 8 is available.

*04.01.12—Lecture 11 * Negation -- Declarative Interpretation (presentation of the slides has been completed). Completeness of SLDNF-Resolution in restricted forms of Programs and queries; definition of fair selection rule, extended consequence operator and characterisation of Herbrand models for extended program as pre-fixpoint and fixpoint of the extended consequence operator; examples of inadequancy of completion (open programs and looping programs); Herbrand Interpretations and models: supportedness, minimality, intended and non-intended models of a program, stratified programs, their standard models and their properties.

- Before the next lecture please revise the presented material, including proofs of theorems.

*10.01.12—Tutorial 10 *Correction of the List 8 (up to 8.3 included).

*11.01.12—Lecture 12 * Termination of Programs (above, is the item 9 among the slides, up to p.18 included) -- Motivations, examples of programs and queries that may or may not terminate, from the logic programming point of view and from the Prolog point of view. Some technicalities on multisets, multiset's ordering, König's lemma. Notion of level mapping for programs, recurrent programs, bounded queries, how to use the multiset ordering on bounded queries, examples, termination of SLD-derivations on recurrent programs and bounded queries.

- Before the next lecture please revise the presented material. You will find a more extended and technical presentation of this topic in the book by Apt.

The Exercise List 9 is available.

*24.01.12—Lecture 13 *Termination of Programs (group 9 of slides has been completed) -- Examples of recurrent programs and examples of why recurrence doesn't capture termination of Prolog programs. Acceptable programs wrt given |.| and given interpretation and bounded queries wrt given |.| and given interpretation. Examples. Relations between recurrent and acceptable programs.

- Before the next lecture please revise the presented material. You will find a more extended and technical presentation of this topic in the book by Apt.

The Exercise List 10 is available.

*25.01.12—Tutorial 11 *Correction of List of exercises 9 and of List of exercises 10 (ex. 1 only). We have agreed to complete the correction of the list 10 today, at 14:30 in room E005 (it will not take long). The FLP will be considered closed at the end of this meeting.

- Before the exam, revise all material and exercises. Remember that electronic devices are not allowed, in particular do not bring computers nor mobile phones. If you have them, you will be asked to switch them off and deposit them with the examiner: this will delay the start of the exam.

- In principle, all what has been covered and is listed in Lectures and topics.
- Modality of exam:
**written examination**. All written materials are allowed, no electronic devices. Id card and TUD registration card are necessary. - Venue: 7 February 2012, starting at 10:00am, duration 120 min, room E5 (and E6 should E5 not be sufficient), for the whole module.

Amin Timany contributes in the smooth running of the course. The Open house slot is a good venue for discussing your questions, and hopefully I can answer them. Otherwise just drop me an email and we'll arrange for an appointment.

25.01.12Paola Bruscoliemail (replace AT by @)