On this page:
1.1 Introduction
1.2 Reading
1.3 Assignment
1.3.1 Errors
1.4 Features to Implement
1.4.1 Desugaring
1.4.1.1 and and or
1.4.1.2 let
1.4.2 Environment
1.4.3 Binary Operators
1.4.4 Conditionals
1.4.5 Functions
1.5 Grammar
1.5.1 Abstract Syntax
1.6 Testing
1.6.1 How We Test Tests
1.6.2 Guidelines for Testing Your Interpreter
1.6.3 Debugging
1.7 Starter Code
1.8 What To Hand In
1 Interpreter

    1.1 Introduction

    1.2 Reading

    1.3 Assignment

      1.3.1 Errors

    1.4 Features to Implement

      1.4.1 Desugaring

        1.4.1.1 and and or

        1.4.1.2 let

      1.4.2 Environment

      1.4.3 Binary Operators

      1.4.4 Conditionals

      1.4.5 Functions

    1.5 Grammar

      1.5.1 Abstract Syntax

    1.6 Testing

      1.6.1 How We Test Tests

      1.6.2 Guidelines for Testing Your Interpreter

      1.6.3 Debugging

    1.7 Starter Code

    1.8 What To Hand In

1.1 Introduction

For this assignment, you will write an interpreter for the Paret language (“pared-down Pyret”) described below.

1.2 Reading

Please read chapters 2—7 of PLAI 2/e.

1.3 Assignment

We have provided a function parse which consumes an expression in the Paret language’s concrete syntax, S-Exp, and returns the abstract syntax representation of that expression (an Expr).

parse :: S-Exp -> Expr

parse only accepts expressions that follow Paret’s grammar.
You will implement two functions: desugar and interp.
  • desugar :: Expr -> Expr
    which consumes an abstract syntax tree (i.e. an Expr, as returned by parse), replaces all instances of syntactic sugar (described below) with desugared equivalents, and returns the result.

  • interp :: Expr -> Value
    which consumes a desugared abstract syntax tree (i.e. the Expr returned by desugar) and returns a Paret Value.
    interp should assume that it’s given an Expr from desugar. If interp is given an Expr containing a sugar-* form, its behavior is undefined.
    Finally, interp should evaluate programs by performing a post-order traversal of the abstract syntax tree (AST): first, evaluate all of the children of an expression from left to right, then evaluate the expression itself. This makes it unambiguous which error to raise if there are multiple errors in the AST.

    Why evaluate our expressions from left to right? One might say we’ve chosen this as a matter of convention, but ultimately the choice is completely arbitrary. Strictly speaking, we could define our language to evaluate sub-expressions from right to left and that would be just fine. What’s important is that an explicit evaluation order choice is made so the language has clearly defined semantics.

Once you have implemented desugar and interp, you should use the provided eval function (which wraps around those two functions and parse) to write test cases for your interpreter.

1.3.1 Errors

We have provided a function raise-error for throwing errors, as well as a type InterpError, which contains all the error cases that your interpreter might run into:

(define-type InterpError

  (err-if-got-non-boolean [val : Value])

  (err-bad-arg-to-op [op : Operator]

                     [val : Value])

  (err-unbound-id [name : Symbol])

  (err-not-a-function [val : Value]))

You can throw an error by using raise-error and providing the correct InterpError. For example:

(raise-error (err-bad-arg-to-op (op-plus) (v-str "str")))

Pay careful attention to how interp’s evaluation order specification impacts which errors are thrown. For example,

(str= (+ 5 "bad") "hello")

(++ false (+ "bad" 6))

("not function" (+ 7 "bad"))

should all raise (err-bad-arg-to-op (op-plus) (v-str "bad")).

1.4 Features to Implement
1.4.1 Desugaring

Racket macros, which you’ll write later in the course, are themselves syntactic sugar. However, we are not asking you to use Racket macros for anything in this assignment.

As described previously, Paret contains several forms of syntactic sugar: and, or, and let. desugar should convert sugar-and, sugar-or, and sugar-let Exprs into functionally equivalent, non-sugar Exprs.
There are multiple implementation strategies for desugar. Be sure to test it well: it’s easy to miss some details when desugaring, especially in regards to evaluation order!

1.4.1.1 and and or

  • and consumes two boolean expressions. It evaluates to true if both boolean expressions are true; otherwise, it evaluates to false.

  • or consumes two boolean expressions. It evaluates to true if at least one boolean expression is true; otherwise, it evaluates to false.

desugar should convert sugar-and and sugar-or Exprs in such a way that, when interp interprets the desugared code, and and or short-circuit. In and expressions, this means that if the first argument of and evaluates to false, the second argument to and is not evaluated and the and expression evaluates to false. (Similarly, if the first argument of or evaluates to true, the second argument to or should not be evaluated.) Thus, the second argument of a short-circuited expression should never throw an error.

1.4.1.2 let

