Programming Homework #4 Solution

This section deals with general submission instructions.




First, grab this assignment from the site. BEFORE MOVING ON RENAME hw4S19.asn to hw4.pl.




You will be able to code in and run the file in the Prolog interpreter directly.




I recommend reading this assignment directly from the source file.




We will be using swipl for our Prolog environment: To load/reload this file, cd to its directory and run swipl. Then, in the prompt, type [hw4].




cd PATH_TO_FILE




swipl




[hw4].




From then on you may execute queries (goals) in the prompt. As usual, you should provide your answers in the designated spot. Once you have added some code to the file, rerun [hw4]. in the swipl prompt to reload.




In addition, there are unit tests for each problem. These are there to help you better understand what the question asks for, as well as check your code. They are included in our "database" as queries and are initially commented out -- % is a Prolog line comment.




%:- member_times(4,[3,3,2,3],0). % SUCCEED




%:- member_times(4,[1,2,3],3). % FAIL




After you have finished a problem and are ready to test, remove the initial % for each test for the associated problem and reload the assignment file ([hw4].). Each SUCCEED line should silently load and succeed, and each FAIL line should throw a WARNING. If a SUCCEED line throws a WARNING, or a FAIL line fails to, then you solution is not correct. If you pass the tests there is a good chance that your code is correct, but not guaranteed; the tests are meant as guided feedback and are not a check for 100% correctness. */




/* Submission */




/*Please store hw3.pl within a tarball named username_hw3.tar.gz */




/* Homework 4 */




/* Due: Wed , 2/20 at 11:59 PM */




/* Purpose: To get comfortable with backtracking, recursion, become familiar with reflective mechanism of Prolog, and Prolog as a symbolic programming language.




*/




my_append([],Ys,Ys).




my_append([X|Xs],Ys,[X|Zs]) :- my_append(Xs,Ys,Zs).




my_prefix(_,[]).




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




/* Problem 0A (NOT GRADED):




Using the preceding predicates, draw the execution trees for the following queries (goals). You should also enter the queries in swipl to test.




my_append([a,b],[c],Z).




my_append(Xs,[c],[a,b,c]).




my_append(Xs,Ys,[a,b,c]).




my_prefix([a,b,c],Z).




After drawing the execution trees, enable tracking on my_append and my_prefix by running (two separate queries)




trace(my_append).




trace(my_prefix).




in swipl. Now, execute the above queries and try and match what you drew to the way the actual query is executed in swipl. To turn off 'trace', type the query 'nodebug'.




If you prefer a graphical debugger/trace, enter the query 'manpce', you should see a small XPCE manual window. Under the 'Tools' menu select: "Prolog graphical tracer".




Some instillations will have "debug" on the terminal tool bar. This will pull down a menu. Select "graphical debugger".




Before you type your query -- type "trace" at the prompt.




When you start executing your query the graphical debugger will start displaying the state of your execution.










*/










/* Problem 0B (NOT GRADED):




Each line is an individual Prolog query; it's a good idea type them in your prompt (not the file itself) to get a feel for the way Prolog works. You should think about whether or not each query will succeed, and if so how the variables will be initialized (unified). It will help in doing some of the problems.




(This will be useful in solving problem 2).




?- number(A), A = 5.6.




?- A = 5.6, number(A).




?- integer(4).




?- help(functor).




?- functor(foo(a,b,c),F,N).




?- functor(T,foo,3).




?- help(arg).




?- arg(3, foo(a,b,c),A).




?- help('=..').




?- T =.. [foo,x, y, z].




?- E =.. ['+',2,3], R is E.




?- foo(who, what) =.. T.




?- foo(who, what) =.. [A, B,C].




?- T =.. [foo,x, y, z], assert(T), clause(foo(A,Y,Z),B).




?- clause(bad(A,Y,Z),B), T =.. [bad,x, y, z], assert(T).




/* Problem 1: Given a list of goals, checkgoals/1 succeeds only if




all of the goals in the list succeeds. Note: the scope of variable names is the entire list.




*/













/* Problem 1 Test */




%:- checkgoals([=(A,5),is(B,+(4,5)),C is max(5,2),A=C]) , A = 5, B = 9, C = 5. %succeeds




%:- checkgoals([member(A,[1,4,5,7]),is(A, max(5,2))]). %succeeds




%:- checkgoals([is(A,+(3,2)),is(B,+(4,5)),C is max(5,2),A=C]). %succeed




