CS 2360
Spring 1998
Homework Assignment 1
Due no later than 8:00am, Monday, April 13, 1998
Greetings young LISPlings! Here's your very first graded homework
assignment in CS 2360. There will be many more, so program early
and often. This assignment comes in two parts. The first part is
just to get your feet wet without worrying about recursion, while
the second part adds the mystery and excitement of functions that
call themselves.
If you were to look through various LISP books, you might find many
solutions to the problems below. In fact, all of them have been solved
by CS2360 students from previous quarters because we've been using
variations of this assignment for years. So it's going to be relatively
easy to find solutions to all these problems if you want to. But knowing
where to find these answers isn't going to help you in the weeks to come; if
you can't solve most of these problems on your own now, you're going to
encounter great difficulty with future homework assignments. So please, do
yourself a very big favor and solve as many as you can on your own and don't
go looking up the answers in textbooks or elsewhere.
For all these problems, make sure that you adhere to the constraints
of the functional programming paradigm (e.g., access only information
passed as parameters, return one value, no side effects, etc.).
Furthermore, remember that you're programming for people, not for the
benefit of the computer. Write your code so that other people can
understand it easily. That means you should worry about modularity
and abstraction where appropriate, and you should employ meaningful
function and parameter names. Don't forget to document your code
with appropriate comments, and it wouldn't hurt to use indentation
to make your code look pretty (which in turn makes for happier and
more generous graders).
Let the LISP hacking begin!
Part One:
You may use only the following predefined LISP functions in constructing your
solutions to the ten problems in part one of this assignment: DEFUN, FIRST,
REST, CONS, LIST, SQRT, *, +, /, and -. Here are the first ten problems:
1) Let's start with something real easy. Construct a function called
SQR which takes one argument, a number, as input and returns the
square of that number.
examples:
? (sqr 3)
9
? (sqr 1.414)
1.9993959999999997
?
2) Let's get slightly more complicated. Define a function called
HEIGHT-IN-INCHES which takes two arguments as input. These
arguments represent a person's height in feet and inches as follows:
if, for example, the person is 5 feet 10 inches tall, the second
argument would be 5 and the third argument would be 10. If the
person is exactly 6 feet tall, the second argument would be 6 and
the third argument would be 0. This function returns one number
which represents the person's height in inches.
example:
? (height-in-inches 5 10)
70
?
3) Feeling a tad pudgy? According to NBC's "Dateline" (which, of
course, is where we should all be getting our medical advice) you
can determine if you're overweight by plugging the appropriate
values into this formula:
704 * your weight in pounds
INDEX = -------------------------------
2
(your height in inches)
If the value of INDEX is 25 or less, you're in great shape according
to NBC. If the value of INDEX is 30 or more, you're at significant
risk for heart disease and other weight-related problems.
Define a function called INDEX which takes three arguments as input.
The first argument is a number representing a person's weight in
pounds. The second and third arguments represent a person's height
as described in problem 2. The function returns the value indicated
by the formula above. Make sure that the value returned by the
function is expressed as a decimal fraction.
examples:
? (index 190 6 0)
25.80246913580247
? (index 190 5 10)
27.29795918367347
?
4) If we use a little algebra, we can rewrite the formula above to
give us something we can use to compute our ideal weight. Assuming
that an index of 25 is optimal, we can then find the ideal weight
as follows:
2
25 * (your height in inches)
IDEAL-WEIGHT = ---------------------------------
704
Define a function called IDEAL-WEIGHT which takes two arguments
as input. These two arguments represent the person's height in
feet and inches as described earlier in problem 2. The function
returns a numeric value representing the person's ideal weight
as calculated by the re-engineered formula just a few lines above.
examples:
? (ideal-weight 5 10)
174.0056818181818
? (ideal-weight 6 2)
194.46022727272728
?
5) Now construct a function called FANCY-IDEAL-WEIGHT which takes three
arguments as input. The first two represent the person's height in
feet and inches, as we've done so many times now. The third
argument is a symbol representing the person's name. The function
returns a list which can be interpreted as a more meaningful
message. The examples below show exactly what we want here. (You
don't need any input/output stuff here; just use what you've learned
so far in class.)
examples:
? (fancy-ideal-weight 5 10 'kurt)
(THE IDEAL WEIGHT FOR KURT IS 174.0056818181818 POUNDS)
? (fancy-ideal-weight 6 2 'john)
(THE IDEAL WEIGHT FOR JOHN IS 194.46022727272728 POUNDS)
?
6) Construct two more functions, called GET-NAME and GET-WEIGHT. Each
function takes exactly one argument, which is a list like that
returned by FANCY-IDEAL-WEIGHT. GET-NAME returns the name contained
in that list (i.e., the fifth element), and GET-WEIGHT returns
the weight (i.e., the seventh element).
examples:
? (get-name '(the ideal weight for kurt is 174.0056818181818 pounds))
KURT
? (get-weight (fancy-ideal-weight 6 2 'john))
194.46022727272728
?
7) When converting between temperatures in degrees Fahrenheit and
degrees Celsius, it is useful to note that -40 degrees Fahrenheit
equal -40 degrees Celsius. This observation makes for the following
symmetric conversion formulas:
C = (F + 40) * 5/9 - 40
F = (C + 40) * 9/5 - 40
Construct conversion functions, F-TO-C and C-TO-F, using these
formulas. Each function takes exactly one argument. The F-TO-C
function takes a number representing a temperature in Fahrenheit and
returns a number representing the same temperature in Celsius. The
C-TO-F function takes a number representing a temperature in
Celsius and returns a number representing the same temperature in
Fahrenheit.
Examples:
? (f-to-c 32)
0
? (f-to-c 98.6)
37.0
? (c-to-f 100)
212
8) Construct a function called SWAP which exchanges the first
and third elements of any list containing three or more elements.
(You can assume the list will have the correct length when
passed; you don't have to do error checking.)
Examples:
?(swap '(a b c))
(C B A)
? (swap '(a b c d e))
(C B A D E)
9) Construct a function called ADDPAIRS which takes two lists of
three numbers as its arguments, and returns a single list containing
the sum of the corresponding numbers from each list.
Example:
? (addpairs '(2 4 6) '(4 5 6))
(6 9 12)
10) Finish the QUADRATIC function we started in class. Add the
SQRT-OF-DISCRIMINANT function that we didn't construct. And so as
not to cause any problems, change the name of DENOMINATOR to
MY-DENOMINATOR, since the DENOMINATOR function already exists
in LISP. Prove to yourself, and to us, that the solution works
by getting it to run on some Common LISP system. Show us the results.
examples:
? (quadratic 2 0 2)
(#c(0.0 1.0) #c(0.0 -1.0))
? (quadratic 2 2 0)
(0.0 -1.0)
Part Two
One of the amazing things about LISP is that so much of the language can be
defined in terms of just a very few pre-existing functions. In this part
of the assignment, you will be constructing your own versions of 14 pre-
existing Common LISP functions by using a relatively small subset of Common
LISP. In the process of constructing those 14 functions, you'll not only
get to practice your LISP programming skills, but you'll also gain familiarity
with a lot of very useful LISP functions such as APPEND and ASSOC.
The functions that you'll be constructing will, in some cases, be
simplifications of the pre-existing functions in that your versions will not
have to deal with optional arguments (which we haven't talked about much
anyway). In all other regards, however, the behavior of your functions should
mimic the behavior of the pre-existing functions. You can check out the
behavior of the pre-existing functions by playing around with them while
you're working in the LISP interpreter, and, if you're especially interested,
you can find exact specifications for those functions in "Common LISP: The
Language" by Guy Steele or "ANSI Common Lisp" by Paul Graham.
The functions that you are to define are listed below, along with examples of
how we expect them to work. For all the functions, you can obtain the name of
their pre-existing counterparts by just removing the prefix "my-".
To construct these functions, you may use DEFUN, COND, IF, NULL, ATOM,
LISTP, NUMBERP, FIRST, REST, CONS, ZEROP, the equality predicates (EQ,
EQL, EQUAL, EQUALP, and =), the inequality predicates (>, >=, <, and <=),
QUOTE (or '), the arithmetic functions (+, -, *, and /), and the Boolean
functions (AND, OR, and NOT). We haven't mentioned all these in class yet,
but if you look them up you'll see what they're all about pretty quickly.
You may not need all these functions, but they are available to you.
You may also use (or reuse) any function which you have defined. Don't
use assignment, and don't use any control structure other than recursion.
Here are the functions we want you to construct:
11) my-member
(my-member 'c '(a b c d e)) => (c d e)
12) my-append
(my-append '(a b) '(c d)) => (a b c d)
13) my-remove-duplicates
(my-remove-duplicates '(a b a c a d)) => (b c a d)
(my-remove-duplicates '(a b (a c) a d)) => (b (a c) a d)
14) my-reverse
(my-reverse '(a b c)) => (c b a)
(my-reverse '(a (b c) d) => (d (b c) a)
15) my-remove
(my-remove 'a '(a b a c a d)) => (b c d)
(my-remove 'a '(a b (a c) a d)) => (b (a c) d)
16) my-substitute
(my-substitute 'x 'a '(a b a c a d)) => (x b x c x d)
(my-substitute 'x 'a '(a b (a c) a d)) => (x b (a c) x d)
17) my-intersection
(my-intersection '(a b c) '(b c d)) => (b c) ; order is unimportant
18) my-union
(my-union '(a b c) '(b c d)) => (a b c d) ; order is unimportant
19) my-make-list
(my-make-list 3) => (nil nil nil)
20) my-subseq
(my-subseq '(a b c d) 0 3) => (a b c)
(my-subseq '(a b c d) 1 3) => (b c)
(my-subseq '(a b c d) 2 3) => (c)
(my-subseq '(a b c d) 3 3) => nil
(my-subseq '(a b c d) 1 4) => (b c d)
21) my-assoc
(my-assoc 'a '((c d)(a b)(e f))) => (a b)
(my-assoc 'c '((c d)(a b)(e f))) => (c d)
22) my-subsetp
(my-subsetp '(c d) '(a b c d)) => T
(my-subsetp '(c d) '(d c b a)) => T
(my-subsetp '(a b c) '(b c d)) => nil
23) my-nthcdr
(my-nthcdr 0 '(a b c)) => (a b c)
(my-nthcdr 2 '(a b c)) => (c)
(my-nthcdr 4 '(a b c)) => nil
24) my-last
(my-last '(a b c d)) => (d)
(my-last '(a b (c d))) => ((c d))
(my-last nil) => nil
Copyright 1998 by Kurt Eiselt. All rights reserved.
Last revised: April 7, 1998