Harvey Mudd College
Computer Science 42
Assignment 6, Due Monday, Oct. 11, by 11:59pm

Programs that (really) make you go Hmmm... 

This week we'll continue our exploration into the Hmmm assembly language.  There are three required problems, and a couple of super-awesome, super-open-ended extra credit suggestions.  A word of advice: do the extra credit for the intellectual reward, not for the points.  The point to minute ratio for the EC options is pretty low, but the coolness to minute ratio is high if you complete either option (we think!).

Problem 1: Fibonacci Fun [20 points; individual]: Submitted in a file named hw6pr1.py

The Fibonacci sequence is one of the most famous sequences of numbers in mathematics. The first Fibonacci number is 1, the second Fibonacci number is 1, and in general, the next Fibonacci number in the sequence is the sum of the previous two. The first few numbers in the sequence are 1, 1, 2, 3, 5, 8, 13, 21.

Your job is to write a Hmmm assembly language program named Fibonacci that takes a single input from the user, call it n, and prints the first n Fibonacci numbers. Copy hw5pr2.py and rename it to be hw6pr1.py for this problem (and modify the contents of that file accordingly, INCLUDING THE HEADER COMMENT).

You will likely want to copy the contents of one register rX into another rY during the course of this problem. Take a look at the Hmmm reference page—the command for copying r1 into r2 is mov r2 r1. Note that it reads right-to-left (as with assignment statements, e.g., r2 = r1).

For this problem, you may assume that the input n will always be at least 2. Here is one sample input and output:

Enter number: 10
1
1
2
3
5
8
13
21
34
55

Problem 2: Recursion Power [20 points; individual]: Submitted in a file named hw6pr2.py

In this problem, you'll implement the recursive program that computes x raised to the power y.

Consider the following Racket program in which main gets input from the user and then calls a recursive "power" function that computes "x to the power y" and returns it to "main" to be printed.

(define (main)
  (let* (
         (x (read from user))  ; this isn't real Racket syntax, but the
         (y (read from user))  ; idea here is to get input from the user.
         (p (power x y))
         )
    (display p)))

(define (power x y)
  (if (= y 0)
      1
      (* x (power x (- y 1)))))

Repeat this maxim to yourself as you design your code: "Immediately before a function call, all of the function's 'precious belongings' must go onto the stack for safekeeping! This includes all of the values in registers that are important to the function including the return address where this function must jump back to when it's done. Immediately upon returning back from a function call, restore all of those values from the stack back into the registers in which they were originally stored."

If you would like to start from the recursive factorial example we covered in class, you'll find it below for easy copy-and-paste. However, please be very sure that you understand how this code works before you use it. This problem is intended to give you the confidence with implementing recursion that you'll need for the more challenging Towers of Hanoi problem, which is the last problem on this week's set. If you use this code "blindly", you won't get that valuable understanding that you'll need when you go to Hanoi!

# Recursive Factorial!
L = """
00 read r1         # read input and put into r1.       
01 loadn r15 42    # 42 is the beginning of the stack, put that address in r15.
02 call r14 5      # begin function at line 5, but first put next address (03) into r14.
03 write r13       # We're back from computing factorial of r1.  Write the answer.
04 halt            # halt!
05 jnez r1 8       # BEGINNING OF FACTORIAL FUNCTION!  Check if r1 is non-zero.  If it is go to line 8 and do the real recursion!
06 loadn r13 1     # otherwise, we are at the base case:  load 1 into r13 and...
07 jumpi r14       # ... return to where we were called from (address is in r14)
08 storei r1 r15   # place r1 onto the stack
09 addn r15 1      # increment stack pointer
10 storei r14 r15  # place r14 onto the stack
11 addn r15 1      # increment stack pointer
12 addn r1 -1      # change r1 to r1-1 in preparation for recursive call
13 call r14 5      # recursive call to factorial, which begins at line 5 - but first store next memory address in r14
14 addn r15 -1     # we're back from the recursive call!  Restore goods off the stack.
15 loadi r14 r15   # restoring r14 (return address) from stack
16 addn r15 -1     # decrement stack pointer
17 loadi r1 r15    # restoring r1 from stack
18 mul r13 r13 r1  # now for the multiplication 
19 jumpi r14       # and return!

"""

Your code will only receive credit if it faithfully translates the Racket pseudo-code for power. In particular, you need to use recursion; looping programs will receive no credit. Include a comment for each line of code, or almost every line, as shown above. Also, be sure to test your code thoroughly (though again, you will not submit your tests this week).

