A0: Warmup

Deadline: Wednesday, 02/07/18, 11:59 pm

This assignment is to be done as individuals, not with partners nor with teams. Please review the course policies on academic integrity.

This assignment is designed to be a warmup: it's considerably easier and shorter than any of the other assignments in the course. Accordingly, it will be worth only about 1% of your final grade. The main purpose of the assignment is to give you a low-stakes opportunity to experience the 3110 assignment workflow, especially coding to a specification and being graded against the course staff's test suite.

Objectives:

Verify your OCaml environment is set up correctly.
Gain familiarity with basic OCaml language features, especially functions.

Recommended reading:

Lectures and recitations 1–3
The CS 3110 Style Guide
The policies about deadlines, extensions, and late submissions in the course syllabus

Requirements:

Your solution must provide the functions specified below, with exactly those names and types.
Your solution must correctly implement those functions.
Your code must be written with good style and be well documented.

What we provide: In the release code on the course website you will find these files:

A template file warmup.ml with some function stubs.
Some additional scripts for compiling your code.

Grading issues:

Late submissions: Carefully review the course policies on submission and late assignments. Verify before the deadline on CMS that you have submitted the correct version.
Environment, names, and types: Your solution must compile and run under OCaml 4.06.0. You are required to adhere to the names and types of the functions specified below. Your solution must pass the make check described below in Part 0. Otherwise, your solution will receive minimal credit.
Code style: Refer to the CS 3110 style guide. Ugly code that is functionally correct will nonetheless be penalized. Take extra time to think and find elegant solutions.

Prohibited OCaml features: You may not use imperative data structures, including refs, arrays, mutable fields, and the Bytes and Hashtbl modules. (We haven't covered any of those, so it's okay if they sound mysterious.) Strings are allowed, but the deprecated functions on them in the String module are not, because those functions provide imperative features. Your solutions may not require linking any additional libraries/packages beyond the standard library, which is linked by default.

Part 0: Sanity check

Download the release code. Run make check from the folder containing the release code. You should get output that includes the following (other lines might be interspersed):

===========================================================
Your OCaml environment looks good to me.  Congratulations!
===========================================================
Your function names and types look good to me.
Congratulations!
===========================================================

If instead you get warnings about your OCaml environment, seek help immediately from a consultant: something is wrong with the version of OCaml you have installed.

Assuming your environment is good, you should not get warnings about about your function names and types at this point, because you haven't modified the provided file warmup.ml yet. As you complete the assignment, you will be modifying that file. As you solve each part of the assignment, you should re-run make check to ensure that you haven't changed the names or types of any of the required functions.

Running make clean will delete generated files produced by the make and build systems.

Part 1: Functions

Implement each of the following three functions. In doing so, consider: how elegant can you make your implementation? Though we identify which lab you could do each problem after, you are encouraged to use any useful language features you have learned in any labs.

Here are a few frequently asked questions that often come up on the first assignment in the course:

Can I add or remove the rec keyword from a function definition without changing the function's type? Yes.
May I use helper functions? Yes. You do not have to nest them inside the primary function you are implementing; you are free to write them before it.
Do I need to write specification comments for all my functions (i.e., preconditions and postconditions)? Yes.

Valid date [doable after Lab 1]. Define a function valid_date : int -> string -> int -> bool that takes an an integer y, a string m, and an integer d as input and returns true just when y and m and d form a valid date. Here, a valid date has

a year that is strictly positive (i.e., greater than or equal to one);
a month that is one of the following abbreviations: Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec;
a day that is between 1 and the number of days in that month, inclusive, taking leap years into account. Use the usual leap year rule for the Gregorian calendar: "Every year that is exactly divisible by four is a leap year, except for years that are exactly divisible by 100, but these centurial years are leap years if they are exactly divisible by 400."

For example, valid_date 2020 "Feb" 29 = true, and valid_date 2010 "Jun" 50 = false.

(For calendar geeks only: pretend that the entire Common Era has used the Gregorian calendar.)

Syracuse [doable after Lab 2]. Define a function syr : int -> int that takes a strictly positive integer n as input, applies the following operation repeatedly to that input until the result is 1, and returns the number of times the operation had to be applied. If the input is already 1, the function returns 0.

If n is even, divide it by 2.
If n is odd, triple it and add 1.

For example, syr 1 = 0, because the operation doesn't need to be applied at all: the input is already 1. Further, syr 2 = 1, because applying the operation once produces 1. Similarly, syr 10 = 6.

(Why call this function syr? Because it is related to the Collatz conjecture aka the Syracuse problem. See Wikipedia and XKCD. The function is known to terminate on all positive OCaml integers.)

Nacci [doable after Lab 3]. Define a function nacci : int -> int -> int list that takes an integer n and an integer k as input, both of which must be strictly greater than zero, and returns the first k elements of the n-step Fibonacci sequence. For example, nacci 2 produces the Fibonacci sequence, so nacci 2 6 = [1; 1; 2; 3; 5; 8].

Testing

We encourage you to get into the habit of testing your implementation early and often. In assignments after this one, we will ask you to turn in OUnit test suites. But for this warmup assignment, we won't collect your tests. You should nonetheless test.

The test cases provided above are a good starting point. Here they are, expressed as assertions that you could put in your source code.

let () = assert (valid_date 2020 "Feb" 29)
let () = assert (not (valid_date 2010 "Jun" 50))

let () = assert (syr 1 = 0)
let () = assert (syr 2 = 1)
let () = assert (syr 10 = 6)

let () = assert (nacci 1 6 = [1;1;1;1;1;1])
let () = assert (nacci 2 6 = [1;1;2;3;5;8])
let () = assert (nacci 3 6 = [1;1;2;4;7;13])

What to turn in

Submit files with these names on CMS:

warmup.ml, containing your solution code.

REMINDER: ensure that your solution passes the make check test described in Part 0; if it does not, your solution will receive minimal credit.