Computer Science 3675
Summer 2001
Answers to practice questions for quiz 3

1. By choosing among the operations lfold, rfold, map and select, write a definition for each of the following that does not use recursion or loops.

   1. Write a function called doubleAll that takes a list x of numbers as its parameter and produces a list of the doubles numbers in list x as its result. For example, doubleAll([5,2,19,3]) = [10,4,38,6].

             double(x) = x + x
             doubleAll = map double
          

      Remark. You can always use helper functions. This definition still does not have any recursion, either direct or mutual.

   2. Write a function called firstPos that returns the first positive number from a list of numbers. For example, firstPos([-4, -2, 0, 6, 12, -9]) = 6. Presume that the list has at least one positive number in it.

             positive(x) = x > 0
             firstPos = select positive
          

2. Consider the following definition written in Astarte.

       Define f(?n) = (:n*n :: f(n+1):).
     

   What value does expression f(2) compute? Give the full value, as it would be if it were examined. (It suffices to give a clear description of the full value.)

   f(2) = [4,9,16,25,...]

   (an infinite list of the squares of the numbers 2,3,4,...)

3. What is the purpose of the static link in a frame in the run-time stack?

   The static link in a frame for function f points to the frame of the function that created f. It is used to find nonlocal bindings.

4. What is the value of Scheme expression (car (cdr (cons 'horse (cons 'zebra ()))))?

   zebra

5. Write a Scheme function called prefix so that (prefix x y) returns true if list x is a prefix of list y. Be careful to use Scheme syntax correctly.

       (define (prefix x y) 
          (cond
             ((null? x) #t)
             ((null? y) #f)
             ((equal? (car x) (car y)) (prefix (cdr x) (cdr y)))
             (else #f)
          )
       )
     

6. What is one important motivation for including exception handling in a programming language?

   Some acceptable answers include the following.

   1. Exception handling makes it possible to move error handling code out of the flow of the main program logic.
   2. Exception handling makes recovery from errors easier, thus making programmers more likely to put in the effort to do it.
   3. Exception handling makes it possible to recover from errors in parts of the program that do not perform any error checking, and might be written in an unreliable way.

7. Using backtracking, write an Astarte program fragment that will print all solutions (x,y) to equation xy - 2x² + y = 10, where x and y are both integers in the range 0,...,100. Do not use a loop or recursion. Your program fragment can fail when it is done.

       Let x = each(0 _upto_ 100).
       Let y = each(0 _upto_ 100).
       {x*y - 2*x^2 + y == 10}
       Writeln[$(x,y)].
       {false}