PA1p is due 8/30 at 11:59pm Central.
PA1c is due 9/6 at 11:59pm Central.
Note: In previous offerings, students were required to use all 6 languages (Cool, Python, OCaml, Ruby, Haskell, and C). However, during Vanderbilt's Fall 2023 semester, you are only required to submit Cool and Python implementations.
Before starting this assignment, you will want to familiarize yourself with the command line (e.g., to use the reference compiler) and Python scripting without using Jupyter or Collab. Ultimately, as an upper level elective, you are expected to make your own setup work. If you need help getting started, please come to office hours. I also made a video tutorial on Linux fundamentals in a previous semester: Linux fundamentals video.
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: 1) Cool, and 2) Python. 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 a compiler for Cool, so it is important that you learn how Cool works now.
For this assignment, you must work alone. Subsequent assignments will allow you to work in pairs.
This assignment consists of two parts:
These items are separate on the autograder. You only need to turn in a readme.txt file for PA1c (detailed below).
Your program must take in a list of dependent tasks and output either (1) a valid order in which to perform them or (2) 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.
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 (stdout) only. Do not write anything to stderr.
There is no fixed limit on the number of lines in the task list, although there will always be an even number of lines greater than zero.
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.
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.
In addition to your code, you must also provide one test case, called testcase.list that follows the format above. We want you to gain practice writing test cases for your own submissions before making them. This is common practice in industrial software development, where managers expect you to test your code before you try to make merge requests. This is the same: you must provide at least one test case (and indeed, you should be testing more thoroughly locally) with your PA1p Python implementation.
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, but is certainly an option. Many students in previous semesters have implemented a Map structure in Cool to store adjacency lists.
You could solve the problem in the Python first However, translating into Cool requires more than just a line-by-line translation.
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. You are not required to watch any of these videos; they are merely a resource for helping you get started.
If you are still stuck, you can post on the forum, approach the TA 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. YouTube embedding is spotty. If necessary, click the "YouTube" button in the bottom right of the video frame to open the video in YouTube.
The videos below were made by a previous colleague when we co-taught the course at the University of Virginia. While they are still useful, please note that this semester's rubric applies, and assignment names and numberings may have changed.
Parts of the Cool language reflect functional programming (as opposed to object-oriented or imperative programming). For your Cool implementation, you may consider referring to the Cons/Nil approach to building lists (see the sample code).
There are two parts to this assignment. We expect you to finish PA1p (Python) first, then PA1c (Cool) a week later. We do not want you to fall behind. Please be sure to have your rosetta.py implementation and testcase.list file submitted to PA1p on the autograder, and both rosetta.cl and readme.txt submitted to the autograder for PA1c (Cool implementation).
This helps split the challenge of this assignment in two phases: (0) Can I write this program at all? and (1) Can I write this program in a new language I've never seen before?
Again, see the autograder for the two submission paths: PA1p and PA1c. You must submit files with the exact correct names:
The autograder will warn you if you do not submit files with correct names. Note that you have a limited number of submissions per day for each assignment (this is to encourage you to test locally before submission, a key aspect of industrial software engineering).
PA1 Grading (out of 25 points):