CS 2360
Summer 1998
Homework Assignment 8
Due no later than 8:00am, Tuesday, August 25, 1998

This assignment revolves around the mini-Scheme interpreter we
discussed in class recently.  The Common LISP code for that interpreter
can be found in your posted class notes.  Lyman has altered that
interpreter a little bit and that revised version is shown 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 (definition:
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.

8)  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.
 
9)  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.

Here's the slightly modified and rearranged mini-Scheme interpreter,
in which Lyman has replaced the use of a property list (look it up)
with a hash table (look that up too) for storing global variables.
He's also added EXIT-SCHEME and SUSPEND-SCHEME.

You don't need to know how to create macros to solve this assignment,
and we haven't taught you how yet anyway, so DON'T USE MACROS HERE.
In previous quarters, students have attempted to apply their own
macros in this assignment, with disastrous results.  So I repeat,
DON'T USE MACROS HERE.


;;;-*- Mode: LISP; Syntax: Common-Lisp; Base: 10; Package: COMMON-LISP-USER -*-
 
;;;$Id: scheme_newer.lisp,v 1.4 1997/08/21 23:03:46 lyman Exp lyman $
;;;$Revision: 1.4 $
 
 
;;;; Overview
;;;
;;; For:    CS 2360 
;;;
;;; Modified by: Lyman and Kurt
;;;
;;; Note the addition of EXIT-SCHEME, which results in a graceful exit
;;; from the interpreter when called.  And SUSPEND-SCHEME which allows
;;; you go back to the Lisp Listener (and type (scheme) to restart). 
;;;
;;; This file contains the scheme interpreter discussed in 
;;; class.... with some modifications... 
;;;
 
(defconstant *scheme-symbol-table* (make-hash-table)) 
 
(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 suspend-scheme ))
 
(defun interp (x &optional env)
  (cond
    ((symbolp x) (get-var x env))
    ((atom x) x)
    ((case (first x)
       (QUOTE  (second x))
       (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)
  (check-type var symbol )
  (setf (gethash var *scheme-symbol-table*) val))
 
(defun get-global-var (var)
  (let* ((default "unbound")
         (val (gethash var *scheme-symbol-table*  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 ()
   (clrhash *scheme-symbol-table*)
   (throw 'schemer  nil ))
 
(defun suspend-scheme ()
   (throw 'schemer  nil ))

;;;EOF
;;;;;;


Copyright 1998 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).