Title: Recursive Parsing and Searching in Lisp.

Instructions: Choose a partner. Study the problem and design some suitable representations for the statements and other data constructs needed to solve the problem. Break down the problem into simpler problems and make up function names for functions to solve the simpler problems. Solve the overall problem.
Write a Lisp program that accepts a set of statements in English, transforms them into a symbolic representation, and then performs a simple kind of reasoning with them, answering a question. Optionally, put your program on the web so that users can operate it from a browser.

• Phase 1. Read in the sentences as strings. You may assume that they are given in a file, one per line. If you are using the web, you may assume they are given by the user in a series of text fields in an HTML form that you design.
  Convert each sentence into a list by first concatenating parentheses around it and then using the function READ-FROM-STRING.
  Parse each sentence, taking advantage of the assumption that each sentence is either a simple fact with no special logical connective words in it (IF, THEN, or AND) or it is a sentence of the form IF [antecedent] THEN [consequent] where [antecedent] is a simple statement optionally followed by AND and another [antecedent], and where [consequent] is a simple statement.
  Assign to each simple statement a proposition symbol such as A, B, C, D, etc. Store the associations between proposition symbols and the phrases they representing using an ASSOCIATION LIST. (Association lists are described in the spiral-bound Lisp notes).
  Create an explicit logical representation of each sentence. For each of the simple statements, this could just be a list containing the corresponding proposition symbol. For each IF-THEN sentence, you might consider a list in which the consequent's proposition symbol is listed first and then the proposition symbol(s) for the antecedent follow.
  Your program should print out its analysis of the sentences, identifying the simple statements ("atomic propositions") found, and what symbols are being used to represent them. It should also print out the coded versions of the premises (the statements corresponding to the lines of input).
• Phase 2. Accept an input question of the form, "Is it the case that..." followed by a simple statement. Your program should then express this question using an atomic proposition.
  Using a recursive searching technique, your program should try to answer the question and justify its answer.
  Sample input:

  If the butler desperately needed money and the victim was carrying a bundle of cash then the butler had a motive
  
  If the butler was with the victim and nobody else was with the victim then the butler was alone with the victim
  
  If the butler had a motive and the butler was alone with the victim then the butler is guilty
  
  The butler desperately needed money
  
  The victim was carrying a bundle of cash
  
  The butler was with the victim
  
  Nobody else was with the victim
  

  Sample question:

  Is it the case that the butler is guilty
  

    Possible output for Phase I:

  Atomic propositions found:
  A: (THE BUTLER DESPERATELY NEEDED MONEY)
  B: (THE VICTIM WAS CARRYING A BUNDLE OF CASH)
  C: (THE BUTLER HAD A MOTIVE)
  D: (THE BUTLER WAS WITH THE VICTIM)
  E: (NOBODY ELSE WAS WITH THE VICTIM)
  F: (THE BUTLER WAS ALONE WITH THE VICTIM)
  G: (THE BUTLER WAS GUILTY)
  
  Premises:
  P1: (C A B)
  P2: (F D E)
  P3: (G C F)
  P4: (A)
  P5: (B)
  P6: (D)
  P7: (E)
  

  Possible output for Phase 2:

  QUERY: IS IT THE CASE THAT THE BUTLER WAS GUILTY
  
  Yes, because
  P4, P5, and P1 imply Lemma L1 = (C)
  P6, P7, and P2 imply Lemma L2 = (F)
  L1 and L2 imply Conclusion = (G)
  

  
  Hints and suggestions: Make use of the MATCH function presented in the spiral-bound notes. It is available here, and it can make simple parsing easy. The notes give some examples of its use. You might want to use a hash table to store the associations between symbols and propositions or premises. The function MAKE-HASH-TABLE is built into Common Lisp and can be called with no arguments. The function call, (GETHASH 'SYMBOL MY-HASH-TABLE) will retrieve the value associated with SYMBOL in the hash table that is the value of MY-HASH-TABLE. To store a value, use the SETF macro as follows: (SETF (GETHASH 'SYMBOL MY-HASH-TABLE) 5). You don't need to handle the logical operators OR, ELSE, NOT, and the only place you have to handle AND is in the antecedents (condition parts) of IF sentences.

  Group Work:  This assignment is intended for teams of two.