Module 02630 (2011)

Syllabus page 2011/2012

06-02630
Software Workshop Prolog

Level 2/I

Peter Hancox
10 credits in Semester 1

Links | Outline | Aims | Outcomes | Prerequisites | Teaching | Assessment | Books | Detailed Syllabus


The Module Description is a strict subset of this Syllabus Page. (The University module description has not yet been checked against the School's.)

Relevant Links

Module web page
Prolog teaching pages


Outline

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.


Aims

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

Learning Outcomes

On successful completion of this module, the student should be able to: Assessed by:
1judge for what applications and in what circumstances logic and Prolog programs are appropriate Examination
2read Prolog programs, for instance in technical literature which necessitates an understanding of Prolog in conveying its content Examination
3represent knowledge in the form of Prolog facts and rules Workshop assignments and examination
4write simple Prolog programs that can compute relations using facts and rules Workshop assignments and examination
5write Prolog programs to process and manipulate lists Workshop assignments and examination
6write larger Prolog programs, for instance a program to play a game Workshop assignments
7design Prolog programs to use a representations of knowledge and search in an efficient and appropriate manner Workshop assignments and examination

Restrictions, Prerequisites and Corequisites

Restrictions:

None

Prerequisites:

None

Co-requisites:

None


Teaching

Teaching Methods:

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

Contact Hours:

51 (11 hrs lectures, 40 hrs labs)


Assessment

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

Recommended Books

TitleAuthor(s)Publisher, Date
The course is supported by extensive WWW notes -- see links below.
Programming in Prolog for Artificial Intelligence (3rd edn)Bratko IAddison-Wesley, 2000
Programming in Prolog (4th edn)Clocksin W F & Mellish C SSpringer, 1995
The Craft of PrologO'Keefe R AMIT, 1990
Prolog programming in depthCovington M A, Nute D & Vellino APrentice Hall, 1996
The Art of Prolog (2nd edn)Stirling E & Shapiro LMIT, 1994

Detailed Syllabus

  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.

Last updated: 4 August 2009

Source file: /internal/modules/COMSCI/2011/xml/02630.xml

Links | Outline | Aims | Outcomes | Prerequisites | Teaching | Assessment | Books | Detailed Syllabus