Scheme evaluator

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 of updates to the global environment. Remember, we will not be using mutation in this program. The challenge of implementing an interpreter in functional programming style is not using mutation for updating our environments.

Part 1: Evaluating Primitive Types (20% of maximum points) Your first milestone is to make sure that you can evaluate very simple expressions that are not function calls or are not syntactic sugar of function calls (e.g., ‘(1 2 3) is syntactic sugar for (cons 1 (cons 2 (cons 3 ()))), which is a function call). For example, (my-eval ‘5 ‘() ‘()) should return the cons cell ‘(5 . ()), which happens to be the list ‘(5) (but see the “Return Values” section later in this document; this example is to illustrate that the correct environment has been returned, but the data structure choice is up to you; I don’t want to add undue restrictions). The same applies to boolean values #t and #f. If the expression that you are evaluating is a symbol, perform an environmental lookup. If the symbol resolves to an expression, return the value of that expression. If the symbol resolves to a built-in function, then return ‘BUILT-IN-FUNCTION.

Part 2: Primitive Functions (80% of maximum points) Your task is to implement all of the primitive functions listed in Appendix A. Here are the weights of the following implementations:

Function/Function Class Percentage of Maximum Points define 10% lambda 10% set! 10% cons, car, cdr 10% if 5% quote 5% +, -, *, /, remainder, modulo, and, or

7.5%

eq?, equal?, =, >, <, >=, <=, =, empty?, number?, pair?, symbol?

7.5%

The ability to call functions, whether built-in or program- defined.

15%

Once the above has been implemented, we can run Scheme programs such as the following:

(define (even? n) (= (remainder n 2) 0)) (even 10)

(define (length elems) (if (empty? elems) 0 (+ 1 (length (cdr elems))))) (length (cons 1 (cons 3 (cons 5 (quote ())))))

Return Values • my-eval has no specific requirements regarding return values since it is based on your

implementation of env and env-map. Your code should return a data structure that contains the evaluated expression and the updated environment and/or environment mapping information.

• eval-prog returns the evaluation of the final S-expression in the S-expression list. For example, if I run

(eval-prog ‘((define x 10) (set! x (+ 2 3)) (* x x)))

it should return 25 as its answer.

Grading Nodes • If your code does not run due to syntactic errors, then that relevant portion of the code gets a

zero grade. • Your functions my-eval and eval-prog must have the parameters in the exact order as

specified; do not change the number of parameters or their order, or they won’t get graded. • Your submission must be a single file called my-scheme.rkt. Do not split your work into

separate files. • Mutation is banned, even when implementing set! in your interpreter. If you use set!, set-

car!, set-cdr!, or any other function that uses mutation, then that code gets a zero grade. • Do not use Scheme’s eval function to implement any portion of this assignment, or you won’t

get credit for those portions.

Tips • Feel free to use Sections 3.2 and 4.1 of Structure and Interpretation of Computer Programs,

which discusses how environments work and how a basic Scheme interpreter works. It is okay to use this reference. Please keep in mind that your environment will not use mutation, whereas in the textbook the environment it uses is modified using mutation.

