All of the problems in this assignment involve writing CommonLISP code using MCL. You should drop off an electronic copy of your solutions inside the drop folder in the CS251 folder on the CS file server on Celeste. In addition, hand in a hard copy of your code, along with sample runs of your functions that demonstrate that they work correctly (you can print the contents of the Lisp Listener window). Make sure you have tested your functions thoroughly. Please document your code so that it is clear what it does. In addition to the specific functions requested, you may, in some cases, want to write an additional auxiliary function of some sort.

Problem 1 [30]: Recursion versus Iteration

As discussed on page 382 of the MacLennan text, "recursion and iteration are theoretically equivalent." However, some algorithms are expressed more easily using one approach versus the other. Consider the following function count_atoms, which recursively counts all atoms that appear in a list, at all levels of nesting of embedded lists:

(defun count_atoms (L)
(cond ((endp L) 0)
((atom (first L)) (1+ (count_atoms (rest L))))
(t (+ (count_atoms (first L)) (count_atoms (rest L))))))

? (count_atoms '((d f (h k (i)) (h (k l (n h)) h)) ((j (k)) f)))
14

Functions such as this that can process a complex hierarchically-structured list are easy to express using recursion, but much more difficult to implement using iteration. However, it can be done, and the aim of this problem is to demonstrate this fact. Write an iterative version of the count_atoms function. You can use do, dolist or dotimes in your function, and can also make use of any of the built-in LISP functions that we discussed in class. You are not allowed to write any recursive functions! The solution is tricky, but does not need to be overly complex -- I was able to find a solution with 11 lines of LISP code. (If you are not certain whether your particular implementation satisfies the rules of this problem, please come by and ask me about it.)

Problem 2 [30]: Interpreting Infix Arithmetic Expressions

Some of us much prefer to read arithmetic expressions written in the usual infix notation, rather than the prefix notation embodied in LISP expressions. Write a recursive function value whose input is a list that contains a fully-parenthesized arithmetic expression written in infix notation, and which returns the value of the expression. For example:

(value '(3 + ((8 - 2) * (4 / 2))))
15

You only need to handle the four arithmetic operators +, -, * and /.

Problem 3 [30]: Symbolic Pattern Matching

One area of Artificial Intelligence focuses on the construction of so-called expert systems that embody a large database of expert knowledge about a particular problem domain, and are capable of reasoning and problem solving in that domain. Some of these systems are rule-based, which means that their reasoning capabilities are based in part on a large set of simple if-then rules that can make a new assertion if a set of conditions are true. A rule-based deduction system solicits and maintains a body of facts about a current situation, and then tries to match the existing facts with parts of its rules, in order to determine whether a particular rule applies to the current situation, and can be used to make a new inference.

Consider the example of a simple rule-based system to identify animals at a zoo (one of Winston's "pet" problems...) Rules in the system may look like this:

If ?x has hair
Then ?x is a mammal

If ?x gives milk
Then ?x is a mammal

If ?x has feathers
Then ?x is a bird

If ?x flies
?x lays eggs
Then ?x is a bird

If ?x is a mammal
?x eats meat
Then ?x is a carnivore

The symbol "?x" in each rule acts like a variable that could be assigned to a particular animal whose properties are stored in the database of existing knowledge. The database, for example, might contain facts like:

Stripes has hair
Stripes eats meat

By applying two of the above rules, it can be inferred that Stripes is a carnivore. One of the implementation tasks in the construction of such a rule-based system is to match facts in the database with patterns contained in the rules. Part of this task involves binding names used in the facts of the database to variables in the rules (for example, binding Stripes to x above).

Chapter 24 of the Winston and Horn LISP book develops code for performing this matching operation. The patterns being matched have a different syntax from the above facts and rules, but the matching process embodies the same kinds of operations that would be needed in the above application. Pages 353-363 of this chapter are attached to this assignment. The final code for implementing the match function, shown on page 361, can be found in the match.lisp code file inside the match folder that is contained inside the CS251 folder on the CS file server on Celeste (a copy of this code file is also attached). This folder also contains a compiled version of the current code file, match.pfsl. The match.lisp code file contains a function test_match that can be run to see the results of some simple matching examples. On page 362 of the Winston and Horn chapter, Problem 24-1 describes an extension to the matching function, in which the user can specify that a pattern element is to match a data element only if the data element satisfies one or more predicates. Complete the solution to this problem. In your solution, you should also create additional predicates that can be used in your test examples.

Problem 4 [10]: Implementation of Lists as Linked-Node Structures

Suppose that the following sequence of LISP statements were executed in the LISP Listener:

(setf L1 '(a b c))

(setf L2 '(g (h i) (j (k))))

(setf L3 (cons '(m n) (rest L2)))

(setf L4 (append L1 L3))

(setf (first L3) L1)

(setf (rest (rest L1)) (first (rest L2)))

First draw a box-and-pointer diagram that captures the linked-list structures that LISP creates as it evaluates these statements, as discussed in class and described in Chapter 17 of the Winston and Horn LISP book. On the basis of your diagram, then predict what LISP would print as the contents of each list if you then entered the list names:

L1

L2

L3

L4

You can confirm your predictions by entering the above statements into the LISP Listener, and making sure that your diagrams correspond to the actual lists printed in MCL. Hand in your box-and-pointer diagrams.