Homework Assignment 8

CS 2360
Spring 1996
Homework Assignment 8
Due no later than 8:00am, Friday, May 31, 1996

Here it is...the last homework assignment.  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 
nine 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.)

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)  In Scheme, DEFINE is pretty much the same as LISP's DEFUN, except
Scheme doesn't allow for documentation strings.  Implement DEFINE so
that, for example, either of the following are accepted:

==> (define foo (x) (* x x))
#{COMPILED-LEXICAL-CLOSURE #xB48DD6}
==>

or

==> (define foo (x) "this is my doc string" (* x x))
#{COMPILED-LEXICAL-CLOSURE #xB48DD6}
==>

How and where do you store the documentation strings?  Think 
carefully about this, because some answers might create more work for 
you than other answers.

7)  Scheme doesn't have an equivalent of LISP's DEFCONSTANT or 
DEFVAR.  Add both capabilities to this mini-Scheme interpreter.  Call 
them DEFINE-CONSTANT and DEFINE-VARIABLE, respectively.  Remember 
that in LISP, constants defined through DEFCONSTANT are unmodifiable 
thereafter.  You'll want to carry that behavior into your new Scheme 
equivalent.

8)  Implement LET for the mini-Scheme interpreter.  

9)  You know it as ASSOC in Common LISP, but it's called ASSV in Scheme.
Add ASSV to your mini-Scheme interpreter.

Here's the mini-Scheme interpreter: 

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

;;;; Overview
;;;
;;; For:    2360 Spring 96
;;;
;;; 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 1996 by Kurt Eiselt.  All rights reserved.