CS 2360
Spring 1998
Homework Assignment 8
Due no later than 8:00am, Monday, June 1, 1998
This assignment revolves around the mini-Scheme interpreter we
discussed in class today, albeit briefly because of a little
bitty problem with temperature control in our lecture hall. 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).
Last revised: May 26, 1998