You may choose to work with a partner on this lab. Although labs are meant to
be an open and collaborative environment, it is the responsibility of
both partners to contribute to learning the materials in every lab.
In particular, both partners are responsible for ensuring that submissions are
received by the due date, and for letting us know if one teammate does
not participate in a given lab.
# Introduction: Goals for this lab
+ Practice writing OCaml code using exceptions
+ Practice writing OCaml code in continuation-passing style
The file `prog.ml` contains a datatype representing a small (but “Turing
complete” — meaning capable of expressing any computation that can be expressed
in any other programming language) part of our fragment of a programming
language and an evaluation function for programs in this datatype. It also
defines five values representing miserable failures of programs, literally:
evaluating any of these programs with an initially empty state will result in an
unhelpful exception. Add exceptions to represent each of these situations
(including enough information to give a useful debugging message):
+ `UnboundName` that carries the name that caused the exception
+ `ArithTypeErr` (raised when the program tries to do arithmetic on at least one non-integer value) that carries the two arguments causing the error
+ `CondTypeErr` (raised when the condition for an if or while expression evaluates to a non-boolean value) that carries the value that caused the error
+ `CompTypeErr` (raised when the program attempts to compare at least one non-integer value) that carries the two arguments causing the error.
and modify `eval` so that it raises the appropriate exception in each of these cases.
Once you’re done, modify the definition of the function `runProg :
expr -> unit` that runs its argument with an empty initial state and prints
out the result of the program evaluation. If any exceptions are
raised by `eval`, `runProg` should handle the exception by printing a
useful error message. (For example, the message printed for an unbound
name should include the name.)
The file `kfuncs.ml` includes four non-tail recursive functions, and a
continuation-passing version of the first, `map_k`. Let’s transform
the rest of these functions to continuation-passing style: add OCaml
definitions for the following functions:
+ `append_k : ‘a list -> ‘a list -> ‘a list`: Just like in `map_k`,
you can define an internal helper function that takes the
continuation `k` as an argument; since `l2` is never modified you
could leave it off to make your tail calls a bit simpler to read.
`append_k` should have the same behavior as `@`, e.g. `append_k [1;3] [2;4]` should evaluate to `[1; 3; 2; 4]`, but should be able to handle long lists without a stack overflow.
+ `assoc_update_k: ‘a -> ‘b -> (‘a * ‘b) list -> (‘a * ‘b) list`
updates the binding associated with a key in an associative list, or
adds the binding if none is found. Using a local helper function
will also help make the tail calls simpler here. A few example evaluations:
* `assoc_update_k “v1” 4 [(“v2”,3); (“v1”, 6); (“v0”, 9)]` should evaluate to `[(“v2”,3); (“v1”,4); (“v0”, 9)]`
* `assoc_update_k “u” 1 [(“v”,0); (“x”,0)]` should evaluate to `[(“v”,0); (“x”,0); (“u”,1)]`
* Long lists should be handled without a stack overflow.
# Commit and push so that everything is up on GitHub
Now you need to just turn in your work. Commit your changes and push
them up to your central GitHub repository.
Verify that this worked, by using your browser to see the changes on
If you do not properly push your changes to the repository we
cannot give you credit for the lab, so please remember to do this
__This concludes lab 7.__
Note that any required changes must exist in your repository on
github.umn.edu. Doing the work but failing to push those changes
to your central repository will mean that we cannot see your work
and hence can’t grade it.