RLAI 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


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:

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)
     (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)
           (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))

(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)
   (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)

;; 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)
  (map (lambda (item) (display item) (display " "))

;; 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)))

(define (driver-loop)
  (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")
          (display (my-eval read-ln the-global-environment))

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 y z)
(+ 1 2)
(* 4 6)
(* 4 (+ 7 2))
(cons x y)

Test set #2:

(define x 1)
(define f (lambda (a) x))
(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)
       (fact-iter (+ counter 1)
(* product counter)

(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:

  (define simple_set 3)
  (set! simple_set 4)

(define start 3)
(define increment
  (lambda (x)
    (set! start (+ start x))))
  (increment 4) (increment 5) (increment 2) start)

Test set #4:

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

Test set #5:

(define (f x)
  (display 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))
(define c0 (make-counter 3))


Mark Breakdown:

Cumulative Total

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