University of Virginia, Department of Computer Science
CS200: Computer Science, Spring 2004

Exam 1 - Comments

1. Make a list containing the number 1, 2 and 3 in order: (cons 1 (cons 2 3)) 2. Divide every number in lst by 7 (assume lst is already defined to a list of numbers):
     (map (/ x 7) lst)
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) 
       (is-even? (- n 2))))


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.

Answer: There are several possible answers depending on the order the rules are used. Here's one:

Language ALanguage B
Using rule A4Noun and NounPhrase
Using rule 6Jack and NounPhrase
Using rule A5Jack and Noun
Using rule 7Jack and Jill
Using rule B3Noun NounExtra
Using rule 6Jack NounExtra
Using rule B4Jack and NounPhrase
Using rule B3Jack and Noun NounExtra
Using rule 7Jack and Jill NounExtra
Using rule B5Jack and Jill

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

Answer: Language B can generate "see Socks run and see Jill jump" but Language A cannot.

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

Answer: There was lots of confusing on this questions, perhaps because it was the only exam question that did not relate to something you did on a problem set (but it was covered in the GEB reading, Lecture 5 and Lecture 6, so seems like a fair question to me). The paths through the RTN must contain only terminals (that is, symbols that do not appear on the left side of a replacement rule). Otherwise, the RTN does not actually generate a string. One RTN that is equivalent to Language B is:


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)))
Answer: From the definition of dowhile, you can see that the actual parameters passed as proc, continuetest and incr must all be procedures, since they are applied within the body of dowhile. To define intsto, we can use the identity procedure for proc, a procedure that tests if the current value is still less than or equal to n for the continuetest, and a procedure that adds one for incr:
   (define (intsto n)
       (dowhile (lambda (x) x)         ;;; identity procedure
                (lambda (x) (<= x n))  ;;; keep going as long as the
                                       ;;; current value doesn't exceed n
                (lambda (x) (+ x 1))   ;;; add one each time
                1))                    ;;; start at 1
Many other approaches were possible. For example, we could count down from n, but that makes calculating the elements trickier:
   (define (intsto n)
     (dowhile (lambda (x) (+ (- n x) 1))
	      (lambda (x) (> x 0))
	      (lambda (x) (- x 1))  

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.

Answer: The easiest way to define averageval is to use map:

(define (averageval proc lst) (/ (map proc lst) (length lst)))
People who tried to define it without using map often ran into troubles, since you cannot calculate the average of a list of numbers by combining the first number with the average of the rest of the numbers (at least not in a straightforward way).

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.

Answer: The easiest way to define lastelement is to just take the first element in the reverse of the list:

(define (lastelement lst) (car (reverse lst)))
Another option (which is more efficient), is to cdr down the list, but make the base case the case where the list has one element:
(define (lastelement lst)
  (if (null? (cdr lst)) (car lst) (lastelement (cdr lst))))

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.

Answer: The easiest way is to use filter to remove the non-satisfying elements, and then use lastelement as defined in the previous question:

(define (lastsatisfyingelement lst proc) (lastelement (filter proc lst)))
If you attempted to define lastsatisfyingelement without separating the task of filtering the elements from selecting the last one, it was quite tricky. A simple recursive definition doesn't work, since the last element might not be satisfying, even if an earlier element was. One approach is to use a helper procedure, and pass the satisfying element as an extra parameter:
(define (firstsatisfyingelement lst proc)
  (if (null? lst)
      (error "No satisfying element!")
      (if (proc (car lst)) 
	  (car lst)
	  (firstsatisfyingelement (cdr list) proc))))

(define (lastsatisfyingelementhelper lst proc sofar)
  (if (null? lst)
       (cdr lst) proc 
       (if (proc (car lst))
	   (car lst)   ;; the current first element satisfies, and is later in the list than sofar
	   sofar))))   ;; the current first element fails, so keep sofar as the best so far

(define (lastsatisfyingelement lst proc)
  (lastsatisfyingelementhelper lst proc (firstsatisfyingelement lst proc)))
Defining lastsatisfyingelement using insertl is left as an exercise. If you do this, you will receive some bonus points on the exam.
Using these Materials