Machine Problem 6, due at the end of Apr 29

Part of the homework for CS:2630, Spring 2024
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

A problem:

The following file contains a shell archive:
https://homepage.cs.uiowa.edu/~dwjones/assem/hw/mp6shar.txt

This shell archive contains:

However, the body of the file liststack.a is mostly missing.

The Makefile supports make demo which will assemble, link and launch the Hawk emulator and waiting for you to hit the r key to actually make the code run. Of course, it will only work if you provide the code missing from liststack.a.

Note: The above text is lifted directly from MP5. There is one big change. The documentation in stack.h now commits each implementation of stacks to detect stack overflow and stack underflow, throwing STACKEXCEPT when either of these problems occurs. The main program has been modified to handle these exceptions. It always tries stack underflow, and if the window is large enough, it will force a stack overflow.

Your assignment is to write the code that is missing in liststack.a. Your code must correctly handle stack underflow and overflow. This code must implement stacks using linked lists, where pushing a word on the list-stack involves a call to MALLOC to create a new list item and popping a value from the list-stack involves a call to FREE to deallocate the node that held the popped value. Each object representing a list stack will hold a list head plus any other fields needed to implement it.

You must create a directory (call it mp6) to hold your project, and then install the shell archive there before you can begin work. Feel free to copy your solution to MP5 into your new directory and (assuming it works) feel free to build on it to solve MP6.

Eventually, the only code you submit will be your code in liststack.a.

Your need not change any other files in the project, but you will almost certainly need to explore them. Feel free to use the organization of the code from arraystack.a. Your code will need to conform to the interface specificaiton given in stack.h and liststack.h. Your code will need to work when used by main.a.

Grading: 5 points. Correct output is worth 2.5 points. The remaining credit will be offered only for those who have correct output.

Code that does not assemble will not earn any credit.

Code that still says YOUR NAME HERE in the title will be discarded.

Stylistically clean code is important; that is why half the credit is reserved for style, but only if the code works. When integrating your code into a larger pre-existing project, it is always a good idea to try to match the style of the pre-existing code so your contribution blends into it. There should be no need to duplicate the nitpicking style requirements from previous assignments here. They still apply.

Submission: To submit your work, it must be in a file named liststack.a in your mp6 directory on the CLAS Linux system, and you must know your section number. Make sure mp6 is the current directory. In the following, what you type is shown in bold face. Begin at the linux command-line prompt: 

   [HawkID@fastx?? ~]$ ~dwjones/submit 0A0X liststack.a

Note: The ~dwjones must be verbatim, do not substitute another name. Also, use your section number (one of 0A01 to 0A05).

In the event of insurmountable trouble, do not delete or edit files you have submitted until the graded work is returned. The operating system record of the last edit time and date and the backups maintained by the operating system are proof of what you did and when, and they allow us to investigate what happened. until your graded work is returned. This way, the time stamp marking the time of last edit is a trustworthy indicator of whether you did the work on time.

Note 1:

No solution is being distributed to MP5 in order to allow students who did not solve it in time to continue working on it while adding the new elements needed to solve MP6.

Note 2:

Up until now, we have been able to assume that your code begins at address 100016 so all you had to do in order to convert between addresses in your listing and addresses in your code is add 100016 to the address in your code. This has been particularly important in interpreting bus traps and other error messages.

Now that our project requires multiple object files that are combined by the linker, this doesn't always work. You can use the linker's -d option to get a map showing where the linker put everything in memory, but there is another handy trick.

The linker arranges object files in memory in the same order you put them in as arguments to the hawklink command. This comment in makefile looks like this: 

        $(hawklink) -o stackdemo main.o arraystack.o liststack.o

As a result, it puts main first in memory, starting at address 100016. That is convenient if you are debugging the main program and trying to interpret bus traps there. You can make it put liststack first by changing this line to: 

        $(hawklink) -o stackdemo liststack.o main.o arraystack.o

Your program should run just as well with the object files in any order, but by using this order, bus traps that occur while executing code in liststack will be easy to interpret because it will start at location 100016.

Discussion

Thursday, April 18, 2024 6:00 PM

Are you saying that if I complete a working solution, I can submit MP5 for re-grading, or just that it will serve me for MP6?

This is just MP6, but if you didn't finish MP5, you can finish it, add the code to throw exceptions at the right time, and thereby meet the requirements for MP6.

Thursday, April 18, 2024 6:54 PM

Are we supposed to detect and throw the exception, and then let the tree finish printing on its left side? And are those exception messages meant to stay there even when the program finishes running?

The main program, file main.a in the shell archive, contains some try-catch blocks. You can read that code, it's well enough commented that you can read just the comments to see what it's up to.

In any case, how could you let the tree finish printing after one of the three stacks in the text program has been corrupted? The messages are definitely intended to stay on the screen so that you can see evidence that exceptions were thrown at the right times.

Monday, April 22, 2024 12:42 PM

Several students have asked the desired output is for mp6.

The assignment has no specific desired output, since the assignment is asking for a correct implementation of link-list stacks. The requirement is that the code implement the specified behavior, and of course, that the code be readable, clear, etc.

The program included in file main.a is merely a test program to help verify that your code works. If you wonder what output it should produce, read the code.

Since the required behavior for your code includes throwing exceptions, the main program tries to force your code to throw an exception, and it reports that your code did so. There are two try catch blocks, and they are nested in order to make sure nested try-catch blocks work.

To test that your stacks still work, you should also run your code in a window sized small enough to only permit a 3-level tree. In that case, the whole tree should plot.