Home
Syllabus
Schedule
Projects
Tests
Resources
Piazza
Submit Server
Grades Server

CMSC 330, summer 2016

Organization of Programming Languages

Project 2a - OCaml basics

Due 11:59pm Mon, Jun 13, 2016

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
mult_of_five x int -> bool true if x is a multiple of 5
false otherwise 		mult_of_five 5 = true
mult_of_five 1 = false
sum_upto_three ls int list -> int the sum of the list's elements up to the first three sum_upto_three [1] = 1
sum_upto_three [1;2;3] = 6
sum_upto_three [1;2;3;4;5] = 6
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
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]
is_sorted x 'a list -> bool true if elements in x are in sorted order, false otherwise
return true for [] 		is_sorted [5;5;7;9] = true
is_sorted [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