Compilers

Higher-Order Functions and Trees

Due on Monday, January 31st at 11:59 PM. This is an individual lab. You are to complete this lab on your own, although you may discuss the lab concepts with your classmates. Remember the Academic Integrity Policy: do not show your code to anyone outside of the course staff and do not look at anyone else’s code for this lab. If you need help, please post on the course forum forum or contact the instructor. If you have any doubts about what is okay and what is not, it’s much safer to ask than to risk violating the Academic Integrity Policy.

Overview

This lab will provide you with additional OCaml experience. You will familiarize yourself with recursive algorithms on trees and with higher-order functions. The practice you get in this assignment will become important as your use of these techniques becomes commonplace throughout the semester.

Miscellaneous Features in OCaml

Throughout this lab, you’ll need to use a variety of OCaml features we have not discussed at length in class. These features are generally straightforward based upon what you already know; you’ve seen most of them in other languages. You’ll probably want to keep the OCaml Transition Guide handy while you work on the assignment.

Working on the Lab

This week, your lab assignment can be cloned with

git clone git@github.swarthmore.edu:cs75-s22/ocaml2-<username>

As with last week, your task is to read through the source files in this assignment and fill in all of the places containing the string “TODO”. You are recommended to pursue this in the following order:

functions.ml
arithmetic.ml
algorithms.ml
bst.ml

Testing

For this lab, you are required to write tests for every function you write. Your tests should demonstrate that you have considered the possibilities of input for each of your functions and determined how to verify their behaviors. In a function that reverses a list, for instance, there should be tests for an empty list, a multi-element list, and possibly a single element list. Poorly tested or untested functions will be reflected in the assessment of your assignment. If you have any questions about what is sufficient, please let your instructor know.

Testing Output

So far, we’ve been using assert_equal from the OUnit library. This function is good at telling when we don’t get the value we expect but very bad at telling us what the different values were. This is because OUnit doesn’t necessarily know how to turn every value into a string for you, but we can teach it! For instance, consider the following test (that will always fail):

let test_failure =
  "test failure" >:: fun _ ->
    assert_equal 4 5
;;

If we run that test, we get the (uninformative) output:

Error: suite:0:test failure.

File "oUnit-suite-hostname#01.log", line 2, characters 1-1:
Error: suite:0:test failure (in the log).

Raised at file "src/oUnitAssert.ml", line 45, characters 8-27
Called from file "src/oUnitRunner.ml", line 46, characters 13-26

not equal

We can instead give the test an optional “printer” argument, which is a function that knows how to turn our test values into strings:

let test_failure =
  "test failure" >:: fun _ ->
    assert_equal ~printer:string_of_int 4 5
;;

Here, ~printer:int_of_string tells the assert_equal function to take an extra pretty-printing argument named string_of_int and call it on the values if they differ. When we run this test, we get a much more informative output:

Error: suite:0:test failure.

File "oUnit-suite-hostname#01.log", line 2, characters 1-1:
Error: suite:0:test failure (in the log).

Raised at file "src/oUnitAssert.ml", line 45, characters 8-27
Called from file "src/oUnitRunner.ml", line 46, characters 13-26

expected: 4 but got: 5

In order to take advantage of this, of course, we need to have a way of taking whatever type the test is using and turn it into a string. This is a matter of writing a string_of-style function, though, and you have practice at that by now. :)

One caveat: OUnit will not try to print its arguments without a printer argument even if the arguments are already strings. To fix that, we just need to give a printer which can turn strings into strings. One example is the identity function, fun x -> x. So we can write e.g.

let test_failure_string =
  "test failure_string" >:: fun _ ->
    assert_equal ~printer:(fun x -> x) "a" "b"
;;

Print Debugging

In learning a language, it’s important to develop a set of debugging techniques. Print debugging is a common tool for understanding the behavior of a program which can work well in OCaml so, for this course, you can draw from your experience print debugging in other languages.

OCaml supports a binary operator ; called the “sequence operator”. As this is a binary operator, you can use it to write an expression with the form <expr> ; <expr>. This operator simply evaluates the first expression, then evaluates the second, and then gives back the result of the second expression (throwing the first expression away). For instance, the expression 4+1 ; 5+3 evaluates to 8 in the OCaml toploop. The expression 4+1 was evaluated, but the result was discarded.

This is useful when you don’t care about the result of the first operation but want it to be evaluated anyway, as we do when printing a string. For instance, the following OCaml code prints a message whenever a function is called and whenever it returns; it looks somewhat like Python or C++ code that does the same thing.

open Printf;;
let rec summate (n : int) : int =
  printf "Calling summate with n=%d\n" n;
  let answer : int =
    if n > 0 then
      let smaller : int = summate (n-1) in
      smaller + n
    else
      0
  in
  printf "Returning from summate with n=%d and answer=%d\n" n answer;
  answer
;;

In the above, printf has the effect of printing a message to the program’s output stream but returns (). We use the ; to evaluate the printf (so that it prints) but then to throw away the () and continue evaluating the rest of the function.

Submitting

To submit your lab, just commit and push your work. The most recent pushed commit as of the due date will be graded. For more information on when assignments are due, see the Policies page.

After each lab, you will complete a brief questionnaire found here. In most cases, the questionnaire should take less than a minute. This questionnaire is required and will be used as part of your participation grade.

If You Have Trouble…

…then please contact your instructor! The course forum is the preferred method, but you can reach out via e-mail as well. Good luck!