CMSC 671
Artificial Intelligence -- Fall 2005
HOMEWORK ONE
out 9/1/05 due 9/15/05
PART I. What is AI? (20 pts)
READING: Read John McCarthy's paper, "What is AI? (http://www-formal.stanford.edu/jmc/whatisai.html)"
ASSIGNMENT: Describe in your own words what you think AI
is all about, and why you decided to take this class. Did your view
of AI change after reading McCarthy's paper? Tell me what you think
is most interesting or exciting about AI.
PART III. Lisp Programming (80 pts.)
ASSIGNMENT: These problems are intended to help you become familiar
with the basic programming concepts in the Lisp language. Documentation
and error checking are essential in this class, so although these problems
are simple, your code must be documented, and error cases must be handled.
(For example, in problem #2, what happens if the argument isn't a list?)
You should always use the function names and argument
order that I specify, since I may be running automated test programs on your
submitted code. For the same reason, your Lisp file must be
named hw1.lisp.
1. Writing simple functions (10 pts.: 5 pts. each)
(a) Write a function (triple n) to return the the number
that is three times its integer argument n. For example, (triple
2) should return 6; (ltriple 5) should return 15.
(b) Write a function (sumto n) to return the sum of the integers
from 1 to n. For example, (sumto 3) should return 6;
(sumto 10) should return 55. (What do you think (sumto
'hello) should return? What about (sumto -3)?) You should
use recursion to write this function (not the closed-form expression
for the sum.).
2. Operating on lists (30 pts.: 10 pts. each)
There are often many different ways to solve the same problem in Lisp.
In this problem, you will need to use your creativity and knowledge of Lisp
functions to write the same function in several different ways. The function
(noevenp l) should take a list l and return a list containing
everything except the even integers in the list. For example, (noevenp
'(a 2.3 -1 6 hello 3 1 2)) should return (a 2.3 -1 hello 3 1).
You may use the built-in functions integerp and evenp in
your solutions.
- Implement the noevenp function using mapcar. Name this function
noevenp-m.
- Implement the noevenp function using the loop macro. Name this
function noevenp-l.
- Implement the noevenp function recursively. Name this function
noevenp-r.
3. Converting prefix notation to infix notation (40 pts.)
Write a function (infix l) that takes an unevaluated Lisp
expression using the mathematical operators +, -, *, and /, and returns the
"infix" version of this Lisp expression (as a string). As an example,
here are some Lisp expressions and their corresponding infix versions:
- (infix '(+ 1 1)) should return
"1+1" or "(1 + 1)"
- Note that in this case, the outside parentheses are unnecessary and
aesthetically not as pleasing -- but you may find it easier to write the
code in such a way that parentheses are always produced, even for the outermost
expression. Either way is fine.
- (infix '(* (+ 1 2) (- 10 8))) should return
"(1 + 2) * (10 - 8)"
- (infix (* (+ (- 3 4) (/ 4 6)))) should
return "(((3 - 4) + (4 / 6)) * 3)"
Remarks: (1) The exact spacing is not important, but the output
should be readable and correct. (2) All operators should be assumed
to be binary, and you should check for the right number of arguments (e.g.,
(+ 1) and (* 3 4 5) are illegal inputs for the purposes
of this assignment, although the second is a perfectly legal Lisp expression).
Your code should gracefully handle other error cases as well.
Food for thought: (1) What would happen in the above examples
if I left off the quote before the argument to infix? (2) Does this
exercise give you any insight into why Lisp uses prefix notation?
Hints: Here are some built-in Lisp functions that you may find useful:
- numberp, listp
- member
- (format nil "~a ~a" EXPR1 EXPR2) -- print EXPR1 and EXPR2 into
a string (rather than to the screen) and return that string