# Homework 6: MiniScheme C, D & E

**Due: Friday, November 8 at 23:59****First Commit: Monday, November 4 at 23:59**

This assignment continues our work on MiniScheme. Specifically, you’ll complete MiniScheme parts C, D, and E. Each part builds a new version of MiniScheme, adding functionality step by step. Each part requires testing. You’ll definitely want to add testing for each part as you’re working on it.

Your implementations will be in several files. The start of each file should be

```
#lang racket
; Your name(s) here.
```

## Preliminaries

Click on the assignment link. A reminder that **new teams are not allowed** for Homework 6. Your teams from Homework 5 have been ported over automatically. You should work in the same manner as Homework 5 (i.e. with the same partner or solo). Please reach out to me if that will be an issue.

### Submission

To submit your homework, you must commit and push to GitHub before the deadline.

Note that apart from a new `HONORCODE.md`

, **there are no starter files for Homework 6**. This is because you will be directly building on your Homework 5 work! So, start by copying all of your `.rkt`

files from Homework 5 into your repository and committing them.

Upon submission, your repository should include the following files:

`parse.rkt`

`parse-tests.rkt`

`interp.rkt`

`interp-tests.rkt`

`env.rkt`

`env-tests.rkt`

`minischeme.rkt`

`HONORCODE.md`

It may also a `.gitignore`

file which tells Git to ignore files matching patterns in your working directory.

Any additional files you have added to your repository should be removed from the `main`

branch. (You’re free to make other branches, if you desire, but make sure `main`

contains the version of the code you want graded.)

Make sure you put your name (and your partner’s name if you’re working with one) as a comment at the top of each file.

## Overview

As a reminder, the version of MiniScheme you built as part of Homework 5 handles numbers and variable mappings. Now it is time to actually support computation!

## Part C: Calls to primitive procedures

Now we can add arithmetic expressions to our MiniScheme implementation. The first step is to handle primitive operators themselves, before we move on to applying them to arguments.

Parsing for operators like `+`

, `-`

, etc. is handled for us already. Why? They are symbols and therefore get parsed to `var-exp`

nodes.

Next our environment needs to associate these symbols to values. There are many ways to do this, but the way we will use will be easy to expand to procedures derived from `lambda`

expressions. We will first make a data type `prim-proc`

to represent primitive procedures. The only data this type needs to carry is the symbol for the operator, so this looks similar to the `var-exp`

type. Make a constructor, a recognizer, and a getter for the data type.

Think about which file should contain this data type definition. Keep in mind that *nothing in the parser needed to change to support these primitive procedures*.

Next, we make a list of the primitive arithmetic operators. Start with the following, but make sure to expand it later on (see below for list primitives, for example):

```
(define primitive-operators '(+ - * /))
```

We can define a primitive operator environment and make our `init-env`

extend that instead of the `empty-env`

.

```
(define prim-env
(env primitive-operators
(map prim-proc primitive-operators)
empty-env))
(define init-env
(env '(x y)
'(23 42)
prim-env))
```

This means that when we evaluate `+`

by looking it up in the environment we will get the structure `'(prim-proc +)`

.

We will now extend the grammar to include applications so we can *use* primitive operators. The grammar for MiniScheme C is:

```
EXP → number parse into lit-exp
| symbol parse into var-exp
| (EXP EXP*) parse into app-exp
```

Finally, a language that can compute! You need to implement an `app-exp`

data type that can hold a procedure (which is itself a tree) and a list of argument expressions (again, these are trees). The constructor for that might be `(app-exp proc args)`

. Update the parser to build an `app-exp`

node when the expression being parsed is a (non-empty) list. Remember that you will need to parse both the operator and the list of operands.

Add tests to `parse-tests`

to test that applications are parsed correctly. Make sure you test parsing applications with different numbers of parameters `(foo)`

, `(bar 1)`

, `(baz x y)`

, etc. Add a test to check that `()`

causes an error (see HW5 for testing errors if you don’t remember how to!).

In the `interp`

module extend `eval-exp`

to evaluate an `app-exp`

node by calling a new procedure `apply-proc`

with the evaluated operator and the list of evaluated arguments. Here is `apply-proc`

:

```
(define (apply-proc proc args)
(cond [(prim-proc? proc)
(apply-primitive-op (prim-proc-op proc) args)]
[else (error 'apply-proc "bad procedure: ~s" proc)]))
```

The `apply-primitive-op`

procedure takes a symbol corresponding to the primitive procedure and a list of argument values. Here is the start of one possible `apply-primitive-op`

:

```
(define (apply-primitive-op op args)
(cond [(eq? op '+) (apply + args)]
...
handle '-, '+, '*, '/
...
[else (error 'apply-primitive-op "Unknown primitive: ~s" op)]))
```

Our language should now be able to evaluate calls to primitive operators, such as `(+ 2 4)`

or `(+ x y)`

.

Next extend MiniScheme C to handle to following primitive procedures:

`add1`

`sub1`

`negate`

-`(negate 6)`

is`-6`

and`(negate (negate 6))`

is`6`

`list`

`cons`

`car`

`cdr`

Remember this is Mini*Scheme*, so there is no `first`

and `rest`

. Make sure to also add a new symbol `'null`

