LISP - Diagnosis Tree

In this LISP assignment, you will provide a medical diagnosis based on a patient's symptoms.

Example Medical Diagnosis Tree:

Q1 Question: PAIN ?

Y: Q5 Question: TENDERNESS IN ABDOMEN ?

Y: Q8 Question: X-RAY SHOWS STONES ?

Y: D9 Diagnosis: TREAT KIDNEY STONES

N: D8 Diagnosis: SCHEDULE APPENDECTOMY

N: Q6 Question: PAIN IN THROAT ?

Y: D7 Diagnosis: ADMINISTER STREP TEST

N: Q7 Question: FEVER ?

Y: D6 Diagnosis: TREAT FLU

N: D5 Diagnosis: PRESCRIBE ACETAMINOPHEN

N: Q2 Question: COUGH ?

Y: D1 Diagnosis: TREAT COMMON COLD

N: Q3 Question: FEVER ?

Y: D2 Diagnosis: TREAT FLU

N: D3 Diagnosis: THANK YOU FOR VISITING

Suppose patient "Alice" has simply a "fever". Based on the diagnosis tree:

Q1: Pain ? N

Therefore, we ask

Q2: Cough ? N

Therefore, we ask

Q3: Fever? Y

So, the diagnosis is "treat flu"

Suppose patient "Bob" has the symptom "tenderness in abdomen", what happens? First, we realize the "tenderness in abdomen" is a type of pain when we see the symptom.

Q1: Pain ? Y

Therefore, we ask

Q5: TENDERNESS IN ABDOMEN? Y

Therefore, we ask

Q8: X-RAY SHOWS STONES ? N

So, the diagnosis is "SCHEDULE APPENDECTOMY "

In our use of the diagnosis tree, the medic would have done the x-ray and then known an answer to Q8. In our execution we will only know the symptoms before going through the tree.

We will represent the diagnosis tree using a hash table entry for each node in the tree:

Q1: an entry in a question-HT:

key: Q1

value: (Q5 Q2 PAIN)

Q2: an entry in a question-HT:

key: Q2

value: (D1 Q3 COUGH)

Q5: an entry in a question-HT:

key: Q5

value: (Q8 Q6 TENDERNESS IN ABDOMEN)

D1: an entry in a diag-HT:

key: D1

value: (TREAT COMMON COLD)

Needed hash tables:

question-HT - each entry represents a question as three values: ID for Y, ID for N, question

diag-HT - each entry represents a diagnosis which is a list of atoms

isa-HT - for a type of symptom, it maps it to higher concept. For example, (tenderness in abdomen) is a pain.

symptom-HT - each entry represents a patient's current symptoms. Examples:

Alice: (FEVER) - T

Bob: (TENDERNESS in ABDOMEN) - T

and also (based on the isa-HT)

(PAIN) - T

I provided two LISP files:

p4LispDef.txt - execute this first (before loading your functions)

It defines:

putp - function to put a property in a hash table for a key value

getp - function to get a property from a hash table for a key value

question-HT

diag-HT

symptom-HT

isa-HT

qyn - macro to put a question into the question-HT hash table.

clearSymptoms - clears (deletes) all entries in symptom-HT

p4LispRun.txt - execute this after you have loaded your functions

It uses QYN, DIAG, and ISA to create the diagnosis tree and isa information.

It uses printTree, clearSymptoms, symptom, and triage to exercise that functionality.

You must code these macros:

diag similar to qyn except it puts the entry in diagnosis-HT.

(diag diagnosisID diagnosis) uses putp to record the diagnosisID as the key and diagnosis (which can be many atoms) as the value in the diagnosis-HT.

Example: (DIAG D1 Treat common cold) would record

D1 (treat common cold) in diag-HT

isa puts an entry in the isa-HT. Please examine the example above.

(isa expr type) uses putp to record the expr (which can be an atom or a list) as the key and type as the value in the isa-HT.

Example: (isa (tenderness in abdomen) pain) would record

(tenderness in abdomen) (pain) in isa-HT

symptom puts an entry in the symptom-HT. If the symptom has an isa in the isa-HT, it also inserts an entry for that isa in the symptom-HT.

(symptom symptom) uses putp to record the symptom as the key and T as the value in the symptom-HT. Additionally, if symptom is a type, it records that the patient has that type as a symptom.

Example: (symptom tenderness in abdomen) would actually record two symptoms since (tenderness in abdomen) is a (pain):

(tenderness in abdomen) T in symptom-HT

(pain) T in symptom-HT

You must code these functions:

printTree prints a nicely diagnosis definition tree (as shown above)

(printTree rootId) is passed the ID of the root of the diagnosis tree and prints the diagnosis tree like what is shown above. This will probably also use your princWOP function. Hint: printTree probably should call another function to recursively print indented nodes of the tree.

