Assignment 10: Assembly Language!
Due: Monday, April 10 by 11:59 PM

First, a reminder that Exam 2 will be held in class on Wednesday, April 12. You may bring a 8.5 by 11 sheet with writing on both sides. The exam will cover material covered since the last exam. This includes the more advanced features of rex, Prolog, computer design, and assembly language programming.

This assignment has two parts. The first part introduces you to ISCAL (our assembly language) by implementing an iterative and recursive version of the power function. The second part involves writing a solution to the Towers of Hanoi puzzle in ISCAL. The objective of this assignment is to demonstrate how sophisticated programs (you MUST agree that recursion is "sophisticated" :^) ultimately get translated, i.e., compiled, down to the language of the machine!

You should have abundant comments in your code. Part of your grade will be based on commenting. Assembly language is hard to read and you should comment your code as you write it. This will save you time when you go back to look at your own code. We promise! Please see the sample code in /cs/cs60/assignments/assignment10 for an example of what constitutes good commenting. Many assembly language programmers have a comment for every line of code. You can have slightly fewer comments if you wish, but you should have enough comments that someone else reading your code can easily understand exactly what your code is doing as they read it.

First, you will write two short programs in ISCAL (ISC Assembly Language). Although everything you need to do this assignment was covered in class by Wednesday's lecture, you might still wish to refer to the on-line documentation on ISCAL as well as a page with just the ISCAL instruction set. These pages contain example code and thorough documentation of the assembly language.

Notice that by using isc -t you will be running in trace mode. This can be quite useful! You will find the basic IO file io.isc, the iterative factorial.isc program, and the recursive factorial program rfac.isc from class all in the directory /cs/cs60/assignments/assignment10/. You should use these programs as a starting point for your programs. You have permission to copy and modify any of these files as part of your own homework submissions -- please do!

To use ISCAL, you may either type /cs/cs60/bin/isc OR you can set up a shortcut by doing the following:

1. In your home directory on turing, edit the file .zshrc using your favorite editor (e.g. emacs, vi, pico). (You'll notice that when you type ls in your home directory, you won't see this file listed. Any file whose name begins with a period is not listed by ls. These are usually special "configuration" files which are used to define all kinds of settings. However, you CAN see these files listed if you type ls -a.)
2. On or around line 19 of this file, you'll see a line

   #export PATH=$PATH:/cs/cs60/bin
   

   Remove the "#" symbol. Now save the file and exit the editor.
3. Next, either logout and then log back into turing OR just type source .zshrc at the turing prompt. (You only need to do this just this one time!)

Part 1: The Power Problems (30 Points)

1. First, write a simple ISCAL program that prompts the user for two integers X and Y. The program then prints out X raised to the power Y. The program then repeats. (You can terminate by typing CTRL-C). You may assume that both inputs will be greater than or equal to zero. Also, 0 to the 0 power should return 1. Submit this program in a file called power.isc. For example, here is some sample input and output:

         2 3
         8
         10 2
         100
       

   First the user entered 2 and 3 and the program printed 8. Then the user entered 10 and 2 and the program printed 100. Then the user typed CTRL-C and ended the program.
   
   
2. Now write an ISCAL program that does the same thing but uses recursion instead of iteration. In other words, the program should effectively be implementing the following rule:

       power(X, Y)
       {
         if (Y == 0)
           return 1;
   
         else
         {
           return X * power(X, Y-1);
         }
       } 
       

   You will need to implement a stack as we discussed in the example in class. Like power.isc, this program should repeatedly take 2 inputs and produce an output until the user types CTRL-C. Submit this program in a file called recpower.isc.

Part 2: Towers of Hanoi Revisited (70 Points)

In this part of the assignment you will write an ISCAL program called hanoi.isc that prints out a solution to the Towers of Hanoi problem given three pegs and an arbitrary number of disks. In particular, you must implement the recursive solution to this problem.

The recursive solution works like this: Let hanoi(N, A, B) represent the problem of moving N disks from peg A to peg B. To solve this problem, we break it up into three recursive steps: First move the top N-1 disks from peg A to the remaining peg, C. Then move the remaining 1 disk from peg A to peg B. Finally, move the N-1 disks on peg C to peg B. That is, using Ran++ syntax, we do the following:

hanoi(N, A, B)
{  
  if (N == 1) // Base case!
    {
      print "Move disk from peg" + A + "to peg" + B;
      return;
    }
  else 
    {
      let C denote the "other" peg;  // Wow!  Ran++ syntax is convenient.
      hanoi(N-1, A, C);  
      hanoi(1, A, B);    
      hanoi(N-1, C, B);
      return;
    }
}

Your assembly language program should be an accurate representation of the program above. That is, it should have a base case for moving 1 disk and if the base does not apply then it should have 3 recursive calls to the function.

Your program should obtain three numbers from the user: The number of disks, the number of the peg on which the disks are initially placed, and the number of the peg on which the disks should be placed at the end. The program then prints out a solution in the following format: There is one number (1, 2, or 3) on each line. Each pair of lines is interpreted as a move. Here's an example of running isc hanoi.isc:

3 1 3
1
3
1
2
3
2
1
3
2
1
2
3
1
3

A few tips:

• Be sure to follow the above convention regarding input: The three inputs are the number of disks, followed by the starting peg, followed by the ending peg. Also use our output convention. We'll be grading your program, in part, using an automatic tester which assumes these IO conventions.
  
  
• Don't use the variable from in your ISCAL program. It's reserved already.
  
  
• Think the solution out carefully before implementing it. Assembly language debugging with the trace feature is helpful, but it's much easier if the logic of your program is correct from the start.
  
  
• Write your code as faithfully to the Ran++ code above. That is, start with a test for the base case. If the best case does not apply, jump to a later piece of code for the general case. The general case has three recursive calls. Before each recursive function call, place all of your "precious belongings" on the stack. Immediately after returning from the function call, restore all of these belongings off of the stack. You might find it tempting to be clever and avoid pushing some things on the stack, but this is a recipe for bugs. Try to follow the mindless rule: Before a function call everything goes onto the stack and afterwards its all restored off the stack. This is the secret to ALL happiness.