CMPUT 325: Assignment 5

	Reinforcement Learning and Artificial Intelligence (RLAI)
	CMPUT 325: Assignment 5

Due: Monday, 23 October, 2006 by 23:59:59

Specs:
Do exercises 2.77, 2.79, 2.83, 3.1, 3.2, 3.6 and 3.8 from Structure and Interpretation of Computer Programs (second edition).
Please follow the rules given below. If there is a discrepancy between the text and the rules below, follow our instructions.
UPDATE: see below

Submission Instructions:
Write all your answers in a plain text file named a5. From the directory where this file is located, type in the following command:

astep -c c325 -p ex5 a5

When prompted if this is your primary submission, answer Y. You may submit as many times as you like; the last version you submit will be marked. All submissions should be primary submissions, not just the last.

Ensure that you follow the Style and Submission Guidelines exactly. Failure to do so will result in lost marks.

Rules, Guidelines and Suggestions:

To help you with the tracing in exercise 2.77, we have provided you with the code collected from sections 2.4.3 and 2.5.1. Once you copy/paste this code to your file, you can then create the complex number z by calling:

(define z (make-complex-from-real-imag 3 4))

Please note that this code is for you to experiment with only. Do not include this code in yout submission, not even as comments. Also, if your tracing answer spans more than 15 lines, then you are showing more detail than is necessary. Only show calls to the procedures we are concenred with in the question. As a side note, it helps to test this code under the language Textual (MzScheme ...) under PLT. The reason is that this code uses the function error which is not supported by the language Standard(R5RS).

For question 2.83, we will not run your code. But you will have to provide correct procedure calls. You must respect the interfaces used in the package installations (look at code provided for question 2.77). In addition to what the question asks, answer the following two questions:

Where would you add each of your put calls?
Why?

The code you write for exercises 2.79, 3.1, 3.2, 3.6 and 3.8 will be tested electronically. To ensure we can test your code, please do the following:

Write your answers to all the other exercises inside comments. Comments in Scheme are delimited by the characters #| and |#.
For 2.79, we'll be testing the procedure equ? which takes in two arguments. You can do your own tests using the code provided to you for question 2.77.
For 3.1, define the procedure make-accumulator which takes only one argument.
For 3.2, define the procedure make-monitored which takes one argument: the name of a procedure.
For 3.6, define the procedure rand as described in the question. Use the following rand-update:

(define (rand-update x) (+ x 5))

and use the fixed value 10 as random-init.

For 3.8, define the procedure f as described in the question.

UPDATE (Oct 16): Also, to make it possible for us to test it, make a copy of the procedure f but with the name g. Submit both procedures in your file.

For questions which require procedures to be written, hand in syntactically correct Scheme code (which hopefully is also algorithmically correct)
We will be marking for style on some questions. Code which is cleanly written, and which performs the given task well will receive a higher mark than solutions which are poorer in terms of structure and algorithm. Put closing parenthesis on the same line as the thing they enclose, not on a new line by themselves. No orphan parenthesis!
Be certain you are using the correct edition of the text. Not all exercises are similar between the first and second editions of the text. Ditto for the online version

Code (taken from the text):

Do not include this code in the file you submit not even as comments.



;;exercise 2.77



;;;; defining the generic operators

