School of Computer Science

Module 06-25433 (2012)

Logic Programming

Level 2/I

Peter Hancox Semester 1 10 credits
Co-ordinator: Peter Hancox
Reviewer: Manfred Kerber

The Module Description is a strict subset of this Syllabus Page.

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 and alternatives such as concurrent logic programming and constraint logic programming

Learning Outcomes

On successful completion of this module, the student should be able to:

  • 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
  • demonstrate an understanding of the principles underlying Prolog, logic programming and its implementation and its extension to constraint logic programming

Teaching methods

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


Assessment

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

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 section 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.
  10. Beyond Prolog
    • to include one or more topics that show the logical foundations of logic programming, concurrent implementations of logic programming, and the extension of unification in constraint logic programming.

Programmes containing this module