CMSC 330, fall 2016

Organization of Programming Languages

Project 2a - OCaml basics

Due 11:59pm Sep 23, 2016

Errata

  • Part A,B,C is changed to Part 1,2,3. Everything is due on 09/23.
  • Testing instructions are updated on 09/19. Read README for details.

Introduction

The goal of this project is to get you familiar with programming in OCaml. You will have to write a number of small functions, each of whose specification is given below. In our reference solution, each function's implementation is typically 3-6 lines of code; in a couple of cases you will want to write a helper function which will add another 3-6 lines.

This project is due in one week! We recommend you get started right away, going from top to bottom, and the problems get increasingly more challenging.

Getting Started

Download the following archive file p2a.zip and extract its contents.

Along with files used to make direct submissions to the submit server (submit.jar, .submit, submit.rb), you will find the following project files:

You may want to use functions from testUtils.ml for printing debugging messages, but your actual submission in basics.ml should not print any output nor should it depend on the testUtils.ml file in any way.

To run an individual test, you can type commands like ocaml testRecursion1.ml. The output from the test will be printed to the console. You should compare it to the corresponding .out to see if it is correct (this is what goTest.rb does).

Note that you must implement your functions with the exact parameter and return type specified, or else the submit server tests will fail.

For this project the only OCaml libraries you are allowed to use are those defined in the Pervasives module loaded by default. You are not allowed to use library functions found in any other modules, particularly List and Array.

Part 1: Simple functions

Write the following functions:

Name Type Return value Example
head_divisor l int list -> bool true if the head of the list divides the second element of the list
false otherwise
head_divisor [1;2] = true
head_divisor [2;5] = false
tuple_addr t int * int * int -> int the sum of the tuple's elements tuple_addr (1,2,3) = 6
tuple_addr (-10,50,30) = 70
caddr_int int list -> int the second element of the list
-1 if the list has 0 or 1 elements
caddr_int [1;2;3] = 2
caddr_int [1] = -1

Part 2: Simple Curried Functions

A curried function is one that takes multiple arguments "one at a time". For example, the following function sub takes two arguments and computes their difference:

   let sub x y = x - y
The type of this function is int -> int -> int. Technically, this says that sub is a function that takes an int and returns a function that takes another int and finally returns the answer, also an int. In other words, we could write
   sub 2 1
and this will produce the answer 1. But we could also do something like this:
   let f = sub 2 in
   f 1
and this will also produce 1. Notice how we call sub with only one argument, so it returns a function f that takes the second argument. In general, you can think of a function f of the type
   t1 -> t2 -> t3 -> ... -> tn
as a function that takes n-1 arguments of types t1, t2, t3, ..., tn-1 and produces a result of type tn. Such functions are written with OCaml syntax
   let f a1 a2 a3 ... = body
where a1 has type t1, a2 has type t2, etc.

Implement the following simple, curried functions:
Name Type Return value Example
mult_of_n x y int -> int -> bool whether x is a multiple of y mult_of_n 5 5 = true
mult_of_n 2 3 = false
triple_it x y z 'a -> 'b -> 'c -> 'a*'b*'c a tuple containing the three arguments, in order triple_it 5 5 5 = (5,5,5)
triple_it "hello" "b" "a" = ("hello","b","a")
maxpair (x,y) (m,n) 'a*'b -> 'a*'b -> 'a*'b (x,y) if it is larger than (m,n), according to lexicographic ordering
(m,n) otherwise (see note about comparison functions below)
maxpair (1,2) (3,4) = (3,4)
maxpair (1,2) (1,3) = (1,3)

The OCaml comparison functions (=,<=,>=,<, and >) are polymorphic, so you can give them any two arguments of the same type.

Part 3: Recursive Functions

