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

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?

Answer: The expression evaluates to the cons pair (1 . (2 . 3)) (that is, the car of the pair is 1, and the cdr of the pair is the cons pair (2 . 3). This is not a list, since a list is either null or a cons pair where the cdr part is a list. In this case, the cdr part is a cons pair, not a list, so the expression does not produce a list.

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

Answer: Ben needs to make the second part of the pair a list:

(cons 1 (cons 2 (cons 3 null)))

Or, more simply: (list 1 2 3).
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?

Answer: Most students got this wrong (but still received partial credit) by forgetting to consider the evaluation rules carefully. The expression is an application, so the evaluation rule for application says to first evaluate each subexpression. The first subexpression is map, a name that evaluates to a procedure. The second subexpression is (/ x 7). It is an application, so to evaluate it we use the evaluation rule for applications which says to first evaluate each subexpression. The second subexpression is the name x, but x is not defined here. Hence, the evaluator will produce and error complaining that x is not defined. Note that this happens before the second step in evaluating the map application. It is true that the first parameter to map must be a procedure, and (/ x 7) does not evaluate to a procedure, but the evaluation never gets that far since it cannot evaluate all the subexpressions.

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

Answer: Ben needs to use lambda to make a procedure:

(map (lambda (x) (/ 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)
#t
(is-even? (- n 2))))
• Explain what the procedure Ben defined does?

Answer: The procedure evaluates to #t when applied to a non-negative even number. When applied to any other kind of number (that is, an odd number, a negative number, or a non-integral number) it never finishes evaluating but instead enters an infinite loop, where it continues to recursively evaluate (is-even? (- n 2)) without ever reaching the base case. When applied to any value that is not a number, an error results since (- n 2) cannot be evaluated unless n is a number.

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

Answer: Ben needs to add another base case to handle non-even numbers:

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

This will still not finish evaluating for non-integral numbers and negative numbers. Instead, Ben could replace the (= n 1) with (< n 0) to define a procedure that evaluates to #f for any non-even number.

You could also use the built-in modulo procedure: (define (is-even? n) (= (modulo n 2) 0))

### 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.

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

Language ALanguage B
 NounPhrase Using rule A4 Noun and NounPhrase Using rule 6 Jack and NounPhrase Using rule A5 Jack and Noun Using rule 7 Jack and Jill
 NounPhrase Using rule B3 Noun NounExtra Using rule 6 Jack NounExtra Using rule B4 Jack and NounPhrase Using rule B3 Jack and Noun NounExtra Using rule 7 Jack and Jill NounExtra Using rule B5 Jack 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:

### 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))
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))
n))

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)
sofar
(lastsatisfyingelementhelper
(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.