Monday, March 1, 2010


Pascal Costanza wrote:
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 A might argue: “The professor is the one that is assuming there is a correct meaning. I'm simply pointing out that whatever meaning he might have in mind could be wrong.”

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).
Student C replies: “Oh, I meant that the program named FACTORIAL implements the mathematical function ‘factorial’.” (This is a beginner's course, so we shouldn't make him work too hard.)

Alexey wrote:
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?
Student A replies: “How should I know? I can't read minds!”

What do we say to Student A?

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?
Student B asks: So what is the difference between what it “means” and what it “does”? Doesn't “(+ 2 3)” mean 5? Doesn't “(factorial 4)” mean 24?


  1. I think all 3 students are (rightly) confused about the question: a _program_ doesn't have semantics; a language has semantics, then a program is written in that language. Each student is exploring a different facet of an undefined language semantics, given a program, a reference implementation and an intuition.

    Student B's point is closest to the "expected" answer, but missing a qualifier: from a denotational perspective, "(+ 2 3)" means "5", assuming that (+), 2, 3, 5 and the function application operation of the language are all mapped straightforwardly to their corresponding mathematical objects.

  2. Student A replies: “How should I know? I can't read minds!

    Then he's either socially inept or a smartass. If knowing what answer someone is after required mindreading skills, we would all be great mindreaders. We usually know what answer someone is after, despite the ambiguity of his question.

  3. It seems to me that student C is right completely. In fact, I would say this stronger thing.

    Suppose FACTORIAL read like this instead:

    (define (factorial x)
    (if (< x 2)
    (* x (factorial (- x 1)))))

    Even with a huge bug that removes any mathematical similarity between FACTORIAL and factorial, I would hold that this program *still* means factorial.

    Why? Because we know with a high degree of confidence that a human mind designed this program to implement the mathematical function factorial (because of clues like the name and the single very human error.) As a result, we can say that the flipped comparison is a bug, and we can correct the author, since he didn't write what he meant!

    In practice, this is what everyone has to do with programs all the time. If you're reading someone's program and trying to fix something without the benefit of a big formal spec, you've got to get inside their head (or speak with them) and understand what their program meant to them, because that meaning is going to inform how the program is being used, and making the program conform to that meaning is probably your priority.

  4. Sorry - I must have made an error writing the above post. I meant to introduce a bug in FACTORIAL by changing the less-than to a greater-than, to illustrate my point.

  5. Student A seems to admit at least that the author had a meaning in mind when they wrote the program. There is a specification of the language Scheme that - in case predefined operators and procedures are not redefined - gives this program unambiguous semantics, and it is safe to assume that these are the intended semantics. If not, we would expect that redefinitions would be specifically mentioned and hinted at, due to the fact that under normal circumstances it's highly unlikely that somebody indeed redefines them. This is very similar to the case of normal daily conversations, where we also usually do not expect speakers to silently redefine English words and grammar rules. Of course, we are talking here only about social norms, but not anything that can be enforced, so there is a potential grey area here where silent redefinitions are possible. However, it's more than safe to assume under normal circumstances that this doesn't occur without explicit mention.

    Student B doesn't seem to understand that the meaning of a program is in terms of all possible inputs, not just a few random ones.

    Student C understands that there is a distinction between the program and the mathematical function it implements. So student C is actually right.

  6. Haven't you been trying all along to point out that the "students" are related to compilers, and that the compiler needs to know if things are redefined before it can compile them?

  7. It surprises me that Student A was able to honestly answer the question the way he did: he must have presumed that his brain had correctly interpreted the lecturer's question about the code, over the alternative that he is a brain in a vat presided over by a Matrix Overlord who wants him to learn about programming.

    Student A could, in theory, use the same process of doubting the regularity of the lower level of operation to answer any question -- be it about programming, everyday conversation, biology or visual arts. This means that the answer does not yield any information other than a retro skepticism about the nature of reality. An answer that is completely correct yet yields no information about the question itself is not an adequate answer.

    Student B is the most right, in the sense that he at least got nothing wrong in his reasoning about the program. Still, Student B is meant to be a programmer and not a calculator. A programmer, when examining code, has to demonstrate some understanding about what the program does, what it is meant to do and how the reality lines up with those expectations.

    Student C, presuming your code is R5RS scheme, is wrong. Factorials of negative numbers are undefined, as the operation results in division by zero. Yet (factorial -2) => 1, (factorial -1) => 1, (factorial 0) => 1. The code is something that resembles the factorial function, of course, but to not seek dis-confirmation between the definition of factorial and his mind's view about what the code does is a flaw much deeper than Student B's unthinking calculation. At least Student B had no particular ends in mind and thus was served only by his ignorance of what a factorial is, Student C took his preconceptions and ran with them.

  8. I would say to Student A: The purpose of languages, computer and otherwise, is to communicate. By listening to me speak you are reading my mind, and so far you have been accurate, if obstinate. Apply the same faculty to this written program.

    I would say to Student B: Hm. I drew the distinction in the wrong place. I should have said "The question was about what the meaning of the FACTORIAL program is, not what the meaning of the FACTORIAL program does when further invoked."

    For example, we can say, if we want, that
    ((lambda (x) (+ x x)) 1) means 2
    ((lambda (x) (+ x x)) 2) means 4
    ((lambda (x) (+ x x)) 3) means 6
    ((lambda (x) (+ x x)) 4) means 8
    ((lambda (x) (+ x x)) 3/2) means 3
    ((lambda (x) (+ x x)) 1+2i) means 2+4i
    but that is not the same as saying that
    (lambda (x) (+ x x)) means "The doubling function".

  9. They are all right. And wrong. "Meaning" depends on the context and the context was not specified.

  10. Student C is the closest to being correct, but ...

    First, we should determine whether we are talking about an operational meaning or a purely denotational meaning. The most straightforward type of operational meaning would be the sequence of evaluation steps, which allows divergent calculations to have an intuitive meaning. With denotational semantics the student's answer has to account for the inputs causing divergence in some other way.

    One problem with Student C's answer is the artificial limiting of the inputs to positive integers, since the code is non-divergent for any numerical input.

    One non-problem with Student C's answer is circularity - the mathematical definition of factorial is not operational but declarative: the factoral function is the function on non-negative integers satisfying the equation (n+1)!=(n+1) * n! and the initial condition 0!=1, assuming there exists a unique solution to these constraints.