Carleton University
School of Computer Science
95.501  Assignment 3 (Fall '2001)

Due:    Nov. 16 before class

There are two basic styles using logic programs: defining a logical database, and manipulating data structures. A logic database is comprised of a set of facts and rules. This assignment gives you experience developing facts that define relations, as in relational databases, and developing rules that define complex relational queries, as in relational algebra. Together, facts and rules can express functionalities associated with relational databases. The power of logic programs comes from their ability to handle recursive data types.
1) In this question you will develop a system for representing knowledge about a collection of toy blocks. A typical configuration is shown in the list DATABASE below:

    (SET! DATABASE
        '(      (B1 SHAPE BRICK)
                (B1 COLOR GREEN)
                (B1 SIZE SMALL)
                (B1 SUPPORTED-BY B2)
                (B1 SUPPORTED-BY B3)
                (B2 SHAPE BRICK)
                (B2 COLOR RED)
                (B2  SIZE SMALL)
                (B2 SUPPORTS B1)
                (B2 LEFT-OF B3)
                (B3 SHAPE BRICK)
                (B3 COLOR RED)
                (B3  SIZE SMALL)
                (B3 SUPPORTS B1)
                (B3 RIGHT-OF B2)
                (B4 SHAPE PYRAMID)
                (B4 COLOR BLUE)
                (B4  SIZE LARGE)
                (B4 SUPPORTED-BY B5)
                (B5 SHAPE CUBE)
                (B5 COLOR GREEN)
                (B5  SIZE LARGE)
                (B5 SUPPORTS B4)
                (B6 SHAPE BRICK)
                (B6 COLOR PURPLE)
                (B6  SIZE LARGE)))

Assertions about objects in the blocks world are represented as triples of the form (block attribute value). Here are some assertions about block B2:

                (B2 SHAPE BRICK)
                (B2 COLOR RED)
                (B2  SIZE SMALL)
                (B2 SUPPORTS B1)
                (B2 LEFT-OF B3)

