CS 345 TEST II name _____________________________ Work quickly but carefully. Answer the easy questions first and come back to the hard ones, so that you don't run out of time and leave a bunch of easy questions unanswered. If you don't know what a question means, you can come to the front and quietly ask me for a clarification. I may explain things to you (and the class) if I agree the question is unclear. (If you're still unclear on a question ANNOTATE your answer to show what you THOUGHT it meant. You may get credit, or partial credit, if I think your interpretation is reasonable and you basically know what's what.) Assume that Schemish examples are in standard Scheme, or Scheme extended with define-macro, as appropriate. When asked for the value of an expression, write it as Scheme's write procedure would, with the following exceptions * For procedures, write #. * For expressions that result in an error, write ERROR. * For expressions that yield a cyclic structure (which would cause write to loop infinitely) write CYCLIC. * If evaluation of the expression gets stuck in an infinite loop, write INFINITE 1. Which of the following procedures are tail recursive? a) (define (lsum lis) (if (null? lis)) 0 (+ (car lis) (lsum (cdr lis))) YES NO b) (define (math-eval expr) (cond ((list? expr) ((look-up-op (car expr)) (math-eval (cadr lis)) (math-eval (caddr lis))) (else expr))) YES NO c) (define (memq item lis) (if (not (null? lis)) (if (not (eq? (car lis) item)) (memq item (cdr lis)) lis) #f)) YES NO 2. Consider the following definition of the procedure reduce (define (reduce op base lis) (if (null? lis) base (op (car lis) (reduce op base (cdr lis))))) a) is reduce a higher-order procedure? YES NO given this definition of reduce, what is the value of each of the following expressions? b) (reduce list 0 '(1 2)) VALUE: c) (reduce (lambda (a b) (* a b)) 1 '(1 2 3)) VALUE: d) (reduce cons '() '(1 2 3)) VALUE: 3. Suppose we evaluate the following forms, in order: (define foo '(a b c)) (define bar 'foo) (define-macro (quux x y) `(if (list? ,x) ,x (list ,y))) (define-macro (bleen x) (list 'list x)) what is the value of each of the following expressions? a) 'foo VALUE: b) `bar VALUE: c) `(foo bar) VALUE: d) `(foo ,foo) VALUE: e) (quux foo bar) VALUE: f) (bleen foo) VALUE: g) (bleen (quote foo)) VALUE: 4. Consider the following series of forms, evaluated in order at the top level: (define (to-do thunk) (let ((done? #f) (value '*junk*)) (lambda () (cond (done? value) (else (set! value (thunk)) (set! done? #t) value))))) (define inc (let ((count 0)) (lambda () (display "in inc") (newline) (set! count (+ count 1)) count))) (define foo (to-do inc)) (foo) (foo) (foo) a) does to-do memoize a computation represented by a thunk? YES NO b) how many times is the string "in inc" displayed? NUMBER: c) what does foo return the third time it is called? VALUE: d) how many closures are created each time to-do is called? NUMBER: e) how many bindings are created each time to-do is called? NUMBER: f) how many closures are created each time foo is called? NUMBER: 5. Consider the d.f.a. for a simple scanner shown on the board. (remember, unlabeled arcs are defaults, and dashed arcs do not consume characters) a) how many tokens will result from scanning the input character sequence "foo bar12 13" (without the double quotes)? NUMBER: b) will scanning the string "foo 12bar baz" reach the error state? YES NO c) is "{letter | digit}*" (without the double quotes) a correct regular expression for the lexical syntax of identifiers? YES NO d) if we implement this d.f.a. as a graph-driven scanner, how many procedures will we need to represent the shown states and transitions? NUMBER: 6. Consider the following BNF grammar for a language L ::= B C ::= A ::= ::= a) A is a terminal TRUE FALSE b) is a nonterminal TRUE FALSE c) A B C is a in L TRUE FALSE d) B C A B C A is a , but not a , in L TRUE FALSE 7. The simple reader presented in the Scheme notes/book a) parses a language defined by a grammar TRUE FALSE b) recognizes tokens TRUE FALSE c) relies on Scheme's continuation chain to record nesting of expressions, so that it can recognize a grammar without managing an explicit stack TRUE FALSE 8. In the example Scheme (subset) interpreter in the Scheme notes/book a) eval is mutually recursive with eval-quote TRUE FALSE b) eval takes (as its expr argument) a string object representing a Scheme expression. TRUE FALSE c) eval-apply extracts the environment pointer from a closure, and extends that environment with bindings from the call site, so that variables bound in the calling environment will be visible to the body of the procedure being called. TRUE FALSE d) the reader is mutually recursive with the evaluator, so that eval can call read to read subexpressions when evaluating an enclosing expression. TRUE FALSE 9. Suppose we use the following set of rule assertions with the backward-chaining propositional calculus theorem prover (from propcalc.scm): (assert-rule! '(Morning :-)) (assert-rule! '(Friday :-)) (assert-rule! '(JasonIsOnARampage :- FridayTheThirteenth Evening)) (assert-rule! '(FridayTheThirteenth :- November Thirteenth)) (assert-rule! '(FridayTheThirteenth :- Friday Thirteenth)) (assert-rule! '(Thirteenth :-)) (assert-rule! '(TimeForFinal :- Morning FridayTheThirteenth)) a) What does the theorem prover return as the answer to the query (provable? 'TimeForFinal) ? VALUE: b) Does the number of backtracking steps involved in answering the query (provable? 'TimeForFinal) depend on the order in which preconditions are tried by rule-satisfiable? (That is, will it affect the number of attempts to satisfy a rule or prove a rule precondition, if preconditions are tried right-to-left?) YES NO c) What does the theorem prover return as the answer to the query (provable? 'November) ? VALUE: d) Assuming that the rules and facts in our database are correct, does the answer to (c) tell us whether or not the proposition November is true? YES NO 10. In the simple object-based programming system presented in class (which uses classes and generic procedures, and whose implementation is described in the Scheme notes/book), a) define-class is a macro which generates an expression which will create a class object (when that (generated) expression is evaluated). TRUE FALSE b) generic procedures are represented as Scheme vectors TRUE FALSE c) generic procedures are used for late binding of methods TRUE FALSE d) the object system presents a partly declarative interface, and the object system infers some properties of classes and methods. TRUE FALSE 11. Suppose we want to define a subtype S of a type T. Which of the following are true? a) S should inherit methods from T. TRUE FALSE b) instances of S can be used in at least as many ways as instances of T TRUE FALSE c) if we're using C++, we should use private inheritance to define S in terms of T. TRUE FALSE d) T can't be an abstract class TRUE FALSE e) T is a parameterized type (e.g., C++ template class) TRUE FALSE ---- Questions in this section count the same as lettered parts of questions in the previous section 12. member is a true function, not just a procedure TRUE FALSE 13. all of the following are special forms, which can't be implemented as normal Scheme procedures: set! quote lambda define if TRUE FALSE 14. A macro can extend the syntax of a language TRUE FALSE 15. A call to a macro defined with define-macro may have side effects when macro transformation is done, before the resulting expression is evaluated TRUE FALSE 16. Late binding is not needed (or is much less important) in a language with inheritance TRUE FALSE 17. In declarative programming languages such as logic programming languages, you don't have to worry about how a problem is solved, just about how to state it correctly TRUE FALSE 18. Some theorem provers can prove any logical statement that logically follows from a set of logical statements, but it may take a very long time and/or a very large amount of memory TRUE FALSE --- Questions in this section count 5 times as much as questions in the previous section, i.e., the same as a 5-part question in the section before that. 19. Write a procedure inorder-display to display arithmetic expressions in parenthesized, infix notation. Assume that arithmetic expressions are represented as Scheme s-expressions, which may be * numbers, or * 3-element lists whose first element is a symbol and whose second and third elements are arithmetic expressions Example uses: (inorder-display '(+ 1 (- 2 3))) This should have the side effect of displaying "(1 + (2 - 3))" (without the double quotes) on the screen. (inorder-display 1) This should have the side effect of displaying "1" (without the double quotes) on the screen. Your solution should be recursive in the natural way that reflects the recursive definition of arithmetic expressions given above. You don't bother to put in a bunch of checking to see whether a list is of length three or its car is a symbol, but you should ensure that an error is signaled if the argument to inorder-display is not a number or a pair. 20. Write a procedure compose3 which takes three arguments named proc1, proc2 and proc3, and returns a procedure of one argument named val. The procedure returned should apply the last of these procedures to the argument val, the second procedure to the result of that, and the first procedure to the result of that, and return that result. For example, (compose3 car cdr cdr) should return a procedure equivalent to caddr, which takes the car of the cdr of the cdr of a value, i.e., the third element of a list. Example uses: ((compose3 car cdr cdr) '(a b c d)) => c ((compose3 list list cdr) '(a b c d)) => (((b c d))) ---