Homework 8: Interpreters

  • Due: Thursday 11/12 @ 11:59pm
  • Points: 1
  • Download: hw08.zip

Complete your work in src/hw08.gleam, and from inside the folder run your tests with gleam test (or gleam test -- score to see your score).

To receive credit, you must solve each problem and then complete a short checkoff interview about your solution. You may use Preceptor for the interview or come to office hours to be interviewed by a member of the course staff. If the interviews are not working, please still submit your working code on time or request an extension by the deadline. Staff will be doing in-person checkoffs for up to 3 business days after the assignment deadline (including any approved extension). If a checkoff happens more than 3 business days after the regular deadline, staff may ask to confirm your extended deadline via Flextensions. You will submit a Provenance bundle that includes a record of how you used VS Code, including interactions with Preceptor. Please do not use AI tools other than Preceptor for this assignment.

Like Homework 7, this assignment is written in Gleam. From inside the unzipped folder, run one question's tests by naming it after --, run every question with gleam test -- score, or run the whole suite with gleam test:

gleam test -- eval     # just this question
gleam test -- score    # every question, with your score
gleam test             # the whole suite

Read the Test Output

Until you finish every question, gleam test first prints compiler warnings such as warning: Todo found and warning: Unused function argument, one for each part you haven't written yet. These warnings are expected. Your test results appear after all of the warnings, at the bottom of the output. As you finish each question, its warnings go away.

Run Your Gleam Code

The file you're editing ends with a main function, which gleam run calls:

gleam run

Right now, main just prints a message. You can add any Gleam code there you want, including calls to the functions in this assignment.

echo also works inside any other function, so you can print intermediate values while the tests run.

You can also test out Gleam code on the online Gleam Playground.

Required Questions

Evaluating Arithmetic Expressions

An arithmetic expression such as (x * (2 + 3)) is either a variable, an integer, or one of the operators +, -, *, or / applied to two smaller expressions to its left and right. The Expr type has one variant for each of these cases. For example, (x * (2 + 3)) is represented as:

Binary(Mul, Var("x"), Binary(Add, N(2), N(3)))

In this assignment, Binary lists its operator before its left expression. This ordering is consistent with how Gleam's built-in parser and its Glance parser library order their binary-operator expressions.

A variable's name is one letter from a to z. The symbol function returns the symbol for an Operator, and calculate applies an Operator to two integers.

/// The four arithmetic operators: +, -, *, and /.
pub type Operator {
  Add
  Sub
  Mul
  Div
}

/// An expression that can be evaluated.
pub type Expr {
  Var(String)
  N(Int)
  Binary(operator: Operator, left: Expr, right: Expr)
}

/// A variable name must be one letter from a to z.
pub fn is_variable(name: String) -> Bool {
  string.length(name) == 1
  && string.contains("abcdefghijklmnopqrstuvwxyz", name)
}

/// The symbol for each operator.
pub fn symbol(operator: Operator) -> String {
  case operator {
    Add -> "+"
    Sub -> "-"
    Mul -> "*"
    Div -> "/"
  }
}

/// The result of applying an operator to numbers.
pub fn calculate(operator: Operator, a: Int, b: Int) -> Int {
  case operator {
    Add -> a + b
    Sub -> a - b
    Mul -> a * b
    Div -> a / b
  }
}

Q1: Expression to String

Implement to_string, which returns an expression written out as a string. Write every Binary expression in parentheses, with a space on each side of its operator, even when the parentheses wouldn't normally be needed.

assert to_string(Binary(Mul, Var("x"), Binary(Add, N(2), N(3))))
  == "(x * (2 + 3))"
assert to_string(Binary(Add, Binary(Add, N(1), N(2)), Binary(Add, N(3), N(4))))
  == "((1 + 2) + (3 + 4))"

Hints:

  • int.to_string converts an Int to a String.
  • <> joins two strings into a longer string (like + in Python).
  • Use the provided symbol function.
/// An expression written out, with every Binary expression in parentheses.
pub fn to_string(expr: Expr) -> String {
  // YOUR CODE HERE (replace the code below)
  todo
}

gleam test -- to_string

Q2: Evaluate

Implement eval, which returns the value of an expression when its variables are bound to integer values. Its bindings argument is a Dict(String, Int) that holds the bindings from each variable name to its value. Return Ok(value) for the value of the whole expression, or Error(NameNotFound(name)) if the expression has a variable name that isn't in bindings.

