CSC244 / CSC444 - Assignment #1 - Part 2 DUE: 5PM, Tuesday, September 26th, 2006 TURNIN: Please email the following to ardis@cs.rochester.edu : + 1 LISP file (a1_2.lisp) containing all function and structure definitions used to solve the assignment problems. + 1 text file (a1_2_usage.txt) containing a text log of using your defined functions/structures to solve the assignment problems. For example: > (funcall fibonacci 1) 1 > (funcall fibonacci 2) 1 > (funcall fibonacci 3) 2 Please include all code usage which you believe helps show the correct behavior of your provided LISP code. + 1 text file (a1_2_readme.txt) containing a brief description of all defined functions/structures including their intended purpose, input/output, etc. Please indicate here if your code has any problems/incapatabilities/failures, as well as any improvements for efficiency or robustness, for purposes of partial credit and/or extra credit. Your email should have the subject line "CSC244 Assignment 1_2" if you are in CSC244 and "CSC444 Assignment 1_2" if you are in CSC444. Multiple submissions are allowed, but only the most recent submission (prior to the deadline) will be graded. Please put your name at the top of your submission email. Late submissions will be accepted for 2 days with a 10% penalty per day. All submissions after September 28th will not be graded. PROBLEMS: The focus of this assignment is to introduce you to the concept of storing/retrieving logical knowledge in LISP using simple structures. 1.) Create a structure called "predicate" which has three fields: name (a symbol, like P1) true_objects (a list of symbols) false_objects (a list of symbolss) This will be used to store information about a predicate and what knowledge we possess about it in relation to a model. 2.) Create a structure called "object" which has one field: name (a symbol) This will be used to represent an object in the domain. 3.) Create a structure called "world" which has two fields: domain (a list of objects) facts (a list of predicates) This will be used to represent knowledge about the world. 4.) Create a function "parse_world" which, when given input in the following format, returns a world object which has the corresponding information stored within it: ((obj1 obj2 obj3) ((Big obj1) (Big obj2) (NOT Big obj3))) That is: There should be _one_ parameter, which is a list that has two elements. The first element is a list of symbols, each being the unique name of a domain object. The second element is a list, with each element having the form "([NOT] symbol1 symbol2)". Note that "NOT" is optional. Each of these indicates predicate information on a domain element named in symbol2, with the predicate named in symbol1. If "NOT" is present, this indicates negation. You should store this information into predicate objects, which are then added to the returning world object. NOTE: It is acceptable to store each of these as a separate predicate object, meaning that there may be more than one predicate object with the same name stored in the world object you are returning. If you wish to instead combine these pieces of knowledge and return a world object which has unique predicate objects (such as, in the provided example, having "Big" with true_objects obj1 and obj2), you may do so, and will receive 5% extra credit on this assignment if correctly implemented. Below is another example of correct parsing: INPUT: (a b) ((P1 a) (P2 b)) OUTPUT: A world object with "domain" containing a and b, as well as "facts" containing predicate objects for P1 and P2 (the first having "true_objects" containing a, etc.). 5.) Create a function "check_world" which takes a world object parameter and a list of predicate facts (of the same format as in the previous function) and which returns "t" if the provided world is consistent with those facts. For example: Let us call the world from the last example (with P1, P2, a, and b) "w1". When you use this function, it is easiest to store a pre-created world object (using setf) which you can reference by name. INPUT: w1 ((P1 a) (NOT P2 b)) OUTPUT: NIL, since we know P2(b) is true and therefore contradicts the input. And here's a slightly different example: INPUT: w1 ((P1 a)) OUTPUT: t, since we know P1(a) is true and there are no contradictions. If no contradictions exist, t should be returned. This implies that adding these facts to the world knowledge will not introduce an inconsistency. So, if nothing is known about a predicate Q, then a call to check_world which only involves Q should return t. EXTRA CREDIT: The function check_world, which checks for consistency when adding facts to a knowledge base, is very similar to a model checker. For extra credit, implement a (similar) function named "model_world" which takes identical parameters as check_world but which does the following: Determine if there exists a mapping between provided names in predicates and existing object names for which these facts are true. For example: w2 = w1, but with the fact (NOT P2 b) instead of (P2 b) INPUT: w2 ((P1 x) (NOT P2 y)) OUTPUT: t, since the mapping of x to a and y to b satisfies the list of facts provided. Another example: INPUT: w2 ((NOT P2 x) (NOT P2 y)) OUTPUT: t, since both x and y can map to b. Yet another example: INPUT: w2 ((P1 x) (NOT P2 x) (NOT P2 y)) OUTPUT: NIL, since we don't have a domain object for which we have positively asserted both P1 and ~P2. Note that are not looking for simply a lack of inconsistencies, but for a definite matching. Correct implementation of this function will result in 5% extra credit on this assignment, with partial extra credit possible for semi-functional implementation. For an additional 5%, you may implement "forall" and "exists" keywords (to indicate universal and existential quantification) in model_world, with correct behavior. For instance: INPUT: w1 ((forall (x) P1 x)) OUTPUT: NIL, since we don't have P1(b) Note that the format should be "forall (list of names)" preceding the rest, and likewise "exists". REMINDER: If you have any questions about the assignment, please email ardis@cs.rochester.edu or come to room 624 between 11 and 12 on Tuesday or Thursday. The provided LISP reference sheets should be a good place to start regarding list handling and simple structure creation. Additional resources are listed on the website, though the structure-manipulating code should be very simple.