bound to the empty list to the initial environment.

Add tests to `interp-tests`

to test evaluating some of your primitive procedures. Make sure you specify your tests in terms of `app-exp`

, `var-exp`

, and `lit-exp`

.

Our methodology should now be pretty clear. At each step, we have a new line in the grammar to handle a new kind of Scheme expression. We update the parser, which requires making a new tree data type to handle the new parsed expression. We then update the `eval-exp`

procedure to evaluate the new tree node. For the remaining steps, the instructions will assume that you are comfortable with this methodology, so please ask questions if not!

## Part D: Conditionals

Let’s update our language to include conditional evaluation. We will adopt the convention that 0 and `False`

represent false, and everything else represents true. Note that `#t`

and `#f`

are not values in MiniScheme. You should assign the value `'True`

and `'False`

to the symbols `'True`

and `'False`

. True expressions, such as `(eqv? 2 (+ 1 1))`

should evaluate to `True`

, not to `#t`

(Note that we will use `eqv?`

as our equality operator in MinScheme and it should be implemented using `eqv?`

in Racket).

This is the grammar for MiniScheme D:

```
EXP → number parse into lit-exp
| symbol parse into var-exp
| (if EXP EXP EXP) parse into ite-exp
| (EXP EXP*) parse into app-exp
```

Now implement both parsing and interpretation for if-expressions. You will need to add `False`

and `True`

to the initial environment as described above. The meaning of `(if foo bar buzz)`

is just what you’d expect: If `foo`

evaluates to `False`

or `0`

, then the value of the if-then-else expression is obtained by evaluating `buzz`

; otherwise, the value is obtained by evaluating `bar`

.

You need to make a new data type (maybe called `ite-exp`

) and update the parser in `parse.rkt`

, and update the `eval-exp`

procedure in `interp.rkt`

. For the parser, note that both if expressions and application expressions are lists. We know a list represents an if-expression if its first element is the symbol `'if`

. Put the test for this in the inner `cond`

after the test for an empty list. We will assume a list represents an application expression if we don’t recognize its first element as a special form. So far, `if`

is our only special form. Later parts will have more special forms.

Now extend MiniScheme D to implement the primitives `eqv?`

, `lt?`

, `gt?`

, `leq?`

and `geq?`

where `eqv?`

behaves like Scheme’s `eqv?`

and `lt?`

, `gt?`

, `leq?`

, and `geq?`

behave like the usual inequality operators `<`

, `>`

, `<=`

, and `>=`

. Each of these should return `'True`

or `'False`

and not `#t`

or `#f`

.

Add primitive procedures `null?`

, `list?`

, and `number?`

which behave like their Scheme counterparts, but return `True`

or `False`

rather than `#t`

or `#f`

.

Make sure to *add tests* for the parser and interpreter and commit your code once you’re finished.

## Part E: Let expressions

The grammar for MiniScheme E is

```
EXP → number parse into lit-exp
| symbol parse into var-exp
| (if EXP EXP EXP) parse into ite-exp
| (let (LET-BINDINGS) EXP) parse into let-exp
| (EXP EXP*) parse into app-exp
LET-BINDINGS → LET-BINDING*
LET-BINDING → [symbol EXP]
```

As you can see, we have added new clause for the `let`

expression. To make `eval-exp`

clearer, I suggest that you make a `let-exp`

data type that contains three children:

- A list of the symbols that are bound in the binding list
- A list of the parsed expressions (i.e., trees) that the symbols are bound to
- The
`let`

body.

Thus, although we have grammar symbols for `LET-BINDING`

and `LET-BINDINGS`

, we choose to build the tree slightly differently.

After the parser is extended to handle `let`

expressions, extend `eval-exp`

to handle the `let-exp`

nodes created by the parser. The general approach is to evaluate a `let-exp`

node in an environment by extending the environment with the let symbols bound to the values of the `let`

bindings (`map`

a curried version of `eval-exp`

onto the binding expressions), and then evaluate the let body within this extended environment.

When you are finished you should be able to evaluate expressions such as

```
(let ([a 1]
[b 5])
(+ a b))
```

and

```
(let ([a (* 2 3)]
[b 24])
(let ([c (- b a)])
(* c (+ a b))))
```

Make sure to add parser and interpreter tests. Once you’ve done that, you’re all done with parts A through E of MiniScheme!

## Notes on Testing

Please don’t write tests like this below, if you can help it:

```
(test-equal? "Apply (- 23 3)"
(eval-exp (parse '(- 23 3)) test-env)
20)
```

Rather:

- Test
`parse`

by giving it a structured list (i.e. a MiniScheme expression) - Test
`eval-exp`

by giving it a parse tree you write yourself

**Why?** It’s easy to make mistakes in `parse`

that would then carry over to your `eval-exp`

tests.

An example (good) test for `eval-exp`

for MiniScheme C is below:

```
(test-equal? "Apply (- 23 3)"
(eval-exp (app-exp (var-exp '-)
(list (lit-exp 23)
(lit-exp 3)))
test-env)
20)
```

## Finishing up

Make sure you (and your partner, if you have one!) have signed the Honor Code and then add/commit/push. Also make sure your name(s) is in all of the files you submit. Your friendly graders thank you!