TITLE: An Unusual Scheme-ism This Semester AUTHOR: Eugene Wallingford DATE: May 14, 2013 2:35 PM DESC: ----- BODY: While grading final projects and final exams in my Programming Languages courses this week, I noticed my students using an unusual Scheme construction. Instead of writing:

(cons new-item result-of-recursive-call)

... a few troubled souls fell into the habit of writing:

(append (list new-item) result-of-recursive-call)

We have been using Scheme in this course for many years, and this may be the first semester that I've ever seen this. It is certainly the first time I saw it enough to notice it and wonder, "What's up with that?" Of course, in previous semesters, a few students have always used a similar construction when putting new items at the back of the list:

(append result-of-recursive-call (list new-item))

This semester, though, a handful used (append ... (list ... all over the place. When I asked one of them about it after seeing it on an earlier homework assignment, he didn't have much to say, so we talked about the more direct solution a bit and moved on. But after seeing it multiple times on the final exam, I have to wonder what is going on. Maybe they simply adopted this form as a mental shorthand, a one-size-fits-all tool that gave them one fewer thing to think about when writing code. Maybe, though, it masks a systematic error in thinking that I might address. Out of curiosity, I ran a quick experiment to see what sort of time advantage (cons ... has over (append ... (list .... Surely, initializing the cdr field of a new list's cons cell to null, then asking append to walk there and set it to point to the other list wastes time. But how much? In Racket, the penalty is actually quite small, in the ballpark of 40ms for every million executions. That's not surprising, given that append must examine only one cell before reaching the end of its first argument. This stands in contrast to the more general case of wrapping an O(n) append operation inside another O(n) operation, which my students encounter when learning how to implement more efficient algorithms using an accumulator variable. More important than any speed penalty, though, is the misunderstanding that enables or encourages a student to think about reassembling a structure of this sort with anything other than a straightforward call to cons. Seeing an anti-pattern of this sort in my students' code makes me want to uncover the pathology at play and root it out. -----