Exam 1

Out: 20 February 2004 Due: Monday, 23 February 2004, 2:01PM

Name: _________________________________________________________

Directions

Work alone. You may not discuss these problems or anything else related to this course with anyone except for the course staff between receiving this exam and class Monday.

Open book. You may use any books you want, lecture notes and slides, your notes, and problem sets. If you use anything other than the course books and notes, cite what you used.

No DrScheme. You may not run DrScheme or use any other Scheme interpreter between now and when you turn in this exam.

Answer well. Answer all 10 questions. Write your answers on this exam. You should not need more space than is provided to write good answers, but if you want more space you may attach extra sheets. If you do, make sure the answers are clearly marked.

The questions are not necessarily in order of increasing difficulty, so if you get stuck on one question you should continue on to the next question. There is no time limit on this exam, but it should not take more than a few hours to complete.

Full credit depends on the clarity and elegance of your answer, not just correctness. Your answers should be as short and simple as possible, but not simpler.

Evaluation

Due to an unfortunate snowboarding incident, Ben Bitdiddle has become muddled. For each expression below, explain:

• What the Scheme interpreter will produce when the expression is evaluated
• How should the expression be fixed to produce what Ben wants

You may refer to the evaluation rules on Notes 4 in your answers.

For example,

0. Add 3 and 4: (3 + 4)

• The Scheme interpreter will produce an error. The expression is an application, so according to Evaluation Rule 3a we should evaluate each subexpression. Each subexpression is a primitive, so they all self-evaluate. Then, according to Evaluation Rule 3b, we should apply the value of the first subexpression (3) to the values of all the other subexpressions. We have application rules for primitive procedures and compound procedures, but 3 is not a procedure, so no application rule applies and an error is reported.
• (+ 3 4)

1. Make a list containing the number 1, 2 and 3 in order: (cons 1 (cons 2 3))

• Explain what the Scheme interpreter will produce when the expression is evaluated?

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

• How should the expression be fixed to produce what Ben wants?

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

2. Divide every number in lst by 7 (assume lst is already defined to a list of numbers):

     (map (/ x 7) lst)

• Explain what the Scheme interpreter will produce when the expression is evaluated?

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

• How should the expression be fixed to produce what Ben wants?

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

3. Define a procedure is-even? that evaluates to #t when applied to an even number, and evaluates to #f when applied to an odd number:

(define (is-even? n)
   (if (= n 0) 
       #t
       (is-even? (- n 2))))

• Explain what the procedure Ben defined does?

  
  

  
  

  
  

  
  

  
  

  
  

  
  

  
  

• How should the expression be fixed to produce what Ben wants?

Languages

Consider the two languages described using BNF grammars below:

Language A	Language B
A1. Sentence ::= Verb NounPhrase VerbPhrase A2. VerbPhrase ::= Verb and VerbPhrase A3. VerbPhrase ::= Verb A4. NounPhrase ::= Noun and NounPhrase A5. NounPhrase ::= Noun 6. Noun ::= Jack 7. Noun ::= Jill 8. Noun ::= Socks 9. Noun ::= Spot 10. Verb ::= see 11. Verb ::= jump 12. Verb ::= run	B1. Sentence ::= Sentence and Sentence B2. Sentence ::= Verb NounPhrase Verb B3. NounPhrase ::= Noun NounExtra B4. NounExtra ::= and NounPhrase B5. NounExtra ::= 6. Noun ::= Jack 7. Noun ::= Jill 8. Noun ::= Socks 9. Noun ::= Spot 10. Verb ::= see 11. Verb ::= jump 12. Verb ::= run

Note that rules A1-A5 and B1-B5 are different, but rules 6-12 are the same for both languages.

4. Show that both Language A and Language B can generate the string "Jack and Jill" starting from NounPhrase. Your answer should show which replacement rule you used for each step.

Language A	Language B

5. Identify one string that Language B can generate starting from Sentence that cannot be generated by Language A starting from Sentence.

6. Draw an RTN that describes the same language as Language B (repeated on this page for your convenience) produces starting from Sentence.

Language B

B1. Sentence ::= Sentence and Sentence
B2. Sentence ::= Verb NounPhrase Verb
B3. NounPhrase ::= Noun NounExtra
B4. NounExtra ::= and NounPhrase
B5. NounExtra ::=
6. Noun ::= Jack
7. Noun ::= Jill
8. Noun ::= Socks
9. Noun ::= Spot
10. Verb ::= see
11. Verb ::= jump
12. Verb ::= run

Procedures

7. Use the procedure dowhile defined below to define a procedure intsto that takes one parameter n and evaluates to the integers from 1 to n (just like the intsto procedure we have defined in class).

   (define (dowhile proc continuetest incr current)
       (if (continuetest current)
           (cons (proc current) 
                 (dowhile proc continuetest incr (incr current)))
	   null))

   (define (intsto n)
       (dowhile


	




	
	)
       )

8. Define a procedure averageval that take a procedure and a list as inputs, and evaluates to the average value of applying the procedure to every element in the list. For example,

    (averageval (lambda (x) x) (list 2 4 6))

should evaluate to 4 and

   (averageval (lambda (x) (* x x)) (list 1 2 3 4 5))

should evaluate to (/ (+ (* 1 1) (* 2 2) (* 3 3) (* 4 4) (* 5 5)) 5) which is 11.

9. Define a procedure lastelement that takes a list as input and evaluates to the last element in that list. For example, (lastelement (list 1 2 3 4)) should evaluate to 4.

10. Define a procedure lastsatisfyingelement that takes a list and a procedure as input, and evaluates to the last element in the list for which applying the procedure to that element evaluates to true. For example,

(lastsatisfyingelement (list 1 2 -3 4 -5 7 -9)
                       (lambda (x) (> x 0)))

should evaluate to 7.

These two questions are optional and worth no credit, but we appreciate your answers. Please answer them on the back of this page.

11. Do you feel your performance on this exam will fairly reflect your understanding of the course material so far? If not, explain why.

12. Do you have any comments about how the course is going so far or suggests for improving the remainder of the course?