- 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.
- Workload
- 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
- The following is an extensive set of worksheets (that blend tutorial
material
with exercises). Answers to the exercises are also given.
See also these
introductory remarks. All are either small gzipped Postscript files or small
plain text files. Hand-drawn diagrams are missing from the answers
to worksheets 9, 11 and 12.
Worksheet Answers Worksheet Answers WS1 Answ1 WS2 Answ2 WS3 Answ3 WS4 Answ4 WS5 Answ5 WS6 Answ6 WS7 Answ7 WS8 Answ8 WS9 Answ9a & Answ9b WS10 - WS11 Answ11 WS12 Answ12 WS13 Answ13 WS14 Answ14 WS15 Answ15 WS16 Answ16 - The following files are mentioned in the worksheets:
chez_henri edit haha shell1 translate dating evolution kbase shell2 unify derivative family primes shell3 zoo dpf flights river solve zum_fritz - Copies of overheads:
- Exam papers from the later Declarative Programming
incarnation
of the course (gzipped postscript):
- 95-96 (35k),
- 95-96(Resit) (32k),
- 96-97 (42k);
- 96-97(Resit) (48k).
- Students might find the following useful: The WWW Virtual Library: Logic Programming. Amongst much other useful stuff, it lists places where Prolog interpreters can be obtained. (There are other such lists, including a list in the CMU Repository and a list kept by the Software Composition Group at the University of Geneva.)
- The following is an extensive set of worksheets (that blend tutorial
material
with exercises). Answers to the exercises are also given.
See also these
introductory remarks. All are either small gzipped Postscript files or small
plain text files. Hand-drawn diagrams are missing from the answers
to worksheets 9, 11 and 12.
- 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