Assignment 1: Collatz


The goal of this assignment is to introduce you to the basics of OCaml programming and apply them to some simple problems.

Part 1: Online Tasks

Part 2: Setting up your Development Environment

Check out the course resources web site for help getting starting with OCaml and installing or configuring a development environment for your chosen editor, such as emacs, vim, VS Code, or atom. Once you have OCaml installed and your development tools set up, now you just have to learn how to write useful programs!

Part 3: Assignment Basics

To get started, download the tarball a1.tgz. Unzip and untar the code and data by typing the following commands at a shell prompt.

$ tar xzf a1.tgz

A directory called a1 should appear. Now, change directory to a1 and look at its contents:

$ cd a1
$ ls -a
You should see the following files:
  • the main file for your assignment. Look inside the file to find a series of short problems you should solve.
  • .merlin: a file that defines the dependencies for program — useful when using merlin mode in an editor such as emacs or vim. This file is unnecessary if you have not configured merlin for your editor.
  • A file with the tests that will be used to evaluate
  • README.txt: A readme in which you will record your sources.

You can compile by typing:

$ ocamlbuild a1.native
This will do two things. First, it creates the executable file a1.native. Second, it creates a directory called _build full of auxiliary files used by the OCaml compiler system. To run the executable we have created, type:
$ ./a1.native
If you haven't touched any of the code inside yet, you should see the following message printed out:
Fatal error: exception Failure("undefined")
That indicates the Failure exception has been raised. (This exception has been raised because the function unimplemented () has been called at many points in the file. That unimplemented raises the exception using the built-in failwith command. It is your job to replace the unimplemented function calls with code that does the appropriate thing.) Follow the instructions in to eliminate the error and complete the assignment.

To delete the _build directory and remove the executable files you have created, type

$ ocamlbuild -clean

This assignments asks you to answer the questions contained within the file. Make sure the entire file type checks and compiles before you hand it in.

The command ocamlbuild a1.native uses the "native" compiler, which compiles your programs to the hardware for your machine. There is another way to compile your .ml files.

$ ocamlbuild a1.byte
That command uses the "bytecode" compiler, which compiles to a machine-independent OCaml bytecode. The bytecode compiler is slightly faster (which may be good for shortening your debug-compile cycles when creating larger programs) but the performance of the generated executable isn't quite as good (though still not bad). You will notice that running the bytecode compiler will generate the file a1.byte. You can run that by typing:
$ ./a1.byte

Important notes

  1. Compilation errors: Your solution must compile. If you omit problems (you shouldn't!), leave the corresponding definitions commented out so that they will not confuse our automated grader as it checks the other problems. If you are having difficulty getting your code to compile, please visit office hours!
  2. Testing: We have provided tests for some of the functions you will write in In order to run these tests, compile with ocamlbuild testing.native or ocamlbuild testing.byte and run the resulting executible. Note that if you try compiling before doing any work on the assignment, you will get an error message. My message looks like this:
    COS-D25T909EGQ18:handout dpw$ ocamlbuild testing.byte
    + /Users/dpw/.opam/4.10.0/bin/ocamlc.opt -c -o testing.cmo
    File "", line 34, characters 18-24:
    34 | let _ = run_test (prob3a = true) "3a should be true"
    Error: Unbound value prob3a
    Command exited with code 2.
    Hint: Recursive traversal of subdirectories was not enabled for this build,
      as the working directory does not look like an ocamlbuild project (no
      '_tags' or '' file). If you have modules in subdirectories,
      you should add the option "-r" or create an empty '_tags' file.
      To enable recursive traversal for some subdirectories only, you can use the
      following '_tags' file:
          true: -traverse
           or : traverse
    Compilation unsuccessful after building 4 targets (2 cached) in 00:00:00.
    The key thing in the message comes at the top. It mentions a particular line of code (line 34) and it underlines a variable. It tells you: "Unbound value prob3a". This means that it could not find a definition for the variable prob3a. If you look in, you will see that a definition for prob3a is commented out. If you uncomment that (and follow the instructions in as to what to do), then you can resolve this compilation error.

    If you wind up being able to compile or, you may find that when execute either one using ./a1.native (or ./a1.byte depending on how you compiled the file), the code will just generate the message

    Fatal error: exception Failure("undefined")
    You will need to replace the calls to unimplemented() with something else before you can execute the code properly. The testing code we have provided you does not cover all cases which will be tested in grading. You are encoraged to add additional tests using the existing infastructure to ensure correct preformance. Or to test your solutions in some other way. Having said that, the first assignment does not involve a lot of computation. If you can get the code to compile, you might not need to do too much testing. The file is largely for demonstration so don't get too hung up on it.
  3. Auxiliary functions: Feel free to use them when they make your code cleaner, more modular, and/or easier to test — that's what functions are for! Just make sure that if we name a particular function that you have to write (either in the assignment text, or in a template file), that you preserve its name so that our automated grader can find it.
  4. Style: Finally, please pay attention to style. Take the extra time to think about the problems and find the most elegant solutions before coding them up. Many of the problems in this assignment are somewhat artificial. Nevertheless, think about your coding style where appropriate (and certainly, thinking about style in the final question computing pi is appropriate). For reference, consult the COS 326 style guide and the lecture notes. In addition, you are also encouraged to bring style questions to the course staff at office hours.
  5. Line limit: One important element of style is having at most 80 characters per line. This is important for our ability to read your code.

Hand In

Hand in your assignment using the TigerFile link on the assignment page.

We will give you some indication that you have not drastically misinterpreted the specification by checking if your solution compiles. These are not tests, make sure to use the tests in

It is very important that you compile and test your code while in your a1 directory. These steps will check that your code as a whole compiles and that the tests pass. Using merlin (or the interactive toplevel REPL) for typechecking is very useful but is not sufficient for these purposes. Submissions that do not compile will earn very few points!

Start early! Work hard!