DOC

declarative programming exam 08

By Kenneth Alexander,2014-11-08 16:14
14 views 0
declarative programming exam 08

Department of Information Science Computer and systems science

    Declarative problem solving methods 7.5 hp

    Written exam 2008-09-30

Task 1 Problem solving (6 points)

    During the course we have mainly used the problem solving methods “divide-and-conquer” and

    “generate-and-test”. Describe these two methods. Discuss the advantages and disadvantages you can see when utilising them in a declarative programming language such as Prolog.

Task 2 Unification (8 points)

    Check whether the predicate pairs can be unified. If the unification succeeds show the

    instantiations, i.e. the variable values. If the unification is unsuccessful explain the reason to this.

a) info(X,a,Z,b) = info(Y,Z,Y,W).

b) data(f(X),Y,f(Z)) = data(Y,a,f(5)).

c) data(X,p(X),Z,4) = data(d(8,10),Y,W,W).

d) data(Y,p(X),a) = data(p(X),p(Y),Z).

e) info(X,Y,f(Z)) = info(5,f(X),Y).

f) lists(L,[1,2,3],N) = lists([a,b],[E,F|G],[X|L]).

g) lists([a,b],p([1,2],3)) = lists(L,p(X,Y,Z)).

h) lists(L,[1,2,3],N) = lists([a,b],[E|[G,H]],[L|[]]).

Department of Information Science Computer and systems science

    Task 3 Rewrite programs (8 + 8 points)

    Update the given programs so they follow the given definitions.

    a) Write a program add_elements(L1,L2,L3) that takes two lists, L1 and L2, and generates a new list with numbers, L3. The new list’s elements should be the sum of the two elements in the

    same position in the given lists L1 and L2. One list may have more elements than the other. In

    that case the end elements in the longer list should be included in L3.

Ex:

    ?- add_elements([1,2,3],[4,5],L3).

    L3 = [5,7,3]

?- add_elements([1,2,3],[4,5,6,7,8],L3).

    L3 = [5,7,9,7,8]

add_elements([],[],[]).

    add_elements([],[E|R],R3):-

     add_elements([],R,R3).

    add_elements([E1|R1],[E2|R2],R3):-

     E3 is E1 + E2,

     add_elements(R1,R2,[E3|R3]).

b) The recursive program store_odd_numbers(L1,L2) should store the odd numbers in list L1

    in the list L2. Update the program so it follows the given definition. Note, that the program

    should be written in a declarative way, i.e. every Horn clause should contain all necessary

    conditions.

?- store_odd_numbers([12,3,5,8,9],L).

    L = [3,5,9] ? ;

    no

store_odd_numbers([],Lista).

    store_odd_numbers([A,B],[A]).

    store_odd_numbers([E|Rest],Lista):-

     0 is E mod 1,

     store_odd_numbers(Rest,[E|Lista]).

Department of Information Science Computer and systems science

    Task 4 Work with text (11 points)

    The letters å, ä and ö are quite frequently used in Swedish texts. How frequently are they used? Take a text and calculate the mean value of these letters in relation to all letters in the text. Both lower case and upper case letters should be taken into account. The mean value should be calculated in relation to other letters. This means that the characters that are not letters should not be counted. The program should write the mean value and the text according to the given format.

?- swedish_letters.

    Mean value is 0.0796 of å, ä and ö in the text:

    Du gamla, du fria, du fjällhöga nord. Du tysta, du glädjerika sköna!

    Jag hälsar dig, vänaste land uppå jord, din sol, din himmel, dina ängder gröna.

Ascii-code for upper case letters, except Å, Ä and Ö, are in the interval 65 90. Ascii-code for

    lower case letters, except å, ä and ö, are in the interval 97-122.

Assume that the predicate ascii_code(Letter,Ascii) is given and the text is stored in the

    predicate text(T).

ascii_code('å',229).

    ascii_code('ä',228).

    ascii_code('ö',246).

    ascii_code('Å',197).

    ascii_code('Ä',196).

    ascii_code('Ö',214).

