Assignment 11: Assembly Language! [200 points]
Due: Friday, December 1 by 11:59 PM

This assignment has three 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!

In the third part, you will be solving the same problem in ALL FOUR languages that we have used in this course: Java, rex, prolog, and ISCAL. The goal of this part is both to reinforce your comfort with these languages and also to help you identify the relative merits of using different languages. Therefore, there is also a short problem that asks you to compare and contrast the relative strengths and weaknesses of two of the languages for solving this problem.

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/assignment11 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 Tuesday'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/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!

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

Part 3: Stock Market Profit (100 Points)

Here's the story: You've been hired as the Chief Technical Officer of the Wall Street firm Weil, Proffet, and Howe. The firm's specialty is assessing the past history of the stock market. In this problem, you will be given an array (or a list, if you are using rex or prolog) of positive integer values where the element at position i in the array indicates the value of a share of Millisoft stock on day i.

That is, if the array (or list) has length n, it represents a history of n days of the values of this stock. Our objective is to find the maximum profit that could be made by purchasing a single share on some day and selling on that day or later. (Buying and selling on the same day makes 0 profit, so you can't do worse than that!) Remember, you cannot sell on a day before your buy day!

For example, consider the array A[1] = 100, A[2]=30, A[3]=32, A[4]=35, A[5] = 7. Note that although the lowest value of the stock is 7 and the highest value is 100, we cannot make 100-7=93 dollars profit because we cannot sell before we buy! The best we can do here is to buy on day 2 and sell on day 4 for a profit of 35-30 = 5 dollars.

Your job is to write four different programs to solve the stockmarket problem: One in Java, one in rex, one in prolog, and one in ISCAL. Make sure to comment your code in all cases.

Please submit all your files for this part under problem 3 using cs60submit. Here are the details for this problem:

Part 3a: Java (15 Points)

In the directory /cs/cs60/assignments/assignment11 you will find several files: SMHelper.java and StockMarket.java contain code and prices1.txt and prices2.txt contain stock market prices.

Copy these files into your directory. The first file, SMHelper.java contains some code for reading data from files. You don't need to touch it (although you're welcome to look at and see what's there - you'll discover that it has some extra features that we'll be using again in a few weeks).

Take a look at the file StockMarket.java. You'll notice that it has a main method which uses SMHelper to read in some stock prices from a file. After obtaining the stock market prices and putting them in an array, it calls the function solve by passing in the array. You will write the REAL part of this program, namely the solve function. This function computes the maximum profit obtainable and returns that value to main which then prints it.

How do you compile and run this program once you've written the code? First compile SMHelper.java. Then compile StockMarket.java. Then run it by typing java StockMarket prices1.txt or you can use another file (that you create) with stock prices other than prices1.txt or prices2.txt.

Notice that the format of these stock price files is as follows: The first line contains the number of stock prices. Then, each subsequent line contains a single stock value. After the very last stock value be sure to have a carriage return (that is, hit the RETURN or ENTER key after the last stock value).

Submit your StockMarket.java file using cs60submit.

Part 3b: Rex (15 Points)

  rex> stockmarket([2, 4, 1, 10]);
  9

  rex> stockmarket([4, 3, 2, 1]);
  0
  

Place your code in a file called stockmarket.rex and submit it using cs60submit.

Part 3c: Prolog (20 Points)

  prolog> stockmarket([2, 4, 1, 10], X).
  X = 9;
  no

  prolog> stockmarket([4, 3, 2, 1], X).
  X = 0;
  no
  

Place your code in a file called stockmarket.pl and submit it using cs60submit.

Part 3d: ISCAL (40 Points)

Finally, you'll solve this problem in assembly language. The best approach is to effectively translate (or "compile") your Java solve function from Part 3a into ISCAL.

Here's the idea. When the program is started, it will query the user to type in numbers one at a time. These numbers will be positive numbers representing stock values. When the user enters 0, this indicates the end of the input. Notice that the user does not specify in advance how many stock values she plans to enter!

Where do those stock values get stored? In an array! How do we make arrays in machine/assembly language? Remember that your program resides in memory beginning at memory address 0. After the last line of code, there is plenty of memory. We used that memory for our stack in the last assignment. In this case, we'll use that memory to store the array. That is, each element entered by the user will be stored in its own memory location! What we see here, is that arrays are just data elements stored in contiguous memory locations. How cool!

So, your program will take input from the user and store that input into memory. When the user finally enters 0, your program will call a function to compute the maximum profit in that array. You'll need to pass that function some input. For example, you might pass it the address of the beginning of the array and the address of the end of the array. That function will return a result, namely the maximum profit achievable in the array. Your program will print that result and halt.

How do we make an ISCAL program halt? If you jump to memory address 0, this causes ISCAL to halt. That's weird, but that's what ISCAL does.

You may borrow any code you like from code that you've written for Assignment 10 or that we provided for that assignment. In particular, you'll want to use Professor Keller's input and output code.

Here is some sample input and output:

turing> isc stockmarket.isc
1
2
3
0
2

Submit your program stockmarket.isc using cs60submit.

Part 3e: Reflection (10 Points)

One objective of this course is to have you reflect on how different languages provide very different ways of solving a computational problem. Now that we've seen four very different representative languages, we'd like you to think about these languages.

Choose two of the four languages in this assignment and write a paragraph or two comparing and contrasting their strengths and weaknesses for solving this problem. You may want to consider issues such as how much code was required, ease of debugging, the way in which the language forced you to think about the problem, how naturally suited the language was for this task, the readability of the code, your own perception of the "elegance" of the solutions in these languages, etc. You are invited to include your own personal views in this short essay, but try to explain the basis for your positions. Saying "I just don't like language X" isn't sufficient. You can say "Language X does not seem very well-suited for this problem because..." We look forward to reading what you write!

Please write clearly and make sure that your prose is grammatical and free of typographical errors. Submit your text in a file called part3e.txt using cs60submit.