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

First, a reminder that Exam 2 will be held in class on Thursday, April 14. 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, assembly language programming, and the beginning concepts in automata theory.

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!

Part 1: Introduction to Assembly Language (30 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 iterative factorial.isc program, and the recursive factorial program rfac.isc from class all in the directory /cs/cs60/assignments/assignment11/. 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!

Before you get started: checking if isc works...

Try out isc by typing

     > isc

     Usage: isc [-] [lstr <number of registers>] <code file>

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. 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 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.