I found my source code from this URL: http://www.cs.washington.edu/research/metip/eaicl2.html. I found the URL when searching for LISP programs from my browser. The code comes from The Elements of Artificial Intelligence Using Common Lisp, Second Edition, published by W. H. Freeman, 41 Madison Ave., New York, NY 10010. I selected the CASE-BR.CL program from Chapter 8 (Commonsense Reasoning).

I copied the code and pasted it into the Allegro CL Lite 5.01 Allegro Common Lisp Console and the code ran without any modifications. The program executes most of the time. Sometimes I’ll get to the second prompt, enter my input and then the program hangs. When this occurs, I can get the program to run again only after rebooting my PC. I am assuming that this is a PC resource issue, possibly a memory problem. The code is an example of a case-based reasoning program. The general idea behind the program is to generate a suggested menu choice for a user based on a menu problem entered by the user and the adaptation of existing menu examples that are already defined.

I will start out by attempting to describe how this program works by providing a general description of the program and the more complex functions. I will identify the most important and complex functions and provide explanation for the reasoning of their use and their intent. I will also attempt to point out the specific functions or declarations which are typical of a case-based reasoning program. I have provided list of all the parameters passed to the functions and a list of all of the functions used in the program. I have also included an explanation or description of these parameters and an explanation or description of each function. When possible, I have executed the code as stubs in order to gain an understanding of what and how the functions work. Not all of my stub tests were successful, but in that case I would break down the stub to a point where I could glean a general idea of the intent of the function. The last part of this lab contains a flow diagram of the functions.

This code is broken up into three parts by the author/creator.

Part 1 is referred to as Representation of Cases. The section is used to define the structures for the menu examples. The example structure consists of the problem, solution, and result. The problem structure consists of cuisine, n-diners, diet-restrictions, and cost-per-person. The solution structure consists of main-course, appetizer, and dessert. Three menu examples are created using defparameter. Then an example-database is created using defparameter and the three menu examples. This database would be the case base or the set of cases that is used for identifying possible matches. I’m not sure if this could be considered past experience or not.

Part 2 is referred to as Matching of Problems. The functions in this section are used to identify an example-problem which most closely matches the current-problem entered by the user. The key function of this section is the distance function. This function is the main function responsible for "similarity metrics."

Part 3 is referred to as Interpretation of Examples. This is where adaptation of the most closely related example-problem takes place to create a solution to the current-problem entered by the user. The main function responsible for driving adaptations is the adapt-solutions function, but most of the work comes out of the fix-diet-conflicts function.

An example in the context of this program consists of a problem, a solution, and a result. The problem is the cuisine, number of diners, diet restrictions, and cost per person. This case based reasoning program builds three examples which are used as comparisons to the problem example that is built by user input as responses to prompts in the cbr function. You can think of the example problems as the possible match cases that have similar metrics to the problem example. The example problem with the most similarities will be the example that is adapted to provide a solution to the menu problem.

After entering a problem menu, the software retrieves all the existing menu examples and compares the existing menu examples to the problem menu entered by the user. This is accomplished by functions retrieve-examples insert-pair and distance. retrieve-examples uses the dolist command to take each example problem/solution from the database and have it evaluated against the user entered problem menu. The program uses a distance function to calculate the closeness of the problem menu entered to the example problems that exist already. The lower the "distance" the closer the existing menu example is to the problem menu entered. This existing example menu will then be the menu that will be adapted. The distance function checks the similarities of cuisine type (American, Italian, Mexican, etc), number of diners, diet restrictions, and cost per person, giving most weight to the cuisine type and diet restrictions comparisons. In other words, the software will evaluate an existing example menu and choose one with most similarities giving most weight to cuisine type and diet restrictions. If for example an existing menu has a cuisine style of American and another has a cuisine style of Asian and the user entered cuisine of American, then we would want the software to identify the American menu example as a possible solution as it is more similar to what was requested than the Asian menu example would be. The code used to determine the "distance" seems a bit complex, but basically, the cuisine style is compared to a nested list of possible cuisine’s and compared to each item in the list for a match. If the cuisine is found at the root then a zero is returned, otherwise the tree is searched at the next depth for a match and so on until a cuisine type is found or not. The end result of "Matching of Problems" is the identification of an existing example menu that mostly closely matches the problem menu entered by the user.

Once an existing example menu problem is found, the software modifies that example menu problem to meet the requirements of the problem menu entered by the user. This is accomplished by calling four main functions, fix-cuisine, fix-n-diners, fix-diet-conflicts, and fix-cost.

