PA1: Functional and Cool Programming

PA1a Due: 2017-01-31 at 11:50pm

PA1b Due: 2017-02-02 at 11:50pm

PA1c Due: 2017-02-07 at 11:50pm

Programming assignment 1 will give you time to practice functional programming and also give you a chance to become familiar with the Cool programming language. These skills will help prepare you for the remaining programming assignments.

For this assignment, you will be programming in Reason, a dialect of OCaml, and Cool. There are three parts to this assignment.

You may not work in a team of two people for this assignment.

Goal

For this assignment, you will implement several functions using the Reason and Cool programming languages. You will be provided with the interface for various functions or a specific problem, and you are responsible for implementing the specified functionality.

Specification

You must create seven artifacts:

  1. A Reason source file, pa1a.re, that contains your implementations of the function interfaces required for PA1a.
  2. A Reason source file, pa1b.re, that contains your implementations of the function interfaces required for PA1b.
  3. A Cool source file, pa1c.cl, that contains an implementation of topological sort.
  4. Test case testcase.list for PA1c.
  5. A plain ASCII text file called readme.txt describing your design decisions. See the grading rubric. A few paragraphs should suffice.
  6. A plain ASCII text file called references.txt providing a citation for each resource you used (excluding class notes, and assigned readings) to complete the assignment. For example, if you found a Stack Overflow answer helpful, provide a link to it. Additionally, provide a brief description of how the resource helped you.

Unless otherwise noted, you may use standard library functions.

PA1a

Create a Reason file named pa1a.re, and implement the following function interfaces:

  1. c_to_f 
    
let c_to_f = fun (temp:float) : float => {
	/* ... */
};
    Given a temperature in Celsius, return the temperature in Fahrenheit.
  2. split_tip 
    
let split_tip = fun (price:float) (n : int) : option float => {
	/* ... */
};
    Given the total price of a meal, and the number of ways to split the check n, return Some <float>, where float is the price with 20% tip split n ways. If n is less than 1 or price is less than 0, return None.
  3. triangle_area 
    
let triangle_area = fun (s1:float) (s2:float) (s3:float) : option float => {
	/* ... */
};
    Return Some <float> where float is the area of a triangle with those sides. If the sides do not form a valid triangle, return None.
  4. repeat 
    
