1. Write a function sum which sums the elements of a list: 
     sum [1;2;3;4] = 10
  2. Write your own version of append which appends one list to another: 
     append [1;2;3] [4;5;6] = [1;2;3;4;5;6]
    What is the time complexity of append in terms of the input size?

  3. Recall the simple stack machine from the lecture.
    Write a function instructions_to_string : inst list -> string which serializes an instruction list to a string, e.g, 
      instructions_to_string [Push 4; Push 2; Add] = "push 4; push 2; add;"

    week36.ml

  4. Recall Boolean expressions as given in dProgSprog: environments, BNF of boolean expressions, an evaluator

    We can express the same concepts in OCaml as boolean.ml.
    Write a function eval' : bexp -> benv -> bool option which returns an optional boolean instead of raising an exception.

  5. Now recall negational normal forms.

    Write an OCaml datatype bexp_nnf representing Boolean expressions in negational normal form.

  6. Is it necessary to write a well-formedness checker for the OCaml datatype? Why / why not?

  7. Implement a function that evaluates Boolean expressions in negational normal form.

  8. Implement a function normalize-boolean-expression : bexp -> bexp_nnf which translates a bexp into a bexp_nnf

    boolean.ml