A diet restriction is identified by use of a hash table in the food-fact-p function. This function is called with each course from the chosen example menu. This is accomplished with the dolist verb. In the food-fact-p function there exists food facts about listed courses. For example mussels have no meat and fruit has no sugar. food-fact-p is called with the name of the course and the diet-conflict in order to identify whether a substitution needs to be made or not. If the selected example menu had a main course of taco’s, but the user entered a diet restriction of no-meat, then the taco’s would need to be substituted as food-fact-p would return a non T value meaning that the course does not fulfill the diet-restriction. The substitution is accomplished in the apply-diet-subst function. There is a defparameter *ingredient-fixes*definition for the diet restrictions and it is defined as:

(defparameter ingredient-fixes

‘ ((no-gluten . (wheat-flour . rice-flour))

(no-sugar . (sugar . dried-fruit))

(no-meat . (meat . tofu))

(seafood . (meat . shrimp)) ) )

A replacement function performs the following code (rest (rest (assoc diet-restr *ingredient-fixes))). If the diet-restriction is no-meat, then the replacement function returns tofu. This process is repeated for the appetizer and dessert courses.

The solution for solving the cost per person problem is fairly simple. When fix-cost is called with the current problem and the existing menu example, the cost per person amount is compared. If the user entered in a dollar value that is less than the cost per person value of the existing menu example, then the proposed solution has Crackers substituted for the appetizer. I think that this program could be modified to handle this situation a little bit better. For one thing, I think that there should be a choice of appetizers. Also, what if a diet-restriction entered was no-salt? Well, that is not a valid diet-restriction in this code, but the program could be modified to include that diet-restriction. And if it did, then the default substitution of crackers for the appetizer when costs were to high would not always be a valid choice.

The solution for solving the number of diners is a bit odd. The number of diners entered by the user is substituted in the existing example problem, but nothing ever happens with that information. The replacement is made to the problem structure, but it is not used as output anywhere.

There is a call to solve-cuisine, but no code associated with it. The function was listed for consistency. Cuisine is the style of food and I don’t think the style should ever be substituted. If someone request Asian food, then the Case Base Reasoning menu solving software should not, in my opinion, suggest a French style menu.

I ran the menu planning problem with the following inputs: cuisine = Swedish, number of diners = 4, diet-restrictions = no meat, cost per person = 8. The results were:

The proposed menu is as follows:

The proposed main course is: GRAVLAX.

The proposed appetizer is: CRACKERS.

The proposed dessert is: LINZERTORTE.

The program had a similar example problem of Gravlax, mussels and Linzertote at a cost of 10 per person which also had the diet-restriction of no meat, but I responded to the program that I wanted a Swedish meal for four with no meat at a cost of 8 per person. The program modified a known solution by substituting crackers for mussels in order to meet my cost per person request.

I ran the menu planning problem with the following inputs: cuisine = American, number of diners = 4, diet-restrictions = no meat, cost per person = 10. The results were:

The proposed menu is as follows:

The proposed main course is: (SUBSTITUTE TOFU FOR MEAT IN TACOS).

The proposed appetizer is: CHIPS-N-SALSA.

The proposed dessert is: FRUIT.

The program has predefined example2 as a Mexican cuisine, for 6 diners with a no-gluten diet restriction and a cost of 3 per person. This example was selected primarily because of the closeness of the cuisine. In the *cuisine* tree, Mexican food is considered to be within the hierarchy of American food. So the distance functions selected example2 as the closest matching existing menu example to be modified. Then when the program identified that taco’s did not meet the diet restriction criteria, I specified no-meat, a substitution had to be made. apply-diet-subst used both the replacement function and the *ingredient-fixes* structure to substitute tofu for meat in the solution menu.

I ran the menu planning problem with the following inputs: cuisine = French, number of diners = 12, diet-restrictions = NIL, cost per person = 18. The results were:

The proposed menu is as follows: The proposed menu is as follows:

The proposed main course is: GRAVLAX.

The proposed appetizer is: MUSSELS.

The proposed dessert is: LINZERTORTE.

The program selected example1 menu because the distance computed for this menu was lower than the other two menus. I ran the program through trace mode to break down the distance as follows.

Now the distance function uses a formula of a1 x1 + a2 x2 + … +an xn. Using the formula in the function:

Example-menu1’s distance equals 5 8 + 1 8 + 2 1 + 1 8 = 58

Example-menu2’s distance equals 5 8 + 1 6 + 2 1 + 1 15 = 63

Example-menu3’s distance equals 5 8 + 1 10 + 2 0+ 1 13 = 63

Because example-menu1 had the lowest distance return value, it was selected as the menu that would be used as a solution. Because there were no diet restrictions, there were no adaptations to the menu.

node name or cuisine type returned from lowest-common-ancestor and passed to span. Used in depth to identify the closeness of cuisine’s from the current-problem and example-problem.

main-course, appetizer, or dessert

The results of the user inputs from the prompts in the cbr function. This is the case that is to be solved by the program.example:

current-problem cost per person

example-problem cost per person

current-problem cuisine. (European, American, Norwegian, Chinese, etc)

