# Assignment 1:  Comparing Languages(Combinations)

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):

• C#, Go, Rust, or Swift
• Python or Ruby
• Prolog
454 students must also write in Scheme.

Given two integers, k and n, your program should output all combinations of k numbers chosen from {1, 2, ..., n}. So if, for example, you specify the values 2 and 4, you should see (in some order)

```    1 2
1 3
1 4
2 3
2 4
3 4```
You may print the members of each combination in ascending or descending order (your choice); but please don't otherwise scramble them.

Finding combinations 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 (my version is only 4 lines long).  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 various 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, most of your programs should take k and n (in that order) as command-line arguments, and then write combinations, one per line, to standard output.  For Prolog, please arrange for `combinations(k, n, L)` to produce successive combinations (values for `L`) in response to a semicolon prompt.  For Scheme, which runs in an interpreter, please arrange for `(combinations k n)` to return a list of combinations, each of which is a (nested) list.

Your programs should all run in time proportional to the length of the output.  Not all “obvious” programs will do so.  Behind this link, for example, is a Python program that produces the correct output, but takes time exponential in n, regardless of k.  In particular, it takes exponential time when k = n, even though the output is only one line long (try it for, say, k = n = 20).  (For what it's worth, my version of the better Python solution is actually a shorter program.)

## 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?

## Resources

We will be using the following language implementations.  The Ruby, Python, and Prolog interpreters, the Haskell interpreter and compiler, the Ada and Rust compilers, and the OCaml interpreter and compiler are found in `/usr/bin`.  The Scheme interpreter is found in `/usr/staff/bin`. The remaining implementations (for C#, Go, and Swift) are in `/u/cs254/bin`, which you should append to your `PATH` environment variable (ask a friend or one of the TAs if you don’t know how).

Compile your code with `gnatmake` (a wrapper for the GNU Ada translator).  It produces native executables.
C#
Compile your code with `mcs` (the Mono project C# compiler) and run with the `mono` JIT/run-time system.
Go
Run your code from the command line with `go`
Run your code under the `ghci` interpreter, or compile with `ghc` (the Glasgow Haskell Compiler) to produce native binaries.
Prolog
Run your code under the `swipl` interpreter.
Python
Run your code under the `python3` interpreter.
OCaml
Run your code under the `ocaml` interpreter, or compile with `ocamlc` to produce native binaries.
Ruby
Run your code under the `ruby` interpreter.
Rust
Compile your code with `rustc`.
Scheme (for 454 or extra credit)
Run your code at the command line with `plt-r5rs` or, under X, with the `drracket` GUI.  Be sure to configure the latter to use the R5RS language standard (it boots up expecting a vastly expanded language that will try to force you to use modules and other features you don’t want to have to learn at this point.)
Swift
Run your code under the `swift` interpreter, or compile with `swiftc`

You are welcome to work with other language implementations and/or platforms, but you must ensure that your final versions compile and run correctly using the implementations listed above.  We will be testing using only these.

I won’t be devoting lecture time to how to use these languages.  You’ll need to find on-line tutorials or other resources, and teach yourself.  Here are some decent starting points:

Principal web repository for everything Ada, including documentation, compilers, and tools.
An older repository, now going somewhat stale, but still with some excellent content.
The Ada 2012 Reference Manual.  (Note: this is a tough slog.  You’ll want to find a gentler tutorial—do a Google search.)
C#
Go
• go-lang.org/
Principal web site for Go.  Includes a nifty in-the-web-page interpreter with which to experiment.
Prolog
• www.swi-prolog.org/
The Prolog implementation we’re using.  Includes documentation and downloads (if you want to install it on your personal machine).
Python
• www.python.org/
Principal web site for Python, with documentation, tutorials, implementations, tools, and news from the user community.
OCaml
• ocaml.org/
Principal web site for OCaml, with documentation, tutorials, implementations, tools, etc.
Ruby
• ruby-lang.org/
Principal web site for Ruby, with documentation, tutorials, implementations, tools, etc.
Rust
• rust-lang.org/
Principal web site for Rust, with documentation, tutorials, implementations, tools, etc.
Scheme
• '(schemers . org)
Good general site for Scheme resources.
• racket-lang.org/
The Scheme implementation we’re using.  Actually supports a significantly larger extended language.  Includes documentation and downloads (if you want to install it on your personal machine).
• schemers.org/Documents/Standards/R5RS/
The Scheme R5 standard (the version you should use).  R7 is the latest standard, but you won’t be needing any of the newer features.
Swift

## Extra Credit suggestions

1. Try some other languages—from the lists above or beyond.  Java of C++ (with iterator objects) would be interesting.
2. Determine the asymptotic (big-O) space requirements of your various programs.  Are some of them better than others?

## Trivia Assignment

Before 5pm on Friday, September 8, complete the T1 trivia assignment found on Blackboard

## MAIN DUE DATE:

Sunday September 17, at 11:59pm; no extensions.
Last Change:  08 November 2017 /