Computer Science 60
Principles of Computer Science
Fall 2003


Assignment 10: Assembly Language!
Due: Monday, November 10 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.

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. This page contains example code and thorough documentation of the assembly language. In particular, 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/assignment10/. You should use 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)
Add this line after the existing line 
set path= (`/usr/local/bin/localpath`)
After leaving the editor, type source .cshrc at the prompt. This will allow you to type isc at the prompt to invoke ISCAL. Alternatively, you can just run the ISCAL assembler without changing .cshrc by typing /cs/cs60/bin/isc.

  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 (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, we do the following: 
  hanoi(N-1, A, C)  // C represents the remaining peg other than A and B
  hanoi(1, A, B)
  hanoi(N-1, C, B)
(Chapter 6 of Professor Keller's book discusses this recursive solution in some detail, although the above description suffices to solve this problem.) 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
The first line was the user's input indicating that there are 3 disks that should be moved from peg 1 to peg 3. The first pair of lines of output indicate that a disk should be moved from peg 1 to peg 3. The next pair indicate that the next move is from peg 1 to peg 2, etc. Now the user is queried for more input (in case the user wants to solve a bigger hanoi problem, for example).

A few tips: Last modified October 2003 by Ran Libeskind-Hadas