CSE 240 Homework 13, Fall 2020 (50 points)
Due Saturday, November 21, 2020 at 11:59PM, plus one day grace period
Introduction
The aim of this assignment is to make sure that you understand and are familiar with the concepts covered in the lectures. By the end of the assignment, you should have
• strong concept of logic / declarative paradigm;
• strong concept of facts, rules, and questions in Prolog;
• Recursive rules in Prolog
Reading: Text Chapter 5 and lecture slides. Also read Text Appendix B.4 Prolog Tutorial
You are expected to do the majority of the assignment outside the class meetings. Should you need assistance, or have questions about the assignment, please contact the instructor or the TA during their office hours.
You are encouraged to ask and answer questions on the course discussion board. (However, do not share your answers in the course discussion board.)
Practice Exercises (no submission required)
1. Answer the multiple choice questions in text section 5.9 that have been covered in the lectures.
2 Complete the questions 2 through 5 in text section 5.9.
3 Look up the Unix command table in Appendix B.1 and read the Prolog tutorial in B.4.
4 Log onto general.asu.edu and execute the Unix commands and Prolog exercises.
5 Follow the Prolog tutorial in Text Appendix B.4 or this tutorials given in the course Web site, start GNU Prolog and try following simple programs (build-in functions). Don’t forget the period at the end of the statement.
| ?- write(hello). % hello is a constant */
| ?-write(Hello). % Hello is a variable. Its address will be displayed*/
| ?- write(‘hello world’). % a string is printed */
| ?- read(Y), write(‘The variable entered is ‘), write(Y), nl. /* nl prints a newline. Type a period and an enter at the end of the input */
| ?-Xis2+2.
| ?-Yis5*8.
| ?- Y is 2**10.
| ?- length([a, b, x, y, 2, 45, z], L).
CSE240 – Introduction to Programming Languages Homework 13
1 | P a g e
| ?- append([a, b, c, d], [4, 6, 8], LL).
| ?- append(X,Y,[a,b,c]). Then, type “;” to obtain all possible answers. | ?- X is [1 | [2 | [3 | []]]], write(X). Explain the output.
6 Use trace and notrace before and after your questions in Question 5. For example
|?- trace.
| ?- X is [1 | [2 | [3 | []]]], write(X). Explain the output. |?- notrace.
Programming Assignment (50 points)
1. Consider the following diagram of a family tree:
[25 points]
/* Database for family tree. It consists of facts and rules. */ /* A portion of the family tree has been implemented for you */
/* Facts */
male(kam).
male(rob).
female(ana).
female(syd).
father_of(kam, rob). /* kam is the father of rob */ father_of(kam, syd). /* kam is the father of syd */ mother_of(ana, rob). /* ana is the mother of rob */ mother_of(ana, syd). /* ana is the mother of syd */
CSE240 – Introduction to Programming Languages Homework 13
2 | P a g e
/* Rules */
is_male(X) :-
male(X);
father_of(X, _).
1.0 Enter the program using a text editor such as pico or vim under Unix operation system and save the file as family_tree.pl. You may enter the program on your own computer using notepad and upload the program into your cse240prolog directory in general server.
Compile the program using the Prolog command:
> gplc family_tree.pl
Enter GNU Prolog programming environment by executing the Unix command gprolog, Execute the program family_tree by typing GNU Prolog command
|?- [family_tree].
You can also use command: ./family_tree
To exit from GNU Prolog, type your end-of-file character at the main Prolog prompt ^d (Ctrl-d).
| ?- ^d
Ask questions by typing, e.g.:
Please read Textbook Appendix B.4 Prolog Tutorial for more detail. You can also find a complete set of GNU Prolog commands at http://www.gprolog.org/manual/gprolog.html.
Now, you can start to add your code into the program.
1.1 Complete the program by adding facts and rules for the remaining members on the family tree. A portion has already been completed for you above for clarification. Please pay close attention when adding the remaining famiy members. All letters should be lowercase. [4]
For all of the following questions, please label them. For example, if Question 1.0 asks you to define a rule called is_male (X) that returns “yes” (or “true”) if X is the father of a member of the family, then your code should look like:
/* Question 1.0 */ is_male(X) :-
male(X); father_of(X, _).
1.2 Define (add into the database) a rule called is_female(X) that returns “yes” (or “true”) if X is a female or the mother of a member of the family. [4]
CSE240 – Introduction to Programming Languages 3 | P a g e Homework 13
|?- father_of(kam, rob). |?- mother_of(ana, syd).
Note: the system will return a “yes”, if it finds a “true” answer and there exist no more true answers. The system will return “true ?” if it finds a “true” answer and there are still possibly further matches. In this case, if you type “enter”, it will return “yes” and stop. If you type “;”, it will continue to search for further answers.
1.3 Define a rule called parent_of(X, Y) that returns “yes” (or “true”) if X is a parent of Y. [4]
1.4 Define a rule called sibling_of(X, Y) that returns “yes” (or “true”) if X is a sibling of Y. [4]
1.5 Define one rule called grandmother_of(X, Z) that returns “yes” (or “true”) if X is a grandmother of Z and one rule called grandfather_of(X, Z) that returns “yes” (or “true”) if X is a grandfather of Z. [4]
1.6 Define a rule called descendent_of(X, Y) that returns “yes” (or “true”) if X is a descendent of Y. Note: you will need to use recursion as well as the parent rule defined above. [5]
2 Consider the following database information for the following two ASU students, jack and sam. [15 points]
jack
sam
status: sophmore topic:
mat
– calculus
– algebra cse
– algorithms – databases
status: freshman topic:
bio
– taxonomy
– evolution eng
– reading – writing
2.1 Create facts for the students’ academic status: status(X, Y) where X is the student (jack or sam) and Y is the academic status (sophmore or freshman).
Create facts for the students’ class topics: topic(X, Y) where X is the student (jack or sam) and Y is the topic (mat, cse, bio, or eng).
Create facts for the students’ classes : class(X, Y) where X is the topic (mat, cse, bio, or eng) and Y is the class (calculus, algebra, algorithms, databases, taxonomy, evolution, reading, or writing). [5]
2.2 Create a rule info(X, Y), where X is the student (jack or sam) and Y is the info for the student. For example, info(jack, X) should return the status and topics: sophmore, mat, and cse. [5]
2.3 Create a rule schedule(X, Y), where X is the student (jack or sam) and Y is the class (calculus, algebra, algorithms, databases, taxonomy, evolution, reading, or writing). For example, schedule(sam, X) should return taxonomy, evolution, reading, and writing. [5]
CSE240 – Introduction to Programming Languages 4 | P a g e Homework 13
3 Complete the code for the following problem in Prolog. [10 points] 𝑥 𝑖𝑓 𝑦 ≤ 0
𝑓𝑜𝑜(𝑥, 𝑦) = )𝑦 𝑖𝑓 𝑥 ≤ 0 𝑥+𝑓𝑜𝑜(𝑥−2,𝑦) 𝑖𝑓𝑥≥𝑦
𝑦+𝑓𝑜𝑜(𝑥,𝑦−3) 𝑖𝑓𝑥<𝑦
Assume that both x and y are originally non-negative integers greater than 0
For example: foo(5, 6) = 6 + foo(5, 3) 5 + foo(3, 3) 3 + foo(1, 3) 3 + foo(1,0) 1
= 6 + 5 + 3 + 3 + 1 = 18
You must use recursion. Follow the Fantastic Four-Step Abstract approach. You must indicate the steps in the comments for all parts. (Note, a Prolog rule does not return a value. You need to use an additional parameter to hold the return value.)
Define a rule foo(X, Y, Z), where Z is used for the return value.
What to Submit?
You are required to submit your solutions in a compressed format (.zip). Make sure your compressed file is label correctly - lastname_firstname13.zip.
The compressed file MUST contain the following:
1family_tree.pl
2students.pl
3recursion.pl
No other files should be in the compressed folder.
If multiple submissions are made, the most recent submission will be graded, even if the assignment is submitted late.
Submission preparation notice: The assignment may consist of multiple files. You must copy these files into a single folder for canvas submission. To make sure that you have all the files included in the zip file and they work after unzip operation, you must test them before submission. You must also download your own submission from the canvas. Unzip the file on a different machine and test your assignment and see if you can open and test the files in a different location, because the TA will test your application on a different machine. If you submitted an empty project folder, an incomplete project folder, or a wrong folder, you cannot resubmit after the submission linked is closed! We grade only what you submitted in the canvas. We cannot grade the assignment on your computer or any other storage, even if the modification date indicated that the files were created before the submission due dates. The canvas submission may take a few minutes. Be patient and wait for it to complete.
CSE240 – Introduction to Programming Languages 5 | P a g e Homework 13
Where to Submit?
All submissions must be electronically submitted to the respected homework link in the course web page where you downloaded the assignment.
Late submission deduction policy
● No penalty for late submissions that are received within 24 hours after the deadline;
● 10% grade deduction for every day it is late after the grace period;
● No late submission after Tuesday at 11:59PM.
Grading Rubrics
Each sub-question (programming tasks) has been assigned certain points. We will grade your programs following these steps:
(1) Compile the code. If it does not compile, 50% of the points given for the code under compilation will be deducted. Then, we will read the code and give points between 50% and 0, as shown in right part of the rubric table.
(2) If the code passes the compilation, we will execute and test the code using test cases. We will assign points based on the left part of the rubric table.
(3) In both cases (passing compilation and failed compilation), we will read your program and give points based on the points allocated to each sub-question, the readability of your code (organization of the code and comments), logic, inclusion of the required functions, and correctness of the implementations of each function.
(4) Please notice that we will not debug your program to figure out how big or how small the error is. You may lose 50% of your points for a small error such missing a comma or a space!
(5) We will apply the following rubrics to each sub-question listed in the assignment. Assume that points assigned to a sub-question is pts:
CSE240 – Introduction to Programming Languages 6 | P a g e Homework 13
Major
Code passed compilation
Code failed compilation
Points
Pts * 100%
Pts * 90%
Pts * 80%
Pts * 60%-70%
Pts * 40%- 50%
Pts * 10%- 30%
0
Each Sub- question
Meeting all requirements, well commented, and working correctly in all test cases
Working correctly in all test cases. Comments not provided to explain what each part of code does.
Working with minor problem, such as not writing comments, code not working in certain uncommon boundary conditions.
Working in most test cases, but with major problem, such as the code fail a common test case
Failed compilation or not working correctly but showing serious effort in addressing the problem.
Failed compilation, showing some effort, but the code does not implement the required work.
No attempt
Please read the FAQ file in the Course Information folder:
Q: For some reason, my assignment submission did not go through, but I thought it went through. I can show you on my local disk or in my Dropbox that I completed the assignment before the due date. Can my assignment be graded?
A: You should always download your own submission from the blackboard after submission and test if the submission contains all the required files. We will grade the assignment submitted to Canvas only. We cannot grade the assignment sent from email or stored in any other places, regardless its last-modified-time. If you submitted your assignment into the blackboard, it cannot be downloaded from the instructor side, but it can download from your side, we can download from your blackboard and grade the assignment. Please meet the instructor or TA in this case.
CSE240 – Introduction to Programming Languages 7 | P a g e Homework 13