Week 47

Lecture Tuesday (23.11.2010)

The fifth lecture will start with a short introduction to constraint logic programming. Then we will continue with an introduction to Haskell. Here, we will focus on the basics of function declarations and pattern matching.

Topics

functional programming, function declarations, pattern matching

Reading

Lecture Notes in Blackboard (Course Documents)

Exercise Wednesday (24.11.2010)

1) The third lecture showed how to transform any formula in predicate logic into an equisatisfiable formula into CNF where all variables are universally quantified from the outside. Apply these transformation steps to a formula that corresponds to answering the query ?- member(X,[3,1,2]) given the following logic program:

member(X,[X|Xs]).
member(X,[Y|Ys]):- member(X,Ys).

2) The fourth lecture introduced the cut operator. Consider the following logic program:

a :- b, c.
a :- b.
b.
b.
c :- e.
c :- e, b, f.
c :- b.
e :- fail.
e.
f.
f.
f.

Draw the SLD tree and indicate all finite failures.
Now change the 6th clause from c :- e, b, f. to c :- e, b, !, f. and indicate all branches that are cut.

3) Implement the programs from Tasks 4 and 5 of the previous weekly notes and use the cut operator where it makes sense.

4) Consider the following Prolog program (introduced exactly like this in lecture notes for DM509 at least 3 years old):

income(peter,400000).
foreigner(peter).
average_taxpayerWrong(X) :- foreigner(X), fail.
average_taxpayerWrong(X) :- income(X,I), I < 500000.

Here, fail/0 is used to force a finite failure. The query ?- average_taxpayerWrong(peter). should clearly fail since Peter is a foreigner. Why does it not fail? How can you repair the program such that it works as one would expect?

Shorten the program to three clauses by having just one clause for average_taxpayer/1 and keeping the clauses for income/2 and foreigner/1.

5) Write definitions for a predicate divide/3 that performs division of natural numbers. For example, the query ?- divide(13,3,D) should yield the answer D = 4. Use a generate-and-test approach, i.e., use a predicate is_nat/1 defined as follows:

is_nat(0).
is_nat(X) :- is_nat(Y), X is Y+1.

Calling is_nat/1 with a variable as the argument will successively enumerate all natural numbers by backtracking. Now, define a predicate that tests whether a given natural number is a solution to the division problem. Finally, define divide using the generating predicate and the test.

6) A program that uses "," for conjunction and ";" for disjunction can always be written only using "," for conjunction. Discuss how to transform a clause with a right-hand side that is an arbitrary Boolean expression using "," and ";" step by step to a number of clauses that yield the same behaviour.

Apply your transformation to the following clause:

f(X,Y) :- X =:= 0, Y = 0; X > 0, (X > 1, X1 is X-1, X2 is X-2, f(X1,Y1), f(X2,Y2), Y is Y1+Y2; X =:= 1, Y is 1).

Simplify the resulting clauses. What does f actually compute?

Exercise Friday (26.11.2010)

1) Read Section 2.8 (Input/Output) in the lecture notes. Follow the example both with user interactions and with files.

Write a program that asks the user for a query until the user inputs stop. and executes each query. The user should then be informed whether the query succeeded or not.

2) Read Section 2.9 (Constraint Programming) in the lecture notes. Follow the SEND+MORE=MONEY example.

Then apply constraint programming to find a 3x3 magic square. Here, a nxn magic square is a field where each cell has a different number from 1 to nxn, but all rows and columns have the same sum.

Find a more magic square by adding constraints for the diagonals.

How can you change your logic program such that it can find magic squares of any given size?

Design by 1234.info | Modified by Peter Schneider-Kamp | CSS 2.0