►Fall 2026:
Programming Languages
►Assignments
▼Implementation
►1 Interpreter
On this page:
1.1 Introduction
1.2 Assignment
1.3 Grammar
1.4 Abstract Syntax
1.5 Features to Implement
1.5.1 Environment
1.5.2 Binary Operators
1.5.3 Conditionals
1.5.4 Functions
1.5.5 Errors
1.6 Testing
1.6.1 Debugging
1.7 Starter Code
1.8 What To Hand In
    contents    up   

CSCI 1730 · Fall 2026

1 Interpreter🔗

    1.1 Introduction

    1.2 Assignment

    1.3 Grammar

    1.4 Abstract Syntax

    1.5 Features to Implement

      1.5.1 Environment

      1.5.2 Binary Operators

      1.5.3 Conditionals

      1.5.4 Functions

      1.5.5 Errors

    1.6 Testing

      1.6.1 Debugging

    1.7 Starter Code

    1.8 What To Hand In

1.1 Introduction🔗

For this assignment, you will write an interpreter for Core Paret, the core of the Paret (“pared-down Pyret”) language that runs through this thread.

1.2 Assignment🔗

We have provided a module, paret_core.rhm, that defines the language: its abstract syntax Expr, the values Value that programs produce, and a parser

parse :: Sexp -> Expr

parse_str :: String -> Expr

that consumes a program in Core Paret’s concrete syntax, as an S-expression or as a string containing one, and produces its abstract syntax. parse accepts only programs that follow the Grammar.

You will implement one function:

interp :: Expr -> Value

which consumes the abstract syntax of a closed program, one with no free variables, and returns the Value it evaluates to. Since interp takes no environment, you will write a helper that does, and interp will call it with the empty environment.

interp should evaluate programs by performing a post-order traversal of the abstract syntax tree: 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 tree.

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.

1.3 Grammar🔗

<expr> ::= <num>

         | <string>

         | <var>                        # variable (a.k.a. identifier)

         | true

         | false

         | (+ <expr> <expr>)

         | (++ <expr> <expr>)

         | (num= <expr> <expr>)

         | (str= <expr> <expr>)

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

         | (lam <var> <expr>)           # anonymous function

         | (<expr> <expr>)              # function application

Numbers are integers. The keywords (lam, if, the four operators, true and false) cannot be used as variables.

1.4 Abstract Syntax🔗

type Op

| op_plus()

| op_append()

| op_num_eq()

| op_str_eq()

 

type Expr

| e_num(n :: Int)

| e_str(s :: String)

| e_bool(b :: Boolean)

| e_op(op :: Op, left :: Expr, right :: Expr)

| e_if(cnd :: Expr, thn :: Expr, els :: Expr)

| e_lam(param :: Symbol, body :: Expr)

| e_app(fn :: Expr, arg :: Expr)

| e_var(name :: Symbol)

 

type Value

| v_num(n :: Int)

| v_str(s :: String)

| v_bool(b :: Boolean)

| v_fun(param :: Symbol, body :: Expr, env :: Env)

 

type Env = Mapof(Symbol, Value)

1.5 Features to Implement🔗
1.5.1 Environment🔗

Your interpreter should use an environment, Env, to keep track of the Values of variables in scope. Env is a Mapof, so you can use Shplait’s map functions on it: map_get, which returns an Optionof, and map_update, which produces a new map.

Notice that map_update does not change the map it is given; it returns a new one. That is the point. What would go wrong if environments were mutable, so that binding a variable changed the environment for everyone holding it? Shplait has MutableMap and map_set: try them 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 variable shadowing: if you bind a variable 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 variable, raise an error (see Errors).

1.5.2 Binary Operators🔗

Paret includes binary addition (+) and number equality testing (num=), as well as string appending (++) and string equality testing (str=). Rather than a separate syntactic form for each, parse produces a single variant, e_op, which names the operation with an Op.

Implement them with Shplait’s +, string_append, and == on numbers and on strings. Raise an error (see Errors) for non-numeric values passed to + and num=, and for non-string values passed to ++ and str=; for example,

(+ true "string")

1.5.3 Conditionals🔗

An if expression has three parts:

  • the condition, which should evaluate to a Boolean Value;

  • the “then” branch, which is evaluated if the condition evaluated to true;

  • the “else” branch, which is evaluated if the condition evaluated to false.

if short-circuits: only the relevant branch is evaluated. If the condition evaluates to a non-Boolean Value, raise an error (see Errors). The two branches need not produce the same kind of value.

1.5.4 Functions🔗

Functions in Paret are unary (they take exactly one argument). Here are two examples of functions and their applications:

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

 

((lam y 5) 1)

These should both evaluate to 5.

Functions are closures: a function value records the environment in which it was created, and its body is evaluated in that environment, extended with the argument. It is possible that when attempting to perform a function application, the value in the function position isn’t actually a function; for example, (1 2). Raise an error in this case as well (see Errors).

1.5.5 Errors🔗

Some examples of expressions that should raise errors are:

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

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

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

Raise errors with Shplait’s error, always with the symbol #’interp, and a message that says what went wrong:

error(#'interp, "unbound variable: " +& to_string(name))

Shplait converts the symbol to text at the front of the error message, so this error’s message is interp: unbound variable: x, and tests recognize an interpreter error by matching the string "interp" (see the Testing Guidelines). The rest of the message is for you, when debugging.

1.6 Testing🔗

This is the first assignment whose tests we grade. Read the Testing Guidelines before you write any: they explain how your tests are run against our correct and incorrect implementations, and the rules that follow from that.

Your tests go in interpreter_tests.rhm, and every test goes through interp applied to a parsed program:

check:

  interp(parse_str("((lam x (+ x 3)) 2)"))

  ~is v_num(5)

 

check:

  interp(parse_str("(1 2)"))

  ~raises "interp"

 

check:

  interp(parse_str("(lam x 5)")) is_a v_fun

  ~is #true

Test errors by their symbol’s name only, and closures by their kind only, for the reasons given in the guidelines.

1.6.1 Debugging🔗

You may find it useful to use Shplait’s trace to help understand the control flow of your interpreter. If your environment-taking helper is called interp_env, then

trace interp_env:

  interp(parse_str("((lam x (+ x 3)) 2)"))

evaluates the program and prints every call to interp_env, including recursive calls, with its arguments and result. Do not include trace in your final submission.

1.7 Starter Code🔗

You will be provided with:

1.8 What To Hand In🔗

You will submit to two Gradescope drops for this assignment:

  • interpreter.rhm, which should be uploaded to the “Code” drop.

  • interpreter_tests.rhm, which should be uploaded to the “Tests” drop.

    contents    up