let should accept a single identifier-value pair and a body. let evaluates the value, binds it to id, and evaluates the body with the newly bound identifier in scope. For example, the following should evaluate to 3:

(let (x 1) (+ x 2))

let should disallow recursive definitions. That is, in (let (<id> <expr>) <body>), <id> should be bound in <body> but not in <expr>.

The desugaring of sugar-let may not be obvious, so here’s a hint: What Expr(s) allow us to extend the identifiers bound within a given environment? And how would we make that type of Expr actually do that?

1.4.2 Environment

Your interpreter should use an environment, Env, to keep track of the Values of identifiers in scope.
(define-type-alias Env (Hashof Symbol Value))
Since Env is a Hashof, you can use Plait’s built-in hash table functions on your Env.

For your environment, make sure you use hash, which creates immutable hash tables! What happens if you use make-hash, which creates mutable hash tables instead? Try replacing one with the other and see. If none of your tests fail, you aren’t testing enough! You should have at least one failing test, if not several, when you make this switch.

interp should allow identifier shadowing, meaning that if you bind an identifier that is already bound, the new binding takes precedence. When in doubt, your interpreter should behave just as SMoL would.
When interp encounters an unbound identifier, interp should raise the err-unbound-id exception with the name of the identifier.

1.4.3 Binary Operators

Paret includes binary addition (+) and number equality testing (num=), as well as string appending (++) and string equality testing (str=).
In place of having separate syntactic forms for each of +, num=, ++, and str=, parse converts these operators into a single AST datatype variant, e-op, which denotes the operation to use via an Operator variant:

(define-type Operator

  (op-plus)

  (op-append)

  (op-str-eq)

  (op-num-eq))

When you implement these operators, you should use Plait’s + for op-plus, string-append for op-str-eq, string=? for op-str-eq, and = for op-num-eq.
Evaluation should raise a err-bad-arg-to-op error for non-numeric values passed to + and num= operations, and for non-string values passed to ++ and str= operations. The op part of the error is the Operator that was called, and val is the Value it was given that had the wrong type. Argument types to Operators should be checked from left to right. For example,

(+ true "string")

should raise (err-bad-arg-to-op op-plus (v-bool true)).
In line with interp’s evaluation order specification, err-bad-arg-to-op should only be raised after evaluating the arguments to the operator.

1.4.4 Conditionals

if-expressions in Paret have three parts:
  • cond, which should evaluate to a Boolean Value

  • consq, which evaluates if cond evaluated to true

  • altern, which evaluates if cond evaluated to false

if statements should short-circuit (i.e. only evaluate the relevant branch). If cond evaluates to a non-Boolean Value, an err-if-got-non-boolean error should be raised with val being the offending Value.

1.4.5 Functions

Functions in Paret are unary (i.e. they take exactly 1 argument). Here’s two examples of functions and their applications:

((lam x (+ x 3)) 2)

 

((lam y 5) 1)

These should both evaluate to 5.

It’s possible that when attempting to perform a function application, the value in the function position isn’t actually a function; e.g., you might have (1 2). In this case you should raise a err-not-a-function exception, where val is the value that was applied; e.g., 1.
In line with interp’s evaluation order specification, err-not-a-function should only be raised after evaluating the function-position expression and its argument.

1.5 Grammar

The grammar of Paret is as follows:

<expr> ::= <num>

         | <string>

         | <id>

         | true

         | false

         | (+ <expr> <expr>)

         | (++ <expr> <expr>)

         | (num= <expr> <expr>)

         | (str= <expr> <expr>)

         | (if <expr> <expr> <expr>)

         | (and <expr> <expr>)

         | (or <expr> <expr>)

         | (let (<id> <expr>) <expr>)

         | (lam <id> <expr>)

         | (<expr> <expr>)

where <id> is an identifier (i.e., variable), lam defines anonmyous functions, and (<expr> <expr>) is a function application.

1.5.1 Abstract Syntax

Refer to Environment for the definition of Env and Binary Operators for the definition of Operator.

(define-type Value

  (v-num [value : Number])

  (v-str [value : String])

  (v-bool [value : Boolean])

  (v-fun [param : Symbol]

         [body : Expr]

         [env : Env]))

 

(define-type Expr

  (e-num [value : Number])

  (e-str [value : String])

  (e-bool [value : Boolean])

  (e-op [op : Operator]

        [left : Expr]

        [right : Expr])

  (e-if [cond : Expr]

        [consq : Expr]

        [altern : Expr])

  (e-lam [param : Symbol]

         [body : Expr])

  (e-app [func : Expr]

         [arg : Expr])

  (e-id [name : Symbol])

  (sugar-and [left : Expr]

             [right : Expr])

  (sugar-or [left : Expr]

            [right : Expr])

  (sugar-let [id : Symbol]

             [value : Expr]

             [body : Expr]))

1.6 Testing

We care that you test programs well. Programming langauge implementations are expected to be rock-solid (when’s the last time you ran into an implementation bug?). You need to uphold this standard.