let repeat = fun (f: 'a => 'a) (arg: 'a) (n: int) : 'a => {
	/* ... */
};
    Given a unary function f, an argument to the function arg, and an integer n, return f applied to arg n times.
  5. list_length 
    
let list_length = fun (l: list 'a) : int => {
	/* ... */
};
    Given a list, return the length of the list.
    You may not use the built-in List.length function.

PA1b

Create a Reason file named pa1b.re, and implement the following function interfaces:

  1. salutations 
    
let salutations = fun (l: list string) : list string => {
/* ... */
};
    Given a list of strings, return a list of strings with greetings. For example, if you are provided with the following input list
    Example input:
    ["Harry", "Ron", "Hermione", "Minerva", "Albus"]
    your code should return the following list
    Example output:
    ["Salutations, Harry", "Salutations, Ron", "Salutations, Hermione", "Salutations, Minerva", "Salutations, Albus"]
  2. dot_product 
    
let dot_product = fun (l1: list int) (l2: list int) : option int => {
/* ... */
};
    Given two lists of integers of equal length, return Some <int>, where int is the dot product of the two lists. If the lists are not the same length, return None.
  3. count 
    
let count = fun (l: list 'a) (e: 'a) : int => {
/* ... */
};
    Given a list of elements, l, and an element, e, return the number of occurrences of e in l.
  4. pre_order 
    
let pre_order = fun (t: int_tree) : list int => {
/* ... */
};
    Given an integer tree, t, return a list of the tree items in the order that they are visited by a pre-order traversal.
  5. int_tree_map 
    
let int_tree_map = fun (f: int => int) (t: int_tree) : int_tree => {
/* ... */
};
    Given a unary function, f, and an integer tree, t, return a new integer tree with f applied to all nodes of t.

Resources

For this part of the assignment, one resource is provided:

PA1c

Create a Cool program, pa1c.cl. Your program must take in a list of dependent tasks and either output a valid order in which to perform them or the single word cycle. This problem is just topological sort not-so-cleverly disguised. Feel free to look up how to do toposort on the internet and cite your references (but remember that you must turn in your own work; you may not copy someone else's code and claim it as your own).

Your program will accept a number of lines of textual input (via standard input). There are no command-line arguments — you must always read from standard input. Do not open a named file. Instead, always read from standard input.

That text input will contain a non-zero but even number of lines. Every two lines represent a pair of tasks. The first line gives the name of a task, the second line gives the name of a task that it depends on. This text input is also called the task list.

The task list will contain only standard ASCII characters (no UTF/8 Unicode or special accents). The goal is to test programming and program language concepts, not your internationalization abilities.

Each task name starts at the beginning of the line and extends all the way up to (but not including) the end of that line. So the newline or carriage return characters \r or \n are not part of the task name.

Example task list:
learn C
read the C tutorial
do PA1
learn C

The interpretation is that in order to learn C one must first read the C tutorial and that in order to do PA1 one must first learn C.

Desired output:
read the C tutorial
learn C
do PA1

If the task list contains a cycle of any size, your program should output exactly and only the word cycle.

Example cyclic input:
get a job
have experience
have experience
work on a job
work on a job
get a job

Even if the task list contains a few non-cyclic parts, any single cycle forces you to output only the word cycle.

Always output to standard output only. Do not write anything to stderr.

There is no fixed limit on the number of lines in the task list (although it is not zero and it is even).

Two tasks with the same name are really just the same task. Use standard string equality.

Duplicated pairs of tasks are not allowed.

Example duplicated pairs:
learn C
read the C tutorial
do PA1
learn C
learn C
read the C tutorial

The above task list is not valid input because the pair learn C/read the C tutorial appears twice. Program behavior if the task list contains a duplicate pair is undefined. You will not be tested on it.

Your program may not cause any other file I/O to be performed, such as creating a temporary file to keep track of some intermediate sorting results or writing to stderr (or even causing the interpreter to write a warning to stderr). You do not need any such temporary files or stderr-printing to solve this problem.

Choosing Among Unconstrained Tasks

If there are multiple outstanding unconstrained tasks, your program should output them in ascending ASCII alphabetical order. That is, if you ever have two or more tasks, each of which has no remaining dependencies, output the one that comes first ASCII-alphabetically. (This constraint makes your program deterministic; for any given input there is only one correct output.)

Example:
learn C
understand C pointers
learn C
read the C tutorial
do PA1
learn C

Because r comes before u, your output should be:

Correct output:
read the C tutorial
understand C pointers
learn C
do PA1

To put it another way, consider this task list:

Example task list:
B
A
C
D
C
E

Which yields a dependency graph like this: 

A  D E
|  \ /
B   C

The proper ordering for this set of tasks is A B D E C. Note that B comes before D and E, even though B depends on A. This is because, once A is finished, B is free to go and it comes first alphabetically. You may want to consider this requirement when you pick your sorting algorithm. Given this requirement the answer A D E B C is incorrect and will receive no credit.

Resources

For this part of the programming assignment, two coding resources are available:

Commentary

Documentation is your friend! Here are some external resources you might find helpful:

Recall that Reason is a dialect of OCaml. You are able to make use all of OCaml's standard library and pervasives as a result. While it is possible to implement all of the function interfaces on your own, you may find it easier to use library functions in some cases (check out the List module in particular).

When implementing code in Reason, make a particular effort to use local bindings to:

You will most likely need to define recursive helper functions. To improve the performance of your code, be sure to make your functions tail-recursive whenever possible.

Take a look at the files in pa1c-hint.zip. You could do worse than using them as starting points.

If you're having trouble writing anything reasonable in Cool, don't forget to look at the other example Cool programs.

Building and maintaining an explicit graph structure is probably overkill.

Because you receive extra credit for a working Python implementation (see the Grading Rubric below), we recommend that you complete the task in Python first. That way you can be sure that you understand the toposort algorithm in a familiar language before you try it in an unfamiliar one. Once you have it working in Python, you translate that into Cool (see the Video Guides for an example of doing the same problem in Python and then OCaml). The automated grading server will grade any Python implementation you submit, giving you useful feedback on algorithmic correctness. This "Python-first" approach ends up being mathematically optimal for most students.

If you are still stuck, you can post on the forum, approach the TAs, or approach the professor.

Video Guides

Wes Weimer has developed a number of Video Guides that you might find helpful. The Video Guides are walkthroughs in which Wes manually completes and narrates, in real time, a similar assignment. They include coding, testing and debugging elements.

These videos are considered an outside resource for completing this assignment. Be sure to note these videos in your references.txt if you use them.

Note: Wes's videos use a different submission site from this class.

Reminder: You can watch YouTube videos at 1.5x speed with full audio.

What to Submit for PA1a

You must turn in a zip file containing these files:

What to Submit for PA1b

You must turn in a zip file containing these files:

What to Submit for PA1c

You must turn in a zip file containing these files:

The readme.txt file should be a plain ASCII text file (not a Word file, not an RTF file, not an HTML file) describing your design decisions. What library functions did you use? How did you store the (implicit) graph in PA1c? What was the biggest challenge of using Reason? Cool? One or two English paragraphs should suffice. Spelling, grammar, capitalization and punctuation all count.

Working in Pairs

You may not work in pairs for this assignment.

Legacy Grading

There is no legacy grading for this assignment.

Grading Rubric

PA1 Grading (out of 50 points):