Project #1 – Writing a Scheme Interpreter in Scheme
CS 152 Section 5 – Fall 2020
Michael McThrow
San José State University

NOTE: The specification was revised on September 30, 2010 to get rid of Part 3, which would have
involved writing additional functions outside the interpreter.

Introduction
Your task for Project #1 is to write an interpreter for Scheme using Scheme in DrRacket. Your
interpreter will be called my-scheme.rkt and it will be written in the Racket dialect of Scheme just
as Lab #2. An interpreter written in the same language that is to be interpreted is known as a
metacircular interpreter. For example, if we wrote a Python interpreter in Python, that interpreter
would be metacircular.

Your task is to define two functions:
1. my-eval, which evaluates an S-expression given an environment and a list of mappings from

environment names to environments, and
2. eval-prog, which evaluates a list of S-expressions.

Your task is to define a function named my-eval that takes three arguments:
1. expr, which is the S-expression to be evaluated
2. env, which is the environment that the expression is being evaluated under, and
3. env-map, which maps environment names to environments

It is your choice regarding how to implement env and env-map (e.g., cons pairs, lists, binary search
trees, etc.) as long as they adhere to functional programming style (i.e., no mutation and no side
effects).

Here is a usage example:
(my-eval ‘(+ 2 5) (get-global-env) (get-global-env-map))

In this usage example, my-eval will be evaluating the S-expression (+ 2 5). Why is (+ 2 5)
preceded by a quote ‘ in the above call to my-eval? Recall that ‘(+ 2 5) is shorthand for
(quote (+ 2 5)). The quote function tells the top-level interpreter not to evaluate the argument.
We want our interpreter my-eval to evaluate (+ 2 5), not DrRacket, and so we need to pass the
uninterpreted expression into my-eval.

The beauty about writing a Scheme interpreter in Scheme is that we don’t have to worry about parsing
S-expressions. In fact, we don’t have to write any string-handling code at all in our evaluator. Instead,
we can simply leverage Scheme’s built-in support for handling S-expressions.

What are the functions get-global-env and get-global-env-map? These are functions that
we can use for getting the initial global environment and the initial mapping of environment names to
environments. These functions and their names are optional, but they are a design suggestion.

Keep in mind, though, that if we are implementing a full-fledged REPL, we need to keep track of the
ever-changing global environment. Thus, my-eval does not only return the evaluation result of
expr, but it also returns a new global environment; thus my-eval outputs a cons pair where the first
element is the evaluation result and the second element is the new global environment. It’s eval-
prog that loops over the list of S-expressions, evaluating each one while keeping track #lang racket
(define built-in-names ‘(define lambda set! + – * /))

(define (get-global-env)
(let ((global-frame (make-immutable-hash (map (lambda (x) (cons x ‘BUILT-IN-FUNCTION)) built-in-names))))
(cons global-frame 0)))

(define (get-global-env-map)
(make-immutable-hash (list (cons 1 (get-global-env)))))

(define (env-lookup env-map env-id key)
(if (zero? env-id)
(error (string-append “Wasn’t able to find key ”
(symbol->string key)
” in any environment.”))
(let* ((env (hash-ref env-map env-id))
(value (hash-ref (car env) key ‘NOT-FOUND)))
(if (equal? value ‘NOT-FOUND)
(env-lookup env-map (cdr env) key)
value))))

(define (env-add-key-value env-map env-id key value)
(let* ((env (hash-ref env-map env-id))
(frame (car env))
(new-frame (hash-set frame key value))
(new-env (cons new-frame (cdr env))))
(hash-set env-map env-id new-env)))

(define (env-remove env-map env-id)
(hash-remove env-map env-id))

(hash-set (get-global-env-map) 2 (make-empty-env 1))

(define (my-eval expr env-id env-map)
(cond ((number? expr) (cons expr env-map))
((string? expr) (cons expr env-map))
((boolean? expr) (cons expr env-map))
((null? expr) (cons expr env-map))))




Why Choose Us

  • 100% non-plagiarized Papers
  • 24/7 /365 Service Available
  • Affordable Prices
  • Any Paper, Urgency, and Subject
  • Will complete your papers in 6 hours
  • On-time Delivery
  • Money-back and Privacy guarantees
  • Unlimited Amendments upon request
  • Satisfaction guarantee

How it Works

  • Click on the “Place Order” tab at the top menu or “Order Now” icon at the bottom and a new page will appear with an order form to be filled.
  • Fill in your paper’s requirements in the "PAPER DETAILS" section.
  • Fill in your paper’s academic level, deadline, and the required number of pages from the drop-down menus.
  • Click “CREATE ACCOUNT & SIGN IN” to enter your registration details and get an account with us for record-keeping and then, click on “PROCEED TO CHECKOUT” at the bottom of the page.
  • From there, the payment sections will show, follow the guided payment process and your order will be available for our writing team to work on it.