Reinforcement Learning and Artificial Intelligence (RLAI)

CMPUT 325: Assignment 6

Understanding the Q&D scheme interpreter

Due: Thursday, November 9, 2006 by 23:59:59

Specs:

The code and test sets are attached below. For this assignment you may want to use mzscheme and emacs instead of drscheme. I found emacs in scheme mode better for shipping test cases to the interpreter. Your mileage may vary. Let us know if you find a convenient way to do this in drscheme.

The following are the steps you need to complete this assignment successfully:

1. Get the code for the incomplete version of the Q&D scheme interpreter. Load it into emacs or drscheme.

2. Write a definition of the scheme variable the-global-environment. If you do this right, my-eval and driver-loop should work for the expressions in test set #1.

3. Fix the one-line bug in eval-define. After that you should be able to handle the expressions in test set #2, including procedures with internal state.

4. Define the procedure eval-set!. It should take parameters as given in the definition of my-eval. Test your solution on test set #3.

5. Extend my-eval to handle parenthesized defines, e.g. (define (f x) x). Test your solution on test set #4.

6. Extend my-eval to handle lambda bodies with multiple expressions in them, e.g. (lambda (x) (display x) x). After this you should be able to handle internal definitions and the other examples in test set #5.

Submission Instructions:

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

astep -c c325 -p ex6 a6

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:

There is nothing to be written for this assignment. All we need is the scheme code which implements the features outlined above. Explanatory comments are always welcome, as long as they are meaningful, and have been commented out.
Hand in all your code, including any code you didn't alter. In other words, the file a6 should contain the Scheme code for a full, working interpreter, which can be run by calling driver-loop.
For step 5, it is likely easiest to convert any instance of (define (foo x y ... ) body) into (define foo (lambda (x y ... ) body)) inside my-eval, and then evaluate the newly-created definition of foo.
For step 6, remember that my-eval already works for expressions of the form (begin (display x) x).
(display) can make debugging your code significantly easier. Any time when you would like to see what expression you are evaluating looks like, what your environment looks like, or if your code transformations are working correctly, use display to print them to the screen. Remember to remove all superfluous applications of display before submitting. (newline)could also be useful for making your debug output a little more readable.

The (incomplete) code for the Q&D scheme interpreter:

