CSCI 2041 Assignment 1: OCaml Basics

Credit for this assignment will be given based on two categories.

Take the following steps to get started

1. Download the code associated with the project linked at the top of the spec. Unzip it and examine some of the provided code.
2. Examine the overview of the files provided listed in the Download and Setup section. This gives brief descriptions of files that already exist and those that you must create.
3. Pick a problem and read. There is a lot of information and many examples provided for each problem. Reading this will help you write the correct code earlier rather than later.
4. Ask questions: if its not clear how to proceed, put up a Piazza post or visit an office hour.
5. Get coding: don't wait to start for too long as this will greatly increase your stress levels an potentially result in late submissions.
6. Familiarize yourself with the late submission policy for assignments so you are not caught off guard. No submissions will be accepted more than 48 hours after the deadline.

A Makefile is provided as part of this assignment. Building programs in any language is a bit tedious and most folks use build systems of which make is the oldest. The instructions and dependencies to create programs are written in a Makefile which is then interpreted by the make program which will run the OCaml compiler and other commands to create programs.

• make sumfuncs.cmo will compile the code for problem 1
• make test-p1 will compile a test program and run it for problem 1
• ./test_sumfuncs is the test program for problem 1. It runs all tests be default but typing ./test_sumfuncs 3 will run only test #3
• make clean will remove all compiled files and programs
• make on its own will compile all required files and programs
• make test will compile everything and run all tests.

Tests are known to work on lab machines only. They may work on other machines/environments but this is not guaranteed or supported. Check that your code passes tests on lab machines before submitting.

Detailed usage and output from using the provided Makefile are shown below.

> make sumfuncs.cmo                  # build code for problem 1
ocamlc -g -annot -c sumfuncs.ml      # make runs command command

> make sumfuncs.cmo                  # build again
make: 'sumfuncs.cmo' is up to date.  # no need as no changes have been made

> make abovefuncs.cmo                # build code for problem 2
ocamlc -g -annot -c abovefuncs.ml    # make runs compile commands

> make clean                         # remove all compiled/auxiliary files
rm -f *.cmo *.cmi *.mlt *.annot collatz_main  test_sumfuncs test_abovefuncs test_revfuncs test_collatz 

> make test-p1                       # compile and run tests for problem 1
ocamlc -g -annot -c mltest.ml        # compile various stuff to create test_sumfuncs program
ocamlc -g -annot -c sumfuncs.ml
./process-mltest.awk test_sumfuncs.ml > test_sumfuncs.mlt
ocamlc -g -annot -c test_sumfuncs.mlt
ocamlc -g -annot -o test_sumfuncs mltest.cmo sumfuncs.cmo test_sumfuncs.cmo
===TESTS for P1 sumfuncs.cmo===
./test_sumfuncs                      # run test_sumfuncs program
Found 10 tests
RUNNING 10 tests
==================================================
Test  1: ok
Test  2: ok
Test  3: ok
Test  4: ok
Test  5: ok
Test  6: ok
Test  7: ok
Test  8: ok
Test  9: ok
Test 10: ok
==================================================
10 / 10 tests passed                 # looks good


> make test-p2                       # compile and run problem 2 tests
ocamlc -g -annot -c mltest.ml        # compile various codes
ocamlc -g -annot -c abovefuncs.ml
./process-mltest.awk test_abovefuncs.ml > test_abovefuncs.mlt
ocamlc -g -annot -c test_abovefuncs.mlt
ocamlc -g -annot -o test_abovefuncs mltest.cmo abovefuncs.cmo test_abovefuncs.cmo
===TESTS for P2 abovefuncs.cmo===
./test_abovefuncs                    # run the testing program
Found 10 tests
RUNNING 10 tests
==================================================
Test  1: ok
Test  2: FAIL                        # failure
--------------------------------------------------
test_abovefuncs.ml:31                # test file line 31; code leading to it shown
24:  (* array_above on short int array *)
25:  let thresh = 0 in
26:  let input = [|4; -2; -1; 7; 0; 3|] in
27:  let original = Array.copy input in
28:  let actual = array_above thresh input in
29:  let expect = [|4; 7; 3|] in
30:  let msg = sprintf "Expect: %s\nActual: %s" (intarr2str expect) (intarr2str actual) in
31:  __check__ (actual = expect);    # this check failed