• I am also okay with you using Peter Norvig’s Java (https://norvig.com/jscheme.html) and Python (https://norvig.com/lispy.html) implementations of Scheme interpreters as a reference. Once again, these implementations have the same caveat as the one in SICP.

• For the curious who is really interested in learning more about the history of Lisp, I highly recommend taking a read of the first 13 pages of The LISP 1.5 Programmer’s Manual (http://www.softwarepreservation.org/projects/LISP/book/LISP%201.5%20Programmers %20Manual.pdf). Page 13 has a description of a basic LISP 1.5 interpreter, which Alan Kay calls “the Maxwell equations of software.” Please keep two things in mind: ◦ LISP 1.5 is a very early version of Lisp from 1962 that has different semantics from Scheme

(particularly when it comes to variable scoping) or from other modern Lisps such as Common Lisp and Clojure.

◦ The syntax of page 13 is not our familiar S-expressions, but an earlier syntax known as M- expressions. It turns out that when John McCarthy created Lisp in the late 1950s, he originally meant to have Lisp implemented using M-expressions; S-expressions were originally meant as primitive representations of Lisp expressions. However, when one of his students read his paper and implemented Lisp, he used S-expressions. The other researchers in McCarthy’s lab also wrote their Lisp programs in S-expressions, and S- expressions ultimately became the canonical way of writing Lisp programs. However, there have been attempts at making Lisp-style languages that don’t use S-expressions; in the 1990s Apple worked on an object-oriented Lisp called Dylan which syntax resembles contemporary procedural programming languages.

• Please don’t refer to any other Scheme or Lisp interpretations, however.

Appendix A: Scheme Primitive Functions

Name Usage Definition define (define name expr)

(define (function-name x1 … xN) body)

If the second element is a symbol, then evaluates expr and assigns it to name in the current environment. If the second element is a list, then this is syntactic sugar for (define function- name (lambda (x1 … xN) body))

lambda (lambda (x1 … xN) body) Creates an anonymous function that evaluates body with parameters x1 to xN, or with no parameters. Note that body can consist of multiple expressions expr1 to exprM. The result of body is the value of the final expression exprM.

set! (set! name expr) Evaluates expr and modifies the value stored at name to be the evaluated result of expr.

cons (cons expr1 expr2) Creates a cons cell where the first element contains the evaluated result of expr1 and the second element contains the evaluated result of expr2.

car (car expr) Returns the first element of the cons cell expr1. If expr does not evaluate to a cons cell, then return an error.

cdr (cdr expr) Returns the second element of the cons cell expr1. If expr does not evaluate to a cons cell, then return an error.

quote (quote expr) Returns expr without evaluating it. + (+ x1 … xN) Performs the sum x1 + … + xN. If there is only

one argument x1, it returns x1. - (- x1 … xN) Performs the repeated difference x1 - … - xN. If

there is only one argument x1, then it negates it. * (* x1 … xN) Performs the product x1 * … * xN. If there is only

one argument x1, it returns x1. / (/ x1 … xN) Performs the repeated division x1 / … / xN. If

there is only one argument x1, it returns 1 divided by x1. Returns an error if any of the parameters evaluate to 0.

remainder (remainder x y) Returns the remainder of the division x divided by y.

modulo (modulo x y) Returns the modulo of the division x divided by y. There is a nuance between remainder and modulo that is important when dealing with negative numbers.

and (and x1 … xN) Performs x1 ˄ … ˄ xN. Returns #f at the first occurrence of a parameter that evaluates to #f.

or (or x1 … xN) Performs x1 ˅ … ˅ xN. Returns #t at the first occurrence of a parameter that evaluates to #t.

if (if expr1 expr2 expr3) If expr1 evaluates to #t, then evaluate expr2 and return it. Otherwise evaluate expr3 and return it.

= (= expr1 expr2) If expr1 and expr2 both evaluate to numbers, then this function checks to see if they are equal. Returns #t if equal, #f otherwise. Returns an error if expr1 or expr2 don’t evaluate to numbers.

> (> expr1 expr2) If expr1 and expr2 both evaluate to numbers, then this function checks to see if expr1 > expr2. Returns #t if equal, #f otherwise. Returns an error if expr1 or expr2 don’t evaluate to numbers.

< (< expr1 expr2) If expr1 and expr2 both evaluate to numbers, then this function checks to see if expr1 < expr2. Returns #t if equal, #f otherwise. Returns an error if expr1 or expr2 don’t evaluate to numbers.

>= (>= expr1 expr2) If expr1 and expr2 both evaluate to numbers, then this function checks to see if expr1 >= expr2. Returns #t if equal, #f otherwise. Returns an error if expr1 or expr2 don’t evaluate to numbers.

<= (<= expr1 expr2) If expr1 and expr2 both evaluate to numbers, then this function checks to see if expr1 <= expr2. Returns #t if equal, #f otherwise. Returns an error if expr1 or expr2 don’t evaluate to numbers.

eq? (eq? expr1 expr2) Evaluates the expr1 and expr2 and checks if they both evaluate to symbols of the same name. Note that symbols are case-sensitive. Returns #t if they do, #f otherwise.

equal? (equal? expr1 expr2) Encompasses = and eq? for numbers and symbols, respectively, and also checks cons cells for equality.

empty? (empty? expr) Returns #t if expr evaluates to the empty list, #f otherwise.

number? (number? expr) Returns #t if expr evaluates to a number, #f otherwise.

pair? (pair? expr) Returns #t if expr evaluates to a cons cell, #f otherwise.

symbol? (symbol? expr) Returns #t if expr evaluates to a symbol, #f otherwise. Note that the Boolean constants #t and #f are not considered symbols, but rather constants of the Boolean type.