% The first verse in the Swedish national anthem.

    text(‘Du gamla, du fria, du fjällhöga nord

    Du tysta, du glädjerika sköna!

    Jag hälsar dig, vänaste land uppå jord,

    din sol, din himmel, dina ängder gröna.’).

Department of Information Science Computer and systems science

    Task 5 Work with a database (5 + 3 + 5 + 4 + 5 + 5 points)

The following database describes some typical Swedish dishes. Furthermore, it describes the

    ingredients that can be found at home for the moment.

:- dynamic dish/4.

    % dish(Swedish_name,English_name,List_of_ingredients,Time_for_cooking)

    dish('Köttbullar','Meat-balls',['minced meat', salt, pepper, egg,

     'brown dried', onion, water], time(30,minutes)).

    dish('Biff a la Lindström','Beef a la Lindström',['minced meat', cream, onion,

     capers, 'pickled beetroot', salt, pepper], time(40,minutes)). dish('Gravad lax','Raw spiced salmon',[salmon, salt, pepper, sugar, dill],

     time(2,days)).

    dish('Köttfärssås','Mincedmeat sauce',[tomato, onion, 'minced

     meat', salt, pepper, sugar, paprika], time(40,minutes)).

    dish('Dillkött','Mutton with dill sauce', [lamb, salt, pepper, onion, carrot, cream, dill, sugar, vinegar], time(100,minutes)).

% at_home(Ingredient)

    at_home(water).

    at_home(salt).

    at_home(pepper).

    at_home(egg).

    at_home(paprika).

    at_home(sugar).

    at_home(vinegar).

    at_home(onion).

a) Write a program that gives the Swedish name for a dish that contains a special ingredient, e.g.

    minced meat.

?- dishname('minced meat',SName).

SName = 'Köttbullar' ? ;

    SName = 'Biff a la Lindström' ? ;

    SName = 'Köttfärssås' ? ;

    no

    b) Give a list of all the dishes in Swedish that contains onion.

c) Make a shopping list for a special dish when the name is given in English. Do not put the

    ingredients that you have at home on the list.

?- shoppinglist('Raw spiced salmon', List).

    List = [salmon, dill] ? ;

    no

Department of Information Science Computer and systems science

Department of Information Science Computer and systems science

    d) Present all the English names on dishes that can be cooked in 40 minutes, or less, in a list.

    e) It should be possible for the user to change the list of ingredients related to a dish given in English by putting a new ingredient in the list and then store the new information in the database. The new ingredient should be included last in the list. The old information should of course be abolished.

?- new_ingredient(garlic,'Mincedmeat sauce'),listing(dish).

    :

    dish('Köttfärssås', 'Mincedmeat sauce', [tomato, onion,

     'minced meat', salt, pepper, sugar, paprika, garlic], time(40,minutes)).

    f) It should also be possible for the user to change a dish, given in English, by taking away an ingredient in the list of ingredients. The new information should be stored and the old taken away.

?- take_away_ingredient(garlic,'Mincedmeat sauce'),listing(dish).

    :

    dish('KöttfärssÅs', 'Mincedmeat sauce', [tomatoes, onion,

     'minced meat', salt, pepper, sugar, paprika], time(40,minutes)).

Task 6 Trace a Prolog program (8 + 3 + 7 points)

check([],1).

    check([F|Rest],X):-

     l(F),!,

     check(F,A),

     check(Rest,B),

     X is A + B.

    check([F|R],X):-

     check(R,X).

l([]).

    l([_|_]).

a) If we ask the program the following, which value does the variable Answer get?

    ?- check([[a],b,[c,d,[]],e],Answer).

b) Explain in words what the program performs.

    c) Is the program tail recursive? Justify your answer. If the program is not tail recursive, is it possible to rewrite to become that? In that case, explain in words how this can be done.

Department of Information Science Computer and systems science

    Task 7