FLP

Z OI wiki

Verze z 11. 6. 2011, 09:24

Info o předmětu

(CZ) A4B33FLP - Funkcionální a logické programování

• Cvičící (CZ): Ing. Ondřej Kuželka; Ing. Lenka Nováková, Ph.D.
• Přednášející (CZ): Prof. RNDr. Olga Štěpánková, CSc.; Ing. Filip Železný, Ph.D.

(EN) AE4B33FLP - Functional and Logic Programming

• Přednášející (EN): Ing. Filip Železný, Ph.D.; RNDr. Jiří Vyskočil, Ph.D.
• Cvičící (EN): Radomír Černoch, MSc.

Pravidla předmětu

Odkaz na pravidla předmětu (bude doplněno)

Studijní materiály

• (CZ) Stránka předmětu na CourseWare
• (EN) Stránka předmětu na CourseWare

Zkoušky

Tohle mi odpovedel Vyskocil na dotaz, co bude z prvni poloviny anglicke verze FLP u zkousky (kdyby to nekoho zajimalo):

Dobry den,

 1) otazky na Haskell lze jiste u zkousky ocekavat, protoze byl
 probiran jak na prednasce tak na cviceni. Samozrejme, ze otazky se
 budou tykat pouze toho, co se probiralo.
 2) Lze ocekavat, ze vetsi duraz bude kladen na Scheme, protoze mu byla
 venovana vetsi pozornost.
 3) Protoze jsem funkcionalni programovani probiral hlavne prakticky,
 lze ocekavat, ze u zkousky se objevi hlavne prakticke otazky typu: "co
 dela nasledujici kod" nebo "napiste kod funkce dle pozadavku".

S pozdravem
Jiri Vyskocil

Exam 24.5.2011

Je to dost strucny, klidne to nekdo rozsirte... --Ondra "Kofolák" Jelínek 25. 5. 2011, 18:50 (UTC)

Rozšířeno, upraveno --Erik 11. 6. 2011, 09:24 (UTC). Text, který je kurzívou (hinty), nebyl součástí zadání.

--- Part I - Functional programming [25p] ---

Question 1.

Consider the following Scheme code:

(define foo
  (lambda (x)
    (cond ((null? (cdr x)) (car x))
          (else ((lambda (y)
                    (if (< (car x) y)
                        (car x)
                        y))
                (foo (cdr x)))))))

1. [5p] Write down an English description of foo function behaviour/functionality. (hint: specify also behaviour in marginal cases - empty list, one number)

2. [10p] Write down a Scheme code with only one function called w with the same behaviour as foo function but without using lambda keyword. (hint: use accumulator or let construction)

Question 2.

[10p] Write down a Haskell code of rotateMatrix function. The function rotateMatrix rotates an input matrix 90° to the right. The input and output matrices are represented as list of lists. (hint: very similar to matrix transposition, just reverse element order on each row)

Haskell type of rotateMatrix function:

rotateMatrix :: [ [a] ] -> [ [a] ]

Example:

Main> rotateMatrix [[1,2,3],[4,5,6],[7,8,9],[10,11,12]]
[[10,7,4,1],[11,8,5,2],[12,9,6,3]]

--- Part II - Logic programming [25p] ---

Question 3.

Given are the following clauses:

pass(S) :- clever(S).
pass(S1) :- next_to(S1,S2), pass(S2).
clever(trevor).
next_to(trevor,bob).
next_to(alice,carol).
next_to(X,Y):- next_to(Y,X).

(a) Consider the query

?-pass(bob).

i. [2p] How many proofs are there for this query? Explain your answer.

ii. [4p] Give one of the proof trees.

(b) Consider the query

?-pass(X).

i. [3p] Indicate all answers Prolog would find, and the order in which they are returned (duplicates included).

ii. [2p] Discuss two possible adaptations to Prolog's search strategy so that it would return all answers.

(c) [3p] Show that

pass(alice)

is not a logical consequence of this set of clauses. (hint: find model of P that is not model of pass(alice))

Question 4.

Consider the following problem. There are two jugs of 7 and 5 litres, initially empty, and an unlimited supply of water. There are three ways to change the amount of water in a jug:

1. a jug can be filled completely,
2. a jug can be emptied completely,
3. water can be poured from one jug into the other, until one jug is empty or the other is full.

(a) [3p] Sketch part of the search space, starting from the initial situation (0,0) (two empty jugs) and at least containing the situation (0,2), i.e., large jug is empty, small jug contains 2 litres of water.

(b) [4p] The following Prolog clauses represent part of the search space.

arc(s(X,Y),s(7,Y)) :- X<7.
arc(s(X,Y),s(X,5)) :- Y<5.
arc(s(U,V),s(0,Y)) :- U>0, Y is U+V, Y=<5.
arc(s(U,V),s(X,0)) :- V>0, X is U+V, X=<7.

Give the remaining 4 clauses.

Question 5. Definite Clause Grammar

Imagine you are going to write a user interface for a Prolog program, which stores information about the British Royal Family. For simplicity, there will be only two types of information stored in the database: properties of objects ("Charles is a man.") and relations between objects ("Charles is the father of William.").

The initial implementation stub is given to you in the form of Definite Clause Grammar (DCG):

person --> [william].
person --> [camilla].
person --> [charles].

(a) [2p] Using the non-terminal person above, declare a DCG capable of parsing and generating the following sentences.

[charles,is,a,man]
[camilla,is,a,woman]
[camilla,is,the,wife,of,charles]
[charles,is,the,father,of,william]
[charles,is,the,husband,of,camilla]

(b) [1p] (not complete) propagate predicates back

property(X,man(X)) --> [man].
...

(c) [1p] (not complete) make all relations irreflexive, so that:

?-phrase(sentence(X), [camilla, is, the, wife, of, camilla]).
false.

Zkouška ??.?.2011

...