# 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][ai].*
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][web]
* The [CS 3110 Style Guide][style]
* The policies about deadlines, extensions, and late submissions in the
[course syllabus][late]
[web]: http://www.cs.cornell.edu/Courses/cs3110/2018sp/
[style]: http://www.cs.cornell.edu/Courses/cs3110/2018sp/handouts/style.html
[ai]: http://www.cs.cornell.edu/Courses/cs3110/2018sp/syllabus.php#ai
[late]: http://www.cs.cornell.edu/Courses/cs3110/2018sp/syllabus.php#late
**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][late]. 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][style].
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][string] 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.
[string]: https://caml.inria.fr/pub/docs/manual-ocaml/libref/String.html
## 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][leap]: "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.)*
[leap]: http://aa.usno.navy.mil/faq/docs/calendars.php
* * *
**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][syr] and [XKCD][xkcd].
The function is known to terminate on all positive OCaml integers.)*
[syr]: https://en.wikipedia.org/wiki/Collatz_conjecture
[xkcd]: https://xkcd.com/710/
* * *
**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][nfib]. For example, `nacci 2`
produces the Fibonacci sequence, so `nacci 2 6 = [1; 1; 2; 3; 5; 8]`.
[nfib]: http://mathworld.wolfram.com/Fibonaccin-StepNumber.html
* * *
## 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][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.
[cms]: https://cmsx.cs.cornell.edu/