I assigned 10 points to the assignment: 1 for each of the 5 programs, 3 for appropriate test inputs, 2 for the critique of my proposed Pascal program. I gave 1 or 2 extra points when the presentation was particularly clear, although I will compute grades based on a perfect score of 10. On other assignments, I will continue to give extra points for nice presentations. The resulting scores were 7, 8, 8, 9, 9, 9, 10, 10, 10, 10, 10, 10, 11, 12, 12. I regard all the papers as being pretty good for this assignment.
It is my policy to comment on everything that I notice, even if it doesn't affect the grade. In a few cases, I pointed out that you wrote more than necessary for this problem. I only hold the extra against you if it obscures the main point.
I looked only for a reasonable correct solution in each language. I noted a few minor points of style, but they did not affect the grading. I preferred the functional, rather than the desctructive, version in Pascal and C, but that preference wasn't strong enough to add up to one point.
Aside from not doing one of the 5, the main source of error was misunderstanding the meaning of cons in Scheme. (cons object list) adds the given object to the beginning of the given list. It does not combine two lists into one. That requires an append, which you may define recursively. If you made this error, then your reversal of (a b c) looked like (((() . c) . b) . a) instead of (c b a). In the internal data structure used by Scheme, called S-expressions, (a b c) looks like
.
/ \
a .
/ \
b .
/ \
c nil
.
/ \
c .
/ \
b .
/ \
a nil
.
/ \
. a
/ \
. b
/ \
nil c
The other error was writing a Prolog program with the same flaw as my proposed Pascal program: it printed out the contents of the list in reverse order, but never actually constructed a list. You should ignore I/O commands in Scheme, ML, and Prolog. All of our work in this course will involve the pure functional uses of those languages. The interpreters allow you to take expressions as inputs directly, and they automatically display the resulting evaluated expressions.
I gave full credit for anything vaguely reasonable. As a mental exercise, I'll beat this question harder than it's really worth. It seems that the ideal test set consists of (in Scheme notation) (), (a), (a b), (a b c). (Any other three elements would do as well as a, b, and c.) The empty list is important to check the basis of the iteration or recursion. The list of length 3 is the shortest one that distinguishes reversal from rotation, which is another very natural permutation of lists. I can't think of any real common reordering operations that look just like reversal on lists of length 3. On might argue that the lengths 1 and 2 are superfluous, but it seems sensible to include them because of the simplicity of the sequence 0, 1, 2, 3.
In any case, it makes sense to use the same tests in each language. There is nothing about any of the particular solutions to suggest special tests. I was mildly annoyed (but not enough to deduct a whole point) by the examples that used a word as a sequence of characters to be reversed in some languages, and as an atomic element of a list in other languages. This was misleading given the focus of the assignment.
There are two different sensible recursive algorithms for list reversal. Either one can be encoded very simply in Scheme, ML, and Prolog. The Scheme and ML solutions look very similar. The Prolog one looks very different, but if you think of systematically rewriting x = reverse(y) as reverse(x,y) you should start to see the connection (there's much more to Prolog than this correspondence suggests, but it's a starting point for understanding simple Prolog programs). I will present the two algorithms in a generic recursive notation, and let you translate into the particular languages Scheme, ML, Prolog. I use Prolog's notation for lists.
This is a perfectly sensible recursive definition of reverse, using the additional function append, which combines two lists into one by concatenating the contents. (There is a minor variation using a function that adds a single element to the end of a list). This algorithm takes a quadratically increasing number of steps to reverse a list. That is, it takes 4 times as many steps to reverse a list that is twice as long.reverse([]) = [] reverse([head | tail]) = append(tail, [head]) append([], x) = x append([head | tail], x) = [head | append(tail, x)]
In order to reverse a list in a number of steps proportional to its length, we need a slightly cleverer two-argument function:
Of course, "clever" is an embarassing name for the function. Finding a more sensible name is a good way to work on your understanding of the way this function works. One way to think of clever is that it simulates the efficient iterative reversal algorithm that repeatedly takes an element from the beginning of the list to be reversed, and adds it to the beginning of the result. The arguments to clever at the ith level of recursion simulate the local variables of that iterative algorithm. I'm not quite satisfied. Instead, let's think of what clever actually does as a function. It appends the reversal of its first argument to its second argument. That is, clever(x, y) = append(reverse(x), y). So, it makes sense to use a name that suggests the appending of a reversal, such as append_reverse, or apprev if we don't like long function names.reverse(x) = clever(x, []) clever([], y) = y clever([head | tail], y) = clever(tail, [head | y])
Last modified: Mon Jan 16 08:41:54 1995