The questions for your first midterm exam will be taken from only
two sources...the questions below or the questions from your first
three homework assignments. There might be slight wording changes,
but the problems will be the same.
-----
Here's how the Common LISP function butlast works:
(butlast '(a b c d)) => (a b c)
(butlast '((a b) (c d))) => ((a b))
(butlast '(a)) => ()
(butlast nil) => ()
This is a non-destructive function---the argument is not destroyed.
In the space below, without using either butlast or reverse or your
own variant of reverse , use Common LISP and augmenting recursion to
construct your own version of butlast. Call it my-butlast. Note
that butlast takes an optional argument---ignore that.
-----
Now construct the tail-recursive version of my-butlast. Call it
my-butlast-tr. As always, use Common LISP to do this.
-----
Now pretend that you have a working Common LISP interpreter handy,
and while you're at it, pretend that your answers to the two problems
above are actually correct. If you executed my-butlast on that
interpreter, what would be the shape of the process? (You don't have
to draw a picture...an English description would be fine.) What would
be the shape of the process if you executed my-butlast-tr on that
interpreter? Which shape is preferable? Why?
-----
The crossproduct of two lists of numbers, X and Y, where each list
has the same length, is defined as a list of the products XiYi, where:
Xi is the ith element of list X, and
Yi is the ith element of list Y.
Construct a Common LISP function which uses mapcar to compute the
crossproduct of X and Y. Call the function (what else?) crossproduct.
Here's an example of how it would work:
(crossproduct '(1 2 3) '(1 2 3)) => (1 4 9)
-----
Consider the following Common LISP functions:
(defun trans-pairs (list)
(trans-pairs-rec list new-list))
(defun trans-pairs-rec (list new-list)
(cond ((null list) new-list)
(T (trans-pairs-rec (rest (rest list))
(append new-list
(cons (first (rest list))
(first list)))))))
My intent was to write a function called trans-pairs that would take a
list of elements as input, and return that list with successive pairs
of elements transposed, using tail recursion. For example,
(trans-pairs '(a b c d)) => (b a d c)
(trans-pairs '(a b c d e)) => (b a d c e)
Sadly, I can't get it to work. Please find the bugs, tell me what
they are, and show me the corrections, while maintaining as much of
the original code as possible. Thanks.
-----
Using only recursion, write a function called SHUFFLE which takes
two lists as input (assume both lists have the same length) and
returns one list which contains the first element of the first list
followed by the first element of the second list followed by the
second element of the first list and so on, like this:
? (shuffle '(A K Q) '(J 10 9))
(A J K 10 Q 9)
-----
Use a lambda function and mapcar (as the primary control structure)
in constructing the Common LISP function my-sub which substitutes
one item for another in a list, as follows:
? (my-sub 'foo 'bar '(a bar b bar c (bar) d bar))
(A FOO B FOO C (BAR) D FOO)
? (my-sub 'foo 'bar '(a b c d))
(A B C D)
?
-----
A long time ago there was a U.S. president who, despite his oath of
office, didn't always uphold the Constitution. To make matters worse,
this president liked to make tape recordings of himself and his
colleagues as they plotted to sidestep annoying federal laws. When
some of those recorded conversations were revealed to the public,
the less-than-presidential language had been edited out so as not to
offend. In the near future many more of those taped conversations
will be released to the public. So that the citizenry can continue to
be informed without being offended, your task now is to construct a
Common LISP function (or functions) that will automate the censorship
of foul language. You are to call this function sanitize. This
function takes two arguments. The first argument is a list of
offensive words. The second argument is a list representing a
sentence to be censored. The function then returns a copy of the
list passed as the second argument, but with all offensive words
replaced by *expletive-deleted*. You are to use augmenting recursion
as the only control structure, and adhere to functional programming
constraints. And don't forget the importance of abstraction here.
(For purposes of this problem, you can assume that every function shown
on the cheat sheet is available in an augmenting recursion form. If
you need a function not shown on the cheat sheet, you'll have to
construct your own augmenting recursion version of it.) Here's an
example of the function's behavior:
? (sanitize
'(heck darn goshdarn poop hiney)
'(tell that goshdarn john dean to come here or i will kick his hiney
to heck and back))
(TELL THAT *EXPLETIVE-DELETED* JOHN DEAN TO COME HERE OR I WILL KICK HIS
*EXPLETIVE-DELETED* TO *EXPLETIVE-DELETED* AND BACK)
?
-----
Now construct another version of sanitize, but this time use tail
recursion as the only control structure, and again, adhere to
functional programming constraints. Call this version sanitize-tr.
This function should accept the same arguments and give the same
results as sanitize. (For purposes of this problem, you can
assume that every function shown on the cheat sheet is available in
a tail recursion form. If you need a function not shown on the cheat
sheet, you'll have to construct your own tail-recursive version of it.)
Again, don't forget how much graders appreciate good abstractions.
-----
Here are some questions you might be able to answer (with no more than
two sentences each, please) even if you can't write an iota of LISP code:
a) What's functional programming?
b) What's a side effect?
c) What's abstraction?
d) What's reference?
e) What's synthesis?
f) What's the difference between a procedure and a process?
g) What's the "shape" of a process?
h) What's the difference between tail recursion and augmenting recursion?
i) How does the difference between tail recursion and augmenting recursion
affect the shape of a process?
j) Why should programmers care about all of these issues?
-----
So far in this class, we've talked about two control structures for
LISP programming: recursion and applicative programming. (A third
control structure, iteration, is yet to be discussed.) Applicative
programming is based on the idea that functions are data, just like
symbols and lists are data, so one should be able to pass functions
as inputs to other functions, and also return functions as values.
Applicative programming uses applicative operators, which are
functions that take another function as input and apply it to the
elements of one or more lists in various ways. For this problem
you are to use only applicative programming techniques.
Use applicative programming to construct a function called shuffle
which takes as its arguments two lists of equal length and returns
a single list consisting of the elements of the two input lists interleaved:
(shuffle '(a b c) '(d e f))
(A D B E C F)
You don't have to worry about what happens if the two input lists
are of different length. You can construct shuffle however you want
to, so long as you don't use recursion or iteration.
-----
Inevitably in your LISP-hacking career, you'll need the services
of a function which will take a nested list of arbitrary length and
depth and convert it into a simple linear list. This function doesn't
exist in Common LISP, but just about every LISPer has a version
stashed away in their personal library of LISP functions. The
function is usually called flatten, and it works like this:
? (flatten '(((many) new (lisp ((hackers are) stumped) by) this)))
(many new lisp hackers are stumped by this)
In the space below, define your own version of flatten in Common LISP
such that it behaves as just described.
-----
Below is one possible definition of reverse which uses append and list:
(defun my-reverse (r-list)
(cond ((null r-list) nil)
(t (append (my-reverse (rest r-list))
(list (first r-list))))))
Using the substitution model of evaluation described in class,
illustrate the shape of the process generated by evaluating the
expression (my-reverse '(a b c)). Is this a linear iterative
process or a linear recursive process?
-----
Now construct a new version of my-reverse which is tail-recursive.
Use the substitution model of evaluation to illustrate the shape
of the process generated by this new version when evaluating
(my-reverse '(a b c)). Is this a linear iterative process or
a linear recursive process?
-----
Write a function in Common LISP called compare-scores. The
function takes two arguments, both of them numeric values, and
compares them. (You can assume that the values being passed will
be numeric; do not do error checking.) If the second value is
greater than the first, the function returns the symbol better.
If the second value is less than the first, the function returns
the symbol worse. If the two values are equivalent, the function
returns the symbol same. Here are some examples of this function at work:
? (compare-scores 50 80)
BETTER
? (compare-scores 80 50)
WORSE
? (compare-scores 60 60.0)
SAME
-----
Show the following lists in box (or box-and-pointer) notation:
(a (b (c)))
(((a) b) c)
-----
Here are some questions that don't require you to write LISP
code (short but understandable answers would be greatly appreciated):
a) What are the basic principles of the functional programming paradigm?
b) What advantages does the functional programming paradigm offer over
other programming paradigms?
c) Some unenlightened programmers think that recursion is unnecessarily
inefficient when it comes to resource usage. What recursive technique
might these dullards employ to overcome this perceived problem?
-----
Let's make a new function. The function delete-every-nth does
exactly what its name suggests: that is, it deletes every nth
element from a given list. Here are some examples of
delete-every-nth in action:
? (delete-every-nth 3 '(a b c d e f g h i))
(A B D E G H)
? (delete-every-nth 2 '(a b c d e f g h i))
(A C E G I)
? (delete-every-nth 1 '(a b c d e f g h i))
NIL
? (delete-every-nth 0 '(a b c d e f g h i))
(A B C D E F G H I)
? (delete-every-nth 4 '(a b c d))
(A B C)
? (delete-every-nth 4 '(a b c))
(A B C)
? (delete-every-nth 4 nil)
NIL
Your job now is to use Common LISP to construct the delete-every-nth
function (and any other functions which might be necessary). The
delete-every-nth function takes two arguments, as shown in the examples.
The first will always be a non-negative integer, and the second will
be a list of arbitrary length. You can assume that these constraints
will always be met; don't do any error checking on the parameters being
passed. Oh, I almost forgot...you are to implement delete-every-nth with
augmenting recursion. (If you were hoping to do it with tail recursion,
see the next problem. And while we're on the topic, the augmenting
recursion version of this function is not just the tail recursive version
with some meaningless computation tacked on.)
-----
Now construct another version of delete-every-nth, but this time use
tail recursion as the only control structure. Call this version
delete-every-nth-tr. This function should accept the same arguments
and give the same results as delete-every-nth. (For purposes of
this problem, you can assume that every function shown on the cheat
sheet is available in a tail recursion form. If you need a function
not shown on the cheat sheet, you'll have to construct your own
tail-recursive version of it.)
-----
After the second midterm, I'll want to compare each student's score
on the second midterm to his or her score on the first midterm and
see who seems to be getting better at this stuff. To do this, I'll
need a function called analyze-scores. This function will take three
arguments. The first is a list of student names. The second is a
list of scores from the first midterm; the first score belongs to
the first student in the previous list, the second score belongs
to the second student, and so on. The third argument will be a
list of scores from the second midterm. This function will return
a list of lists. Each list within the list will contain a pair
of elements; the first element is a student's name and the second
element is an indication of how the student's second midterm score
compares to that student's first midterm score. Here's an example of
how analyze-scores works:
? (analyze-scores '(alphonse bubba cassandra diogenes edsel)
'(30 40 50 60 70) '(70 60 50 40 30))
((ALPHONSE BETTER) (BUBBA BETTER) (CASSANDRA SAME) (DIOGENES WORSE)
(EDSEL WORSE))
Your task now is to construct analyze-scores (and any other supporting
functions you might need) in Common LISP. You've already done some of
the necessary work in a previous problem, so you can assume the
existence of a compare-scores function if you think it's useful
(hint: it is). Oh, one other thing...the only control structure
you can use here is mapcar. Don't use if, or cond, or anything other
than mapcar.
-----
The figure below shows a high-level abstraction of a binary search tree.
[A diagram would go here.]
If we take the abstraction down a level, an equivalent LISP structure
could look like this:
(55 (25 (12 (6 nil (7 nil nil)) (15 nil nil)) (30 nil nil))
(70 (62 (60 nil nil) (68 nil nil)) (80 nil (99 nil nil))))
In converting our high-level abstraction to a LISP structure, we followed
these conventions:
1. Every tree is represented by a list with three elements.
2. The first or root element must be a node (a number, in this case).
3. The second and third elements represent the descendants of the node
on the left and right, respectively. These elements can be either
another tree or nil, indicating that there are no descendants on that side.
Binary search trees have the nice property that searching for something
in one is relatively quick. A binary search algorithm to find a given
key (i.e., a number) in a tree might look like this:
binary-search
if the tree is empty then return failure
if the value of the key is equal to the value at the root of the tree
then return success
if the value of the key is less than the value at the root of the tree
then perform binary-search on the left subtree
else perform binary-search on the right subtree
In the space below, use Common LISP to construct a function called
binary-search which takes two arguments. The first argument is an
integer representing a key to be found in a binary search tree, and
the second argument is the binary search tree itself, represented in
the list format shown on the previous page. Of course, you'll want
to incorporate all those nice things you've learned about functional
programming, modularity, abstraction, readability, and so on, in your
design. The binary-search function should work like this:
? (binary-search 12 '(55 (25 (12 (6 ... (99 nil nil))))
T
? (binary-search 73 '(55 (25 (12 (6 ... (99 nil nil))))
NIL
?
-----
Remember the flatten function? For this problem, you are to define
a slightly different version of flatten, which we'll call
flatten-with-depth. Just like flatten, flatten-with-depth takes
one argument, a hierarchical list structure of arbitrary depth, and
removes the hierarchical structure. But instead of just returning a
list of atoms, as flatten does, flatten-with-depth returns a list of
two-element lists, where the first element of each pair is an atom
from the input list structure, and the second element is a number
representing the depth of the atom in the original structure. In
other words, flatten works like this:
? (flatten '(a (b (c) d ((e)))))
(A B C D E)
?
but flatten-with-depth works like this:
? (flatten-with-depth '(a (b (c) d ((e)))))
((A 0) (B 1) (C 2) (D 1) (E 3))
?
In the space below, define your own version of flatten-with-depth
in Common LISP such that it behaves as just described.
-----
Think about flatten-with-depth again. Can you construct a function
in Common LISP which when given the output from flatten-with-depth
will return the original list structure (i.e., the input to
flatten-with-depth)? Let's say we call this function unflatten.
It would work like this:
? (unflatten '((a 0) (b 1) (c 2) (d 1) (e 3)))
(A (B (C) D ((E))))
?
If such a function is possible, construct unflatten in the space
below. If you think it is not possible to construct this function,
provide a convincing argument as to why it can't be done.
-----
One of the built-in functions provided by Common LISP is called sublis.
This function makes substitutions for objects in any nested list
structure (a tree). The first argument to sublis is an association
list of dotted pairs. The second argument is the list structure in
which substitutions are to be made. sublis looks at all subtrees and
leaves of the tree; if a subtree or leaf appears as a key in the
association list (that is, the key and the subtree or leaf satisfy
the default equality test), it is replaced by the object with which
it is associated. For example:
? (sublis '((love . hate) (lisp . pascal)) '(i love lisp programs))
(I HATE PASCAL PROGRAMS)
? (sublis '((love . hate) (lisp . pascal)) '(i (love (lisp (programs)))))
(I (HATE (PASCAL (PROGRAMS))))
?
Getting your own version of sublis to work on the first example is
relatively easy. In the space below, construct your own limited
version of the sublis function. Call it my-sublis. This version
of sublis should be limited in that it does the appropriate
substitutions at the very top level of the list hierarchy, but
does not do the substitutions at the lower levels. In other
words, it can do the first example but not the second.
Here's a hint about dotted pairs:
? (first '(a . b))
A
? (rest '(a . b))
B
?
-----
Now construct the full-blown version of sublis as described in
the first part of the previous problem. In other words, it can
do both examples correctly. This function should also be
called my-sublis.
-----
The function my-merge takes two arguments as input. Each argument
is a list, and each list consists of a series of number sorted in
increasing order. This function returns a single list which is
the result of combining the two sorted lists into one sorted list.
Here are some examples:
? (my-merge '(1 2 4 8) '(3 5 6))
(1 2 3 4 5 6 8)
? (my-merge nil '(3 5 6))
(3 5 6)
? (my-merge '(1 2 4 8) nil)
(1 2 4 8)
In the space below, use augmenting recursion to construct your
own version of my-merge in Common LISP (and no, you can't use
LISP's predefined merge function):
-----
Now show us the tail-recursive version of my-merge. In Common
LISP, of course.
-----
Here's a sample of a database for keeping track of baseball statistics:
((KLESKO 44 13 17 5)(LOPEZ 49 5 14 3)(JONES 33 3 9 2))
Each five-element sublist in this structure contains all the data
we're interested in for a given player. The first element is the
player's last name. The second element is his number of times at
bat (abbreviated "ab"). The third element is the number of runs he
has scored (abbreviated "r"). The fourth element is his total hits
(abbreviated "h"). The fifth element is his number of home runs
(abbreviated "hr").
Your job now is to use Common LISP, while employing good procedural
and data abstraction techniques, to construct a retrieval function
called retrieve-data. This function takes three arguments. The
first argument is the player's name. The second argument is the
abbreviation for the data requested. The third argument is the
database itself. The function returns the specific data requested
for that specific player. Here are some examples of how
retrieve-data will be used (assume that the database shown above
has been bound the the variable database):
? (retrieve-data 'lopez 'hr database)
3
? (retrieve-data 'jones 'ab database)
33
? (retrieve-data 'justice 'r database)
NIL
? (retrieve-data 'klesko 'rbi database)
NIL
-----
In baseball, a player's batting average is computed by dividing
the player's hits by the player's times at bat. With that piece
of information, you can now use Common LISP to construct a function
called determine-batting-averages. This function takes only one
argument, the database from the previous problem, and returns a
list of two-element lists. In each of the two-element lists, the
first element is the player's name, and the second element is the
player's batting average. Here's an example:
? (determine-batting-averages database)
((KLESKO 0.386) (LOPEZ 0.286) (JONES 0.273))
Oh, one other thing. Just to make this interesting, we're requiring
you to use mapcar to provide the basic control structure for this function.
-----
The format of the database two problems above isn't necessarily
the best way to represent that data---you can't look at the data
and immediately tell what number means what. This reliance on
the position of a number to tell you what that number means can
in turn lead to errors. At the expense of using up more memory,
we can add some information that will make this database more readable:
((KLESKO (AB 44)(R 13)(H 17)(HR 5))
(LOPEZ (AB 49)(R 5)(H 14)(HR 3))
(JONES (AB 33)(R 3)(H 9)(HR 2)))
In fact, once we add this additional information, the order in which
the numbers are presented is no longer important, which adds some
flexibility:
((KLESKO (AB 44)(R 13)(H 17)(HR 5))
(LOPEZ (HR 3)(R 5)(AB 49)(H 14))
(JONES (H 9)(HR 2)(AB 33)(R 3)))
In the space below, revise your solution from two problems ago so
that retrieve-data works with this new format for the baseball database.
-----
The cheat sheet
(first '(a b c d e)) => a
(second '(a b c d e)) => b
(third '(a b c d e)) => c
(rest '(a b c d e)) => (b c d e)
(cons 'a '(b c d e)) => (a b c d e)
(cons '(a) '(b c d e)) => ((a) b c d e)
(append '(a b) '(c d)) => (a b c d)
(append '(a) '(b) '(c)) => (a b c)
(list 'a 'b 'c) => (a b c)
(list 'a) => (a)
(list '(a b) '(c d)) => ((a b) (c d))
(remove 'a '(a nil b nil a)) => (nil b nil)
(remove nil '(a nil b nil a)) => (a b a)
(length '(a b c d e)) => 5
(length nil) => 0
(* 4 2) => 8
(+ 4 2) => 6
(/ 4 2) => 2
(- 4 2) => 2
(sqrt 25) => 5
(null '()) => T
(null '(a b c)) => nil
(atom 'a) => T
(atom '(a b c)) => nil
(listp 'a) => nil
(listp '(a b c)) => T
(eql 'a 'a) => T
(eql '(a b) '(a b)) => nil
(equal 'a 'a) => T
(equal '(a b) '(a b)) => T
(= 3 3.0) => T
(= 3 5) => nil
(< 3 5) => T
(> 3 5) => nil
(cond ( )
:
( ))
(mapcar #'sqrt '(16 25 36)) => (4 5 6)
(assoc 'b '((a x) (b y) (c z))) => (b y)
(defun )
(function ) =>
It's abbreviated as #'
It can also be applied to lambda functions
Copyright 1997 by Kurt Eiselt. All rights reserved.
Last revised: October 19, 1997