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

This assignment has two parts. The first part introduces you to ISCAL (our assembly language) by implementing some simple functions. 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 (compiled) down to the language of the machine!

Part 1: Introduction to Assembly Language (25 Points)

First, you will write two short programs in ISCAL (ISC Assembly Language). Check out 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 simple factorial.isc program from class, and the recursive factorial program rfac.isc from class all in the directory /cs/cs60/assignments/assignment11/. You should use these programs or the IO program (io.isc) as the starting point for your programs. (You have permission to copy and modify any of these files as part of your own homework submissions.)

You will also want to add the following line to your .cshrc file in your home directory:

set path= ($path /cs/cs60/bin)

set path= (`/usr/local/bin/localpath`)

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. 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 went to eat some Foster's doughnuts.
   
   
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. This program should also 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 (60 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 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.