let bindings = dict.from_list([#("x", 3)])
assert eval(Binary(Mul, Var("x"), Binary(Add, N(2), N(3))), bindings) == Ok(15)
assert eval(Binary(Add, Var("x"), Var("y")), bindings)
  == Error(NameNotFound("y"))

The Binary case is started for you: it evaluates both operands and matches the two results at once. If either is an error, so is the whole expression.

Hints:

  • dict.get returns Ok(value) for a bound name and Error(Nil) for any other.
  • Use the provided calculate function to perform arithmetic.
  • Add cases for both the N and Var variants.
pub type EvalError {
  NameNotFound(String)
  // WrongArgumentCount is used later in Q4: apply
  WrongArgumentCount(want: Int, got: Int)
}

/// The value of `expr` when each variable has the value it is bound to in
/// `bindings`, or `NameNotFound(name)` for a variable that isn't bound.
pub fn eval(expr: Expr, bindings: Dict(String, Int)) -> Result(Int, EvalError) {
  case expr {
    Binary(operator, left, right) ->
      case eval(left, bindings), eval(right, bindings) {
        // YOUR CODE HERE (replace the code below)
        Ok(a), Ok(b) -> todo
        Error(e), _ | _, Error(e) -> Error(e)
      }
    // YOUR CODE HERE (replace the code below)
    _ -> todo
  }
}

gleam test -- eval

Q3: Making Functions

A function such as fn(x, y) { 2 * y - x } has a list of formal parameters (x and y) and a body expression (2 * y - x), which a UserFn holds. The make_fn function makes a UserFn only if the function is valid: no parameter is repeated, and every variable in the body is one of the parameters. Otherwise, it returns an FnError that lists the names involved.

assert make_fn(["x", "y"], Binary(Add, Var("y"), Var("x")))
  == Ok(UserFn(["x", "y"], Binary(Add, Var("y"), Var("x"))))
assert make_fn(["x", "x"], Var("x")) == Error(DuplicateParameterNames(["x"]))
assert make_fn(["x"], Binary(Add, Var("x"), Var("y")))
  == Error(VariablesNotBound(["y"]))

Implement the two functions that make_fn calls: find_duplicates, which returns every name that appears in a list more than once, and find_unbound, which returns every variable in an expression that is not one of the parameters. Either may list a name more than once, since make_fn removes the repeats. Then finish make_fn by returning the UserFn it makes when neither function finds any names.

Hint: list.contains(names, name) is True when name is in names, and list.append joins two lists.

/// A function: a list of formal parameters and a body expression.
pub type UserFn {
  UserFn(params: List(String), body: Expr)
}

pub type FnError {
  DuplicateParameterNames(List(String))
  VariablesNotBound(List(String))
}

/// A function with formal parameters `params` and a `body` expression, or an
/// error if a parameter is repeated or the body has a variable that is not a
/// parameter. Each error lists the names involved, without repeats.
pub fn make_fn(params: List(String), body: Expr) -> Result(UserFn, FnError) {
  assert list.all(params, is_variable)
    as "Each parameter must be one letter from a to z"
  case find_duplicates(params) {
    [] ->
      case find_unbound(body, params) {
        // YOUR CODE HERE (replace the code below)
        [] -> todo
        s -> Error(VariablesNotBound(list.unique(s)))
      }
    s -> Error(DuplicateParameterNames(list.unique(s)))
  }
}

/// Every name that appears in `params` more than once.
pub fn find_duplicates(params: List(String)) -> List(String) {
  // YOUR CODE HERE (replace the code below)
  todo
}

/// Every variable in `expr` that is not one of `params`.
pub fn find_unbound(expr: Expr, params: List(String)) -> List(String) {
  // YOUR CODE HERE (replace the code below)
  todo
}

gleam test -- make_fn

Q4: Apply

Implement apply, which takes a UserFn and a list of integer arguments and returns the value of the function's body when each parameter is bound to the argument in the same position. If the number of arguments differs from the number of parameters, return a WrongArgumentCount error. Otherwise, call eval on the body with bindings that bind each parameter to its argument. (If the body has a variable that isn't a parameter, which can happen when a UserFn is built directly rather than by make_fn, eval returns NameNotFound.)

let f = UserFn(["x", "y"], Binary(Sub, Binary(Mul, N(2), Var("y")), Var("x")))
assert apply(f, [1, 5]) == Ok(9)
assert apply(f, [1]) == Error(WrongArgumentCount(want: 2, got: 1))

Hint: list.zip(["x", "y"], [1, 5]) is [#("x", 1), #("y", 5)], and dict.from_list makes a Dict from a list of pairs.

/// The value of the body of `f` when each parameter is bound to the argument
/// in the same position in `args`, or an error if the number of arguments is
/// wrong or the body has a variable that isn't a parameter.
pub fn apply(f: UserFn, args: List(Int)) -> Result(Int, EvalError) {
  // YOUR CODE HERE (replace the code below)
  todo
}

gleam test -- apply

(Optional) A Calculator

Once you've finished all four questions, the provided src/repl.gleam turns your functions into a calculator. Run it with gleam run -m repl and type an arithmetic expression. An expression can call a function written in Gleam's syntax, fn(params) { body }(args). A call's result is a number, so a call can be an operand of an operator or an argument of another call.

In this calculator, variables can only appear in function bodies, and each must be one of the function's parameters. When eval, make_fn, or apply returns an error, the calculator prints it.

There are a few restrictions that simplify the implementation:

  • A function's body is an arithmetic expression, so it can't contain a call (or another function).
  • Numbers can't be negative (write 0 - 4 instead of -4).
  • All numbers are integers, so / divides integers and drops any remainder (7 / 2 is 3). In Gleam, dividing by zero gives 0.
$ gleam run -m repl
Type an expression such as 1 + 2 * 3 or fn(x, y) { 2 * y - x }(1, 5). Press Ctrl-D to quit.
> 1 + 2 * 3
7
> fn(x, y) { 2 * y - x }(1, 5)
9
> fn(x) { x * x }(fn(x, y) { y - x }(1, 4)) + 1
10
> fn(x) { x * (2 + 3) }
fn(x) { (x * (2 + 3)) }
> x + 1
error: NameNotFound("x")
> fn(x) { x + y }(1)
error: VariablesNotBound(["y"])
> fn(x, y) { x + y }(3)
error: WrongArgumentCount(want: 2, got: 1)

Press Ctrl-D or type exit to quit.

Submit

Run Provenance: Prepare Submission Bundle from the VS Code command palette to create your submission zip, and upload that zip to Gradescope. For a refresher on how to do this, refer to Lab 00.

Practice for Quiz 7

Quiz 7 will occur on Monday, November 16th and Tuesday, November 17th and will have a variant of the find_unbound function in Q3. The practice quiz is released now on PrairieLearn so that you can prepare.

Back to Top

Accessibility Nondiscrimination

Copyright ©2026, Regents of the University of California and respective authors.

This site is built following the Berkeley Class Site template, which is generously based on the Just the Class, and Just the Docs templates.

View all course offerings