Assignment 9, due Jul 12

On every assignment, write your name legibly as it appears on your University ID card! Homework is due on paper at the start of class on the day indicated (Tuesday or Thursday). Exceptions will be made only by advance arrangement (excepting "acts of God"). Late work must be turned in to the TA's mailbox (ask the CS receptionist in 14 MLH for help). Never push homework under someone's door!

1. Background: The function INTTOS from MP4 could be compiled separately from the user program that calls it.

   a) Write contents appropriate for the interface specification that should go in the header file inttos.h (or, if someone wants to put INTTOS in the hawk monitor, your answer would be added to monitor.h).

   Well written answers could use the format of the material in monitor.h or in the header file format suggested in Chapter 10 of the notes; these two sources are not too different. (0.5 points)

   b) What code would you have to add to your INTTOS routine in order to allow it to be called from separately assembled source files linked through the linker? (0.5 points)

2. Background: We have been declaring activation records like this:

   RETAD	=	0
   A	=	4	; a 4-byte local variable
   B	=	8	; another 4-byte local variable
   ARSIZE	=	12
   

   This works well enough when all local variables are the same size, 4 bytes, but if some of them are objects of other sizes, things get messy fast. This is apparent in the iterative solutions that were posted for MP3, where one field of the activation record was an array of MAXROWS<<2 words.

   a) Suppose the local variable A is of size ASIZE and B is of size BSIZE. These sizes might be defined in the header files for the classes involved, so they aren't known by the programmer writing the code (except that we trust the values to be divisible by 4). Rewrite the above activation record description to use these sizes in the expressions used to define A, B and ARSIZE so that each is successively bigger than the previous item by the appropriate amount. (0.5 points)

   b) The answer to part A is ugly. It would be much nicer to define the layout of the example activation record like this:

   	NEWAR
   	FIELD	RETAD, 4
   	FIELD	A, ASIZE
   	FIELD	B, BSIZE
   

   In the above, NEWAR and FIELD are macro calls that, as used above, conspire to define the assembly-time symbols RETAD, A, B and ARSIZE. Write these macros.

   You may want to look at the first example in section 6.4 of the SMAL manual, and you may want to do some little experiments. If you surround your experiments with LIST +1 and LIST -1, the assembler listing will show you how it expands each macro call. (0.5 points)

3. Background: The programming language LISP (which stands for LIst and String Processing) has just one basic data type, the list element. List elements have two fields, called car and cdr, each one word long (the field names come from the names of machine instructions on the first computer where LISP was implemented back in the 1960s).

   List elements are constructed with cons(a,b), and the basic operations on an element e are car(e) and cdr(e). By definition car(cons(a,b)) is a and cdr(cons(a,b)) is b.

   a) Write an appropriate header file for an assembly language interface to LISP the LISP list object class. (0.5 points)

   b) Write SMAL Hawk code for CAR that conforms to this interface and also any private definitions on which it might depend. (We assume that if you can write CAR, you can also write CDR so just write the one.) (0.5 points)

   Afterword: CONS is messier because it must dynamically allocate a new object from the heap. That's a subject for an operating systems course. LISP was the first language to have a garbage collector, also a subject you'll typically find in operating systems or advanced algorithms courses.