PL II

For this assignment you will get some experience programming in monadic style in OCaml. The file monads.ml contains basic definitions and examples of monads we covered in class, you can use any libraries in this file (and we will assume they are loaded when running your code).

1. Write list_hd and list_tl functions for OCaml lists in the Exception monad which will raise (exceptions monad, not OCaml) exceptions when these operators are applied to empty lists. Note that the type for e.g. list_head should be 'a list -> 'a Exception.mon - it could return an exception. (One nice feature of using the exceptions monad is that effect must show up in the type, like Java exceptions.)
2. Now write a list_foldl function which is like the standard List.fold_left except it only works on lists of length two or more, and there is no need to supply the "zero" argument for this reason: the type will be ('a -> 'a -> 'a) -> 'a list -> 'a Exception.mon. The base case instead of a zero-element list is a 2-element list, for which we just apply the binary operator. In order to get monad programming experience you are to use the previous list_hd and list_tl functions only to take apart the list argument, and if the list is shorter than two those operations will raise (exceptions monad) exceptions which your code should bubble up "automatically" as you will be writing your list_foldl monadically.
3. It is possible to define an operation reset which will clear out the store in the OCaml State monad. With this function the following code

   	  State.(run (let* r = ref 0 in
   	  let* _ = reset in
   	  let* va = deref r in ret va))
         

   will return an OCaml exception Not_found from trying to access a key that is not in the store -- the reset zeroed it out. For this question write such a reset function such that copying and pasting the above code will give the OCaml not found exception.
4. reset is in fact fairly ugly for this reason, it is similar to freeing a heap value in C when the program still holds a pointer to it. For this question let us write some less ugly store manipulation operators which should not raise any exceptions: State.checkpoint and State.snapback. Checkpointing will remember the current store (in an implicit location in the monad wrapper), and snapback will restore to a previous checkpointed heap. The restore operation will only override any values in the current store to be the (older) checkpointed ones, any new references created after the checkpoint will remain and so we will not get any dangling pointers.

   To implement this you will need to make a new version of the State module called StateSnap which will include these two new operators and additional wrapping to implement them. Hint: to implement the override use the union operation on the underlying OCaml Map implementing the store. This operation will need to be exposed in the interface so you will also need to make your own StoreSnap which extends the Store with an override operation.

5. The monad laws should hold for any monad constructed. Argue informally that the laws hold for the Exception monad in monads.ml. The laws are found on the Leroy slides #8/81. To reason about OCaml code, use OCaml operational equivalences. We did not formally define operational equivalence on OCaml but the laws are similar to the Fb laws in the PL book; feel free to use any common-sense equation on OCaml programs.
6. Argue that ExceptionTransf(Identity), the exceptions monad transformer applied to the identity monad, has equivalent behavior to the Exception monad, again reasoning about operationally-equivalent OCaml code as in the previous question.

For this assignment just place the code answers in a single file monad-programming.ml. You can either include the written question answers as comments in that file, or upload a separate .txt or pdf or jpg or whatever with your answers. Submit all files using Gradescope.