Module 06-02630 (2011)

• give an appreciation of a declarative programming paradigm as an alternative the imperative programming paradigm as represented by, for instance, C++ and Java
• introduce the basic concepts and terminology of logic programming
• introduce Prolog as the most common practical implementation of a logic programming language

• judge for what applications and in what circumstances logic and Prolog programs are appropriate
• read Prolog programs, for instance in technical literature which necessitates an understanding of Prolog in conveying its content
• represent knowledge in the form of Prolog facts and rules
• write simple Prolog programs that can compute relations using facts and rules
• write Prolog programs to process and manipulate lists
• write larger Prolog programs, for instance a program to play a game
• design Prolog programs to use a representations of knowledge and search in an efficient and appropriate manner

1 hr lectures/tutorials per week, 4 hrs/week laboratory work.

• Sessional: 1.5 hr examination (80%), continuous assessment (20%).
• Supplementary: By examination only.

1. An overview of Prolog including:
   • the execution of a basic non-deterministic program showing the role of the stack exploration of alternative solutions binding of variables
   • a discussion of the consequences of Prolog's execution strategy for: search strategy unification
2. Writing and running simple Prolog programs. Topics covered include:
   • writing basic facts;
   • querying facts, without and with unbound variables;
   • querying more than one fact at a time;
   • writing basic rules;
   • writing recursive rules;
   • what happens to variables in queries;
   • the distinction between deterministic and non-deterministic rules.
3. Using recursion in programs. The topic of session 1 is revisited to explore Prolog's use of the stack in executing deterministic and non-deterministic recursive programs and to introduce tail recursion optimisation.
   • basic (singly) recursive procedures, for instance to describe family trees;
   • doubly recursive procedures, for instance to compute Fibonacci numbers and to explore binary trees.
4. Elementary list processing
   • unification of lists, including the unification of lists within lists;
   • three basic patterns of processing lists: terminating at the end of the list; terminating when a given element is found; terminating when a given number of elements have been scanned.
5. Less elementary list processing. A number of topics including:
   • processing lists within lists;
   • changing the order of clauses in a procedure to alter the order in which elements are processed;
   • using accumulators for efficiency;
   • using open-ended ("difference") lists.
6. Prolog's execution strategy explained more precisely. The Prolog engine includes several methods of optimisation that make programs run more quickly. Experienced programmers deliberately take advantage of these optimisations to write more efficient programs. The topics presented include:
   • revision of the elementary Prolog execution strategy;
   • optimisations to the elementary model based on determinism;
   • optimisations to the elementary model based on indexing;
   • exploiting determinism and indexing;
   • proper use of the cut and the if...then...else construct.
7. Writing and debugging programs
   • designing programs top-down;
   • building programs bottom-up;
   • testing procedures bottom-up;
   • diagnosis of typical programming bugs.
8. Definite Clause Grammar. Context-Free Grammar (CFG) is introduced as a way of writing rules about structured knowledge. Definite Clause Grammar (DCG) is Prolog's in-built notation for writing CFGs. Writing DCGs is introduced showing: DCGs suffer from problems with left-recursive rules. DCGs are a general programming tool with applications beyond language parsing.
   • the basic framework;
   • adding arguments for agreement;
   • embedding calls to ordinary Prolog;
   • building structures.
9. Applications of Prolog: logical inference. This lecture will cover:
   • writing "user-friendly" rules in Prolog using operator declarations;
   • making logical inferences from new facts;
   • providing an interface to the inference engine using a DCG.