%:- checkgoals([=(A,5),is(B,+(1,2)),B is max(9,A)]). %fails




/* Problem 1 Answer */




/* Problem 2:




Write a predicate computeS/4. computeS(Op, Arg1, Arg2, Result) succeeds if Result is the value after computing Arg1 Op Arg2. Use the insight you gained in Problem 0B. Op must be a builtin Prolog operator.




*/




/* Problem 2 Answer: */




/* Problem 2 Test: */




:- computeS(-, 19, 7, 12).



:- computeS(div, 19, 7, 2).



:- computeS(div, 19, 7, R), R = 2.



:- computeS(/, 19, 7, 2) - fail ; true.



:- catch((computeS(sin, 90, 1, _), fail), error(_Err, _Context), true).












/* Problem 3:




In class we discussed the 'is' predicate for evaluating expressions. Write a predicate results/2.




result(Elst,RLst) succeeds if Rlst is unifies with the values computed from idem in the list of expressions, Elst.




*/




/* Problem 3 Answer: */




/* Problem 3 Test */




:- result([],[]).



:- result([+(3,7), mod(104,7),-(5)],[10, 6, -5]).



:- result([+(3,7), +(15, -(3,11))],X), X = [10, 7].



:- result([+(3,7), mod(104,7)],[10,13]) - fail ; true.



/* Problem 4:




Write a predicate sumlist(List,Sum) which succeeds if Sum is the total value of all the elements of List. This will be a top down recursion.




The recursion clause will add the current value to the result of the sum of the rest of the list.




We have already provided the base case for this predicate underneath 'Problem 1 Answer'. You just need to add the recursive clause.




*/

* Problem 4 Answer */




sumlist([], 0).




/* Problem 4 Test */




/* There should be no warnings when compiling,




tests which are supposed to fail are written as such */




:- sumlist([], 0). % succeed



:- sumlist([], 1) - fail ; true.



:- sumlist([1,2,3,4], 10). % succeed



:- sumlist([1], 1). % succeed



:- sumlist([40,10,12],Sum). % succeed



:- sumlist(L,10). % breaks






/* Problem 5:




Write the predicate sumlist2(List,Sum) which succeeds if Sum is the sum total of all the elements of List. Instead of adding the current value to the result of the sum of the tail, you will calculate the partial sum of the all the elements you have reached so far. You will need an extra argument to store the partial sum, so you will write an auxiliary predicate sumlist2/3 to handle the extra argument.




Underneath 'Problem 2 Answer' we have provided sumlist2/2, which calls the auxiliary predicate sumlist2/3. We have also provided the base case for the auxiliary predicate. You just need to add the recursive clause for sumlist2/3.




*/




/* Problem 5 Answer */




sumlist2(List,Sum) :- sumlist2(List, 0, Sum).




sumlist2([], Sum, Sum).




/* Problem 5 Test */




:- sumlist2([], 0).



:- sumlist2([], 1) - fail ; true.



:- sumlist2([1,2,3,4], 10).



:- sumlist2([40,10, 12], SUM).



:- sumlist2([1], 1).



/* Problem 6:




Write the predicate sumPartialR(N, SumLst), which succeeds as follows:




given a number N, SumLst is a sequence of sums such that first number in




S is the sum of all the numbers from N to 1, the second number in S the sum of all the numbers from N-1 down to 1, and so on.




In other words, SumLst = [N+(N-1)+..+1, (N-1)+(N-2)+..+1, ..., 1].




For example:




?- sumPartialR(6,S).




S = [21, 15, 10, 6, 3, 1] .




This problem can be solved in 2 clauses.




*/







/* Problem 6 Answer */

* Problem 6 Test */



:- sumPartialR(1, [1]).



:- sumPartialR(1, []) - fail ; true.



:- sumPartialR(2, [3, 1]).



:- sumPartialR(6, [21, 15, 10, 6, 3, 1]).












/* Problem 7:




Write the predicate sumPartialL(N, SumLst). This problem is very similar to Problem 3, but has one key difference. The sum totals accumulate from left to right, so the SumLst generated will be different. For example, the first value in S will be N, the second value will be N + (N-1), and so on. In other words, SumLst = [N, N+(N-1), ..., N+(N-1)+(N-2)+...+1].




For example,




?- sumPartialL(6,S).




S = [6, 11, 15, 18, 20, 21]




It would be helpful to follow the idea used in problem 2. So your first clause should be:




sumPartialL(N,Lst):-sumPartialL(N,N,Lst).




You need to add 2 additional clauses.*/