CMSC 25000 - Artificial Intelligence
Winter 2004
Assignment #1: Due January 13, 2004

Note: Please include the names of any collaborators in the submitted homework.

Note 2: The chalk site for the course is now up and all registered students have been added. Solutions for this and all other coding assignments should be submitted on-line through the student drop-box for the course. Please refer to the on-line help system for chalk to resolve any difficulties with homework submission.

The goals of this assignment are to refresh your skills with Scheme, and to serve as a diagnostic. Most of the subsequent assignments in this course will require a solid foundation in Scheme programming, such as is required to complete the problems below. If you have trouble with this assignment, you will likely have trouble in the rest of the course as well.

Problem 1:

Implement a simple Scheme program to count the number of atoms in an arbitrary Scheme expression. An atom is anything which does not satisfy the pair? predicate. The final null () in a list should be counted as a separate atom. For example,

• (count 'a) ==> 1
• (count '()) ==> 1
• (count '(a b)) ==> 3
• (count '((the sun) (rose (over (the clouds))))) ==> 11
• (count '(a (b . c)) ==> 4

Problem 2:

In this problem, you will extend a simple list matching program. The matcher takes two lists as input, one of which contains variables (the pattern) and one of which does not (the data). The matcher returns a list of bindings that would make the pattern match the data. Variables are represented as a list the first element of which is ?, e.g. (? x).

(match '(a (? x) b c) '(a d b c)) ==> (bindings (x d))

The return value is a list of which the car is "bindings" and the cdr is a list of lists, where the first element of each list is the name of the variable and the second is the value to which it should be bound. E.g.

• (match '(a (? x) b (? x)) '(a c b c)) ==> (bindings (x c))
• (match '(a c b d) '(a c b d)) ==> (bindings)
• (match '(a (?x) b (? x)) '(a c b d)) ==> #f

Matches can appear at any level, and a successful match returns an empty list of bindings. An unsuccessful match returns #f. The code also supports unnamed variables that simply match without returning assignments and are not required to match the same values.

Extend the matcher to allow a new class of variables which match can match sublists of data rather than only atoms. The binding value MUST be a list - even if it is the null list. You should produce SOME binding for each of these variables, though the assignment may not be unique. The solution need not be efficient. (In fact, the straightforward solution is likely to be quite INefficient.)

• (match '((* x) c) '(a b c)) ==> (bindings (x (a b)))
• (match '(a (* x) c) '(a b c)) ==> (bindings (x (b)))
• (match '(a (* x) c) '(a c)) ==> (bindings (x ()))
• (match '(a (* x) c (* x)) '(a b c d)) ==> #f

Please ignore the case where the pattern is a singleton variable rather than a list. Also ignore the error case in which both sublist and atom variables have the same name - you don't need to do the error checking.

The basic code can be found here .