Exam 1 - Comments

• 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).

     (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)
  

(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

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:

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

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

   (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

   (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)))

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

(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)))

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

(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)))