CS 1 Fall 2007

Lab 4: Conjunction Junction....What's your Function?

Assigned: Monday, October 22, 2007
Due: Thursday, November 1, 2007, 02:00:00


You should read through the end of Section 2.1 in order to be fully prepared for this lab.

Part @: Time Synopsis

  1. As you answer the problems below, make a note on how long you spent on each of the sections.

  2. If any of the individual problems took you notably more time than the rating stated, please identify them and write down your actual time spent. This will help us calibrate future problem sets.

Part A: Exercises

Please complete the following exercises before your recitation on Friday. Should you have any difficulties working these basic exercises, bring your questions to recitation.

  1. Consider:

    (define (make-add-constant constant) (lambda (x) (+ constant x)))
    
    1. [5] Show how this procedure can be used to define a function which adds 5 to its argument.

    2. [5] Define an analogous, make-multiply-constant function.

    3. [15] Define the higher-order function make-op2-constant which takes both the two argument function (e.g. + or * shown here) and the constant as arguments and returns a single argument function just as make-add-constant and make-multiply-constant do.

    4. [5] Show how to use make-op2-constant to define the same procedure you defined in part a.

  2. Determine the value of the following by working through the substitution model evaluation of each expression. Use the DrScheme editor to help with the parenthesis matching. Include your full substitution evaluation in your solution.

    You may use the evaluation shortcuts that were allowed in previous labs, i.e.:

    1. [10]

           (((lambda (y) (lambda (x) (/ x y))) 2) 4)
      
    2. [20]

           ((((lambda (x) (lambda (y) (lambda (x) (+ x y)))) 3) 4) 5)
      
  3. [10] What's wrong with these expressions?

    1. (car 1)

    2. (cdr 2)

    3. (+ (cons 1 2) 2)

    After figuring out what's wrong with them, type them into the Scheme interpreter and see how the interpreter will respond to these "bugs".

  4. [10] Given:

       (define (order a b)
          (if (< a b) 
              (cons b a)
              (cons a b)))
    

    Define max and min in terms of order.


Part B: Book Exercises

Please work the following exercises from the textbook:

  1. [20] Exercise 1.42 (compose -- operations of functions on functions)

  2. [20] Exercise 1.43 (repeated application of functions)

    Note that the first argument of the repeated function is a function f that takes one argument only. This is implied by the problem statement but isn't specified as clearly as it might be.

    We definitely suggest that you use your compose function from the previous problem in this problem; it'll make the solution much simpler.

  3. [20] Exercise 2.4 (cons and car in terms of lambda)

    You don't have to rigorously prove that (car (cons x y)) = x for any x and y and the new versions of car and cons. Just give a brief explanation.

    Then verify that (cdr (cons x y)) = y for any x and y in detail by determining the value of (cdr (cons 1 2)) using the new versions of cons and cdr and using the substitution model.

    N.B.: You probably want to use a clean Scheme interpreter session for this problem only, so that you can return to the normal definition of cons/car/cdr for the other parts of the lab.


