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!
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)
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
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.