Homework Assignment 8

CS 2360
Winter 1997
Homework Assignment 8
Due no later than 8:00am, Friday, March 14, 1997

Here it is...the last homework assignment.  And posted *before*
a night of Must See TV, no less!  This assignment revolves 
around the mini-Scheme interpreter we discussed in class today.  The 
Common LISP code for that interpreter (which Lyman has altered a little)
is listed at the end of this posting.  Your assignment consists of 
seven parts:

1)  Figure out how this interpreter works.  Demonstrate your 
understanding by submitting, for each function, a description of how 
it works, what the arguments are all about (in terms of what 
information is passed there as well as its structure), and what 
information is returned.  Also describe the form and content of any 
global data structures.

2)  This interpreter only deals with three special forms (reminder: 
special forms are functions that don't deal with their arguments in 
the usual way -- for example, QUOTE doesn't evaluate its argument).  
These forms are QUOTE, SET!, and LAMBDA.  Add the LISP code that will 
let the mini-Scheme interpreter interpret the IF special form 
correctly.  (IF in Scheme works the same way that it does in Common 
LISP.)  Since we did this one in class, you get this one for free.

3)  Now add the LISP code that will let the mini-Scheme interpreter 
interpret the BEGIN special form correctly.  (BEGIN in Scheme works 
the same way that PROGN does in Common LISP...look it up.)

4)  IF was simple.  Now add COND (which works just like it does in 
Common LISP).

5)  REVERSE in Scheme also works just like it does in Common LISP.
Implement REVERSE in your mini-Scheme interpreter.

6)  Implement LET for the mini-Scheme interpreter.  

7)  You know it (and you love it) as ASSOC in Common LISP, but it's 
called ASSV in Scheme.  Add ASSV to your mini-Scheme interpreter.

Here's the slightly modified and rearranged mini-Scheme interpreter: 

;;;-*- Mode: LISP; Syntax: Common-Lisp; Base: 10; Package: COMMON-LISP-USER -*-

;;;; Overview
;;;
;;; For:    2360 Winter 97
;;;
;;; Modified by: Lyman and Kurt
;;;
;;; Note the addition of EXIT-SCHEME, which results in a graceful exit
;;; from the interpreter when called.
;;;
;;; This file contains the scheme interpreter discussed in 
;;; class....
;;;

(defparameter *scheme-procs*
  '(+ - * / = < > <= >= cons car cdr
    not append list read member 
    (null? null) (eq? eq) (equal? equal) (eqv? eql)
    (write prin1) (display princ) (newline terpri)
    exit-scheme))

(defun interp (x &optional env)
  (cond
    ((symbolp x) (get-var x env))
    ((atom x) x)
    ((case (first x)
       (QUOTE  (second x))
       (BEGIN  (cerror "Return NIL"
                       "The feature is not implemented."))
       (SET!   (set-var! (second x) (interp (third x) env) env))
       (IF (cerror "Return NIL"
                   "The feature is not implemented."))
       (LAMBDA (let ((parms (second x))
                     (code (maybe-add 'begin (rest (rest x)))))
                 #'(lambda (&rest args)
                     (interp code (extend-env parms args env)))))
       (t      (apply (interp (first x) env)
                      (mapcar #'(lambda (v) (interp v env))
                              (rest x))))))))


(defun extend-env (vars vals env)
  (nconc (mapcar #'list vars vals) env))

(defun maybe-add (op exps &optional if-nil)
  (cond ((null exps) if-nil)
        ((length=1 exps) (first exps))
        (t (cons op exps))))

(defun set-var! (var val env)
  (if (assoc var env)
      (setf (second (assoc var env)) val)
      (set-global-var! var val))
  val)

(defun get-var (var env)
    (if (assoc var env)
        (second (assoc var env))
        (get-global-var var)))

(defun set-global-var! (var val)
  (setf (get var 'global-val) val))

(defun get-global-var (var)
  (let* ((default "unbound")
         (val (get var 'global-val default)))
    (if (eq val default)
        (error "Unbound scheme variable: ~a" var)
        val)))

(defun scheme ()
  (init-scheme-interp)
  (catch 'schemer
    (loop (format t "~&==> ")
        (print (interp (read) nil)))))

(defun init-scheme-interp ()
  (mapc #'init-scheme-proc *scheme-procs*)
  (set-global-var! t t)
  (set-global-var! nil nil))

(defun init-scheme-proc (f)
  (if (listp f)
      (set-global-var! (first f) (symbol-function (second f)))
      (set-global-var! f (symbol-function f))))

(defun length=1 (x)
  (and (consp x) (null (cdr x))))

(defun last1 (list)
  (first (last list)))

(defun exit-scheme ()
   (throw 'schemer  nil ))




;;;EOF
;;;;;;



Copyright 1997 by Kurt Eiselt.  All rights reserved except those 
reserved by the original author of this program (it's not Lyman,
and it sure isn't me).