CS 1 Fall 2008

Lab 6: Generic Assignment

Assigned: Monday, November 3, 2008
Due: Friday, November 14, 2008, 18:00


You should read through the end of Section 2.4 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.

You probably want to start the exercises from A.4 on with this unit's code base.

  1. [15] What is the value of each of the following expressions?

    1. (let ((x 2)) 
        (quote x))
            
    2. (let ((x 5)) 
        (list '(x x) x '(cons '(x x) x)))
            
    3. (let ((y 1) 
            (z 2) 
            (x '(y z))) 
        (list x y z))
            
    4. (car '(x y z))
            
  2. [10] Give a Scheme expression which will build each of the structures shown in the box and pointer diagrams:

    1. image not found
    2. image not found
  3. [10] What's wrong with these expressions?

    1. (+ ''5 5)

    2. (+ '(+ 2 3) 1)

    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. [25] Recall the abstracted unit-handling procedures developed in the lectures (the code is collected here). Fill in the abstractions for a mass unit by defining the following procedures. Your mass unit will support both grams and slugs in the same style as feet and meters were supported for length. NOTE: a slug is a unit of mass corresponding roughly to 14593.903203 grams (give or take a bit ;-)). Also, some of these procedures are already defined in the code base; in that case, just use those definitions.

    1. make-gram (*), make-slug
    2. gram? (*), slug?
    3. gram-add, slug-add
    4. get-gram, get-slug
    5. mass-add
    6. mass?

    (*) means the function is already defined in the code base. Please include it in your solution to make it easier to follow the rest of the code.

    You're free to put contracts, comments, and tests into this code, but you're not required to.

  5. [10] Show that, with this addition, unit-add can now handle:

    1. (unit-add (make-gram 20) (make-gram 23))
    2. (unit-add (make-gram 2000) (make-slug 1))
    3. (unit-add (make-slug 3) (make-slug 1))
    4. (unit-add (make-slug 3) (make-meter 1)) ;; should give an error

    Do this by printing the results that DrScheme gives you when you enter the above expressions.

  6. [25] Give a message-passing implementation for the gram unit which supports the following messages:

    1. 'get-slug

      returns a Scheme number representing the mass in slugs

    2. 'get-gram

      returns a Scheme number representing the mass in grams

    3. 'unit-type

      returns 'gram

    4. 'compatible

      returns true when given anything which 'add supports (gram or slug); here is an example:

      ;; NOTE: You do not have to define make-slug or make-foot.
      ;; This is an example to show how it should work.
      
      (define agram (make-gram 1))
      (define bslug (make-slug 1)) 
      (define cfoot (make-foot 1))
      
      (agram 'compatible agram)  ;; #t
      (agram 'compatible bslug)  ;; #t
      (agram 'compatible cfoot)  ;; #f
      

      Hint: You can assume that make-slug and make-foot return message-passing objects that accept the 'unit-type message.

    5. 'add

      adds a compatible mass; here's an example:

      (define agram (make-gram 1))
      (define bslug (make-slug 1)) ;; similarly, you do not have to define make-slug
      (define cgram (agram 'add bslug))
      

      Once again, you're free to put contracts, comments, and tests into this code, but you're not required to.


Part B: Book Exercises

Please work the following exercises from the textbook. In addition to writing the code, also add contracts and comments to the functions you define. You can also add tests if you like, but you are not required to (though it may help you debug the code!).

(N.B. The amount of code you need to write for each of these exercises is pretty small. However, you will need to understand the systems to which you are adding the code. The longer time estimates here are more of a reflection of the time it may take you to fully understand the systems rather than the time we expect it to take you to write and debug the code.)

  1. [60] Exercise 2.56 (extend differentiator) [You will need to start with the base code from Chapter 2.3]

  2. [30] Exercise 2.57 (extend differentiator) [same as above]


Part C: Message Passing

In this section, we will consider a message-passing implementation of the differentiator from part B. In addition to taking the derivative, it will be possible to print and evaluate an expression. For evaluation, we will provide a value for a variable and compute the expression (or number) that results from substituting in the number for the value (much like evaluation in our substitution model, except that we will only be giving a value to one variable at a time, so we must keep track of symbolic expressions involving the variables which have not been given values).

Each expression will be a message passing object which responds to the following messages:


Some examples:

;; g represents 5*x + x*y + 7*y
(define g (make-sum 
           (make-product 
            (make-number 5)
            (make-variable 'x))
           (make-sum
            (make-product 
             (make-variable 'y)
             (make-variable 'x))
            (make-product 
             (make-number 7)
             (make-variable 'y)))))

(g 'print)
; result: (+ (* 5 x) (+ (* y x) (* 7 y)))
; Note that these results are not maximally simplified.

((g 'evaluate 'x 2) 'print)
; result: (+ (* 5 2) (+ (* y 2) (* 7 y)))

((g 'evaluate 'y 3) 'print)
; result: (+ (* 5 x) (+ (* 3 x) (* 7 3)))

(((g 'evaluate 'x 2) 'evaluate 'y 3) 'print)
; result: (+ (* 5 2) (+ (* 3 2) (* 7 3)))

((g 'derive 'x) 'print)
; result: (+ 5 y)

((g 'derive 'y) 'print)
; result: (+ x 7)

((g 'derive 'z) 'print)
; result: 0

((((g 'derive 'x) 'evaluate 'x 2) 'evaluate 'y 3) 'print)
; result: 8

Starting Code base:

;; make-number: number -> mp-number
;; Define a number as a message-passing object. 
;; "mp-number" in the contract means "message-passing number".
;; "value" is just an ordinary Scheme number.
(define (make-number value)
  (lambda (m . args) ;; remember dotted tail notation!
    (cond ((eq? m 'derive) (make-number 0))  ; derivative of a number is 0
          ((eq? m 'print) value)
          ((eq? m 'evaluate) 
           (make-number value)) ; must evaluate to a message-passing object
          ((eq? m 'zero?) (= value 0))
          ((eq? m 'number?) #t)
          ((eq? m 'value) value)
          (else (error "unknown message: " m)))))

;; make-variable: symbol -> mp-variable
;; Define a variable as a message-passing object.
;; "mp-variable" in the contract means "message-passing variable".
;; "varname" is a Scheme symbol.
(define (make-variable varname)         
  (lambda (m . args)
    (cond ((eq? m 'derive) 
           (if (and (= (length args) 1) ;; length returns the length of a list
                    (symbol? (car args)))
               (if (eq? (car args) varname)
                   (make-number 1)
                   (make-number 0))
               (error "derive needs a variable argument")))
          ((eq? m 'print) varname)
          ((eq? m 'zero?) #f)
          ((eq? m 'number?) #f)
          ((eq? m 'value) 
           (error "should not be asking for the value of a variable"))
          ((eq? m 'evaluate) 
           (if (and (= (length args) 2)
                    (symbol? (car args))
                    (number? (cadr args)))  ;; n.b. (cadr args) is same as (car (cdr args))
               (if (eq? varname (car args)) 
                   (make-number (cadr args))
                   (make-variable varname))
               (error "evaluate needs a variable symbol and a number")))
          (else (error "unknown message: " m)))))

;; make-sum: mp-expr mp-expr -> mp-expr
;; Define a sum as a message-passing object.
;; "mp-expr" in the contract means "message-passing expression",
;; i.e. a message-passing object representing an algebraic expression.
(define (make-sum exp1 exp2)
  (cond ((exp1 'zero?) exp2) ;; exp + 0 --> exp
        ((exp2 'zero?) exp1)
        ((and (exp1 'number?) (exp2 'number?))
         (make-number (+ (exp1 'value) (exp2 'value)))) ;; num + num --> num
        (else  ;; create a new message-passing object representing the sum
         (lambda (m . args)
           (cond ((eq? m 'derive) 
                  (if (and (= (length args) 1)
                           (symbol? (car args)))
                      (let ((variable (car args)))
                        ;; derivative of a sum is the sum of the derivatives
                        ;; of the parts of the sum
                        (make-sum (exp1 'derive variable) 
                                  (exp2 'derive variable)))
                      (error "derive needs a variable argument")))
                 ((eq? m 'print) (list '+ (exp1 'print) (exp2 'print)))
                 ((eq? m 'zero?) #f)
                 ((eq? m 'number?) #f)
                 ((eq? m 'value) 
                  (error "should not be asking for the value of a sum expression"))
                 ((eq? m 'evaluate) 
                  (if (and (= (length args) 2)
                           (symbol? (car args))
                           (number? (cadr args)))
                      (let ((variable (car args))
                            (number   (cadr args)))
                        (let ((exp1-eval (exp1 'evaluate variable number))
                              (exp2-eval (exp2 'evaluate variable number)))
                          (make-sum exp1-eval exp2-eval)))
                      (error "evaluate needs a variable symbol and a number")))
                 (else (error "unknown message: " m)))))))

;; evaluate: mp-expr symbol number -> mp-expr
;; Evaluate a message-passing expression with a number
;; substituted for a variable.
(define (evaluate expression variable value)
  (expression 'evaluate variable value))

;; print: mp-expr -> (list-of symbols OR symbol OR number)
;; Return the expression as its representation as a Scheme list,
;; or as a symbol or a number if possible.
(define (print expression)
  (expression 'print))

;; We ask you to define differentiate below.

  1. [90] (about 30 lines) Provide make-product to create message-passing product expressions (one expression multiplied by another) in a manner analogous to make-sum. It should create a single numeric result when possible (i.e. when all the argument expressions given are numbers). Multiplication by the number zero should be reduced to the number zero, and multiplication of a term by one should be reduced to the term. You can use the make-sum procedure above as a skeleton to build your solution around, but be careful to notice the differences between sums and products (for one thing, there are more base cases with products). Note that the derivative of a product of two expressions can be computed with the following rule:

    Deriv(f(x) * g(x)) = Deriv(f(x)) * g(x) + f(x) * Deriv(g(x))
    

    where the derivatives are all with respect to x.

    You should include a contract and comment for make-product itself, but you don't have to write contracts for internal lambdas. You can also leave out tests; we'll talk about testing below.

  2. [5] (2 lines) Provide a definition for differentiate, so that the user can say:

    (define derivf (differentiate f 'x))
    

    and get an expression for the derivative of f in this system.

  3. [15] Demonstrate that your operations work by evaluating the following expressions and showing your results:

    1. ;; f = x3*y + 3*x2*y2 + y2 + 2
      (define f
        (make-sum
         (make-product 
          (make-variable 'x)
          (make-product 
           (make-variable 'x)
           (make-product
            (make-variable 'x)
            (make-variable 'y))))
         (make-sum
          (make-product 
           (make-number 3)
           (make-product
            (make-variable 'x)
            (make-product
             (make-variable 'x)
             (make-product
              (make-variable 'y)
              (make-variable 'y)))))
          (make-sum
           (make-product 
            (make-variable 'y)
            (make-variable 'y))
           (make-number 2)))))
      
    2. (define dfdx (differentiate f 'x))
      
    3. (print dfdx)
      
    4. (print (evaluate f 'x 3))
      
    5. (print (evaluate (evaluate f 'x 3) 'y 4))
      
    6. (print (evaluate (evaluate dfdx 'x 3) 'y 4))
      

Hint: You probably want to test your functions on some simpler operations first. Here are some examples. You do not have to submit the results of using your functions on these values.

(define n0 (make-number 0))
(define n1 (make-number 1))
(define n2 (make-number 2))
(define x (make-variable 'x))
(define s1 (make-sum n1 n2)) 
(define s2 (make-sum n1 n0)) 
(define s3 (make-sum x n1)) 
(define s4 (make-sum (make-variable 'y) (make-number 4)))
(define p1 (make-product n2 n2)) 
(define p2 (make-product x n0)) 
(define p3 (make-product x n2)) 
(define p4 (make-product x s1)) 
(define sl1 (make-sum p3 (make-sum p4 s3)))
(define p5 (make-product n2 p4))
(define p6 (make-product x s3))
(define ap1 (make-sum p3 p4))
(define pa1 (make-product  s3 s4))
(define pl1 (make-product s3 (make-product s4 sl1)))
(print (p3 'derive 'x))
(print (p3 'derive 'y))
(print (p6 'derive 'x))
(print (pl1 'derive 'x))
(print (pl1 'derive 'y))
(print (e3 'derive 'x))

Part D: Good Code, Bad Code

There is no part D this week.