Week 45

Announcements

There is no official printed course book. I supply lecture notes covering the course on Blackboard under "Course Documents".

For the part on logic programming, the book Logic, Programming and Prolog can be obtained free of charge from the web site of Ulf Nilsson. This book covers the contents of the course from a more theoretical starting point.

For the part on functional programming, the book Real World Haskell is avilable from its website. This book covers the practical aspects of programming in Haskell and is a nice read in case you want to expand your practical command of Haskell.

Lecture Monday (07.11.2011)

The first lecture will start with a short introduction about programming languages focusing on the differences between imperative and declarative languages.

The main part of the lecture will be an introduction to the logic programming language Prolog.

Topics

course organization, declarative languages, facts, queries, rules

Reading

Chapter 1 and Section 2.1 in Lecture Notes in Blackboard (Course Documents)

Exercise Tuesday (08.11.2011)

The file family.pl contains a slightly extended version of the knowledge base from the lecture. That is, you can assume that the following predicates are fully defined:

• female(X) % true if X is female
• male(X) % true if X is male
• married(X,Y) % true if X is married to Y
• motherOf(X,Y) % true if X is the mother of Y
• diff(X,Y) % true if X and Y are instantiated with different objects

1) Write clauses that define the following predicates:

• fatherOf(X,Y) % true if X is father of Y
• parent(X,Y) % true if X is parent of Y
• siblings(X,Y) % true if X and Y are siblings
• sisters(X,Y) % true if X and Y are sisters
• isFather(X) % true if X is a father
• isMother(X) % true if X is a mother
• isSibling(X) % true if X is a sibling
• isBrother(X) % true if X is a brother
• granddad(X,Y) % true if X is grandfather of Y
• uncle(X,Y) % true if X is uncle of Y
• cousin(X,Y) % true if X is cousin of Y
• descendant(X,Y) % true if X is descendant of Y

2) Try to produce all answers of isMother(X). by repeatedly pressing semicolon. Do you see any answer ocurring more than once? What is the reason?

3) How does the behaviour of diff change if we replace \== by \= in its defining rule? Do your predicates using diff still work?

Lecture Thursday (10.11.2011)

The second lecture will formalize Prolog evaluation and focus on unification. At the end, we will introduce predicate logic.

Topics

Prolog evaluation, unification, Robinson's algorithm, termination of Robinson's algorithm, SLD tree, predicate logic

Reading

Section 2.2 and first subsection of Section 2.3 in Lecture Notes in Blackboard (Course Documents)

Lecture Friday (11.11.2011)

The third lecture will introduce SLD trees. Then we will look at the connection between predicate logic and logic programming. We will then introduce more advanced features of Prolog focusing on built-in data types and operations.

Topics

predicate logic, conversion to CNF, SLD resolution, arithmetics, lists, operators

Reading

rest of Section 2.3 and Sections 2.4-2.6 in Lecture Notes in Blackboard (Course Documents)