Problem set procedures for CS51

Problem set procedures for CS51 #

Setup #

We’ll assume that you have successfully configured your development environment as specified in the Setting up your OCaml development environment document. If not, you’ll want to do that before getting started.

Creating and cloning the remote repository #

Follow these instructions to generate your git repository for the problem set via Github classroom:

  • Go to http://url.cs51.io/ps{n}. (The {n} is the problem set number.)

  • You may have to “Authorize application”.

  • Click on “Accept this assignment”.

  • Click on the generated link to https://github.com/cs51/ps{n}-2024-{yourname}.

  • Click on the “Code” button.

  • Select “SSH” if needed.

  • Copy the SSH URL for the generated repo: git@github.com:cs51/ps{n}-2024-{yourname}.git

  • We recommend that you place all your local problem set repositories in a directory for that purpose, say the psets directory. Create the directory, if you haven’t already:

    % mkdir psets

    and change to that directory:

    % cd psets

    and clone the repository into a subdirectory ps{n}:

    % git clone git@github.com:cs51/ps{n}-2024-{yourname}.git ps{n}

    If all went well, you should have seen something like this:

    Cloning into 'psets/ps{n}'...
remote: Counting objects: 51, done.
remote: Compressing objects: 100% (51/51), done.
remote: Total 51 (delta 51), reused 51 (delta 51)
Receiving objects: 100% (51/51), 51 MiB | 51 MiB/s, done.
Resolving deltas: 100% (51/51), done.

  • Now go to the directory for your just-created local repository:

    % cd ps{n}

You should find a file ps{n}.ml that contains detailed instructions and scaffolding code for all of the problems. (Some problem sets may have multiple top-level files.)

Working with a partner #

Some later problem sets allow students to work in pairs with a partner. The course collaboration policy still applies to the pairs.

On partner problem sets, one member of your pair should follow the Github classroom link http://url.cs51.io/ps{n}. After clicking this link there is a “Create team” option. Once you enter a name for your team and submit it, your partner can follow the link on the problem set specification and choose that team as well.

If you want to work solo on a partner problem set, just create a team for yourself.

If you are working with a partner, you should endeavor to keep up-to-date with your partner’s code. Run git pull to fetch any commits from your partner, and git push to upload your commits to the repository. It’s generally a good practice to pull before you push, so you can resolve any conflicts between your and your partner’s code. More information about Git and its use can be found in Eddie Kohler’s guide to Git and in Brian Yu’s Git video.

Doing the problem set #

Stub code #

In these problem sets and in the labs as well, we’ll often supply some skeleton code for functions that you are to write. Typically, this “stub” code merely raises an exception noting that the function has not yet been written – something like

let merge =
  fun _ -> failwith "merge not implemented" ;;

(The failwith function will be explained later in the course. For the time being, you can treat this as a fixed idiom.)

You’ll want to replace these stubs with a correct implementation of the function. Other parts of the assignment may have you perform other tasks to check your understanding of the material.

Use of standard OCaml libraries #

OCaml constructions and libraries are introduced in a staged manner throughout the readings and assignments. The assignments typically make clear which libraries are appropriate and inappropriate to use for the pedagogical purposes of the assignments, and you should code accordingly. It is neither needed nor helpful to comb the libraries for additional library functions to use on the assignments.

As a special case, especially in early labs and problem sets we ask you to implement functions that already exist in basic OCaml libraries like Stdlib or List. The intention is to gain experience using the particular implementation techniques of the lab or problem set. Therefore, as a general rule, if a library function trivializes the problem, you shouldn’t use it. For example, if in problem set 1 on structure-driven definition of functions we ask that you implement a function zip to combine two lists, an implementation of the form

let zip = List.combine ;;

is clearly not what was intended.

Modifying the header line #

Often, the stub code is written to give you an idea of the function’s intended name and its signature (its type, including its arguments and their types, and the return type), for instance,

let somefunction (arg1 : type) (arg2 : type) : returntype =
  failwith "somefunction not implemented"

This stub code indicates that somefunction takes two arguments of the indicated types and returns a value of the indicated return type. But there’s no need to slavishly follow that particular way of implementing the function to those specifications. In particular, you may want to modify the header line, and in some cases you’ll need to. For instance, you may want to introduce a rec keyword (if your function is to be recursive):

let rec somefunction (arg1 : type) (arg2 : type) : returntype =
  ...your further code here...

Or you might want to define the function using anonymous function syntax:

let somefunction =
  fun (arg1 : type) (arg2 : type) : returntype ->
    ...your further code here...

Other modifications may be needed as well.

In short, you can and should write these function definitions in as idiomatic a form as possible, regardless of how the stub code has been organized.

Design and style #

It is a theme of this course that programming well involves good design and style. The code you submit should not only work, but be well designed. Once you get your code working, take another pass over the code to improve its design. Refactor the code following the edicts from the textbook. Feel free to use auxiliary functions to make your code cleaner, more modular, and easier to test. Document it consistently and clearly.

Good style is an important part of programming well. It is useful not only in making code more readable but also in helping identify syntactic and type errors in your functions. For all assignments, your code should adhere to the style guide in Appendix B of the textbook.

Compiling with make #

In early problem sets, we provide a makefile that allows you to compile your code without directly calling ocamlbuild (the compiler that takes your .ml files and turns them into executable .byte files).

For later problem sets, a makefile might again prove helpful in compiling your code, especially if you don’t want to compile it all at once. Consider the following sample makefile (which not coincidentally happens to to be a good starting point for Problem Set 1).

all: ps1 ps1_tests

ps1: ps1.ml
    ocamlbuild -use-ocamlfind ps1.byte

ps1_tests: ps1_tests.ml
    ocamlbuild -use-ocamlfind ps1_tests.byte