Example-problem cuisine. (Swedish, Mexican, Szechuan)

The diet restriction entered by the user from the prompts in cbr. Could be "no-meat", "no-sugar", or "no-gluten"

Diet restriction from the current-problem

Diet restriction from the example-problem

An example in the context of this program consists of a problem, a solution, and a result. The problem is the cuisine, number of diners, diet restrictions, and cost per person. This case based reasoning program builds three examples which are used as comparisons to the problem example that is built by user input as responses to prompts in the cbr function. You can think of the example problems as the possible match cases that have similar metrics to the problem example. The example problem with the most similarities will be the example that is adapted to provide a solution to the menu problem.

One of the pre-defined problems that exists in the example-database.

A food item from either the main course, appetizer, or dessert.

Same as cuisine1

Same as cuisine2

A cuisine

Same as current problem.

Same as diet-rest

The adapted example-problem that is presented to the user

Same as example-problem

*cuisines* defined as:

(defparameter *cuisines*

‘(world (asian (chinese (szechuan)))

(european (scandinavian (norwegian) (swedish))

(italian (tuscan) (sicilian)) )

(american (mexican) (canadian))

) )

Same as current-problem

The number returned from distance

Parameters passed in: None.

Function description: Top level function or main function. Prompts user for inputs which is used to build the suggested menu. Asks user for and accepts input for cuisine type, number of diners, diet restrictions, and cost per person. Uses a "loop" command to control multiple iterations through the menu planner.

Parameters passed in: problem

Function description: A top level function called by cbr. solve calls retrieve-examples which looks for the existing example problem that most closely matches the user input problem. It then calls adapt-solution which may modify the selected example in order to provide a solution to the problem entered by the user.

Parameters passed in: current-problem, example-database.