Expect: [|4; 7; 3|]                  # expected results
Actual: [|4; 7|]                     # result actually produced by the program
--------------------------------------------------
Test  3: FAIL
--------------------------------------------------
test_abovefuncs.ml:57                # another failed test
50:  (* array_above on short float array *)
51:  let thresh = 1.5 in
52:  let input = [|4.2; 0.5; 1.2; 7.6; 8.9; 0.8; 8.5|] in
53:  let original = Array.copy input in
54:  let actual = array_above thresh input in
55:  let expect = [|4.2; 7.6; 8.9; 8.5|] in
56:  let msg = sprintf "Expect: %s\nActual: %s" (floatarr2str expect) (floatarr2str actual) in
57:  __check__ (actual = expect);

Expect: [|4.2; 7.6; 8.9; 8.5|]
Actual: [|4.2; 7.6; 8.9|]
--------------------------------------------------
Test  4: FAIL
--------------------------------------------------
test_abovefuncs.ml:95                # another failed test
88:  (* array_above on short bool array *)
89:  let thresh = false in
90:  let input = [|false; true; false; true; true;|] in
91:  let original = Array.copy input in
92:  let actual = array_above thresh input in
93:  let expect = [|true; true; true|] in
94:  let msg = sprintf "Expect: %s\nActual: %s" (boolarr2str expect) (boolarr2str actual) in
95:  __check__ (actual = expect);

Expect: [|true; true; true|]
Actual: [|true; true|]
--------------------------------------------------
Test  5: ok
Test  6: ok
Test  7: ok
Test  8: ok
Test  9: ok
Test 10: ok
==================================================
 7 / 10 tests passed

> ./test_abovefuncs 3                # re-run only problem 2's test #3
Found 10 tests
RUNNING 1 tests
==================================================
Test  3: FAIL
--------------------------------------------------
test_abovefuncs.ml:57
50:  (* array_above on short float array *)
51:  let thresh = 1.5 in
52:  let input = [|4.2; 0.5; 1.2; 7.6; 8.9; 0.8; 8.5|] in
53:  let original = Array.copy input in
54:  let actual = array_above thresh input in
55:  let expect = [|4.2; 7.6; 8.9; 8.5|] in
56:  let msg = sprintf "Expect: %s\nActual: %s" (floatarr2str expect) (floatarr2str actual) in
57:  __check__ (actual = expect);

Expect: [|4.2; 7.6; 8.9; 8.5|]
Actual: [|4.2; 7.6; 8.9|]
--------------------------------------------------
==================================================
 0 /  1 tests passed

> make clean                         # remove all compiled/auxiliary files
rm -f *.cmo *.cmi *.mlt *.annot  test_sumfuncs test_abovefuncs test_revfuncs 

> make                               # make all of the required files
ocamlc -g -annot -c sumfuncs.ml
ocamlc -g -annot -c revfuncs.ml
ocamlc -g -annot -c abovefuncs.ml

> make test                          # test all of the required files
...
===TESTS for P1 sumfuncs.cmo===
./test_sumfuncs
Found 10 tests
RUNNING 10 tests
==================================================
Test  1: ok
...

===TESTS for P2 abovefuncs.cmo===
./test_abovefuncs
Found 10 tests
RUNNING 10 tests
==================================================
Test  1: ok
...

===TESTS for P3 revfuncs.cmo===
./test_revfuncs
Found 10 tests
RUNNING 10 tests
==================================================
Test  1: ok
...

Create a source file sumfuncs.ml which will have the following bindings in it.

