Assignment 1
Due Sun 2/5 on or before 11:59:59 pm
Write a LISP program to solve the "I am my own grandfather" predicate logic problem. Instead of a full-blown unification system, we will make some simplifying assumptions for this assignment. First, the database will not contain any variables. Second, the implications will consist only of AND'ed antecedent clauses and these antecedents will contain at most one of each variable. Finally, variables will consist of 'X, 'Y, and 'Z only.
We will also simplify the predicates for the problem by replacing any gender-specific predicates like has-son or has-daughter with gender-neutral predicates like has-child. This gives us a simplified database (in LISP notation with the predicate name represented in LISP as the car of a list):
((has-child father me) (married me wife) (has-child wife daughter) (married father daughter))
To simplify the problem some more, we will also guide the search by hand by passing the implications to our program in a specific order as shown below. We will start with the inference, ∀X ∀Y married(X, Y) → married(Y, X), adding the inferred consequents to the database. Next we will process the inference, ∀X ∀Y∀Z married(X, Y) ∩ has-child(Y, Z) → has-child(X, Z), adding the inferred consequents to the database. Finally we will process the inference, ∀X ∀Y∀Z has-child(X, Y) ∩ has-child(Y, Z) → has-grandchild(X, Z). At least one of the final result consequents should be (married me me). Turn in a transcript of a sample run by saving your LISP Listener (aka Debug Window) into a file and submitting this transcript along with your source code file combined into a zip file. Below is a sample run without the final results. Besides (has-grandchild me me), what other logical conundrums do you think your program will produce?
CG-USER(138): (load "a1") T CG-USER(139): *db* ((HAS-CHILD FATHER ME) (MARRIED ME WIFE) (HAS-CHILD WIFE DAUGHTER) (MARRIED FATHER DAUGHTER)) CG-USER(140): (setq *db2* (append (infer '(((married X Y)) ((married Y X))) *db*) *db*)) ((MARRIED WIFE ME) (MARRIED DAUGHTER FATHER) (HAS-CHILD FATHER ME) (MARRIED ME WIFE) (HAS-CHILD WIFE DAUGHTER) (MARRIED FATHER DAUGHTER)) CG-USER(141): (setq *db3* (append (infer '(((married X Y) (has-child Y Z)) ((has-child X Z))) *db2*) *db2*)) ((HAS-CHILD DAUGHTER ME) (HAS-CHILD ME DAUGHTER) (MARRIED WIFE ME) (MARRIED DAUGHTER FATHER) (HAS-CHILD FATHER ME) (MARRIED ME WIFE) (HAS-CHILD WIFE DAUGHTER) (MARRIED FATHER DAUGHTER)) CG-USER(142): (infer '(((has-child X Y) (has-child Y Z)) ((has-grandchild X Z))) *db3*)
Hints
First define the global variable *db* to be the database shown above using
the LISP function defconstant. Check to make sure *db* has
the right value by evaluating *db* in your LISP Listener (aka Debug Window).
Next write a function to check if a symbol is a variable (that is, whether
the symbol is 'X, 'Y or 'Z). Check that this function works correctly
before writing more code. Next write a function to match two predicates.
This function should recurse down the list, stopping when the list is nil
(whereupon it returns the empty set, nil). First the match
function should check that both arguments are lists and have the same length.
If not, then it should return 'fail. Next if the first predicate is an
empty list, then return nil. Next if the car's of the
two predicates are the same symbol (eq), then return the result
of recursively matching the cdr's of the two predicates and 'fail if the
two car's are not eq. Test this match function to make sure
it works before continuing. Two identical predicate arguments should
return nil and tow non-identical arguments should return
'fail.
The next step is to modify the match function to allow the first predicate
to have variables inside its list. Now instead of just checking to see if
the car of the first predicate is eq to the car of the
second predicate, the match function must also check to see if the car
of the first predicate is also a variable, in which case it will
automatically match any symbol in the second predicate. Make this
change and test the revised match function before continuing. Once
this works, add returning a set (represented as a LISP list) of variable
bindings where each binding is a list of the variable and what it matched
in the second predicate). For example, matching (married X Y) with
(married me wife) should return ((X me) (Y wife)) and matching (married me Y)
with (married father daughter) should return 'fail.
After debugging your matching function, write a function to replace
variables with their bindings throughout a tree (actually just a list of
lists). This function should take two arguments, the tree and the
variable binding set (in the same exact format as the result of
the matching function). You may want to look at the LISP built-in
function, subst to help with substituting the bound value
for the variable in the tree. For example, calling the function with
tree argument, (nil ((married Y X))), and bindings arguments,
((X me) (Y wife)), should return (nil (married wife me)).
Now write a match-all function similar to your matching function that takes as its second argument a list of predicates (the database) instead of just a single predicate. This match-all function should recurse on the second argument, stopping when it is nil (returning nil at that point). This match-all function should return a list of variable binding sets consisting of all non-fail individual matches between the first predicate argument (which may contain variables) and each list member of the second database argument. For example calling the match-all function with arguments '(married X Y) and *db* should return (((X ME) (Y WIFE)) ((X FATHER) (Y DAUGHTER))) where ((X ME) (Y WIFE)) and ((X FATHER) (Y DAUGHTER)) are different variable binding sets gotten from matching in *db* (married me wife) and (married father daughter) respectively.
Next write the main infer function that takes two arguments: the inference and the database. The infer function is tricky because it recurses in two ways: it recurses down the inference antecedents list and it recurses down the database list. First, recursing on the inference list means matching each list element of the antecedents (but not the consequents) against the database using the match-all function. For each of the variable binding sets returned by match-all, infer will have to replace any bound variables in the rest of the antecedents and any bound variables in inference's consequents with the matching value in the variable bindings using your replace variables function and append the results of each variable binding set. It is helpful to break up infer into two functions, one that recurses down the inference antecedents list and another that helps infer by recursing through the list of variable binding sets. The helper function will replace the variables in the inference, call infer on the variable-replaced inference and the database, and finally return the result of infer appended with the results from recursing down the rest of the list of variable binding sets.
My solution takes 29 lines of code, not counting blank lines or comment lines. If your solution is taking much longer, you are probably doing something wrong and should come see me or our TA for help.
Submit by zipping together your source code file (e.g., a1.lisp) and your typescript file (e.g., typescript.txt) into a1.zip and then upload a1.zip to Assignment 1 on Laulima.
David N. Chin / Chin@Hawaii.Edu