The rest of the project asks that you implement a number of recursive functions, many of which compute on lists.
Name Type Return value Example
power_of x y int -> int -> bool returns true if y is a power of x
false otherwise
power_of 2 8 = true
power_of 0 5 = false
prod l int list -> int the product of all elements in l
1 if l is empty
prod [5;6] = 30
prod [0;5;3] = 0
unzip l ('a*'b) list -> ('a list)*('b list) a pair of lists consisting of the all first and second elements, respectively, of the pairs in l unzip [(1,2);(3,4)] = ([1;3],[2;4])
unzip [(3,7);(4,5);(6,9)] = ([3;4;6],[7;5;9])
maxpairall l (int*int) list -> int*int the largest pair in input list l, according to lexicographic ordering
(0,0) if l is empty
maxpairall [(1,2);(3,4)] = (3,4)
maxpairall [(1,2);(1,3);(0,0)] = (1,3)
addTail l x 'a list -> 'a -> 'a list a new list where x is appended to the end of l addTail [1;2] 3 = [1;2;3]
get_val x n int list -> int -> int element of list x at index n (indexes start at 0)
-1 if n is outside the bounds of the list
get_val [5;6;7;3] 1 = 6
get_val [5;6;7;3] 4 = -1
get_vals x y int list -> int list -> int list list of elements of list x at indexes in list y,
-1 for any indexes in y are outside the bounds of x (as with get_vals)
elements must be returned in order listed in y
get_vals [5;6;7;3] [2;0] = [7;5]
get_vals [5;6;7;3] [2;4] = [7;-1]
list_swap_val b u v 'a list -> 'a -> 'a -> 'a list list b with values u,v swapped
change value of multiple occurrences of u and/or v, if found
change value for u even if v not found in list, and vice versa
list_swap_val [5;6;7;3] 7 5 = [7;6;5;3]
list_swap_val [5;6;3] 7 5 = [7;6;3]
index x v 'a list -> 'a -> int index of rightmost occurrence of value v in list x
(indexes start at 0)
-1 if not found
index [1;2;2] 1 = 0
index [1;2;2;3] 2 = 2
index [1;2;3] 5 = -1
distinct l 'a list -> 'a list a new list that contains the distinct elements of l, in the same order they appear in l distinct [1;2;2] = [1;2]
distinct [2;1;2;2;3] = [2;1;3]
find_new x y 'a list -> 'a list -> 'a list list of members of list x not found in list y
maintain relative order of elements in result
find_new [4;3;7] [5;6;5;3] = [4;7]
find_new [5;6;5;3] [4;3;7] = [5;6;5]
power_list l int list -> bool true if each consecutive element is a power of the previous, false otherwise
return true for []
power_list [3;9;81] = true
power_list [9;7;5] = false

Submission

You can submit your project in two ways:
  • Submit your basics.ml file directly to the submit server by clicking on the submit link in the column "web submission".

    Next, use the submit dialog to submit your basics.ml file directly.

    Select your file using the "Browse" button, then press the "Submit project!" button. You do not need to put it in a Jar or Zip file. Some students have mentioned problems with using Internet Explorer, because submissions being extracted in directories (e.g., "C:\My Documents\330\basics.ml") where the submit server could not find them. The problems went away when switching to the Mozilla Firefox browser.

  • Submit directly by executing a Java program on a computer with Java and network access. Use the submit.jar file from the archive p2a.zip. To submit, go to the directory containing your project, then either execute submit.rb or type the following command directly:

    java -jar submit.jar

    You will be asked to enter your class account and password, then all files in the directory (and its subdirectories) will be put in a jar file and submitted to the submit server. If your submission is successful you will see the message:

    Successful submission # received for project 2a

Hints and Tips

  • Be sure you have read and understand the project grading policies in the course syllabus. Do this well in advance of the project due date.

    Academic Integrity

    The Campus Senate has adopted a policy asking students to include the following statement on each assignment in every course: "I pledge on my honor that I have not given or received any unauthorized assistance on this assignment." Consequently your program is requested to contain this pledge in a comment near the top.

    Please carefully read the academic honesty section of the course syllabus. Any evidence of impermissible cooperation on projects, use of disallowed materials or resources, or unauthorized use of computer accounts, will be submitted to the Student Honor Council, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to project assignments. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. Full information is found in the course syllabus---please review it at this time.

  • Web Accessibility