CSE341 Section #7 Problems

1. In lecture we discussed the idea of writing a function that would find the
   derivative of a function with respect to some variable.  I mentioned that I
   wanted our code to work for numbers, variables, sums, and products.  We
   didn't get to the product part, but we finished the other parts other than
   the writing of a few helper functions.  Here's where we left off:

        ; symbolic differentiation
        ; derivative of an expression:
        ;     number
        ;     variable
        ;     sum
        ;     product

        (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)))
                (else (error "illegal expression"))))

        (define (arg1 exp) (cadr exp))

        (define (arg2 exp) (caddr exp))

        (define (sum? exp)
          (and (pair? exp) (eq? (car exp) '+)))

        (define (make-sum exp1 exp2)
          (list '+ exp1 exp2))
         
   Add helper functions product? and make-product and then modify the
   derivative function to handle products.

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

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

4. Modify the derivative function 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

   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)

   Notice that we had to add an extra parameter to tell arg2 to use a + (versus
   using a *).  Of course, arg2 should still return a single result in the
   simple case:

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