Problem 3: Towers of Hanoi [60 points; individual or pair]: Submitted in a file named hw6pr3.py

"The Towers of Hanoi" is a traditional puzzle involving moving different-sized disks among three pegs. The key constraint is that one is only allowed to place a disk onto an empty peg or another disk of larger radius.

An applet and a full explanation of the long history of this puzzle are available at this link.

Here is a summary of the algorithm for solving the puzzle, in Racket-style pseudocode.

(define (main)
  (let*  (
           (Disks (read from user))   ; This isn't real Racket syntax!
                                      ; Ask the user for the number of disks           
           (FromPeg (read from user)) ; Next, we ask the user for the
                                      ; starting peg (1, 2, or 3)
           (ToPeg (read from user))   ; Now we ask the user for the
                                      ; destination peg (1, 2, or 3)
          )
      (hanoi Disks FromPeg ToPeg)))   ; Call hanoi to print out
                                      ; the moves in the solution

(define (hanoi Disks FromPeg ToPeg)
       (if (= Disks 1)
           (begin 
               (print FromPeg)
               (print ToPeg)
           ; else
           (let  ((OtherPeg (the peg other than FromPeg and ToPeg)))
                            ; How do you find OtherPeg
                            ; without much work?  Is there
                            ; a formula?
               (begin
                   (hanoi (- Disks 1) FromPeg OtherPeg)
                   (hanoi 1 FromPeg ToPeg)
                   (hanoi (- Disks 1) OtherPeg ToPeg)))))

Your job is to "compile" (or translate) this code into HMMM assembly language as faithfully as possible. By "faithful" we mean that you will have a section of HMMM code that corresponds to "main" and a section that corresponds to "hanoi". The "main" part will read in three inputs from the user and then call "hanoi" to solve it. Your "hanoi" code will have a base case at the top to handle the situation where there is just one disk, and will have a general case afterwards with three recursive calls. Although the program may look long (about 80-85 lines of HMMM code is typical here), much of it is repeated several times and can be cut-and-pasted.

Here is some sample input and output:

Enter number: 1
Enter number: 1
Enter number: 3
1
3

Notice that in this example we asked to move 1 disk from peg 1 to peg 3. The program printed out the instructions "1" and then "3" indicating that we should move a disk from peg 1 to peg 3. That is, the instructions appear as pairs of numbers indicating the peg to move from and the peg to move to. Here's a bigger example of moving 3 disks from peg 1 to peg 2:

Enter number: 3 
Enter number: 1
Enter number: 2
1
2
1
3
2
3
1
2
3
1
3
2
1
2

Extra Credit Section:

Extra Credit Option 1: A Hmmm machine (up to +20 points; individual or pair): Submitted in files named hmmmMachine.circ and hmmmMachineReadme.txt

• You must maintain a PC and read instructions from memory to process them.
• You must implement at least two of the Hmmm instructions to get any credit for this assignment
• You must use a clock to synchronize your machine.  Each instruction may take more than one clock cycle to process if need be.

1. A high level description of how your machine is architected (so that we know what we're looking at when we open the logisim file.
2. A description of which instructions are implemented, and, for each instruction, a short sentence or two about how it is implemented.
3. A description of seveal test cases (e.g., a short Hmmmm program, perhaps) that we can use to test your machine.  Please provide use detailed instructions for how to load the program into your machine's memory, how to start the program and how we can verify its correctness.  You might also include a few Hmmm programs as support files that we can use to test your machine.

Extra Credit Option 2: A Racket to Hmmm compiler (up to +20 points; individual or pair): Submitted in a file named racketToHmmm.XX (where you replace XX with the proper extension for whatever language you choose) and compilerReadme.txt

• You're free to implement your compiler in whatever language you wish.  Racket itself is an option.  As is Java, Python, etc.  However, the grutors have to be able to understand and run your program so please don't choose a very obscure or hard to read language (in fact, if you want to use something other than Racket, Python, Java, C or C++, please talk to us).
• We recommend starting with a small subset of Racket and building your compiler slowly.
• Because Hmmm only handles integer types, we recommend you limit your compiler to handling only integers. 
• At the top level, all function arguments come by asking the user to type them at the command line.  Thus you can always expect to have one function, named main, in the programs you will compile that reads its input from the user.  This is where you will always start the program's execution.

1. A description of how to run your compiler, including what language it is implemented in and exactly how to run your compiler on a racket (.rkt) file.
2. A description of the subset of the Racket language that your compiler can handle.
3. Several tests, including input and correct ouput, that we can use to verify the correctness of your compiler.  You must include a justification of the correctness of the hmmm output that you provide.