A collection (i.e., a list) of assertions is called a database. Given a database describe the blocks world in the list, we can write functions to answer questions such as "What color is block B2?" or "What block supports block B1?". To answer these questions, we will use a function called a pattern matcher (fetch) to search the database fur us. For example, to find out the color of block B2 we sue the pattern (B2 color ?).

            (fetch '(B2 color ?))
                would return ((B2 COLOR RED))

To find which block support B1, we use the pattern (? SUPPORTS B1)

            (fetch '(? SUPPORTS B1))
                would return ((B2 SUPPORTS B1) (B3 SUPPORTS B1))

The FETCH function returns those assertions from the database that match a given pattern. It should be apparent from the preceding examples that a pattern is a triple, like an assertion, but with some of its elements replaced by question marks. The following example shows a collection of patterns with their English interpretations.

        Pattern                                        English interpretation
        (B1 COLOR ?)                           What color is B1?
        (? COLOR RED)                        What blocks are RED?
        (B1 COLOR RED)                      Is B1 known to be RED?
        (B1 ?  B2)                                   What relation is B1 to B2?
        (B1 ? ?)                                       What is known about B1?
        (? SUPPORTS ?)                        What support relationship exists?
        (? ? B1)                                       What blocks are related to B1?
        (? ? ?)                                            What assertions are in the database?

A question mark in a pattern means any value can match in that position.. Thus the pattern (B2  COLOR ?) can match assertions like (B2  COLOR RED), (B2  COLOR GREEN), (B2  COLOR BLUE), and so on. It cannot match the assertion (B1  COLOR RED) because the first element of the pattern is the symbol B2 while the first element of the assertion is B1.

REQUIREMENTS:


Enter the block database as it appears above (saving the database in the global variable DATABASE).

Write a function MATCH-ELEMENT that takes two symbols as input. If the two are equal, or if the second is a question mark, MATCH-ELEMENT should return true. others it should return false. Thus

        (MATCH-ELEMENT 'RED 'RED) returns #t
        (MATCH-ELEMENT 'RED '?) returns #t
        (MATCH-ELEMENT 'RED 'BLUE) returns #f
 

Write a function MATCH-TRIPLE that takes an assertion and a pattern as input and returns true if the assertion matches the pattern. Both inputs will be three-element lists. Thus:

        (MATCH-TRIPLE '(B2 COLOR RED) '(B2 COLOR ?))
            should return #t

          (MATCH-TRIPLE '(B1 COLOR RED) '(B2 COLOR ?))
            should return #f

Write a function FETCH that takes  a pattern as input and returns all assertions in the database that match the pattern. Remember that DATABASE is a global variable.

        (FETCH '(B2 COLOR ?) should return ((B2 COLOR RED))

        (FETCH '(? SUPPORTS B1)) should return ((B2 SUPPORTS B1) (B3 SUPPORTS B1))

Use FETCH with patterns you construct yourself to answer the following questions: What shape is B4? Which blocks are bricks? What relation is block B2 to B3? What are the colors of every block? What facts are know about block B4?

What a function SHAPE-OF that takes a block names as input and returns a pattern which represents the question "What is the shape of the block?". For example, give the input 'B3, your functions should return the list that represents the question, "What is the shape of B3?".

Write a functions SUPPORTERS that takes on input - a block- and returns a list of blocks that support it. (SUPPORTERS 'B1) should return the list (B2 B3). Your functions should work by constructing a pattern containing the block's name, using that pattern as input to FETCH, and then extracting the block names from the resulting list of assertions

2) In this question you will extract different sorts of information from a genealogical database. The database gives information for five generations of a family. Such databases are usually called family trees, but this family's genealogical history is not a simple tree structure. Marie has married her first cousin Nigel. Wanda has had one child with Vincent and another with Ivan. Zelda and Robert, the parents of Yvette, have two great grandparents in common (Got that?)

Each person in the database is represented by an entry of the form

    (name father mother)

When someone's father or mother is unknown, a value of  '() is used.
 

REQUIREMENTS:


The functions you write in this questions need not be recursive, except where indicated.

Enter the following genealogy database into the global variable FAMILY:
 

    (define FAMILY
            '(  ( colin () () )
                (deirdre () ())
                (arthur () () )
                (kate () () )
                (frank () () )
                (linda () ())
                (suzanne colin deirdre)
                (bruce arthur kate)
                (charles arthur kate)
                (david arthur kate)
                (ellen arthur kate)
                (george frank linda)
                (hillary frank linda)
                (andre () () )
                (tamara bruce suzanne)
                (vincent  bruce suzanne)
                (wand () () )
                (ivan george ellen)
                (julie  george ellen))
                (marie  george ellen)
                (nigel andre hillary)
                (frederick () tamara)
                (zelda vincent wanda)
                (joshua ivan wanda)
                (quentin () ())
                (robert quentin julie)
                (olivia nigel marie)
                (peter nigel marie)
                (erica () ())
                (yvette robert zelda)
                (diane peter erica)))

Write the functions FATHER, MOTHER, PARENTS and CHILDREN that return a person's father mother, a list of his or her known parents, and a list of his or her children, respectively.

    (FATHER 'suzanne) should return colin
    (PARENTS 'suzanne) should return (colin deirdre)
    (PARENTS 'frederick should return (tamara) since frederick's father is unknown

If any of these functions is give '() as input, it should return '(). This feature will be useful later when you write some recursive functions.

Write SIBLINGS, a function that returns a list of a person's siblings, including genetic half-siblings.
 

    (SIBLINGS 'bruce) should return (charles david ellen)
    (SIBLINGS 'zelda) should return (joshua)

Write MAPUNION, an applicative operator that takes a function and a list as input, applies the function to every element of the list and computes the union of all the results. Example:

    (MAPUNION 'cdr ((1 a b c) (2 e c j) (3 f a b c d))) should return the list (a b c e j f d)

Write GRANDPARENTS, a function that returns the set of a person's grandparents. Use MAPUNION in your solution.

Write COUSINS, a function that returns the set of a person's genetically related first cousins (i.e., the children of any of their parent's siblings). Use MAPUNION in your solution.

    (COUSINS 'julie) should return the set (tamara vincent nigel)

Write a two-input recursive predicate DESCENDED-FROM that returns a true value if the first person is descended from the second.

    (DESCENDED-FROM 'tamara 'arthur) should return #t
    (DESCENDED-FROM 'tamara 'linda) should return # f or ().

(NOTE: you are descended from someone if that person is one of your parents of if either your father or mother is descended from that person. This is a recursive definition)

Write a recursive function ANCESTORS that returns a person's set of ancestors.

    (ANCESTORS 'marie) should return (ellen arthur kate george frank linda)

(The exact order in which these names appear is unimportant, but there should be no duplicates. Note: a person's ancestors are his parents plus his parents' ancestors. This is a recursive definition).

Write a recursive function GENERATION-GAP that returns the number of generators separating a person and one of his or her ancestors.

    (GENERATION-GAP 'suzanne 'colin) should return 1
    (GENERATION-GAP 'frederick 'colin) should return 3
    (GENERATION-GAP 'frederick 'linda) should return #f or () because linda is no an ancestor of frederick

Use the functions you have written to answer the following questions:
 

  1. Is robert descended from deirdre?
  2. Who are Yvette's ancestors?
  3. What is the generation gap between Olivia and Frank?
  4. Who are Peter's cousins?
  5. Who are Olivia's grandparents?

Testing:

REMEMBER: YOU MUST VERIFY AND TEST THAT YOUR SOLUTIONS WORK FOR ALL POSSIBLE GOALS, NOT JUST FOR THE ONES PROVIDED.  It is up to you to make up a convincing test plan (i.e. convince the TAs that your procedures work properly).   Make sure you test all your procedures.

Submission:

Submit a printout of all of your procedures and along with a copy of the output generated from the testing.   Be sure to include comments where appropriate in your code and make sure that all output is clearly explained.  Testing will be marked!   It is always a good idea to highlight the beginning of the procedure on the printout.  Place your name, student #, course#, and assignment # on the top of each page.   Put all printouts in one unsealed envelope, with this same information clearly marked on the envelope. You should also include a diskette containing the procedures and test output files you generated for the assignment. All of these files should be stored in the directory A:\ASS3 (actually B:\ASS3 when in the labs here).  Finally, hand in your assignment in the correct slot in room 4135 of the Herzberg Building (beside the lab) or slide it under your professor's door if the slot is full. Don't forget that the assignment will be marked for style, testing and your solutions.