Language Comparison

Overview

In this assignment, you will implement the same program in two different programming languages: OCaml and a language of your choice. Both implementations must:

• Expose exactly the same interface
• Follow the same specification
• Produce identical behavior on all valid inputs

Problem Specification

Your program reads a list of dependent tasks and must produce either:

• A valid order in which to complete all tasks, or
• The single word cycle if any dependency cycle exists

This is a deterministic, well‑specified problem.

Input Format

• Input is provided via standard input only

  • No command‑line arguments
  • Do not open or create any files

• The input contains a non‑zero, even number of lines

• Every pair of lines represents a dependency:

  • First line: task name
  • Second line: a task it depends on

This input is called the task list.

Task Name Rules

• ASCII characters only (no Unicode or accents)

• Each task name:

  • Starts at the beginning of the line
  • Extends to—but does not include—the newline
  • Is at most 60 characters long (this limit mainly exists to support C.)

Two tasks with the same name are considered the same task (string equality).

Example

Input

learn OCaml
read the OCaml documentation
do the programming assignment
learn OCaml

Interpretation

• To learn OCaml, you must first read the OCaml documentation
• To do the programming assignment, you must first learn OCaml

Output

read the OCaml documentation
learn OCaml
do the programming assignment

Cycles

If the task list contains any cycle, regardless of size or whether other parts are acyclic, your program must output: cycle

Example Cyclic Input

A
B
B
C
C
A

A depends on B, B depends on C, but C depends on A.

Output Rules

• Output must go to standard output only

• Do not write anything to standard error

• Do not write anything to a file

• Output must contain only:

  • A valid task order or
  • The word cycle (exactly)

Invalid Inputs

Duplicate task pairs (same dependency appearing twice) are invalid. The program behavior for such inputs is undefined. You will not be tested on invalid inputs

Choosing Among Unconstrained Tasks

If multiple tasks have no remaining dependencies, you must choose which to output next using ascending ASCII alphabetical order. This guarantees a unique, deterministic output for every valid input.

Example

B
A
B
C
D
B

Correct output:

A
C
B
D

Here, both A and C are initially unconstrained; since A < C, the former is chosen first.

More Complex Example

Task list:

B
A
C
D
C
E

Correct output:

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. A D E B C is incorrect and will receive no credit.

Submission

Submit a single ZIP file named project6-handin containing:

Required

• p6.ml — OCaml implementation
• p6.x - implementation in another language where x is the appropriate file extension
• README — plain ASCII text

README Content

Write several paragraphs addressing:

• Which language you implemented first
• How you represented dependencies
• Which language was hardest and why

Grammar, spelling, and clarity matter.

Grading Rubric (25 points total)

• 20 points – autograding

  • 10 points – OCaml implementation
  • 10 points – implementation in another language
  • Each failed test deducts 1 point (minimum 0)

• 5 points – clear description in README

  • 5 points – thorough discussion of design decisions including language comparisons
  • 2 points – vague or difficult to understand; omits important details
  • 0 points – little to no effort

• 5 points extra credit

  • +1 point each — perfect autograder score per extra language