This isn’t a course in something like AI, where we don’t even know what the right answer might be!

In addition to the quality and correctness of your code, you will be evaluated on the quality and correctness of your tests.

1.6.1 How We Test Tests

It’s probably useful for you to understand how we test your tests.
What’s the job of a test suite (i.e., set of tests)? It’s to find errors in a program. (Examples help you understand the problem before you start writing code, tests help you catch errors in the program as and after you write it.) In short, test suites are like sorting hats, putting programs in a “good” or “bad” bin.

If you are a mathy person, you might call a test suite a classifier.

So, here’s how we will test your test suites. We construct a collection of implementations for the problem. One is known to be correct (because we built it that way); we call this a wheat. The rest are known to be incorrect (because we intentionally introduce errors); we call each of these a chaff. Your test suite’s job is to separate the wheat from the chaff. That is, we will run the wheat and each of the chaffs against your test suite and see what happens:

                   | On a wheat… | On a chaff… |

------------------------------------------------

…all tests passed  |    GREAT!   |  Not great… |

…some tests failed |    Ooops!   |    GREAT!   |

All tests passing a wheat, and at least one test failing on a chaff, is exactly what we are hoping for. If all tests pass on a chaff, that’s not ideal, but you may miss some chaffs, so it may be okay. But when any tests fail on a wheat, that’s definitely a problem because it should never happen. It quite likely means you’ve misunderstood the problem statement, or perhaps the problem statement is ambiguous, or something like that. This should get cleared up right away.
The quality of your test suite is then a measure of whether you passed the wheat and how many chaffs you caught. Of course, we can make the latter arbitrarily hard. For instance, we could define a chaff that always works correctly except when the given list has, say, exactly 1729 elements. We won’t do things like that, both because it’s cruel and because real implementations are very rarely buggy in this way. Instead, we will make “reasonable” mistakes (but not all of them will be easy!).
In short, we will be running your test suite against our implementations. Therefore, it is very important that when you turn in your test suite (see details below), it not be accompanied by your implementation: otherwise, when we try to load ours, DrRacket will complain.

1.6.2 Guidelines for Testing Your Interpreter

Please read the Testing Guidelines for guidelines on how to write tests for the Implementation assignments.

For the purposes of testing, we have defined an eval function that calls parse, desugar, and interp for you. eval consumes a program in the Paret language’s concrete syntax (S-Exp) and returns a Paret Value:

eval :: S-Exp -> Value

You should use eval in your testing file when writing test cases. You should not directly test desugar and interp individually in your test file (though you are welcome to and encouraged to individually test these functions in your code file). There’s good reason for this: there is more than one correct desugaring, so any tests you write may be implementation-specific. (And, of course, your submitted test cases should indirectly test desugaring, because you should test that and and or let work correctly.)
In addition to the testing forms documented in the Testing Guidelines, we provide the following testing form:
  • (test-raises-interp-error? name expr interp-error)
    Tests that the given expr raises the given interp-error. (Example usage can be found in the testing stencil.)

Finally, recall that programs can evaluate to functions. However, you may have chosen a different representation for closures than we did. Therefore, your tests in your test file should only check that such a program returned a function, and not rely on the specific function returned (because of the differences in representation). For instance, you may write:

(test-pred "My predicate test"

           v-fun? (eval `{lam x 5}) #t)

Reminder: In Plait, you can add a ? to the end of the name of any given type variant to create a function that returns true if the expression evaluates to that type variant.

However, you may not write:

(test-equal? "Don't write this test"

             (eval `{lam x 5}) (v-fun 'x (e-num 5) (hash (list ))))

because our representation of closures may not match your exact representation. (You are, of course, welcome to write test cases of the latter form in your code file.)

1.6.3 Debugging

You may find it useful to use Plait’s trace to help understand the control flow of your interpreter. For instance, if you write

(trace interp)

then all subsequent calls (including—and especially—recursive calls) to interp will be presented with their arguments and results. Please do not include calls to trace in your final submissions.

1.7 Starter Code

We’ve provided starter code for your implementation at interpreter.rkt and support code at support.rkt. You are not allowed to change the signature of eval, desugar, and interp, but you are welcome to add any helper functions that you need for your implementation.
We’ve also provided a stencil for your eval test cases at interpreter-tests.rkt and testing support code at test-support.rkt. You should check that you can run your interpreter-tests.rkt file successfully in DrRacket before submitting—if you can’t, it means that a definition is missing or you’re trying to test a function that you shouldn’t be testing (e.g. a helper function or interp or desugar directly).
Do not modify the contents of support.rkt and test-support.rkt.

1.8 What To Hand In

You will submit two files for this assignment:
  • interpreter.rkt, which should be uploaded to the “Code” drop on Gradescope.

  • interpreter-tests.rkt, which should be uploaded to the “Tests” drop on Gradescope.

You can update your submissions as many times as you want before the deadline.