CSE341 Section #7 Problems

We left off with this version of the symbolic differentiation code in lecture:

    (define (derivative exp var)
      (cond ((number? exp) 0)
            ((symbol? exp)
             (if (eq? exp var) 1 0))
            ((sum? exp)
             (make-sum (derivative (arg1 exp) var)
                       (derivative (arg2 exp) var)))
            ((product? exp)
             (make-sum
              (make-product (arg1 exp)
                            (derivative (arg2 exp) var))
              (make-product (derivative (arg1 exp) var)
                            (arg2 exp))))
            (else (error "illegal expression"))))
    
    (define (arg1 exp) (cadr exp))
    
    (define (arg2 exp) (caddr exp))
    
    (define (make-sum exp1 exp2)
      (list '+ exp1 exp2))
    
    (define (make-product exp1 exp2)
      (list '* exp1 exp2))
    
    (define (sum? exp)
      (and (pair? exp) (eq? (car exp) '+)))

    (define (product? exp)
      (and (pair? exp) (eq? (car exp) '*)))

1. Write new versions of make-sum and make-product that perform some
   simplification.  For example, there is no reason to produce results like:

        (+ x 0)
        (+ 1 1)

   The first is simply x and the second is 2.  Try to think of as many cases as
   you can to simplify.

2. Modify the derivative code to allow for expressions with more than 2 values
   being added together or multiplied, as in:

        > (derivative '(+ x x x x x x) 'x)
        6

   It is best to do this without modifying the derivative function itself.  One
   way to make this work is to modify arg2 so that it sometimes returns an
   expression list with a + or * as the first element.  In the example above,
   it would behave this way:

        > (arg2 '(+ x x x x x x))
        (+ x x x x x)

   Of course, arg2 should still return a single result in the simple case:

        > (arg2 '(+ x x) '+)
        x
        
3. Extend the derivative function so that it handles expressions that involve a
   variable carried to a numeric exponent.  For example, instead of saying:

        (derivative '(* x x x x x x) 'x)

   we want to be able to say:

        (derivative '(^ x 6) 'x)

   The clauses should always begin with an up-arrow that indicates
   exponentiation followed by a single variable followed by a number.

4. Define a function count that takes a value and a list as argument and that
   returns the number of occurrences of the value in the list.  Your function
   should use a deep equality comparison.  For example:

        > (count 3 '(7 9 2 4 a (3 2) 3 "hello" 3))
        2
        > (count 'a '(3 a b a 19 (a b) c a))
        3
        > (count '(a b) '(a b c (a b) d 3 a b))
        1

5. Define a function zip that takes two lists as arguments and that returns the
   list obtained by combining pairs of values in corresponding positions into
   lists of 2 elements.  The first element should be a list containing the
   first values from each list.  The second element should be a list containing
   the second values from each list.  And so on.  If one list is shorter than
   the other, then zip should return a list of that shorter length.  For
   example:

        > (zip '(1 2 3) '(a b c))
        ((1 a) (2 b) (3 c))
        > (zip '(1 2 3 4 5) '(a b c d))
        ((1 a) (2 b) (3 c) (4 d))

6. The Fibonacci sequence is defined recursively:
        fib(0) = fib(1) = 1
        fib(n) = fib(n - 1) + fib(n - 2) for n > 1
   This is easily translated into a Scheme function:

        (define (fib n)
          (if (<= n 1)
              1
              (+ (fib (- n 1)) (fib (- n 2)))))

   This is a highly inefficient way to compute the result.  Even computing
   values like fib(35) is noticeably slow.  Consider the following Java method
   for computing Fibonacci iteratively:

        public static int fib(int n) {
            int prev = 1;
            int prevPrev = 1;
            while (n > 1) {
                int sum = prev + prevPrev;
                prevPrev = prev;
                prev = sum;
                n--;
            }
            return prev;
        }

   Translate this code into an equivalent Scheme function.  You'll find that
   you can ask for fib of large values, as in (fib 9999), and get an answer
   almost immediately.

7. In lecture we developed parsing code for the following grammar:

        <sequence> ::= <item> {"+" <item>}
        <item> ::= <number> | <symbol>

   We ended up with the following functions:

        (define (parse-item lst)
          (if (not (pair? lst))
              (error "item error")
              (let ((first (car lst)))
                (cond ((number? first) (cons (number->string first) (cdr lst)))
                      ((symbol? first) (cons (symbol->string first) (cdr lst)))
                      (else (error "item error"))))))
        
        (define (parse-sequence)
          (let ((result (parse-item lst)))
            (cond ((and (> (length result) 1) (eq? '+ (cadr result)))
                   (let ((result2 (parse-sequence (cddr result))))
                     (cons (string-append (car result) "," (car result2))
                           (cdr result2))))
                  (else result))))

   Recall that this converts a sequence into a string where elements are
   separated by commas, as in:

        > (parse-sequence '(3 + 4.5 + x + foo + 9.8))
        ("3,4.5,x,foo,9.8")

   Suppose that we add a new rule to the grammar:

        <multisequence> ::= <sequence> {"&" <sequence>}

   The idea is that we can chain together multiple sequences with an &.  We
   want to define a parsing function that consumes a multisequence and replaces
   it with a string that uses "--" to separate the sequences as in:
   
        > (parse-multisequence '(3.4 + x + 9.7 + 2.4 & 3.8 + 2.4))
        ("3.4,x,9.7,2.4--3.8,2.4")
        > (parse-multisequence '(x + y & 2 + 3.4 & 7.4 & 9 + 2 + z))
        ("x,y--2,3.4--7.4--9,2,z")

   Notice that + has a higher level of precedence than the &.  This is a direct
   result of the way that the grammar is written.  Translate the grammar rule
   for multisequence into a parse-multisequence function.