CIS 479 Machine Problem 1
                           Spring 2002

     For your first programming assignment problem you have an 
opportunity to write some Lisp functions to for a simplified 
version of a famous AI application known as the Blocks World. 
Assertions describing this world are housed on the Intranet at 

http://www.engin.umd.umich.edu/CIS/course.des/cis479/block.dat. 
These assertions are of the form:
 
                         (B5 SHAPE CUBE)
                         (B5 COLOR GREEN)
                         (B5 SIZE LARGE)
                         (B5 SUPPORTS B4)
 
     Download the contents of this data file and implement the 
Lisp functions described below.
  
 1. Write a function MATCH-ELEMENT that takes two symbols as 
    input. If the two are equal, or if the second is a question 
    mark T is returned. Thus (MATCH-ELEMENT 'RED 'RED) and 
    (MATCH-ELEMENT 'RED '?) return T, while (MATCH-ELEMENT 'RED 
    'BLUE) returns NIL.
 
 2. Write a function MATCH-TRIPLE that takes an assertion and a 
    pattern containing a '? in any position and returns T if they 
    match. (MATCH-TRIPLE '(B2 COLOR RED) '(B2 COLOR ?)) returns T 
    and (MATCH-TRIPLE '(B2 COLOR RED) '(B2 COLOR GREEN)) should 
    return NIL.
 
 3. Write a function FETCH that takes a pattern and returns all 
    assertions which matches the pattern. (FETCH '(B2 COLOR ?)) 
    returns ((B2 COLOR RED)) and (FETCH '(? SUPPORTS B1)) returns 
    ((B2 SUPPORTS B1) (B3 SUPPORTS B1)).
 
 4. Write a function SUPPORTERS that takes a block name and 
    returns a list of blocks which support it. (SUPPORTERS 'B1) 
    returns (B2 B3). Your function should construct a list which 
    is passed to FETCH, MAPCAR should also be helpful to extract 
    block names returned in the list from FETCH.
 
 5. Write a function DESC1 which takes a block name and returns 
    all assertions about that block. (DESC1 'B6) returns ((B6 
    SHAPE BRICK) (B6 COLOR PURPLE) (B6 SIZE LARGE)).
 
 6. Write a function DESC2 which takes a block name, calls DESC1 
    and strips the block name off each element of the result. 
    (DESC2 'B6) returns ((SHAPE BRICK) (COLOR PURPLE) (SIZE 
    LARGE)).
 
 7. Write a function DESCRIPTION which takes a block name, calls 
    DESC2, and merges the resulting list of lists into a single 
    list. (DESCRIPTION 'B6) should return (SHAPE BRICK COLOR     
    PURPLE SIZE LARGE). MAPCAN might be useful, but is not 
    required for your solution.

     None of these functions is particularly long, if you keep in 
mind that you are working with LISP (not Pascal or C++). You 
should feel free to write any auxiliary functions that would make 
your work easier to do. In fact, it may be the case that, using 
one of the functions defined above will make it easier to define 
one of the other functions (and help improve the structure of your 
code as well). I would recommend using XLISP (or some other 
version of Common Lisp) for this assignment. 

     You will need to turn in a well commented source listing 
containing your function definitions, carefully organized test 
runs (perhaps using the XLISP dribble function and adding some 
annotations to the file using your favorite word processing 
program to make your output easier to follow), and a two page 
memo discussing the nature of your solution.

Assigned: 5/09/02
Due date: 5/16/02