About
This course explores the use of "declarative languages" for programming. Such programming languages enable specifying the characteristics of a solution to a problem, rather than specifying the steps that have to be followed to come to this solution. The system itself will find the solution using a general-purpose problem solving procedure. In most declarative programming languages, the problem is specified by means of assertions in a logic. The problem solving strategy is a proof procedure which can be queried for answers that follow from the assertions. We will explore the theoretical underpinnings of the declarative programming paradigm, the diveristy among the programming languages that different logics and proof procedures gives rise to and their applications in the domain of artificial intelligence for which they are particulary well-suited.
The official course description can be found here and here.
The exam consists of an oral test with written preparation about the entire course (theory and exercises) and an oral defense of an individually completed programming project. The end result is calculated as the average of the results on both parts. If one of both results is 7 or less, however, the end result cannot exceed 7.
When and Where
The theory is lectured every Wednesday from 13:00 till 15:00 in room D.2.19 (in room F.4.104 on the 1st of December).
The exercise sessions are organized after the lectures (from 15:00 till 17:00) of October 6th, 13th, 20th, 27th and November 3rd in room E.1.2.
Course Material
Peter Flach, "Simply Logical: Intelligent Reasoning by Example", J. Wiley & Sons, 1994 , ISBN 0471 94152 2
This book is currently out of print, but available for free on-line.
The material for the individual lectures can be found below (or here as one large [PDF] or one with 4 slides per page [PDF]).
- Introduction
-
Completed on 29/09/2010
- Slides: introduction [PDF]
- Programs: London underground [PL], deterministic finite automaton [PL], non-deterministic finite automaton [PL], non-deterministic pushdown automaton [PL], Visualising terms and SLD trees with Graphviz (highly recommended)
- Further reading: Chapter 1 of Simply Logical, The Birth of Prolog, The Early Years of Logic Programming, Aspects of Prolog History, The Fatal Choice
- Theoretical Backgrounds
- Completed on 13/10/2010
- Slides: propositional clausal logic [PDF], relational clausal logic [PDF], full and definite clausal logic PDF
- Further reading: Chapter 2 of Simply Logical, the 1974 paper by Kowalski on "Predicate logic as a programming language", Appendix A.1 of Logic, Programming and Prolog is an interesting read on the historical development of the foundations of logic programming which are discussed in Chapters 2 and 3 of the book, an alternative in-depth treatment of the same foundations can be found in Chapter 4 of From Logic Programming to Prolog, lectures 1 till 7 of this Stanford course on logic can be used to refresh results from elementary logic.
- Logic programming and Prolog
- Completed on 3/11/2010
- Slides: SLD-resolution refutation, pruning the search, negation as failure [PDF], tail recursion optimization, arithmetic, difference lists, second-order predicates, failure-driven loops [PDF], higher-order programming, inspecting terms, extending Prolog (through term expansion, custom operators and meta-interpretation), a methodology for logic programming [PDF], revisiting the Eliza classic in Prolog [PDF]
- Further reading: Chapter 3 of Simply Logical, The Logic Programming Paradigm and Prolog is highly recommended as it summarizes the above from an alternative point of view, A couple of meta-interpreters in Prolog
- Blind and informed search through state spaces and proving as a search process
- Completed on 10/11/2010
- Slides: depth-first and breadth-first search through state spaces, agenda-based meta-interpreters for Prolog, forward chaining [PDF], informed search [PDF]
- Further reading: Chapters 4,5,6 of Simply Logical, environmentally-friendly solution to the water-jugs problem (features a natural language interface implemented through a DCG), LegoLog for a Prolog-based planner for Lego Minstorms robots, those interested in forward chainers and expert systems should check out the on-line Building Expert Systems in Prolog, Space Invaders Enterprise Edition of which the game logic is implemented declaratively using forwardly-chained rules
- Slides: [PDF]
- Further reading: Chapter 7 of Simply Logical, for those interested in natural language processing: Sections 2.7 and 3.7 of the digital edition of the book Prolog and Natural Language Analysis, for those interested in parsers and compilers for programming languages: the 1987 paper Parsing and Compiling Using Prolog
- Slides: meta-interpreters for programming with quantified and qualified truth, programming with constraints on integer domains, implicit parallel evaluation, software engineering applications [PDF]
Additional Material
- I maintain a list of logic programming links on delicious.
- The Prolog Dictionary is valuable resource for starting logic programmers.
- Your programming project is likely to benefit from these Coding Guidelines for Prolog. Refactoring for Prolog Programs lists some interesting refactorings for Prolog (e.g., renaming a predicate, reordering its arguments, replacing particular uses of cut by if-then-else) that can improve the readibility, structure and even the performance of your code. ViPress automates these refactorings as a plugin for the VIM editor.