/******************************************************************************* Report Example Gunnar Gotshalks 2014 September 29 This document describes the work done in completing the tasks as specified in "Example Specification" that can be found in at the following URL. http://www.eecs.course_archive/2013-14/W/3401/ and then following the link "Examples, exam questions and Prolog programs" from the "Resources" page. *******************************************************************************/ /******************************************************************************* Exercise 1 A manual trace of the following suffix function of the query suffix(S, [1, 2, 3]) Rule 1: suffix(S, [_ | L]) :- suffix(S, L). Rule 2: suffix(L, L). ---------------------------------------- Goal 1: suffix(S, [1, 2, 3]) Try to match Rule 1 S = S_1 [1, 2, 3] = [_ | L_1] The match succeeds with L_1 = [2, 3] Try the subgoal suffix(S_1, L_1) with the substitution of L_1 becomes suffix(S_1, [2, 3]) ---------------------------------------- Goal 2: suffix(S_1, [2, 3]) Try to match Rule 1 S_1 = S_2 [2, 3] = [_ | L_2] The match succeeds with L_2 = [3] Try the subgoal suffix(S_2, L_2) with the substitution of L_2 becomes suffix(S_2, [3]) ---------------------------------------- Goal 3: suffix(S_2, [3]) Try to match Rule 1 S_2 = S_3 [3] = [_ | L_3] The match succeeds with L_3 = [] Try the subgoal suffix(S_3, L_3) with the substitution of L_3 becomes suffix(S_3, []) ---------------------------------------- Goal 4: suffix(S_3, []) Try to match Rule 1 S_3 = S_4 [] = [_ | L_4] The match fails on the second argument, the empty list is not equal to a list with at least one member. Try to match Rule 2 S_3 = L_5 [] = L_5 The match succeeds with S_3 = []. There are no further subgoals so back substitute the value of S_3 in Goal 3. S_2 = S_3 and S_3 = [] Therefore S_2 = []. There are no further goals so back substitute the value of S_2 in Goal 2. S_1 = S_2 and S_2= [] Therefore S_1 = [] There are no further goals so back substitute the value of S_1 in Goal 1. S = S_1 and S_1= [] Therefore S = [] and Prolog prints the result. *******************************************************************************/ /******************************************************************************/ /******************************************************************************/ /******************************************************************************* Exercise 2.1 The predicate prefix(Prefix, List) asserts that Prefix is a prefix of List. Require: Prefix and List are lists. Ensure: forall j : 1.. #Prefix :: Prefix[j] = List[j] ****************************************/ % Base case: the empty list is a prefix of any list. prefix([], _). % Recursive case: the first item of Prefix must be the first item of List % and the rest of Prefix is a prefix of the rest of List. prefix([A | B], [A | C]) :- prefix(B, C). /**************************************** Test cases for prefix The names of the tests are the test description. ****************************************/ :- begin_tests(e2_1). test(empty_list_is_prefix) :- prefix([],[1,2,3,4,5,6,7]). test(first_element_is_prefix) :- prefix([1], [1,2,3,4,5,6,7]). test(partial_list_is_prefix) :- prefix([1,2,3,4], [1,2,3,4,5,6,7]). test(all_but_one_is_prefix) :- prefix([1,2,3,4,5,6],[1,2,3,4,5,6,7]). test(whole_list_is_prefix) :- prefix([1,2,3,4,5,6,7],[1,2,3,4,5,6,7]). test(missing_first_is_not_prefix, [fail]) :- prefix([2,3,4,5,6,7],[1,2,3,4,5,6,7]). :- end_tests(e2_1). /******************************************************************************/ /******************************************************************************/ /******************************************************************************/ /******************************************************************************* Exercise 2.2 The predicate sla(Sublist, List) asserts that Sublist is a sub-list of List. The definition uses the built-in predicate append. Require: Sublist and List are lists. Ensure: forall j : 1.. #Sublist :: Sublist[j] = List[#List - #Sublist + j] ****************************************/ % Sublist is a sub-list of List if a list P can be prefixed to Sublist and % a list S can be suffixed to Sublist to form List. % List = P || Sublist || S % The anonymous variable is used for P and S, as they are singletons in the % definition. sla(Sublist, List) :- append(_, Sublist, Lt) , append(Lt, _, List). /**************************************** Test cases for sla The names of the tests are the test description. The predicate sla will run forever trying all possible choice for prefix and suffix, which are unbounded in number. As a consequence, findall and all cannot be used to eliminate choicepoints. ****************************************/ :- begin_tests(e2_2). /* Note that the following test ends with a warning that the test succeeded with choicepoint, which means that if the test query was done interactively Prolog would give you the choice of entering ';' or 'cr', indicating that Prolog could continue searching for another answer. */ test(empty_list_is_sublist) :- sla([],[1,2,3,4,5,6,7]). /* All of the following tests will also end with a choicepoint. To eliminate the warning the parameter '[nondet]' is added to the test query. */ test(first_element_is_sublist, [nondet]) :- sla([1], [1,2,3,4,5,6,7]). test(partial_start_is_sublist, [nondet]) :- sla([1,2,3,4], [1,2,3,4,5,6,7]). test(all_but_one_is_sublist, [nondet]) :- sla([1,2,3,4,5,6],[1,2,3,4,5,6,7]). test(whole_list_is_sublist, [nondet]) :- sla([1,2,3,4,5,6,7],[1,2,3,4,5,6,7]). test(all_but_first_is_sublist, [nondet]) :- sla([2,3,4,5,6,7],[1,2,3,4,5,6,7]). test(partial_end_is_sublist, [nondet]) :- sla([2,3,4,5,6,7],[1,2,3,4,5,6,7]). test(last_is_sublist, [nondet]) :- sla([7],[1,2,3,4,5,6,7]). :- end_tests(e2_2). /******************************************************************************/ /******************************************************************************/ /******************************************************************************/ /******************************************************************************* Exercise 2.3 The predicate sublist(Sublist, List) asserts that Sublist is a sub-list of List. The definition uses the previously defined predicate prefix. Require: Sublist and List are lists. Ensure: forall j : 1.. #Suffix :: Suffix[j] = List[#List - #Suffix + j] ****************************************/ % Base case: A prefix of a list is a sublist. sublist(Sublist, List) :- prefix(Sublist, List). % Recursive case: Sublist is a sub-list of a List if it is a sub-list of all % but the first of List. sublist(Sublist, [_ | List]) :- sublist(Sublist, List). /**************************************** Test cases for sublist. The predicate sublist does not run forever. As a consequence, findall can be used to enumerate all cases for a small list. ****************************************/ :- begin_tests(e2_3). test(all_sublists) :- findall(S, sublist(S, [1,2,3]), AllSubLists) , AllSubLists = [[],[1],[1,2],[1,2,3],[],[2],[2,3],[],[3],[]]. :- end_tests(e2_3). /******************************************************************************/ /******************************************************************************/ /******************************************************************************/ /******************************************************************************* Exercise 3 The predicate total(NumberList, Total) asserts that Total is sum of all the numbers in NumberList. Require: NumberList is a list of numbers. Ensure: Total = +/NumberList ****************************************/ % Base case: An empty list has a total of 0. total([], 0). % Recursive case: Total is the sum of the first number in NumberList plus % the total of the rest of NumberList. total([FirstNumber | RestOfNumberList], Total) :- total(RestOfNumberList, TotalRest) , Total is FirstNumber + TotalRest. /**************************************** Test cases for total ****************************************/ :- begin_tests(e3). % The total for an empty list should be 0. test(empty_list_total) :- total([], 0). % The total for list of length 1 should be the only number in the list. test(length_one_total) :- total([3], 3). % The total of a length many list should be the total of all the numbers in the % list. test(length_many_total) :- total([1,2,3,4,5], 15). :- end_tests(e3). /******************************************************************************/ /******************************************************************************/ /******************************************************************************/ /******************************************************************************* Exercise 4 The predicate strange_swap(Numbers_1, Numbers_2, Smaller, Bigger) that asserts that the smaller of each pair of corresponding numbers in the numbers lists is put into Smaller and the larger of the pair is put into Bigger) Regroup the numbers from two equal length lists such that for corresponding pairs the m Require: Numbers_1 and Numbers_2 are equal length lists that contain only numbers. Ensure: The numbers in both lists are rearranged as in the preceding statment. ****************************************/ /* Base case: both number lists are empty means the two result lists are also empty. */ strange_swap([],[], [], []). /* Recursive case 1: The first number in the first list is less than or equal to the first number in the second list, so place the number in the first list into the smaller list and the other number in the bigger list. */ strange_swap([Hn1 | Tn1], [Hn2 | Tn2], [Hn1 | Ts], [Hn2 | Tl]) :- Hn1 =< Hn2, strange_swap(Tn1, Tn2, Ts, Tl). /* Recursive case 2: The first number in the first list is greater than the first number in the second list, so place the number in the first list into the bigger list and the other number in the smaller list. */ strange_swap([Hn1 | Tn1], [Hn2 | Tn2], [Hn2 | Ts], [Hn1 | Tl]) :- Hn1 > Hn2, strange_swap(Tn1, Tn2, Ts, Tl). /**************************************** Test cases for strange_loop: No tests have been written ****************************************/