PA1 — The Rosetta Stone

The Rosetta Stone aided linguistic understanding by providing the same text in three different languages. In this project you will implement the same simple program in two separate languages: OCaml and Cool. Both of your implementations will have exactly the same interface, will otherwise adhere to the same specification, and should behave exactly the same way.

In PA2 through PA5 you will write an interpreter for Cool, so it is important that you learn how Cool works now.

To practice or test your skills, you may also submit C, Haskell, JavaScript, Python, or Ruby implementations. These will be tested, and can earn you extra credit, but are not necessary for your grade.

For this assignment, you must work alone. Subsequent assignments will allow you to work in pairs.

Specification

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.

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. Each task name is at most 60 characters long. (This limit is to make any C implementation easier. Cool and OCaml both support longer strings natively, and can thus ignore this length limit.)

Example task list:

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 for this example:

If the task list containts a cycle of any size, your program should output exactly and only the word cycle. Example cyclic input:

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. For example:

... that 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.

Specification — 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:

Because r comes before u, your output should be:

To put it another way, consider this task list:

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 programming assignment, two coding resources are available:

• pa1-hint.zip — provides concrete implementations of "task list reversal" (a similar, but simpler, problem) in every language associated with this course
• pa1-testcases.zip — includes a number of test inputs and expected outputs so that you can test your programs before submitting
• pa1-testcases-osx.zip — as above, but with unix linefeed formatting in all text files for use in Mac OS X

Commentary

This problem is just topological sort not-so-cleverly disguised. Feel free to look up how to do toposort on the internet (but remember that you must turn in your own work; you may not copy someone else's code and claim it as your own).

Take a look at the files in pa1-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.

You could solve the problem in the Python, Ruby or OCaml first (depending on where you are most comfortable) and then just translate your solution. Translating into Cool, Haskell, JavaScript or C will not be as easy, however.

Use this as an opportunity to see what you like about various languages. What do you think of Python's enforced tabbing? How about ML's abysmal error reporting? Ruby's below-par execution speed? Haskell's IO Monad? JavaScript's more asynchronous I/O model? C's general hideousness?

For bonus brownie points, try to make any OCaml, Haskell, JavaScript, Ruby or Python implementation as functional as possible (e.g., eschew side effects).

Video Guides

A number of Video Guides are provided to help you get started on this assignment on your own. The Video Guides are walkthroughs in which the instructor manually completes and narrates, in real time, a similar assignment. They include coding, testing and debugging elements.

If you are still stuck, you can post on the forum, approach the TAs, or approach the professor. The use of online instructional content outside of class weakly approximates a flipped classroom model. Click on a video guide to begin, at which point you can watch it fullscreen or via Youtube if desired.

Hints

Because you receive extra credit for a working Python (or Ruby, if you prefer) 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 or OCaml (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.

What To Turn In For PA1c

PA1c is a checkpoint to make sure that you do not fall behind on PA1. You have about two weeks to complete all of PA1, but if you try to do it all at the last minute you're probably doomed to failure.

For the one-week PA1c checkpoint, you must have one of the implementations done. This separates the project into two phases: (0) Can I write this program at all? and (1) Can I write this program in multiple languages?

For PA1c you must turn in one source file. Use the following names:

1. rosetta.cl — Cool implementation
   or
2. rosetta.ml — OCaml implementation

You may also submit Python, Ruby, JavaScript, Haskell or C implementations for PA1 extra credit. Each of your source files should have one of those names (e.g., rosetta.whatever).

What To Turn In For PA1

For PA1c you must turn in two source files and two other files. Use the following names:

1. rosetta.cl — Cool implementation
2. rosetta.ml — OCaml implementation

You may also submit Python, Ruby, JavaScript, Haskell or C implementations for PA1 extra credit. You must also submit these two files:

3. testcase.list — a valid task list that you made up
4. readme.txt — your README file

The testcase.list file should contain a valid novel task list (it may or may not contain a cycle — your choice).

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. Which language did you start with? How did you store the (implicit) graph? Which language was the hardest? One or two English paragraphs should suffice. Spelling, grammar, capitalization and punctuation all count.

Extra Credit

The submission grading server will accept and report on any of the following languages, if you happen to submit them:

1. rosetta.c — C implementation
2. rosetta.cl — Cool implementation
3. rosetta.hs — Haskell implementation
4. rosetta.js — JavaScript implementation
5. rosetta.ml — OCaml implementation
6. rosetta.py — Python implementation
   and/or
7. rosetta.rb — Ruby implementation

Note that only the Cool and OCaml implementations are required for your grade. The others cannot hurt you in any way, but can provide extra credit if you complete them perfectly.

Grading Rubric

PA1 Grading (out of 25 points):

• 20 points — autograding
  • 10 points — autograder tests for PA1c (either OCaml or Cool)
  • 10 points — autograder tests for PA1 (either OCaml or Cool, the other one)
  • The scoring is proportional: if there are 8 tests for PA1c and your best submission passes 4 of them (50%), you will receive 5/10 points for PA1c (50%).
• 4 points — for a clear description in your README
  • 4 — thorough discussion of design decisions (including language comparisons) and choice of test cases; a few paragraphs of coherent English sentences should be fine
  • 2 — vague or hard to understand; omits important details
  • 0 — little to no effort, or submitted an RTF/DOC/PDF file instead of plain TXT
• 1 point — for a valid testcase.list file

• 5 points extra credit — for extra languages
  • 1 point extra credit — perfect autograder test results for C
  • 1 point extra credit — perfect autograder test results for Haskell
  • 1 point extra credit — perfect autograder test results for JavaScript
  • 1 point extra credit — perfect autograder test results for Python
  • 1 point extra credit — perfect autograder test results for Ruby