Homework 6: MiniScheme C, D & E

Due: Friday, November 1 at 23:59
First Commit: Monday, October 28 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:

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:

Remember this is MiniScheme, 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:

  1. A list of the symbols that are bound in the binding list
  2. A list of the parsed expressions (i.e., trees) that the symbols are bound to
  3. 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:

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!