Module 02630 (2011)
Syllabus page 2011/2012
Software Workshop Prolog
The Module Description is a strict subset of this Syllabus Page. (The University module description has not yet been checked against the School's.)
The course consists of taught material and practical work. The taught material introduces the fundamentals of the Prolog programming language. Practical work consists of programming exercises in Prolog. Early exercises are designed to develop a core understanding of programming in Prolog, especially: the importance of unification in the understanding of Prolog; the nature of search in Prolog and alternative search strategies; common recursive program structures, especially for list processing; design of Prolog programs. Later exercises are designed to develop skills in applying Prolog in practical situations.
The aims of this module are to:
- 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
|On successful completion of this module, the student should be able to:||Assessed by:|
|1||judge for what applications and in what circumstances logic and Prolog programs are appropriate||Examination|
|2||read Prolog programs, for instance in technical literature which necessitates an understanding of Prolog in conveying its content||Examination|
|3||represent knowledge in the form of Prolog facts and rules||Workshop assignments and examination|
|4||write simple Prolog programs that can compute relations using facts and rules||Workshop assignments and examination|
|5||write Prolog programs to process and manipulate lists||Workshop assignments and examination|
|6||write larger Prolog programs, for instance a program to play a game||Workshop assignments|
|7||design Prolog programs to use a representations of knowledge and search in an efficient and appropriate manner||Workshop assignments and examination|
1 hr lectures/tutorials per week, 4 hrs/week laboratory work.
- Sessional: 1.5 hr examination (80%), continuous assessment (20%).
- Supplementary (where allowed): By examination only.
|The course is supported by extensive WWW notes -- see links below.|
|Programming in Prolog for Artificial Intelligence (3rd edn)||Bratko I||Addison-Wesley, 2000|
|Programming in Prolog (4th edn)||Clocksin W F & Mellish C S||Springer, 1995|
|The Craft of Prolog||O'Keefe R A||MIT, 1990|
|Prolog programming in depth||Covington M A, Nute D & Vellino A||Prentice Hall, 1996|
|The Art of Prolog (2nd edn)||Stirling E & Shapiro L||MIT, 1994|
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
- 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.
- 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.
- 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.
- 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.
- 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.
- Writing and debugging programs
- designing programs top-down;
- building programs bottom-up;
- testing procedures bottom-up;
- diagnosis of typical programming bugs.
- 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.
- 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.
Last updated: 4 August 2009
Source file: /internal/modules/COMSCI/2011/xml/02630.xml