The five languages are Ruby, OCaml, Python, C and Cool. You will use Ruby, OCaml and Python for PA2 through PA5 (you must use each one at least once; you may use your favorite one twice). In PA2 through PA5 you will write an interpreter for Cool, so it is important that you understand how Cool works now. The C (not C++) implementation is so that you can gain a better appreciation for time-saving features of higher-level languages (e.g., automatic memory management, first-class higher-order functions, object-oriented programming). No assignment in this class after PA1 will use C.
You can find tutorials, manuals and other resources for these languages on the main project webpage.
For this assignment, you must work alone. Subsequent assignments will allow you to work in pairs.
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 the C implementation easier; if you can support longer strings natively, feel free to do so.)
Example task list:
learn C read the C tutorial do PA1 learn C
read the C tutorial learn C do PA1
get a job have experience have experience work on a job work on a job get a job
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:
learn C read the C tutorial do PA1 learn C learn C read the C tutorial
Your program may not perform any other file I/O, such as creating a temporary file to keep track of some intermediate sorting results. You do not need to create any such temporary files to solve this problem.
learn C understand C pointers learn C read the C tutorial do PA1 learn C
read the C tutorial understand C pointers learn C do PA1
B A C D C E
A D E | \ / B C
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 example Cool programs that are distributed near the compiler.
Building and maintaining explicit graph structure is probably overkill.
Since you do not know the number of tasks in advance you will need some sort of dynamic memory allocation.
I recommend solving the problem in the Python, Ruby or OCaml first (depending on where you are most comfortable) and then just translating your solution into the others. Translating into Cool and 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? C's general hideousness?
For bonus brownie points, try to make your OCaml, Ruby and Python implementations as functional as possible (e.g., eschew side effects).
Don't know which languages to pick for the PA1c checkpoint? Look at the pa1-hint.zip file and pick languages that look like they would be easy to debug. Your first attempt (for PA1c) will probably contain the most algorithmic errors. After that it's more of a matter of translating it into other languages.
For the one-week PA1c checkpoint, you must have at least two 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 three other languages?
For PA1c you must turn in two source files. Use the following names:
The testcase.list file should contain a valid task list (it may or may not contain a cycle -- your choice). It may be used as one of the test cases to grade all of the submissions, so you have the chance to be certain of getting at least one right.
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 count.
We will perform the autograding on some unspecified test system. It is likely to be Solaris/UltraSPARC, Cygwin/x86 or Linux/x86. However, your submissions must officialy be platform-independent (not that hard with a scripting language). You cannot depend on running on any particular platform.
There is more to your grade than autograder results. See the Programming Assignment page for a point breakdown.
Your submission may not create any temporary files. Your submission may not read or write any files beyond its input and output. We may test your submission in a special "jail" or "sandbox".
Similarly, a strong argument could be made for The Shakespeare Programming Language, but it is not clear that it supports lexical analyzer generators or parser generators.