(define (add x y) (apply-generic 'add x y))

(define (sub x y) (apply-generic 'sub x y))

(define (mul x y) (apply-generic 'mul x y))

(define (div x y) (apply-generic 'div x y))



(define (real-part z) (apply-generic 'real-part z))

(define (imag-part z) (apply-generic 'imag-part z))

(define (magnitude z) (apply-generic 'magnitude z))

(define (angle z) (apply-generic 'angle z))



;;;; defining the scheme-number
installation package

(define (install-scheme-number-package)

  (define (tag x)

    (attach-tag 'scheme-number x))    

  (put 'add '(scheme-number scheme-number)

       (lambda (x y) (tag (+ x y))))

  (put 'sub '(scheme-number scheme-number)

       (lambda (x y) (tag (- x y))))

  (put 'mul '(scheme-number scheme-number)

       (lambda (x y) (tag (* x y))))

  (put 'div '(scheme-number scheme-number)

       (lambda (x y) (tag (/ x y))))

  (put 'make 'scheme-number

       (lambda (x) (tag x)))

  'done)

(define (make-scheme-number n)

  ((get 'make 'scheme-number) n))

;;;; defining the
rational installation package

(define (install-rational-package)

  ;; internal procedures

  (define (numer x) (car x))

  (define (denom x) (cdr x))

  (define (make-rat n d)

    (let ((g (gcd n d)))

      (cons (/ n g) (/ d g))))

  (define (add-rat x y)

    (make-rat (+ (* (numer x) (denom y))

                
(* (numer y) (denom x)))

             
(* (denom x) (denom y))))

  (define (sub-rat x y)

    (make-rat (- (* (numer x) (denom y))

                
(* (numer y) (denom x)))

             
(* (denom x) (denom y))))

  (define (mul-rat x y)

    (make-rat (* (numer x) (numer y))

             
(* (denom x) (denom y))))

  (define (div-rat x y)

    (make-rat (* (numer x) (denom y))

             
(* (denom x) (numer y))))

  ;; interface to rest of the system

  (define (tag x) (attach-tag 'rational x))

  (put 'numer 'rational numer)

  (put 'denom 'rational denom)

  (put 'add '(rational rational)

       (lambda (x y) (tag (add-rat x y))))

  (put 'sub '(rational rational)

       (lambda (x y) (tag (sub-rat x y))))

  (put 'mul '(rational rational)

       (lambda (x y) (tag (mul-rat x y))))

  (put 'div '(rational rational)

       (lambda (x y) (tag (div-rat x y))))



  (put 'make 'rational

       (lambda (n d) (tag (make-rat n
d))))

  'done)

(define (make-rational n d)

  ((get 'make 'rational) n d))

;;;; defining the
complex installation package

(define (install-complex-package)

  ;; imported procedures from rectangular and polar packages

  (define (make-from-real-imag x y)

    ((get 'make-from-real-imag 'rectangular) x y))

  (define (make-from-mag-ang r a)

    ((get 'make-from-mag-ang 'polar) r a))

  ;; internal procedures

  (define (add-complex z1 z2)

    (make-from-real-imag (+ (real-part z1) (real-part
z2))

                        
(+ (imag-part z1) (imag-part z2))))

  (define (sub-complex z1 z2)

    (make-from-real-imag (- (real-part z1) (real-part
z2))

                        
(- (imag-part z1) (imag-part z2))))

  (define (mul-complex z1 z2)

    (make-from-mag-ang (* (magnitude z1) (magnitude z2))

                      
(+ (angle z1) (angle z2))))

  (define (div-complex z1 z2)

    (make-from-mag-ang (/ (magnitude z1) (magnitude z2))

                      
(- (angle z1) (angle z2))))

  ;; interface to rest of the system

  (define (tag z) (attach-tag 'complex z))

  (put 'add '(complex complex)

       (lambda (z1 z2) (tag (add-complex
z1 z2))))

  (put 'sub '(complex complex)

       (lambda (z1 z2) (tag (sub-complex
z1 z2))))

  (put 'mul '(complex complex)

       (lambda (z1 z2) (tag (mul-complex
z1 z2))))

  (put 'div '(complex complex)

       (lambda (z1 z2) (tag (div-complex
z1 z2))))

  (put 'make-from-real-imag 'complex

       (lambda (x y) (tag
(make-from-real-imag x y))))

  (put 'make-from-mag-ang 'complex

       (lambda (r a) (tag
(make-from-mag-ang r a))))

  'done)



(define (make-complex-from-real-imag x y)

  ((get 'make-from-real-imag 'complex) x y))

(define (make-complex-from-mag-ang r a)

  ((get 'make-from-mag-ang 'complex) r a))

;;;; defining the
rectangular (complex) installation package

(define (install-rectangular-package)

  ;; internal procedures

  (define (real-part z) (car z))

  (define (imag-part z) (cdr z))

  (define (make-from-real-imag x y) (cons x y))

  (define (magnitude z)

    (sqrt (+ (square (real-part z))

            
(square (imag-part z)))))

  (define (angle z)

    (atan (imag-part z) (real-part z)))

  (define (make-from-mag-ang r a) 

    (cons (* r (cos a)) (* r (sin a))))

  ;; interface to the rest of the system

  (define (tag x) (attach-tag 'rectangular x))

  (put 'real-part '(rectangular) real-part)

  (put 'imag-part '(rectangular) imag-part)

  (put 'magnitude '(rectangular) magnitude)

  (put 'angle '(rectangular) angle)

  (put 'make-from-real-imag 'rectangular 

       (lambda (x y) (tag
(make-from-real-imag x y))))

  (put 'make-from-mag-ang 'rectangular 

       (lambda (r a) (tag
(make-from-mag-ang r a))))

  'done)

;;;; defining the
polar (complex) installation package

(define (install-polar-package)

  ;; internal procedures

  (define (magnitude z) (car z))

  (define (angle z) (cdr z))

  (define (make-from-mag-ang r a) (cons r a))

  (define (real-part z)

    (* (magnitude z) (cos (angle z))))

  (define (imag-part z)

    (* (magnitude z) (sin (angle z))))

  (define (make-from-real-imag x y) 

    (cons (sqrt (+ (square x) (square y)))

          (atan y x)))

  ;; interface to the rest of the system

  (define (tag x) (attach-tag 'polar x))

  (put 'real-part '(polar) real-part)

  (put 'imag-part '(polar) imag-part)

  (put 'magnitude '(polar) magnitude)

  (put 'angle '(polar) angle)

  (put 'make-from-real-imag 'polar

       (lambda (x y) (tag
(make-from-real-imag x y))))

  (put 'make-from-mag-ang 'polar 

       (lambda (r a) (tag
(make-from-mag-ang r a))))

  'done)



(define (make-from-real-imag x y)

  ((get 'make-from-real-imag 'rectangular) x y))

(define (make-from-mag-ang r a)

  ((get 'make-from-mag-ang 'polar) r a))

;;;; defining the
apply-generic procedure which, given a generic operator name,

;;;; will apply a specific procedure corresonding to the type of the
arguments

(define (apply-generic op . args)

  (let ((type-tags (map type-tag args)))

    (let ((proc (get op type-tags)))

      (if proc

          (apply proc (map
contents args))

          (error

            "No
method for these types -- APPLY-GENERIC"

           
(list op type-tags))))))

;;;;
attach-tag "attaches" a given tag to a given value

(define (attach-tag type-tag contents)

  (cons type-tag contents))

;;;; type-tag returns
the type of a value, which has previously been attached to it using
attach-tag

(define (type-tag datum)

  (if (pair? datum)

      (car datum)

      (error "Bad tagged datum -- TYPE-TAG"
datum)))

;;;; contents returns
the actual value of a given input

(define (contents datum)

  (if (pair? datum)

      (cdr datum)

      (error "Bad tagged datum -- CONTENTS"
datum)))

;;;; defining the
table structure, which was also used for assignment 4 

;;;; note: you do not need to understand this code thoroughly, just
know how

;;;; to use put and get

(define (make-table)

  (let ((local-table (list '*table*)))

    (define (lookup key-1 key-2)

      (let ((subtable (assoc key-1 (cdr
local-table))))

        (if subtable

            (let
((record (assoc key-2 (cdr subtable))))

             
(if record

                 
(cdr record)

                 
#f))

            #f)))

    (define (insert! key-1 key-2 value)

      (let ((subtable (assoc key-1 (cdr
local-table))))

        (if subtable

            (let
((record (assoc key-2 (cdr subtable))))

             
(if record

                 
(set-cdr! record value)

                 
(set-cdr! subtable

                           
(cons (cons key-2 value)

                                 
(cdr subtable)))))

           
(set-cdr! local-table

                     
(cons (list key-1

                                 
(cons key-2 value))

                           
(cdr local-table)))))

      'ok)   

    (define (dispatch m)

      (cond ((eq? m 'lookup-proc) lookup)

           
((eq? m 'insert-proc!) insert!)

           
(else (error "Unknown operation -- TABLE" m))))

    dispatch))



(define operation-table (make-table))

(define get (operation-table 'lookup-proc))

(define put (operation-table 'insert-proc!))



(define (square x) (* x x))

;;;; installing all
the packages

(install-polar-package)

(install-rectangular-package)

(install-scheme-number-package)

(install-rational-package)

(install-complex-package)

Test Cases:
For this assignment, your code will be tested for you upon submission. Use astep whenever you'd like to see if your code is passing the tests we're providing for you.

Mark Breakdown:

Question	Marks
2.77	4
2.79	4
2.83	5
3.1	2
3.2	3
3.6	4
3.8	2
Total	24
Cumulative Total	123

Back to CMPUT 325 Homepage

Extend this Page How to edit Style Subscribe Notify Suggest Help This open web page hosted at the University of Alberta. Terms of use 1484/0