“The quiz is contained in the file
quiz.scm which you can find in the usual location. For those of you that prefer hardcopy, I have a printout for you.“I know that some of you” (and here the professor glared at Student A) “seem to have issues with the way I present code, so you should assume that this code is to be entered into an unmodified R5RS Scheme interpreter.
“You have two hours.
;; Question 1:
;; What does (fib 4) evaluate to?
;; Question 2:
;; What is domain and range of the EVEN? procedure?
;; Question 3:
;; How many top-level forms are in this file?
;; Question 4:
;; Make a list of the free variables in this file.
(define (even? x)
(or (zero? x)
(odd? (- x 1))))
(define (odd? x)
(and (not (zero? x))
(even? (- x 1))))
(define (fib n)
(if (< n 2)
n
(+ (fib (- n 1))
(fib (- n 2)))))
;; Sanity check
(= (- (fib 100) (fib 99)) (fib 98))
;; Question 5:
;; Are either of the following two forms an infinite loop?
;; Make an informal argument to support your answer.
(define (loop1 n)
(if (positive? n)
(loop1 (- n 1))
(loop1 n)))
(define (loop2 n)
(if (negative? n)
(loop2 (+ n 1))
n))
Meta-questions for readers of this blog:
- Is this a reasonable quiz? If it is too difficult for first-year students, is there a year at which it would be appropriate or even too simple?
- Is two hours enough time to answer the questions?
- Are there any loopholes that will allow Student A to object?
1. Seems perfectly reasonable to me. If they can't follow the syntax, some recursive definitions, and the difference between a definition and an expression, then they've missed all the basics.
ReplyDelete2. More than enough. Unless you're giving them a REPL to work at, for things like this one either gets it quickly or not at all.
3. He could, I suppose, argue that R5RS is ambiguous or which exact version is meant is ambiguous. Or that the program is still ambiguous because one could run out of stack if one passed a large enough number to even?/odd? (But maybe TCO guarantees that one can't overflow the stack with even?/odd?.)
even?/odd? are not manifestly tail-call recursive, so I'm not 100% certain that R5RS guarantees that they can't overflow the stack. Certainly and could be implemented in a way which would trivially make TCO do the right thing.
ReplyDeleteR5RS does have formal definition, so for student A to object along those particular lines seems to imply that he would object to almost all mathematical questions.
ReplyDeleteSorry, my link didn't seem to work properly. The formal definition can be found online as chapter 7 of the R5RS spec.
ReplyDelete1. All five questions have interpretations which are good first-year quiz questions, but some of them don't distinguish those from other plausible interpretations which aren't.
ReplyDeleteQuestion 5, and to a lesser extent 2 and 4, aren't good quiz questions because they have literal interpretations different from their most plausible intended meanings. This forces the students to guess whether to answer the bizarre literal question, or to correct for imperfect communication and answer the question the professor should have asked, as they do for any other sort of communication. Even an expert will often guess wrong, so such questions aren't very informative about the students' knowledge.
2. An hour is plenty. As gwern said, these are questions one gets quickly or not at all. (Modulo ambiguity.)
3. Student A might quibble (and other students might be confused) about the meanings of "form", "variable" and "free variable".
I don't think "form" has a standard definition in Scheme; it might mean either "expression" or "expression, definition or syntax definition". R5RS seems to use it to mean the latter (as does question 5), but doesn't define it.
"Variables" might include names like DEFINE and OR, in an implementation with first-class special forms - IIRC R5RS does not forbid these from being variables. Even in an ordinary implementation with second-class special forms, they imply variables (but not necessarily Scheme variables) somewhere in the environment.
"Free variables" might include all references to top-level variables, or only those without a local definition, or only those with a nonlocal definition, or only those with no definition anywhere.
I think this quiz is too easy for two hours even for first-year students. Some may not be fully cognizant of the difficulties involving floating point and inexact numbers, by aside from that, any sensible freshman should be able to deal with this, if it is offered at a reasonable point in the freshman cirriculum.
ReplyDeleteStudent A could object on the grounds that the behavior of the procedures that are defined in this file can be changed by careful application of set! (and perhaps define) to various identifiers, even after said procedure definitions are executed. I would argue that the professor would be justified in dismissing that objection, on the grounds that it is of course true, and perhaps worth remembering in general, but if the quiz were interested in the conditional behavior of these procedures under such circumstances, that would have been specified, and in the absence of such specification, it is reasonable, and expected of the students, to assume that no such mutation takes place.
Student A might also object on grounds of ambiguities in R5RS. The professor could respond by insisting that if Student A were so cognizant of those ambiguities, he could put his great intellect to use by answering the questions on the quiz repeatedly across different possible interpretations of R5RS, in order from most plausible first.
If Student A wanted to grasp at straws, he could also object on the grounds that the R5RS might be mis-implemented, and there is no way to know the meaning of this set of characters as considered by an arbitrary system, whether it claims to be an implementation of R5RS or not. I don't think this objection even deserves a response.
Did I miss any?
By the way, for concreteness, are these the answers you expect?
Q1: 3
Q2: On exact positive integers, even? will return #t or #f, according to whether they are even or odd. On other numbers (as determined by the number? predicate) it will loop forever (which may or may not be signaled as an error, depending on how sophisticated a loop detector the Scheme implementation in question has). It is an error to apply even? to non-numbers.
Q3: Six.
Q4: define, or, zero?, -, and, not, even?, if, <, +, =, positive?, negative?, and 1, 100, 99 and 98, (depending on whether you want to be pedantic about numerals). While these variables are free in this file, their being so depends on their bindings in the environment in which this file is evaluated, which we were told to assume was a standard R5RS environment.
Q5: The forms themselves are not infinite loops, of course, because they just define procedures. The defined procedures are infinite loops in some circumstances. Specifically, the procedure loop1 will loop if called with any number as an argument, and it is an error to call it with a non-number argument. The procedure loop2 will loop if called with an inexact negative number of sufficient magnitude that adding 1 does not change it (e.g. -1e100 in MIT/GNU Scheme), will terminate if called with any other number, and it is an error to call it with a non-number.