1 Instructions
Begin by downloading the file hw4-base.ml from the course website, and renaming it to hw4.ml. This file contains the functions that you will use and modify in the homework. You should not need to define any new functions, or change any functions other than step cmd. Submit your completed hw4.ml via Gradescope. As always, please don’t hesitate to ask for help on Piazza (https://piazza.com/class/jkh8q52qrh06v).
2 Extending the Step Function with Exceptions
The file hw4-base.ml defines the types exp of expressions and cmd of commands. It also defines two main functions: eval exp, a big-step-style interpreter for expressions, and step cmd, a small-step-style interpreter for commands.
The function eval exp : exp - state - exp res option takes an expression e
and a state s and returns either:
• Some (Val v), if e in the state s evaluates to the value v, that is, (e, s) ⇓ v
• Some Exc, if evaluating e in the state s produces an exception, that is, (e, s) ⇓ exc, which will happen when e involves dividing by zero
• None, if evaluating e in the state s produces an error, such as trying to add bools or evaluate an undefined variable
The function step cmd : cmd - state - (cmd * state) option takes a com- mand c and a state s and returns either:
• Some (c0, s0), if (c, s) → (c0, s0)
• None, if there is no step that (c, s) can take
eval exp has already been updated to produce and handle exceptions, and the cmd type already includes constructors Throw, for the throw command, and Try of cmd * cmd, for the try-catch command.
(15 points) Extend the step cmd so that it handles exceptions and the try-catch command. Use the small-step rules for exceptions and the try-catch command, shown below. For instance,
step cmd (Seq (Assign ("x", Div (Int 1, Int 0)), Skip)) empty state
should return Some (Seq (Throw, Skip), empty state), and
step cmd (Try (Throw, Assign ("x", Int 2))) empty state
should return Some (Assign ("x", Int 2), empty state). (Note that OCaml will display empty state (and any other state) as <fun in the output.)
You should not need to change any existing cases of step cmd, but you may need to add cases to both the top-level match statement and the inner match statements. The throw command itself, like the skip command, does not step to anything.
(e, σ) ⇓ exc
(x := e, σ) → (throw, σ) (throw; c2, σ) → (throw, σ)
(e, σ) ⇓ exc (if e then c1 else c2, σ) → (throw, σ)
1
(c1 , σ) → (c0 , σ0)
1
(try c1 catch c2 , σ) → (try c0
catch c2, σ0)
(try skip catch c2 , σ) → (skip, σ) (try throw catch c2, σ) → (c2 , σ)