Part C: Returning lambda

  1. Numerical differentiation in one argument:

    1. [30] Define the function numerical-derivative which takes a Scheme function of one argument representing a mathematical function and returns a new procedure which calculates the derivative of the specified function. (For this problem you may define dx in a let statement inside your function; set it to 0.001.)

    2. [20] Use your numerical-derivative to define derivative functions for the following functions. Test that your derivatives produce correct results within a reasonable amount of error.

      • (define f1 (lambda (x) (+ (* 12.0 x x) (* 3.0 x) 1.0)))
      • (define f2 (lambda (x) (* x (exp (* 3.0 x)))))
      • (define f3 (lambda (x) (log x)))
    3. [20] Define a function that returns the function that takes the nth-derivative of a function. (You should use your numerical-derivative procedure defined in the previous problem.) Be sure to check that (nth-derivative 1) gives a function that is equivalent to the numerical-derivative function defined above. You can also use the fact that the zeroth derivative of a function is the function itself.

  2. Numerical integration in one argument:

    1. [45] Define a function make-integrator that takes two arguments:

      • a function representing an expansion rule (e.g. Exercise 1.29 has you using Simpson's expansion rule)
      • an integration interval, dx

      and returns another function, which we'll call F2 for short. F2 takes one argument, which is a function to be integrated; we'll call that function F3 for short. The output of F2 is yet another function, which we'll call F4. In other words, F2 takes in function F3 and returns function F4. This function F4 takes two arguments (an upper and lower limit) and returns the value of the integral of F3 between those limits. This value is computed using the expansion rule and the integration interval that were used to create F2 by make-integrator.

      That is, we should be able to do the following:

       
      (define simpsons-integrator (make-integrator 
                                     (lambda (f x dx) 
                                       (* (/ dx 6.0)
                                          (+ (f (- x (/ dx 2.0))) 
                                             (* 4.0 (f x)) 
                                             (f (+ x (/ dx 2.0))))))
                                     0.001))
      
      (define integral-logx (simpsons-integrator (lambda (x) (log x))))
      (integral-logx 2.0 4.0) ; returns the integral of log(x) between 2 and 4
      

      In this case:

      • F2 is the simpsons-integrator function, returned from make-integrator
      • F3 is the function (lambda (x) (log x))
      • F4 is the integral-logx function

      [N.B. We have posted a short explanation of expansion functions for integration on this page.]

    2. [5] Define a Simpson's rule integrator function for dx = 0.00001.

    3. [15] Using your make-integrator show how you would make an integrator based on the simple expansion rule (shown in Section 1.3.1, just before exercise 1.29) for dx = 0.00001.

    4. [20] For the three functions below and each of the two integration functions defined above [in (b) and (c)], evaluate the integrals from x=1.0 to x=3.0. Make a table of your results (you will have 3 x 2 = 6 results).

      • (define f1 (lambda (x) (+ (* 3.0 x) 1.0)))
      • (define f2 (lambda (x) (sin x)))
      • (define f3 (lambda (x) (- 10.0 (exp x))))

Part D: Good Code, Bad Code

  1. [10] Consider this procedure to compute one solution of the quadratic equation a*x2 + b*x + c = 0:

    (define (solve-quadratic-equation a b c) (define disc (sqrt (- (* b b) (* 4.0 a c)))) (/ (+ (- b) disc) (* 2.0 a)))
    
    1. What makes this procedure hard to understand?
    2. Write a cleaned up version of this procedure.

    3. What makes the new version easy to understand?

  2. Alyssa P. Hacker started an implementation for complex numbers. [NOTE: if you aren't familiar with complex numbers see this page.] Her functions are as follows:

    (define (make-complex real imaginary) (cons real imaginary))
    (define (get-real complex) (car complex))
    (define (get-imag complex) (cdr complex))
    (define (print-complex complex)
      (display (get-real complex))
      (display "+")
      (display (get-imag complex))
      (display "i"))
    
    (define (make-complex-from-magnitude-angle magnitude angle)
      ;; recall e^(i*x) = cos(x) + i*sin(x)
      (make-complex (* magnitude (cos angle))
                    (* magnitude (sin angle))))
    
    (define (add-complex a b)
      (make-complex (+ (get-real a) (get-real b))
                    (+ (get-imag a) (get-imag b))))
    

    Alyssa also defined a multiplication function:

    (define (multiply-complex a b)
      (make-complex (- (* (get-real a) (get-real b))
                       (* (get-imag a) (get-imag b)))
                    (+ (* (get-real a) (get-imag b)) 
                       (* (get-imag a) (get-real b)))))
    

    Alyssa also wrote a division function, but it hasn't been returning the correct answers:

    (define (divide-complex-alyssa-broken complex-numer complex-denom)
      (define (magnitude complex)
        (sqrt (+ (square (get-real complex)) (square (get-imag complex)))))
      (define (angle complex)
        (atan (get-real complex) (get-imag complex)))
      (define (reciprocal-complex complex)
        (let ((new-mag (/ 1 (magnitude complex)))
              (new-angle (/ -1 (angle complex))))
          (make-complex-from-magnitude-angle new-mag new-angle)))
      (multiply-complex complex-numer (reciprocal-complex complex-denom)))
    

    (Note that the atan function computes the arctangent, and can have either one or two arguments. See here for more on this.

    Ben Bitdiddle provides an alternate division implementation:

    (define (divide-complex-bitdiddle-broken a b)
      (cons
       (* (/ (sqrt (+ (square (car a)) (square (cdr a))))
             (sqrt (+ (square (car b)) (square (cdr b)))))
          (cos (- (atan (car a) (cdr a)) (atan (car b) (cdr b)))))
       (* (/ (sqrt (+ (square (car a)) (square (cdr a))))
             (sqrt (+ (square (car b)) (square (cdr b)))))
          (sin (- (atan (car a) (cdr a)) (atan (car b) (cdr b)))))))
    

    Ben's function has also been returning incorrect results.

    1. [20] Define divide-complex-alyssa by correcting Alyssa's broken implementation. What was wrong with her division function? How easy was it to identify and correct this error?

    2. [30] Define divide-complex-bitdiddle by correcting Ben's broken implementation. What was wrong with Ben's function? How easy was it to identify and correct this error?

    3. [15] What aspects of the coding style made it easier or harder to identify and correct Ben/Alyssa's errors?