triage shows the execution of the diagnosis tree based on the symptoms and returns the diagnosis or NIL (if there isn't one). This will probably use your printWOP function. See the sample output.

Notes:

If you want to examine the contents of a hash table, simply enter its name in the high-level read loop:

diag-HT

Some built-in output functions:

(princ arg1 arg2 ...) - prints each argument separated by spaces. It does not follow it with a linefeed.

(terpri) - prints a linefeed.

You can only use the functions/macros we discussed in the LISP notes, pgm #2, pgm#3, and macros/functions in this assignment.

Load my definitions using (load "p4LispDef.txt" :echo T :print T).

Load your code using (load "p4Lisp.txt" :echo T :print T).

To execute on the test cases using the file I provided: (load "p4LispRun.txt" :echo T :print T)

Sample Partial Output:

(setf ROOT 'Q1)

Q1

(printTree ROOT)

Q1 Question: PAIN ?

Y: Q5 Question: TENDERNESS IN ABDOMEN ?

Y: Q8 Question: X-RAY SHOWS STONES ?

Y: D9 Diagnosis: TREAT KINDEY STONES

N: D8 Diagnosis: SCHEDULE APPENDECTOMY

N: Q6 Question: PAIN IN THROAT ?

Y: D7 Diagnosis: ADMINISTER STREP TEST

N: Q7 Question: FEVER ?

Y: D6 Diagnosis: TREAT FLU

N: D5 Diagnosis: PRESCRIBE ACETAMINOPHEN

N: Q2 Question: COUGH ?

Y: D1 Diagnosis: TREAT COMMON COLD

N: Q3 Question: FEVER ?

Y: D2 Diagnosis: TREAT FLU

N: D3 Diagnosis: THANK YOU FOR VISITING

NIL

(Symptom fever)

NIL

(symptom pain in throat)

NIL

(triage)

ID: Q1 (Q5 Q2 PAIN) Y

ID: Q5 (Q8 Q6 TENDERNESS IN ABDOMEN) N

ID: Q6 (D7 Q7 PAIN IN THROAT) Y

(ADMINISTER STREP TEST

p4LispDef.txt:

;;; putp ;;; Parameters: ;;; symbol - symbol to be given the property ;;; ht - hash table to store the symbol and its property value ;;; value - the property value ;;; Purpose: ;;; stores the property value for the symbol in the specified hash table (defun putp (symbol ht value) (setf (gethash symbol ht) value) ) ;;; getp ;;; Parameters: ;;; symbol - symbol about which we want its property value ;;; ht - hash table to store the symbol and its property value ;;; Purpose: ;;; returns the property value for the symbol in the specified hash table ;;; Returns ;;; The property value for the symbol in the specified hash table. ;;; If not found, NIL is returned. (defun getp (symbol ht) (gethash symbol ht) ) ;;; set up question and diag hash tables (setf question-HT (MAKE-HASH-TABLE)) (setf diag-HT (MAKE-HASH-TABLE))

;;; since the key for both the symptom and isa hash tables is a list, ;;; we have to tell LISP to use EQUAL for the entry comparison instead of EQ.

(setf symptom-HT (MAKE-HASH-TABLE :test #'equal)) (setf isa-HT (MAKE-HASH-TABLE :test #'equal))

;;; qyn macro ;;; Parameters: ;;; qid - unique ID of a question ;;; ex - the rest of the arguments make up a list which represents the question ;;; Purpose: ;;; Inserts an entry into the question-HT with qid as the key and ex as the value. ;;; Notes: ;;; A macro is used instead of a function so that the arguments do not have to be ;;; quoted.

(defmacro qyn (qid &rest ex) `(putp ' ,qid question-HT ' ,ex ) )

;;; clearSymptoms ;;; Parameters: ;;; n/a ;;; Purpose: ;;; Clears (i.e., deletes) all entries in the symptom-HT. ;;; Returns: ;;; n/a

(defun clearSymptoms() (clrhash symptom-HT))

p4LispRun.txt:

;;; p4LispRun.txt - defines the diagnosis tree and runs your functions

(QYN Q1 Q5 Q2 Pain) (QYN Q2 D1 Q3 Cough) (QYN Q3 D2 D3 Fever) (QYN Q5 Q8 Q6 Tenderness in abdomen) (QYN Q6 D7 Q7 Pain in throat) (QYN Q7 D6 D5 Fever) (QYN Q8 D9 D8 X-ray shows stones) (DIAG D1 Treat common cold) (DIAG D2 Treat Flu) (DIAG D3 Thank you for visiting) (DIAG d5 Prescribe acetaminophen) (DIAG D6 Treat Flu) (DIAG D7 Administer Strep Test) (DIAG D8 Schedule appendectomy) (DIAG d9 Treat kindey stones)

(isa (tenderness in abdomen) pain) (isa (pain in throat) pain) (isa (x-ray shows stones) stones)

(setf ROOT 'Q1) (printTree ROOT)

(Symptom fever) (symptom pain in throat) (triage)

(CLEARSYMPTOMS)

(symptom fever) (triage)

(CLEARSYMPTOMS)

(symptom tenderness in abdomen) (symptom x-ray shows stones) (triage)