DOC

declarative programming exam 08

By Kenneth Alexander,2014-11-08 16:14
11 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 Check the search space (5 + 3 + 6 points)

The program union(L1,L2,UList) should store all the elements in the lists L1 and L2 in UList,

    i.e. the elements that can be found in the input lists should be included in UList. But if an

    element can be found in both lists only one instance of these should be in UList.

     a)

    union([],L,L).

    union([E|R],L2,L3):-

     member(E,L2),

     union(R,L2,L3).

    union([E|R],L2,[E|L3]):-

     union(R,L2,L3).

member(E,[E|R]).

    member(E,[F|R]):-

     member(E,R).

    Give all alternative answers that the program can give on the following question: ?- union([a,b],[a,c,e,g],UList).

    b) Rewrite the program in a declarative way so that only correct answers are generated when asking Prolog for alternative answers.

    c) Another way to make sure that only correct answers are generated, than the solution in b), is to use cut (i.e. !). Rewrite the program with cut and describe whether you have used a red or green cut. Describe the characteristics for red and green cut and utilise an example in the description.

    Good luck!

    from Anneli

Department of Information Science Computer and systems science

    Appendix with built-in predicates in Prolog < less than

    =< less than or equal to

    > greater than

    >= greater than or equal to

    = the two arguments can be unified =/= the two arguments cannot be unified X is Y X gets the value that the arithmetical expression Y has,

     Y must contain instantiated variables

    = = the two arguments are identical \== the two arguments are not identical X+Y addition

    X-Y subtraction

    X*Y multiplication

    X/Y division

    X//Y integer division

    X mod Y gives the rest from the division between X and Y integer(X) is true if X is an integer

    atom(X) is true if X is an atom

    atomic(X) is true if X is a number or an atom read(X) reads a term

    write(X) writes a term

    tab(X) gives X spaces when writing nl gives a new line

    open(File,Type,Stream) opens a file, Type gives read or write

    close(File) closes the file

    see(File) opens a file for reading or switches the input stream to File seen closes file

    tell(File) opens file for writing or switches the output stream to File told closes file

    listing(P) lists the predicate P

    assert(P) stores a predicate P

    retract(P) deletes a stored predicate P

    name(X,AsciiList) the relation between the term X and a list of Ascii-codes

     for the term.

    Ex: ?-name(abö,L) ger L=[97,98,124]

     ?-name(X,[97,46,99,33,63,44]) gives X=a.c!?, bagof(X,P(X),L)

    The first argument decides the elements in the output list, the second is the question, and the third

    is the list with the answers

    findall(X,P(X),L)

    The predicate works like bagof except that all variables in P are existentially quantified

    setof(X,P(X),L)

Department of Information Science Computer and systems science

The predicate works like bagof with the addition that the elements in L are sorted and duplicate items

are deleted.

Report this document

For any questions or suggestions please email
cust-service@docsford.com