let array_sum arr = ... ;;
(* val array_sum : int array -> int
   Return the sum of int array arr. Uses Array.length to calculate its
   length. Uses a ref to a summing int and a loop over the array
   elements. 

   REPL EXAMPLES:
   # array_sum [|1; 3; 5|];;
   - : int = 9
   # array_sum [|4; -3; 12; 2|];;
   - : int = 15
   # array_sum [||];;
   - : int = 0   
*)

let rec list_sum lst = ... ;;
(* val list_sum : int list -> int
   Return the sum of int list lst. Uses recursion and NO mutation.
   Uses List.hd and List.tl to get the head and tail of a list. 

   REPL EXAMPLES:
   # list_sum [1; 3; 5];;
   - : int = 9
   # list_sum [4; -3; 12; 2];;
   - : int = 15
   # list_sum [];;
   - : int = 0   
*)

Quick Start Tip:

• Copy the source code above which is can almost compile.
• Replace any ... with a valid return values for the type of the function.
• In this case, an int is expected so something like

  let array_sum arr =
    0                 (* returns 0 *)
  ;;
  

  and a similar change for list_sum will result in code that can be run against the tests.

• Try compiling on the command line with

  make sumfuncs.cmo
  

  and ensure that no errors are reported.

• Try running the automated tests against the code via

  make test-p1
  

  You will likely see may errors, but compatibility with the tests allows you to see progress as your code improves.

Aside from some cosmetic changes, this function should end up feeling similar to its implementation in other programming languages.

• Iteration is the easiest and mutation are the easiest means to solve implement the function.
• Make use of a ref to an int; it can be accessed using the ! operator and assigned using the := operator
• Note that array lengths can be determined using the module function Array.length arr
• Acquaint yourself with OCaml's syntax for array access: arr.(i). Keep in mind that they are 0-indexed
• Make use of a loop using the for/do/end syntax
• DO NOT make use of any higher-order functions such as folding at this time. Show you can write imperative code by hand.

This function will require some more thought as list elements cannot be directly indexed via an standard syntax. This rules out a loop and should instead cause lead one towards recursion.

• Note that the binding should start let rec list_sum .... The keyword rec allows the name being defined to be used in its own definition, a quintessential element of recursion.
• Use an if/else or other conditional structure to analyze cases
  • An empty list has sum 0
  • A list with at least one element (a head) should add the head value on to the result of summing the remainder of the list
• Make use if list functions to deal with the recursive case. Careful as calling these on an empty list will result in an exception.
  • List.hd will retrieve the first element of a list
  • List.tl will return the remainder of list after the first element
• DO NOT make use of any higher-order functions such as folding at this time. Show you can write recursive code by hand.
• DO NOT use any refs, mutation, or imperative code; no for or while looping

The following criteria will be checked in this problem.

Create a source file abovefuncs.ml which will have the following bindings in it.

let array_above thresh arr = ... ;;
(* val array_above : 'a -> 'a array -> 'a array

   Creates a new array which has only elements which are greater than
   parameter thresh in it. Elements from arr that are larger than
   thresh appear in the same order the return array as they do in arr.
   Uses two passes to count the elements above in arr, allocates
   another array of appropriate size, and then copies in elements from
   arr.  Does not modify the original array arr.

   REPL EXAMPLES:
   # array_above 0 [|0; 1; 2; 0|];;
   - : int array = [|1; 2|]
   # array_above 0 [|4; -2; -1; 7; 0; 3|];;
   - : int array = [|4; 7; 3|]
   # array_above 3 [|4; -2; -1; 7; 0; 3|];;
   - : int array = [|4; 7|]
   # array_above 1.5 [|4.2; 0.5; 1.2; 7.6; 8.9; 0.8; 8.5|];;
   - : float array = [|4.2; 7.6; 8.9; 8.5|]
   # array_above 0.0 [|4.2; 0.5; 1.2; 7.6; 8.9; 0.8; 8.5|];;
   - : float array = [|4.2; 0.5; 1.2; 7.6; 8.9; 0.8; 8.5|]
   # array_above 9.0 [|4.2; 0.5; 1.2; 7.6; 8.9; 0.8; 8.5|];;
   - : float array = [||]
   # array_above false [|false; true; false; true; true;|];;
   - : bool array = [|true; true; true|]
*)