This Makefile has three targets:

  • all (called with make all or just make) compiles both ps1 and ps1_tests, by listing ps1 and ps1_tests as dependencies.

  • ps1 (called with make ps1) compiles only ps1.ml.

  • ps1_tests (called with make ps1_tests) compiles only ps1_tests.ml.

As you might be able to infer, the general structure of a make rule is as follows:

target: first-dependency second_dependency [...]
<tab>   shell-command <arguments>

You can add as many of your own rules as you’d like, provided they are presented in the format above.

So, for example, you might have noticed that compilation produces a _build folder and some annoying .byte files in your directory, which can be pesky to manually delete. As such, you might want to consider including a make clean target in your Makefile, which upon execution will automatically rm files you don’t need. You might also want to consider writing targets for your testing files, so you can compile them as needed.

In later problem sets, you will be expected to write your own makefile if you want one. We highly recommend this.

Testing #

Thorough testing is important in all your work, and we hope to impart this view to you in CS51. Testing will help you find bugs, avoid mistakes, and teach you the value of short, clear functions. In early problem sets, we’ll provide a starter test file, for example, the file ps1_tests.ml, where we’ve placed a few prewritten tests for one or more of the problems. You should augment these to form a complete set of tests for the problem set, ideally covering all code paths and corner cases. (In later assignments, we won’t provide a starter test file; you’re on your own to perform testing.)

To run your tests, run the shell command

% make ps1_tests

in the directory where your ps1.ml file is located, and then run the compiled program by executing ps1_tests.byte:

% ./ps1_tests.byte

The program should then generate a full report with all of the unit tests for all of the functions in the problem set.

Compilation errors #

In order to submit your work to the course grading server, your solution must compile against our unit test suite. The system will reject submissions that do not compile. Changing the names or type signatures of the functions that we ask you to write will cause your code to fail to compile against our unit tests, which expect those names. Consequently, you should not change the names or types of those functions.

If there are problems in the assignment that you are unable to solve, you must still write a function that matches the expected type signature, or your code will not compile. When we provide stub code, that code will typically compile to begin with. If you are having difficulty getting your code to compile, please visit office hours or post on the course forum. Emailing your homework to your TF or the Head TFs is not a valid substitute for submitting to the course grading server. Please start early.

We will often provide an .mli file (for instance, ps1.mli) that checks to make sure your functions in ps1.ml have the correct types so that they will compile against our unit tests. (The full story on .mli files and the related concept of module signatures is discussed in Chapter 12.) Unless specifically mentioned, you should not modify these .mli files.

If you change the type of a function, you may see an error like:

Error: The implementation ps1.ml does not match the
       interface ps1.cmi:
       Values do not match:
         val nonincreasing : int list -> int
       is not included in
         val nonincreasing : int list -> bool

This error means that your function nonincreasing has the wrong type. You should look back at your code and modify it so that it has the type specified in the assignment.

If you delete a function or change its name, you may see an error like:

Error: The implementation ps1.ml does not match the
       interface ps1.cmi:
       The value `nonincreasing` is required but not provided

This error means that you are missing an implementation of the function nonincreasing. If you are not able to get a particular function to compile, do not delete it. Instead, you can revert the function back to the stub implementation in the distribution code. (You can look at previous commits on GitHub to see what the stub implementation was.) Similarly, you should use the function names that we specify (in the stub code or comments) so that the function name will match our unit tests.

Before submission #

Before submitting, please ensure your code compiles by running make while in the main directory. (For early problem sets, we include an appropriate makefile. For later problem sets, you’ll have to provide your own makefile.) Also be sure that any tests you have written run properly. Evaluating definitions in the top level REPL, while useful during development, does not guarantee the code will compile. Remember that submissions or parts of submissions that do not compile receive no credit.

Reflecting on your process #

Before submitting your problem set, please estimate how much time you spent on the assignment by editing the code

let minutes_spent_on_pset () : int =
  failwith "not provided" ;;

to replace the value of the function with an approximate estimate of how long (in minutes) the assignment took you to complete. For example, if you spent 6 hours on this assignment, you should change the line to:

let minutes_spent_on_pset () : int = 360 ;;

(For consistency in our data-gathering, if you worked with a partner, please provide an estimate of the average time each of you spent, not the total.)

We also ask that you reflect on the process you went through in working through the problem set. You might think about questions like: Where did you run into problems and how did you end up resolving them? What might you have done in retrospect that would have allowed you to generate as good a submission in less time? Please provide us your thoughts on these questions or any other reflections by editing the return value of the reflect function. It should look something like

let reflection () : string =
  "...your reflections go here..." ;;

After providing your reflections, make sure that your code still compiles.

Submission #

Submitting homework happens in two phases. First, you’ll commit your changes to your local git repository and push those changes to the remote GitHub repository. Second, you’ll log in to Gradescope and cause Gradescope to fetch that Github commit for the assignment. Gradescope will then retrieve your submission from GitHub so that it can be graded, both through automated unit tests and code review by our staff. See the Gradescope submission instructions for further information.

You can make sure that the right files were submitted by clicking on the “code” tab on the assignment page in Gradescope after you have submitted.

After Gradescope receives your submission, it double checks that your code compiles against our unit testing framework. After this test is complete (it usually takes about 10 seconds), you will receive confirmation that your submission succeeded. Code submissions that do not compile are rejected by the system and count for no credit.

Your last submission before the problem set deadline will be graded. When problem set grades are released you will be able to see your grade under the “Assignments” tab on Gradescope.

We have created a Google Chrome extension that provides helpful messages in case there are any problems with your Gradescope submission. If you use Google Chrome, you should download the CS51 Extension.

Remember, pushing to GitHub does not complete your submission. You must submit your Github repository to Gradescope to complete the homework.