(define (my-eval exp env)

  (cond ((self-evaluating? exp) exp)

    ((symbol? exp) (lookup-variable-value exp env))

    ((eq? (first exp) 'quote) (second exp))

    ((eq? (first exp) 'if) (eval-if exp env))

    ((eq? (first exp) 'begin) (eval-begin exp env))

    ((eq? (first exp) 'define) (eval-define exp env))

    ((eq? (first exp) 'set!) (eval-set! exp env))

    ((eq? (first exp) 'lambda)

     (list
'procedure            
; proc = ('procedure <params> <body> <env>)

           (second exp)

           (third exp)

           env))

    (else 

     (my-apply (my-eval (first exp) env)

       
       (list-of-values (rest exp) env)))))



(define (my-apply proc args)

  (cond ((member proc primitive-procedures) 

         (apply proc args))

        ((eq? (first proc)
'procedure)

         (let* ((params (second
proc))

                (body
(third proc))

   
           
(proc-env (fourth proc))

   
           
(extended-env (cons (make-frame params args)

               
              proc-env)))

           (my-eval body
extended-env)))

        (else (error "ill-formed
procedure:" proc))))



(define (self-evaluating? exp)

  (or (number? exp)

      (string? exp)

      (eq? exp #f)

      (eq? exp #t)))



(define (list-of-values exps env)

  (map (lambda (exp) (my-eval exp env))

       exps))



(define (eval-if exp env)       
    ;if = (if predicate x y)

  (if (true? (my-eval (second exp) env))

      (my-eval (third exp) env)

      (my-eval (fourth exp) env)))



(define (true? x) 

  (not (eq? x #f)))



(define (eval-begin exp env)

  (last 

   (map (lambda (e) (my-eval e env)) 

        (rest exp))))





;; an environment is a list of frames

;; a frame is a list of bindings

;; a binding is a (variable . value) pair



;; warning: this implementation of frames is different from that in the
book



(define (make-frame vars vals)

  (map cons vars vals))



(define (lookup-variable-value var env)

  (if (null? env)

      (error "unbound variable:" var env)

      (let* ((first-frame (first env))

            
(binding (scan-for-binding var first-frame)))

        (if binding

            (cdr
binding)

           
(lookup-variable-value var (rest env))))))



(define scan-for-binding assq)



;; there is a one-line bug in the following procedure

(define (eval-define exp env)

  (let* ((var (second exp))

         (val (third exp))

         (frame (first env))

         (binding (scan-for-binding
var frame)))

    (if binding

        (set-cdr! binding val)

        (set-car! env 

       
          (cons (cons var
val)

                
       frame)))))



;; write your eval-set! here



; little utilities



(define first car)

(define second cadr)

(define third caddr)

(define fourth cadddr)

(define rest cdr)

(define (last list) (first (reverse list)))



(define (error . items)

  (newline)

  (map (lambda (item) (display item) (display " ")) 

       items))



;; top-level stuff to make this run



(define primitive-procedure-names 

  '(+ - * / cons car cdr null? = < > <= >= not
display))



(define primitive-procedures 

  (map (lambda (name) (eval name (interaction-environment)))

       primitive-procedure-names))



(define (driver-loop)

  (newline)

  (display "my-scheme> ")

  (let ((read-ln (read)))

    (if (or (equal?
read-ln '(quit))

           
(equal? read-ln '(exit))

           
(equal? read-ln '(bye)))

       
(display "thank you for using the Q&D scheme interpreter")

       
(begin 

         
(display (my-eval read-ln the-global-environment))

         
(driver-loop)))))

#|

TEST SETS



These consist of expressions that you can type/send to the driver-loop
or send directly to my-eval, for example as in (my-eval '(define x 1)
the-global-environment). You should get answers just as regular scheme
would produce.



Test set #1:



(define x 1)

(define y 2)

'x

x

'(x y z)

(+ 1 2)

(* 4 6)

(* 4 (+ 7 2))

(cons x y)



Test set #2:


(define x 1)

(define f (lambda (a) x))

f

(f 1)



(define g (lambda (x y) (* x y)))



(g 7 8)

(((lambda (x)

(lambda (y) (+ x y))) 3) 4)





((lambda (x y)



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



  (* x y)))

3 4)





((lambda (x)

(if (< x 0) (- 0 x) x))

-2)



(< 2 1)





(define fact-iter

  (lambda (counter product n)

(if (> counter n)

product



       (fact-iter (+ counter 1)

(* product counter)

n))))





(define factorial

  (lambda (n)

(fact-iter 1 1 n)))



(factorial 4)





(define factr

  (lambda (n)

(if (= n 1)

(* n (factr (- n
1))))))



(factr 6)





(begin (display "1") (display "2"))



(define addx 

  (lambda (x) 

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

(define add5 (addx 5))

(add5 10)



Test set #3:



(begin

  (define simple_set 3)

  (set! simple_set 4)

  simple_set)



(define start 3)

(define increment

  (lambda (x)

    (set! start (+
start x))))

(begin

  (increment 4) (increment 5)
(increment 2) start)



Test set #4:

(define (factr n)
(if (= n 1)
1
(* n (factr (- n 1)))))

(factr 6)

Test set #5:

(define (f x)

  (display x)

  x)

(f 5)



(define (g x)

  (define (h y)

    (+ y 1))

  (h (- x 1)))

(g 5)



(define (make-counter x)

  (lambda () (set! x (+ x 1))

            
x))

(define c0 (make-counter 3))

(c0)

(c0)

|#

Mark Breakdown:

Question	Marks
2	4
3	3
4	8
5	5
6	5
Total	25
Cumulative Total	148

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 1504/0