Function description: Called by solve. Returns to solve, the list of example problems in sorted order, sorted from lowest to highest with the value determined by the distance function. This function has a nested call to insert-pairs and distance, i.e. (insert-pair (distance current-problem (example-problem this-example)).

Parameters passed in: value, example, the-list

Function description: Called from retrieve-examples. Uses recursion to sort the list of example problems into increasing order. The first example problem in the list will be the example problem that has the most similarities to the current-problem defined by user input.

Parameters passed in: current-problem, example-problem

Function description: Called from retrieve-examples. Computes and returns the distance between two problems by assigning weight values to the closeness of the user input problem (current-problem) and the existing problem examples. More weight is given to the cuisine, followed by diet restrictions, and then number of diners and cost per person. Distance calls functions which determine the closeness of the cuisine, number of diners, diet restrictions, and cost per person. The value of each difference for each existing example problem is returned to retrieve-examples where the list of example problems are sorted in order of most likeness to the current-problem to least likeness to the current-problem.

Parameters passed in: cpp1, cpp2

Function description: Called from distance. Returns the absolute value of the difference between the current-problem cost per person and each example-problem cost per person.

Parameters passed in: n1, n2

Function description: Called from distance. Returns the absolute value of the difference between the current-problem number of diners and each example-problem number of diners.

Parameters passed in: cuisine1, cuisine2

Function description: Called by distance. The purpose of this function is to assign a value to the closeness of the cuisine chosen in the current-problem and the cuisine’s that exist in the example-problems. Calls lowest-common-ancestor to help identify this closeness value.

Parameters passed in: dr1, dr2

Function description: Called from distance. As stated in the comments of the code, this function "Returns the number of elements that occur in either set DR1 or set DR2 but not both." The code:

(+ (length (set-difference dr1 dr2)

(length (set-difference dr2 dr1))

set-difference returns the items in set 2 that are not in set 1 and then returns the items in set 1 that are not in set 2. The length command returns the number of items returned from the set-difference command. The end result of this function is a number of items that are different from the diet restrictions from the current-problem and each example-problem. If the diet restrictions are identical then this function will return a zero. If the current-problem has a single diet-restriction of "no-meat" and an example-problem has a single diet-restriction of "no-gluten", then this function would return the value of 2 to distance.

Parameters passed in: tree, n1, n2

Function description: Called from cuisine-dist. tree is the pre-defined tree structure called *cuisines*. n1 and n2 are the cuisine’s from the current-problem and the example-problems. Returns to cuisine-dist the name of the cuisine found in the *cuisines* tree. Uses recursion to navigate through the tree searching for a matching cuisine.

Parameters passed in: node, tree

Function description: Called by lowest-common-ancestor. Used with lowest-common-ancestor to identify whether a cuisine is part of the *cuisines* tree or not. This function recursively calls itself.

Parameters passed in: c

Function description: Called by cuisine-dist. One of the many functions used to determine the closeness of cuisine’s from the current-problem and example-problem. Calls tree-depth. Determines the difference between the depth of the *cuisines* (which is 3 in this program) and the depth returned from tree-depth. It then uses "expt" to return a power of 2 on the difference to cuisine-dist.

Parameters passed in: node, tree

Function description: Uses not-in and recursion to walk through the tree searching for the depth of node in the tree, where node is the cuisine type found in lowest-common-ancestor and tree is the *cuisines* tree.

Parameters passed in: current-problem, trial-example

Function description: Called by solve. This function calls the four functions that are responsible for applying adaptations to an example-problem in order to create a solution to the current-problem. This function calls fix-cuisine, fix-n-diners, fix-diet-conflicts, and fix-cost. This function returns the adapted example-problem to the solve function.

Parameters passed in: current-prob, example

Function description: This function does nothing. The author doesn’t change the cuisine.

Parameters passed in: current-problem, example

Function description: Called by adapt-solution. Copies the number of diners from the current-problem to the example-problem. This function doesn’t make much sense to me since the program never uses the number of diners as output. All that happens is that the n-diners variable as part of the solution structure is replaced by the number of diners entered by the user.

Parameters passed in: current-problem, example

Function description: Called by adapt-solution. If the cost per person from the current-problem (user entered problem) is greater than the cost per person of the example-problem, then Crackers are set to the solution-appetizer.

Parameters passed in: current-problem, example

Function description: Called by adapt-solution. For each diet-restriction entered by the user that exists in the current-problem structure the function satisfies-diet is called passing the current-main-course, current-appetizer, and current-dessert. If any of these calls does not satisfy the diet restriction then a call is made to apply-diet-subst passing the current main-course, current-appetizer, or current-dessert where diet substitutions are made to the menu. Once the tests are made to see whether a diet substitution needs to be made or not and then after the diet substitutions are made if needed, this function copies the new structure into a solution structure which is passed back to adapt-solution. This the main driver function responsible for identifying diet conflicts in an example-menu problem and correcting it to meet the requirements of the current-problem entered by the user. For instance, if the user entered an American cuisine for 4, with a diet restriction of "no meat" and a cost per person of eight dollars an example menu, example2, will be found. example2 is defined as:

#S(PROBLEM :CUISINE MEXICAN :N-DINERS 6

:DIET-RESTRICTIONS # :COST-PER-PERSON 3)

:SOLUTION

#S(SOLUTION :MAIN-COURSE TACOS :APPETIZER CHIPS-N-SALSA

:DESSERT FRUIT)

This function, fix-diet-conflicts will be responsible for making the substitution of tofu for meat in order to satisfy the "no meat" diet restriction entered by the user.

Parameters passed in: example

Function description: Called by fix-diet-conflicts, fix-n-diners, and fix-cost. This function simply copies the example-problem structure into a new structure.

Parameters passed in: course, diet-restr

Function description: Called by fix-diet-conflicts. Calls basic-course passing course and food-fact-p with the return value from basic-course and diet-restr. Basic-course returns to satisfies-diet the value from the call to food-fact-p, T or not T. satisfies-diet passes this value back to fix-diet-conflicts.

Parameters passed in: course

Function description: Called by satisfies-diet. Recursively calls itself until course is isolated.

The course can be for the main-course, appetizer, or dessert. Returns the course to satisfies-diet, which in turn calls food-fact-p.

Parameters passed in: food, property

Function description: Called by satisfies-diet. A hash table is created that has a diet restriction assigned to specific courses. The course and diet restriction are passed to this function as food and property. If the diet restriction is found to be matched with the course, then the diet restriction is satisfied and T is returned to satisfies-diet.

Parameters passed in: food, property

Function description: Called by food-fact-p.

Parameters passed in: diet-restr, course

Function description: Called by fix-diet-restr. Calls replacement and offender. If a replacement ingredient can be found then this function builds a string to alert the user of the replacements.

Parameters passed in: diet-restr

Function description: Called by apply-diet-subst. Isolates and returns the diet restriction item from the *ingredients-fixes* association.

Function description: Called by apply-diet-subst. Isolates and returns the diet restriction substitute from the *ingredients-fixes* association.

Parameters passed in: solution

Function description: Called by cbr. Prints out the results of the cased base reasoning program.

Seen a few examples of nested function calls: Example (function-call-1(function-call-2(function-call-2-parameter) function-call-1-parameter).

I found the fact that due to the limited amount of example menus or previous cases, that if I were to request a French meal or Polish meal I would get a cuisine based on the other inputs. I could get a Szechuan or American or Swedish meal based on the diet restrictions, cost per person and number of diners. One change that I would make to this program would be to limit the cuisine choices to the cuisine’s that are already pre-defined. Something else that I thought of to help improve the program would to automate the building of previous experiences or test cases by creating new example menus from the solution results. Any how, I found that this code was pretty complex in some areas and easy in others, but I would of liked to have more time to dissect it some more.