# Assignment 1:  Comparing Languages(Prime Partitions)

Many but not all positive integers can be written as a sum of distinct primes.  The number 12, for example, can be written as either 5 + 7 or 2 + 3 + 7.  The numbers 4 and 6, on the other hand, have no partition into unique primes, and the number 9 has only one:  2 + 7.  This, the first graded assignment of the semester, asks you to enumerate all the ways of partitioning a given number n into a sum of one or more distinct primes, a + b + ... + m and to do so in 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 an integer n, your programs should write the appropriate sums to standard output.  If n = 20, for example, one of your programs might print

```    2 + 5 + 13
2 + 7 + 11
3 + 17
7 + 13```
You should print each partition only once.  Toward this end, you will probably find it easiest to write your programs in such a way that they print the addends in sorted order.  If the number n is prime, one of the lines of output, of course, will simply be n itself.  Note that straightforward solutions tend to be pretty slow.  Don’t be surprised if your program takes longer than you’re willing to wait for values of n over 200 or so.

The prime partition problem is naturally recursive, and can be solved in several ways.  The simplest and most elegant solutions employ 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, Ruby, and C# have true iterators, Ada (2012 version), Rust, and Swift have iterator objects, and OCaml has no special iterator support.  Prolog’s search mechanism can be used to create the equivalent of iterators, and yields a very elegant solution.  “Goroutines” can also be used to emulate iterators easily in Go.  Haskell provides enough machinery to build true iterators on top of the core language; you can find them in add-on packages.

If you already knew 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 much may depend on your past experience.

When run, your programs should generally read the integer n from standard input, and then output the appropriate sums to standard output, one per line, in arbitrary order.  The exception: for Prolog, please arrange for your program to instantiate some variable with successive sums (lists of addends) during backtracking, which you can trigger with repeated semicolon prompts (you’ll understand what that means after reading a bit about Prolog).

Some hints:

1. If you program with iterators, you may find it useful to define
1. An iterator `primes(a, b)` that generates all prime numbers between `a` and `b`, inclusive.
2. An iterator `prime_partitions(n, k)` that generates all prime partitions of `n` using primes greater than `k`.
Given n, your program as a whole would call `prime_partitions(n, 1)`.

2. You can easily find toy programs in all the candidate languages on the web (including on the companion material for the textbook). For many languages you may find it helpful to start with one of these toys:  it will already import appropriate libraries and contain examples of the control constructs, I/O calls, etc.

## 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 and Python interpreters and the Haskell interpreter and compiler are found in `/usr/bin`.  All the rest are in `/u/cs254/bin`, which you should add 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
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.
2. Build a solution based on dynamic programming.  What is the asymptotic complexity of this solution and of its more naive alternative?
3. What can you say about the function P(n), the number of distinct prime partitions of n?  Is there a closed form solution?  How does the function relate to other combinatorial problems—e.g., (non-prime) integer partition, set partition, and tree enumeration?  (A little number theory helps here, but you can learn a surprising amount by browsing obvious topics on Wikipedia.)
4. What about a lower bound on asymptotic complexity?  What is the best possible running time for this problem?

## Trivia Assignment

Before 5pm on Friday, September 9, send e-mail to `cs254@csug.rochester.edu` containing answers to the following questions:

1. Are you working alone or in a team?  If a team, who is your partner?
2. How many unique prime partitions does 24 have?  What are they?
3. What is the version number of each of the language implementations we are using?
4. What is the syntax used to write the string ```"hello, world"``` to standard output in C#?  In Ada?

## MAIN DUE DATE:

Sunday September 18, at 11:59pm; no extensions.
Last Change:  09 September 2016 /