--------cut here and print using lpr (not enscript) -------- CS345 Take-home QUIZ, Part I name _________________________ (Don't worry---part II won't be as long!) If you are not sure you understand a question, you can send me email for a clarification. If it's still not clear, ANNOTATE YOUR ANSWER in the margin to explain what YOU mean. (You may get partial credit for a "wrong" answer if I think you basically had the right idea but misread the question.) Where I ask what the value of something is, write the answer as we've done on previous homeworks and tests, pretty much the way Scheme prints things. (For an expression that generates an error, write ERROR. For a procedure value, write #.) (NOTE: A bunch of these should be easy to get right because you can machine check your answers. Of course, you should do them by hand first, to make sure you can really get them right without machine-checking, because you won't be able to machine-check your answers on the final.) 1. Suppose we evaluate the following RScheme forms once, at the top level, in this order: (define quux 'x) (define x 2) if we then evaluate the following expressions, what are their values? a) (list x quux) b) '(x) c) `(list x) d) `(,x quux) e) `(list x ,quux) f) '(,x ,quux) 2. Suppose we evaluate the following RScheme forms once, at the top level, in this order: (define lis '()) (define-macro (foo x) (set! lis (cons x lis)) `(list ,x)) (foo 1) lis (foo 'bar) lis a) what is the value of the third expression, (foo 1)? b) what is the value of the fourth expression, lis? c) what is the value of the fifth expression, (foo 'bar)? d) what is the value of the sixth expression, lis? 3. Suppose we load propcalc.scm (our simple backward-chaining propositional calculus theorem prover) into Scheme, and then evaluate the following forms, in this order: (assert-rule! '(A :- B C)) (assert-rule! '(B :- D)) (assert-rule! '(D :-)) (assert-rule! '(C :- B)) (provable? 'D) (provable? 'C) (provable? 'E) (provable? 'B) a) When we evaluate the fifth form, (provable? 'D), how many times is rule-satisfiable? called? b) when we evaluate the sixth form, (provable? 'C), how many times is provable? called? c) when we evaluate the seventh form, (provable? 'E), how many times is rule-satisfiable? called? d) when we evaluate the seventh form, (provable? 'E) does the return value tell us that E is false? e) when we evaluate the eighth form, (provable? 'B), how many times is rule-satisfiable? called? 4. Suppose we load propcalc.scm into Scheme, and then evaluate the following forms: (assert-rule! '(R :- S)) (assert-rule! '(R :- T)) (assert-rule! '(P :- Q)) (assert-rule! '(Q :- V)) (assert-rule! '(Q :- W)) (assert-rule! '(T :-)) (provable? 'Q) (provable? 'R) a) when we evaluate the seventh form, (provable? 'Q), how many times is rule-satisfiable? called? b) when we evaluate the eighth form, (provable? 'R), what answer is returned? c) when we evaluate the eighth form, (provable? 'R), does the number of times rule-satisfiable? is called depend on the ordering of the rules in the database? (E.g., if we'd defined the rules in the opposite order, would rule-satisfiable? be called a different number of times?) 5. Consider the simple structure-definition facility presented in the course notes. a) is define-struct a macro? YES NO (circle one) b) does define-struct have side effects? YES NO (circle one) Given the define-struct implementation in the Scheme notes, suppose we evaluate the following form: (define-struct three-d-point x y z) c) how many procedures are defined when we evaluate this form (including constructors, predicates, and accessors)? d) what is the Scheme type of value of the variable three-d-point? e) what is the Scheme type of the value of the expression (make-three-d-point 20 10 50) ? (That is, in terms of Scheme built-in types, what kind of thing is it?) TRUE OR FALSE (circle T or F): 6. Suppose we modified propcalc.scm to understand logical negation, so that (not P) means the opposite of P, i.e., P is false. Assume we don't change the basic backward-chaining inference strategy. Suppose we then initialized the database with the following rules: (assert-rule! '(P :- Q)) (assert-rule! '(P :- (not Q))) Our backward-chaining prover cannot prove P, but a resolution-based forward-chaining prover could. T F 7. The UNIX "utility" make is really a backward-chaining constraint-satisfaction language T F 8. Abstract classes are used to create "plain vanilla" instances, as opposed to more specialized instances of subclasses. T F 9. A strongly-typed OO language provides a means for restricting ways of using data types. T F 10. In C++, private inheritance should be used when defining a subclass that is not usable for the same purposes as the superclass. This allows inheriting implementation (instance variables and methods) without allowing users of the subclass to substitute instances of the subclass for instances of the superclass. T F 11. If a type T has a subtype S (e.g., a public subclass in C++), we usually assume all of the following * S instances can be used in the same ways as T instances, and usually in more ways. * the interface to S's is at least as big as the interface to T's, i.e., the set of operations in the interface of S's is at least as big as the set of operations in the interface of T's. * the type S describes a set of instances that is no bigger than the set of instances described by T. T F 12. A parameterized type (such as Pascal's array type) is a supertype of types created by instantiating that parameterized type (such as a 100-element Pascal array of floats). T F 13. A C++ template class (parameterized type) definition is like a macro definition; when the template is instantiated, it generates a class definition by substituting template arguments into the definition to create a customized class definition. T F 14. A C++ compiler can tell when a declared subtype (a class declared using public inheritance) is not a true subtype, and will generally refuse to compile such a program. T F 15. Threads have their own private address spaces, like UNIX processes---that is, each thread sees a different virtual memory image, rather than sharing memory with other threads. T F 16. In the simple OOP system presented in the Scheme notes, a generic procedure is second-class; generic procedures can't be passed as arguments to procedures such as map and applied by those procedures. T F 17. In our simple OOP system, a superclass link from a class T describes INSTANCES of class T, but the class pointer of the class object for class T describes the CLASS OBJECT itself. (E.g., the fields of instances of T may be determined partly by inheritance from the superclass, but the fields of the class object T are determined by the metaclass .) T F