# Derek Bridge

## Programming in Logic

• Context

This course was taught to second-year undergraduates on the University of York Computer Science Department's main computing B.Sc. degrees. It went through two incarnations: in 1994 and 1995 it was a single unit (18 hours of lectures) and entitled 'Programming in Logic'; in 1996 and 1997, it was merged with a single unit on functional programming, forming a double unit (36 lectures), entitled 'Declarative Programming'. The functional programming component was taught by Colin Runciman, while I taught the logic programmming. The version described below is (mostly) the original 'Programming in Logic' course.

• Lectures: 18*1 hr lectures
• Practicals: 8*1 hr practicals
• Private study: 63 hours (including revision)
• Assessment: 1.5 hr paper (excluding revision)
• Prerequisites

Logic, sets, relations, functions, recurrence, induction, simple programming in a conventional style.

• Assessment

A 1.5 hr closed paper worth 50 marks. A compulsory first question worth 10 marks, and then a choice of 2 from 4 questions each worth 20 marks.

• Description

A sequence of instructions to act upon a collection of stored variables is not the only way of expressing programs. This course examines a different approach in which programs declare properties of relations using conventional idioms of mathematics: logical formulae. The result is an elegant and powerful form of programming in which it is comparatively easy to reason about programs.

In logic programming, results are computed using a standard strategy of automated theorem-proving.

Example programs will include some drawn from the field of Artificial Intelligence, a field in which logic programming is in widespread use.

• Aims
• Students will understand the motivation for declarative programming.
• They will see how automated theorem-proving can form the basis of a style of programming language.
• They will learn the theory and practice of Prolog programming.
• They will see some of the special characteristics of Artificial Intelligence programs.
• Content
• (L1) Background and motivation: logic, logic programming and artificial intelligence.
• (L2-4) Pure Prolog: a rapid overview including recursion, recursive data structures (e.g. lists and trees), polymodality and non-determinism.
• (L5-9) The theory of logic programming: recap on predicate logic; clausal form; resolution; unification; resolution refutation; search strategies.
• (L10-18) The consequences of introducing negation; arithmetic (function or relation?); cuts; metaprogramming.
• Teaching resources
• Recommended books
• ++ Bratko,I: Prolog Programming for Artificial Intelligence (2nd edition), Addison-Wesley, 1990
• ++ Clocksin,W.F. and Mellish,C.S.: Programming in Prolog, Springer-Verlag, 1981
• ++ Flach,P.: Simply Logical, Wiley, 1994
• ++ Hogger,C.J.: Introduction to Logic Programming, Academic Press, 1984
• ++ Maier,D. and Warren,D.S.: Computing with Logic, Benjamin/Cummings, 1988
• ++ Nilsson,U. and Maluszynski,J.: Logic, Programming and Prolog, Wiley, 1990
• ++ Sterling,L. and Shapiro,E.: The Art of Prolog 2nd edition, The MIT Press, 1994