let rec list_above thresh lst = ... ;;
(* val list_above : 'a -> 'a list -> 'a list

   Create a list which has only elements from lst that are larger than
   thresh.  Uses recursion to accomplish this in a single pass over
   the original list. Does not modify the original list lst.

   REPL EXAMPLES:
   # list_above 0 [0; 1; 2];;
   - : int list = [1; 2]
   # list_above 0 [0; 1; 2; 0];;
   - : int list = [1; 2]
   # list_above 0 [4; -2; -1; 7; 0; 3];;
   - : int list = [4; 7; 3]
   # list_above 3 [4; -2; -1; 7; 0; 3];;
   - : int list = [4; 7]
   # list_above 1.5 [4.2; 0.5; 1.2; 7.6; 8.9; 0.8; 8.5];;
   - : float list = [4.2; 7.6; 8.9; 8.5]
   # list_above 0.0 [4.2; 0.5; 1.2; 7.6; 8.9; 0.8; 8.5];;
   - : float list = [4.2; 0.5; 1.2; 7.6; 8.9; 0.8; 8.5]
   # list_above 9.0 [4.2; 0.5; 1.2; 7.6; 8.9; 0.8; 8.5];;
   - : float list = []
   # list_above false [false; true; false; true; true;];;
   - : bool list = [true; true; true]
*)

• Note that the function must be polymorphic: it works with any type of array. The greater than operator > is polymorphic to enable this.
• Make use of two "passes" through the data; i.e. loop once through the array then again.
• In the first pass, set up a ref to an integer and simply count how many elements are above the threshold given. Use an if condition for this.
• After determining the number of elements, allocate an array of appropriate size using the syntax Array.make length x. Here x is an item to fill the array with so; thresh is a good choice.
• In the second pass, insert every element above the threshold into the created array. This will require tracking the index for insertion likely using another ref.
• OCaml is a bit persnickety about multiple expressions in if/else statements, particularly multiple side-effects only statements. The begin/end syntax is useful for this as shown below.

  if condition then
    begin
      sideeffect stuff;
      sideeffect stuff;
     end
  

• DO NOT make use of any higher-order functions such as folding at this time. Show you can write imperative code by hand.

• Similar to the array version, this function is polymorphic so should work with any type of list
• let rec above suggests that a recursive definition should be used.
• You will need to use the double colon :: "cons" operator to construct a list. This operator attaches an element to the front of an existing list to produce a new list as shown in the below REPL session.

  # let l1 = [8; 6; 7];;
  val l1 : int list = [8; 6; 7]
  # let e1 = 3;;
  val e1 : int = 3
  # let l2 = e1 :: l1;;           (* tack 3 onto the front *)
  val l2 : int list = [3; 8; 6; 7]
  # let l3 = 19 :: l2;;           (* tack 19 onto the front *)
  val l3 : int list = [19; 3; 8; 6; 7]
  # l2;;                          (* l2 has not changed *)
  - : int list = [3; 8; 6; 7]
  

• DO NOT make use of any higher-order functions such as folding at this time. Show you can write recursive code by hand.
• DO NOT use any refs, mutation, or imperative code; no for or while looping

The following criteria will be checked in this problem.

Create a source file revfuncs.ml which will have the following bindings in it.

