Assignment 1: Comparing Languages
(Tree Enumeration)
This, the first graded assignment of the semester asks you to solve a simple problem in each of five different programming languages (six if you’re in 454):
● Ada
● OCaml or Haskell
● C#, Go, or Rust
● Python or Ruby
● Prolog
454 students must also write in Scheme.
The problem is Exercise 6.20 in the textbook:
Construct a program that outputs (in some order) all structurally distinct binary trees of n nodes. Two trees are considered structurally distinct if they have different numbers of nodes or if their left or right subtrees are structurally distinct. There are, for example, 5 structurally distinct trees of 3 nodes:
These are most easily output in “dotted parenthesized form”:
(((.).).) ((.(.)).) ((.).(.)) (.((.).))
(.(.(.)))
You can think of the parenthesized expressions as being generated by the following simple grammar:
T → a tree can be empty
T → (T.T) or a node with left & right children
Finding trees is a naturally recursive problem (iterative solutions are also possible). The easiest and most elegant solutions employ a recursive set of iterators, which are abstractions used to
drive a for loop. We will study iterators in Section 6.5.3; you may want to read ahead. In the terminology of that section, you’ll find that Python and C# have “true” iterators. Prolog’s search mechanism can be used to create the equivalent of iterators, and yields a very elegant solution. Ada and Scheme have no special iterator support; for these you’ll have to work with lists (or find some other solution—e.g., tasks in Ada). For what it’s worth, Java and C++ (which you can try for extra credit) have iterator objects, which are sort of half of what you want.
If you already knew all the languages, you’d probably find your task easiest in Prolog and hardest in Ada, with the other languages ranging in between. (Of course you probably don’t know all the languages already, so the unfamiliar ones will be the hardest.) A hint: the companion site for the textbook contains working versions of all the nontrivial examples in the book. For Ada and C# you might find it helpful to start with one of these: it will already import appropriate libraries and contain examples of the control constructs, I/O calls, etc.
When run, your programs should read a single integer n from standard input, and then output the appropriate trees to standard output (as dotted lists, one per line, in arbitrary order). For Prolog, which runs in an interpreter, please arrange for trees(n, L) to produce successive trees (values for L) in response to a semicolon prompt. For Scheme, please arrange for (trees n) to return a list of trees, each of which is a (nested) list.
Division of labor and writeup
You may work alone on this project or in teams of two. If you split up the languages, whoever takes Ada should probably do two; the other person should do three. However you divide the programming, each team member must write his or her own README file (no sharing of text on this allowed), and turn in the project separately (with all five or six programs, which will be the same as the partner’s code). This means, of course, that you’ll need to really understand your partner’s code.
Be sure to read the instructions on the grading page regarding the turn-in procedure and requirements. To turn in your code, use the following procedure, which will be the same for all assignments this semester: On a csug machine, put your write-up in a README.txt or README.pdf file in the same directory as your code, and (while still in that directory) run the script ~cs254/bin/TURN_IN. The script will package the contents of the directory (and any subdirectories) into a bundle and send it to the TAs for grading (so clean up any mess you might have in the directory first). Be sure your write-up (README file) describes any features of your code that the TAs might not immediately notice. In addition, for this assignment, your README file must compare and contrast the programming experience in the different languages you used (all five/six of them). What was easy? What was hard? Are there noticeable differences in speed? What do you like/dislike? Did you find iterators to be helpful?