Assignment 9, due Jul 12

Solutions

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

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!

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)
```
        EXT     INTTOS
                ; expects R3 = b -- address of buffer to use for conversion
                ;         R4 = l -- length of buffer
                ;         R5 = n -- unsigned number to convert to string
                ;         R6 = b -- number base to use (from 2 to 32)
                ; returns R3 = s -- pointer to null terminated result string
                ;         note: s will point somewhere between b and b+l-1
                ;         except when there is an error.
```
The exact text is not critical so long as it conveys substantially the same information. The above is minimally edited from the specification in the assignment for MP4. The only changes aside from the EXT directive are slightly terser wording to keep lines from getting too long after the change in indenting.
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)
```
        INT     INTTOS
```
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)
```
RETAD   =       0
A       =       4          ; local variable of size ASIZE
B       =       A + ASIZE  ; another local of size BSIZE
ARSIZE  =       B + BSIZE
```
The above tries to minimize the mess, but there are many alternatives. Consider the following:
```
RETAD   =       0
A       =       4          ; local variable of size ASIZE
B       =       4 + ASIZE  ; another local of size BSIZE
ARSIZE  =       4 + ASIZE + BSIZE
```
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)
```
        MACRO   NEWAR
          ARSIZE = 0
        ENDMAC

        MACRO   FIELD name,=size
          name = ARSIZE
          ARSIZE = ARSIZE + size
        ENDMAC
```
The use of the = prefix on the second parameter to indicate that it is passed by value is not required for the example in the problem statement, but if someone writes code like this, it will ask the assembler to evaluate the expression when the macro is called before passing just the value of the expression into the macro.
```
        FIELD   ARRAY, ELEMENTS<<2
```
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)
```
; lispobjects.h -- header file for use of LISP objects

OBJSIZE =       8

        EXT     CAR
                ; expects R3 = p -- address of a lisp object
                ; returns R3 = pointer extracted from the car field of p
                ; may use R4 to R7

        EXT     CDR
                ; expects R3 = p -- address of a lisp object
                ; returns R3 = pointer extracted from the cdr field of p
                ; may use R4 to R7

        EXT     CONS
                ; expects R3 = a -- address of a lisp object
                ;         R4 = b -- address of a lisp object
                ; returns R4 = pointer to a new lisp object cons(a,b)
                ;              with the car set to a and the cdr set to b
                ; may use R4 to R7
```
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)
```
; structure of a LISP object
CARFIELD = 0
CDRFIELD = 4
OBJSIZE  = 8

	INT	CAR
CAR:    ; expects R3 = p -- address of a lisp object
        ; returns R3 = pointer extracted from the car field of p
        
        LOAD    R3,R3,CARFIELD
        JUMPS   R1
```
Technically, there is no need to define CDRFIELD nor OBJSIZE here, since these are not needed in the definiton of CAR, but they are given here because the other code would need them.
Also, knowing that CARFIELD is 0, we can easily substitute a LOADS for the LOAD, and if we do that, the need for any definition of CARFIELD goes away -- but we certainly need comments that give the structure of the object!
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.