let array_rev arr = ... ;;
(* val array_rev : 'a array -> unit

   Reverses the given array in place. Uses iteration and mutation to
   do so efficiently. DOES NOT generate any internal copies of the
   parameter array.

   REPL EXAMPLES:
   # let a1 = [|1; 2; 3;|];;
   val a1 : int array = [|1; 2; 3|]
   # array_rev a1;;
   - : unit = ()
   # a1;;
   - : int array = [|3; 2; 1|]
   # let a2 = [|"a"; "b"; "c"; "d"; "e"; "f"|];;
   val a2 : string array = [|"a"; "b"; "c"; "d"; "e"; "f"|]
   # array_rev a2;;
   - : unit = ()
   # a2;;
   - : string array = [|"f"; "e"; "d"; "c"; "b"; "a"|]
   # let a3 = [|true; true; false; false; true;|];;
   val a3 : bool array = [|true; true; false; false; true|]
   # array_rev a3;;
   - : unit = ()
   # a3;;
   - : bool array = [|true; false; false; true; true|]
*)

let list_rev lst = ... ;;
(* val list_rev : 'a list -> 'a list

   Return a reversed copy of the given list. Does not (and cannot)
   modify the original list. Uses an internal recursive function to
   build the reversed list. The internal function is tail-recursive.

   REPL EXAMPLES:
   # list_rev lst1;;
   - : int list = [3; 2; 1]
   # lst1;;
   - : int list = [1; 2; 3]
   # let lst2 = ["a"; "b"; "c"; "d"; "e"; "f"];;
   val lst2 : string list = ["a"; "b"; "c"; "d"; "e"; "f"]
   # list_rev lst2;;
   - : string list = ["f"; "e"; "d"; "c"; "b"; "a"]
   # lst2;;
   - : string list = ["a"; "b"; "c"; "d"; "e"; "f"]
   # let lst3 = [true; true; false; false; true];;
   val lst3 : bool list = [true; true; false; false; true]
   # list_rev lst3;;
   - : bool list = [true; false; false; true; true]
   # lst3;;
   - : bool list = [true; true; false; false; true]
*)

• Note that the type of the function returns unit; this is an indication that side-effects will be used, in this case modification of the parameter array.
• Make use of the array assignment syntax

  arr.(i) <- elem;
  

  This mutates an array in place

• A loop will be required to traverse elements of the array.
• DO NOT make a copy of the array to achieve the reversal. Instead, repeatedly swap elements in the array. In an array of 10 elements indexed 0 to 9, this would mean swapping as follows:
  • 0th and 9th
  • 1th and 8th
  • 2nd and 7th
  • etc.
• DO NOT make a copy of the array: operate on it in place
• DO NOT make use of any library functions for reversal

• Note that the type of this function returns a list of the same kind as the original. It does not mutate the original
• Make use of a locally defined recursive helper function to traverse the list
• The helper should take two parameters, the remainder of the original list and a reversed list that is being constructed
• At each step in the recursive helper
  • Check if the end of the original list has been reached and return the reversed list if so
  • Otherwise, Peel off the head and tail of the original list
  • Attach the head to the reversed list being built
  • Recurse on the remainder (tail) of the original list with the slightly larger reversed list as the other argument
• After defining it, call the recursive helper with the entire original list as the first argument and an empty reversed list as the second argument
• DO NOT employ any mutation, global variables
• DO NOT make use of any library functions for reversal

The following criteria will be checked in this problem.

If creating a zip file is unfamiliar to you, refer to the following guide: Making Zips (tutorial)

Once your are confident your code is working, you are ready to submit. Ensure your folder has all of the required files. Create a zip archive of your lab folder and submit it to Canvas.

On Canvas:

• Click on the Assignments section
• Click on the appropriate link for this lab/assignment
• Scroll down to "Attach a File"
• Click "Browse My Computer"
• Select you Zip file and press OK

You may wish to review the policy on late project submission which will cost you late tokens to submit late or credit if you run out of tokens. No projects will be accepted more than 48 hours after the deadline.

http://www-users.cs.umn.edu/~kauffman/2041/syllabus.html#late-projects