CS 343: Backchaining and the Web

Due: October 19, 2007.

Files Needed:     rule.lsp     webrpc.lsp     parsed.lsp

In this assignment we will experiment with rules written in a back-chaining Prolog-like form. Rules can perform logical reasoning, call Lisp functions, and obtain real-time information from the web.

Each rule is written in the form: 

(defrules
  ( (fact) )
  ( (conclusion) <- (premise1) ... (premisen) )
)
Variables use the question-mark notation, e.g. ?x. You should not quote anything inside a rule. The backchaining interpreter tries premise predicates in order; write test predicates to fail early when appropriate. Predicates and functions cannot be nested, but values can be saved in variables and used in subsequent calls. The backchaining interpreter is not as flexible as Prolog, and it returns only the first answer that is found.

Some example rules: 

(defrules
  ( (yummy ice-cream) )
  ( (parent ?x ?y) <- (father ?x ?y) )
  ( (lng () 0) )     ; length of a list
  ( (lng ?list ?s) <- (consp ?list) (cdr ?list ?y) (lng ?y ?z) (+ 1 ?z ?s) )
)

Lisp functions can be used as predicates, and the result of a function can be saved by including an extra argument: (sqrt ?x ?result). A nil function value is considered false (except in the case of cdr), while any non-nil value is considered true.

Questions are answered by calling backch with a query pattern; the result is a list of bindings of variables in the query pattern that make the query true. Examples: 

(backch '(yummy ?x))
(backch '(sqrt 2 ?z))
(backch '(car (a b c) ?w))
(backch '(cdr (a b c) ?w))
(backch '(lng (a b c d) ?s))
(backch '(factorial 6 ?s))   ; assuming appropriate definitions

Write rules to accomplish the following; test your rules to make sure that they work.

  1. Sum of a list of numbers.
  2. Factorial of an integer.
  3. Given a list of numbers, produce a list of the numbers that are > 3.
  4. A stock is expensive if its price is over $100. Test whether goog, msft and ibm are expensive.
  5. A metal is expensive if its price is over $100. Test whether gold, silver, and aluminum are expensive.
  6. Latitude of a zip code.
  7. List (latitude longitude) of a zip code.
  8. List (latitude longitude) of a city/state list.
  9. A location is cold if its latitude is greater than 40. Test whether Austin, 02139, and Sheboygan, Wisconsin are cold.
  10. Distance between two things based on their latitude/longitude. Find the distance from Muleshoe, Texas to Sheboygan, Wisconsin, and from Sheboygan to 02139.

The following functions are provided. Note: the functions that access the web must be run under gcl Lisp and Linux, such as the Linux machines in Taylor Hall.

  1. (zipcode zip) returns data (city state zip latitude longitude) for the specified zip code. Example: (zipcode 94025)
  2. (stockprice symbol) returns the current price in dollars of the stock whose symbol is symbol. Example: (stockprice 'goog)
  3. (currency from to) returns the conversion of one unit of currency from to currency to. Some metals are defined as currencies, e.g. gold xau, silver xag, and aluminum xal. Example: (currency 'eur 'usd)   (currency 'xau 'usd)
  4. (citystatelatlong citystate) returns latitude/longitude. Example: (citystatelatlong '("Austin" Texas))
  5. (gcdist latlonga latlongb) finds the great-circle distance in miles between two latitude/longitude positions.