Thursday, February 25, 2010

A long series of posts

I was arguing recently that it was important for programs to have semantics. Would someone dispute this? Apparently so. Therefore, I started a series of Socratic arguments. I never finished it, but maybe I'll finish it here in my blog.

Let me start with something extremely simple:
(define (factorial x)
 (if (< x 2)
     (* x (factorial (- x 1)))))
and I ask the question to my hypothetical students “What does this mean?”

Student A says “No computer program can ever have a meaning. Someone could redefine *, or shadow if, and make any answer incorrect.”

Student B says “I don't know, but the computer says ”

 (fact 0) => 1
 (fact 1) => 1
 (fact 2) => 2
 (fact 3) => 6
 (fact 4) => 24 ...
Student C says “It defines FACTORIAL as a recursive program that computes the factorial function for positive integer arguments.”

How do you grade these answers, and why?


Pascal Costanza said...

Student A's statement is self-contradictory. You can only meaningfully talk about making something incorrect when you have a correct meaning in mind in the first place. So for Student A, the program has a meaning, even if he/she denies that.

Student B at least knows what type of arguments the program accepts, but apart from that may really just not know. His/her answer seems to be the most honest one.

Student C's description of the program is circular. He/she states that FACTORIAL implements factorial, which doesn't say much at all - it's both times the same word, both times the same string of characters (only once in upper case and once in lower case).

kbob said...

I'll bite.

A is correct, only because you didn't preface the problem with "In a vanilla Scheme environment, ..." But he's being pedantic.

C is also correct, because he correctly inferred that you meant, "In a vanilla Scheme environment...".

B is lost in the woods, looking for the forest.

I followed this discussion on the other forum, but I still don't understand what point you want to make.

Alexey said...

Thank you for starting to post these! I was very upset by the reception you were given recently, and I really want to see where you are going to go with this.

To answer the question, from my current state of thinking on the topic, and speaking as a (perhaps somewhat older) peer, rather than as a professor,

I would say to student A: That answer is useless. Of course someone could shadow * or IF; but what did the author of the program mean when they wrote it?

I would say to student B: OK, that's what the program does, for a few trials with a few arguments, but what it does is beside the point. The question was: what does the program mean?

I would say to student C: Excellent. If you wanted to be really pedantically precise, you could add that this interpretation depends on this snippet appearing in a Scheme evaluation context, on definitions being appropriate in that evaluation context, on the bindings of DEFINE, IF, <, -, *, 1, and 2 in scope in that context, and on the read syntax of ( and ); but as no information to the contrary was supplied in the problem statement, those default assumptions are reasonable.

Arcane Sentiment said...

Rather than grade the students on how well they remember their last lesson (whatever it was), I think it's more illuminating to identify the circumstances where each of the responses is useful. For someone who encounters the program as an inscrutable artifact written in some weird language with lots of parentheses, Student B's empiricism is a reasonable approach (and sometimes the only one possible). For someone who understands the language and can guess what the author meant, Student C's reconstruction of intent is often best. But for someone who's trying to understand what a compiler can and can't prove - which, I think, is what you're aiming at - Student A's semantic paranoia is necessary, because reasonable default assumptions won't always hold.