# Assignment 7: Imperative Interpreter

This is a **pair or solo Gradescope assignment**—you will submit 2 OCaml files (`a7.ml` and `a7test.ml`) and a README on Gradescope.

:::info
Recall that assignments, if completed as a pair, must be completed **together** rather than dividing work. See the syllabus for more.
:::

In this assignment, you will define a single OCaml function, `interp_stmt`, that is an **interpreter** for _statements_ in a new language called `imp` (for imperative). The pieces of the interpreter required for _expressions_ are already provided for you in the starter code: your task is just to extend the interpreter to handle statements and control flow.

:::warning
For this assignment, you may reference any OCaml language documentation, the [free online OCaml textbook](https://cs3110.github.io/textbook/cover.html), and the class notes. You may find it helpful to look up additional sources on continuations; you may do so (1) if you do not directly copy code, and (2) if you cite them in your README.

For example:
- [Textbook chapter on continuation passing style](https://cs.brown.edu/courses/cs173/2004/Textbook/18-10-04.pdf)
- [Blog post on continuations](https://matt.might.net/articles/by-example-continuation-passing-style/).
- [Wikipedia](https://en.wikipedia.org/wiki/Continuation).

You should not need to use any mutation within your implementation.
:::

### Change log

I will avoid making changes to the assignment after it is posted, but any necessary changes will be added here:

# Setup

:::success
As with Assignment 5, the [stencil code](https://drive.google.com/file/d/1q6AZxtBPyyJTU-fCiKwEVchXQMVZs3-V/view?usp=sharing) is set up as a `dune` OCaml project.

Run `dune test` to compile your code in `a7.ml` and run the inline tests in `a7tests.ml`.
:::

### Attribution

This assignment is adapted from an assignment from [CS4110](https://www.cs.cornell.edu/courses/cs4110/2024sp/) at Cornell University, by Adrian Sampson and others.

# Introduction

`imp` is a small imperative language, with a similar AST to what we designed in class to model Python (though we avoid Python's whitespace syntax, which is difficult to parse/test).

`imp` has a more restricted expression format than `MiniLang`: it makes a distinction between arithmetic expressions on integers, and boolean expressions.

:::info
The `imp` parser handles arithmetic and boolean expressions separately. This means that unlike Assignment 3, you **do not need to insert dynamic type checks**.
:::

We represent the AST with the following OCaml variant type:

(* Arithmetic operators *)
type aop =
  | PlusOp
  | MinusOp
  | TimesOp

(* Arithmetic expressions *)
type aexp =
  | Int of int
  | Var of string
  | ABinOp of aop * aexp * aexp

(* Comparison operators *)
type cmp =
  | Equals
  | NotEquals
  | Less
  | LessEq
  | Greater
  | GreaterEq

(* Arithmetic operators *)
type bop =
  | AndOp
  | OrOp

(* Boolean expressions *)
type bexp =
  | True
  | False
  | Cmp of cmp * aexp * aexp
  | Not of bexp
  | BBinOp of bop * bexp * bexp

(* Statements *)
type stmt =
  | Assign of string * aexp
  | If of bexp * stmt * stmt
  | While of bexp * stmt
  | Test of info * bexp
  | Break
  | Continue
  | Block of stmt list
  | Pass
  | Print of aexp

The stencil code provides all of the needed functionality *except* a complete `interp_stmt` function.

:::success
Your job is to complete the definition of the following function:

let rec interp_stmt (e : env) 
                    (curr : stmt) 
                    (next : stmt) 
                    (conts: (stmt * stmt) list)

:::

Where `e` is the current dynamic environment, `curr` is the current statement (about to be interpreted), `next` is the continuation (the next statement to be run) under normal control flow, and `conts` is a stack of continuations for `break` and `continue`, respectively.

The stencil code also provides the function to parse and then call your interpreter on an input:

let parse_and_interp (input : string) : string =
  let c = parse input in
  get_output c

:::success
You should write a series of tests using `parse_and_interp`. 10 examples are provided for you in `a7tests.ml`.
:::

# Grammar

`imp` has the following concrete grammar.

:::warning
Note that many places can only use arithmetic expressions (integers): for example, assignments can only be done using integers. Thus, our dynamic environment only needs to track integer values.
:::

<aexpr> ::= <num>
         | <var>
         | <aexpr> + <aexpr>
         | <aexpr> - <aexpr>
         | <aexpr> * <aexpr>

<bexpr> ::= true
         | false 
         | <aexpr> == <aexpr>
         | <aexpr> != <aexpr>
         | <aexpr> < <aexpr>
         | <aexpr> <= <aexpr>
         | <aexpr> > <aexpr>
         | <aexpr> >= <aexpr>
         | <bexpr> or <bexpr>
         | <bexpr> and <bexpr>

<stmts> ::= <stmt> ";" <stmts>
         | <stmt> ";"

<stmt> ::= pass
         | print <aexpr>
         | test <bexpr>
         | break 
         | continue 
         | { <stmts> }
         | if <bexp> then <stmt> else <stmt>
         | while <bexp> do <stmt>
         | <var> = <aexpr>

The `a7tests.ml` file has many examples of `imp` programs.

Here is one of those examples:

x = 0;
while x < 4 do {
  print x;
  x = x + 1;
};

Note that `;` is required even after braces for a block.

# `imp` dynamic evaluation rules

## Arithmetic expressions (provided)

- The `imp` dynamic evaluation rules for arithmetic (`+`, `-`, `*`) are the same as `MiniLang'`s (or OCaml's, without the static type checking).

## Boolean expressions (provided)

- The `imp` dynamic evaluation rules for boolean comparisons are the same as `MiniLang'`s (or OCaml's, without the static type checking).
- `and` and `or` do **not** short circuit. For example, in the expression `b1 or b2`, both `b1` and `b2` are evaluated even if `b2` interprets to `true`.

## Statement evaluation rules

- The statement `pass` does nothing (just like in Python).
- The statement `print a` interprets `a` and calls the helper function `output_int` on the result
:::warning
To facilitate testing, call `output_int` rather than e.g. `print_endline` directly.
:::
- The statement `test b` is like an assert. If `b` interprets to `true`, it behaves like `pass`. Otherwise, it raises exception `TestFailed`.
- The statements `break` and `continue` modify the flow of control in `while` loops.
- `continue`: skips the remainder of the current loop iteration and proceeds with the next iteration.
- `break`: terminates the loop and proceeds with the next statement after the loop. (These are the same semantics as in real imperative languages, such as Python.)
:::warning
A `break` or `continue` outside of any `while` loop should be treated as an error.
In your interpreter, such configurations should raise `IllegalBreak` and `IllegalContinue`.
:::
- `if` should work how you expect: if the first argument `b` interprets to `true`, interpret the first branch, otherwise interpret the second branch.
- `while` should work how you expect: repeat the body as long as the condition interprets to `true` (0 or more times).
- Blocks of statements are combined with `;` and should be interpreted one after the other.
- Variable assignment is more simple in `imp` than let bindings in `MiniLang`: `imp` has no functions, and essentially has a global scope (once a variable has been assigned to in the dynamic execution, it can be used at any future point).

For example, the following program should not raise an error, even though `x` is only assigned to inside the `while` braces (but referenced after).

i = 0;
while i != 1 do {
  x = 42;
  i = 1;
};
test i == 1;
test x == 42;

## Unbound variables

Unbound variables should raise the `UndefVar` exception.

For example:

print x;

Should raise `UndefVar` at the use of `x`.

## Error Exceptions

The stencil code provides the following exceptions:

(* You should use in a7.ml *)
exception IllegalBreak
exception IllegalContinue
(* Used by the stencil code*)
exception TestFailure of string
exception UndefVar of string

# Implementation summary

Your `interp_stmt` function should call the existing helper functions for interpreting expressions and handle control flow via the continuation stack. Note that you can call `interp_stmt` recursively on _different_ statements than those passed in: see the `Test` match case for an example of this.

## Using continuations

To implement `break` and `continue`, you'll use a continuation stack to keep track of the statement that should be executed after one of these is encountered.

#### Example Program

x = 1;
y = 1;
while (true) do {
  x = x + 1;
  if (4 < x) then { break; } else { pass; };
  continue;
  y = y + 1;
};
x = x * 2;

After the `break` is executed, execution should proceed with line 9:

x = x * 2;

This concept is called a **continuation**, because it describes how execution should proceed after control flow changes.
We extend our understanding of what the interpreter acts on to include **continuations** during evaluation.

Because we have both `break` and `continue`, and since loops can be nested, we keep track of a **list of continuation pairs**.

Each recursive call to `interp_stmt` should include:

<env, curr, next, conts>

Where:

- `env` is the dynamic environment
- `curr` is the current statement
- `next` is a continuation representing the next statement
- `conts` is a list of continuation pairs `(bstmt, cstmt)`
- `bstmt`: what to do after `break`
- `cstmt`: what to do after `continue`

Initially, `next` is `Pass` and `conts` is `[]`.

Executing `break` or `continue` should discard `next` and proceed with the appropriate continuation from `conts`.

Executing a `while` statement should **add** a pair of statements to `conts`. To model the stack of nested statements, you should add and remove from the head of `conts`.

#### Example Case

One case of `interp_stmt`, for `test <b>`, has been provided in the stencil code. Note how when the test succeeds, the interpreter uses both the `next` statement and `Pass` in the recursive call.

:::info
Think carefully about how to use similar logic (e.g., using `Pass` or other AST constructs in recursive calls) for other cases.
:::

:::warning
This is an assignment where you'll want to make sure you have a plan *before* you start coding!
:::

## Debugging and pretty-printing

The stencil code includes a pretty-printed in `pprint.ml`; `a7.ml` has commented-out examples of using it. You can also find commented-out examples of printing from `a7tests.ml`.

In addition, if you are working on a Unix-based system that has `make` installed, you can run your `imp` interpreter from the command line.

Run `make`, then you can run, for example `./imp test-basic.imp` and see the output to your terminal.

# Submission
Submit the following **3 files** on **Gradescope**:

:::success
- `a7.ml`
- `a7tests.ml`
- `README` as either a `txt`, `md`, or `pdf` file, with:
- Roughly how long did this assignment take you (in hours)?
- Which was the most challenging part of this assignment?
- Which resources did you find to be the most useful?
:::