10. Modularity and Objects

Classes and Objects

In the last chapter, we discussed many distinct number representations, along with the implementation of operations ranging from addition and subtraction to multiplication and division. In an object-oriented programming language such as C++ or Java, we can package each representation or data types using a class definition. A class definition encapsulates all the details of the representation of objects in the class, so that from the outside that the representation is hidden except as exposed by the methods of that class.

Assembly and machine language programmers cannot completely hide the details of the data types with which they work. Any time an object is loaded into registers, its size is exposed, and any time specific machine instructions are used to manipulate an object, these instructions must be used with full knowledge of their effect on the object's representation as well as on its abstract value.

An assembly language programmer on a machine such as the Hawk can go a considerable distance toward isolating users of objects from the details of their representations. We can do this in several steps, first isolating the code used to implement operations from the code that uses those operations, second, providing clean interface specifications for the objects, and finally allowing for polymorphic classes, that is, mixtures of different but compatable representations.

Separate Compilation and Assembly

Suppose you have a set of subroutines, such as multiply and divide, that you want to break off from a large program. Since the mid 1950's, there have been assembly languages that allowed such routines to be separately assembled before use in other programs. We have been using such tools here to call routines in the Hawk Monitor without having to include the monitor in each source file.

There some good reasons to separate a program into multiple source files, no matter what programming language is used. First, smaller files are easier to edit. Real-world application programs are frequently huge, with total sizes measured in thousands or even millions of lines of code. Second, separating an application into separate pieces lets us isolate program components that have been tested from those under development. Third, it lets us reuse components in many different applications. For example, reasons two and three apply to the Hawk monitor.

In assembly language programs, and to some extent, in C and C++ programs, there is another reason to separate programs into multiple files. In these languages, some identifiers are defined locally within one source file, while other identifiers are global to all source files. In C and C++, for example, static functions and static global variables are local to the file in which they are defined, while other functions and globals are genuinely global across all source files in the appliction. The use of the type qualifier static in these languages is eccentric, in that the word does not say what it means, but the idea remains quite useful despite its misnaming.

Separate Compilation in C

Here is a tiny example C program. It has a main program and two functions that we can break off for separate compilation.

A C program to be broken up

#include <stdio.h> unsigned char charmul(unsigned char a, unsigned char b) { return a * b; } unsigned char chardiv(unsigned char a, unsigned char b) { return a / b; } int main() { fprintf("%d = 10\n", chardiv(charmul(10, 12), 12)); return 0 }

If we simply split this file into, main.c holding the main program and charlib.c holding the two C functions, we can compile it using cc main.c charlib.c and it will work. This is because, by default, Undefined C functions are assumed to be externally defined with int arguments and return values, and when C functions take or return char values, they are implicitly widened to int. We ought to document our assumptions in a header file and not rely on defaults.

A C header file

/* charlib.h */ unsigned char charmul(unsigned char a, unsigned char b); /* multiplies a and b */ unsigned char chardiv(unsigned char a, unsigned char b); /* divides a by b */

This header file gives the interface definition for the two functions in our little library. In C, the interface definition for a function is simply the function header giving argument and return types without a body. We've followed three conventions here: First, every file begins with a comment giving its file name. Second, every interface definition is commented with documentation for its function. Third, header files for C programs use the file suffix .h. On Unix systems, there is no enforcement for any of these conventions. While the cc command enforces some file suffix conventions, the compiler itself does not.

Given this header file, we can use the following library file for our little function library; here, we've followed yet another convention, that the inteface specification for a library should have the same name as the source file for that library, differing only in the suffix:

The C source file for a small library

/* charlib.c */ #include "charlib.h" unsigned char charmul(unsigned char a, unsigned char b) { return a * b; } unsigned char chardiv(unsigned char a, unsigned char b) { return a / b; }

Given this, if we use cc charlib.c to compile this, the C compiler will force or definitions of charmul and chardiv to conform to the definitions in the header file. It will also complain that there is no main program, because we need to define the following:

A C source file to test the library

/* main.c */ #include <stdio.h> #include "charlib.h" int main() { printf("%d = 10\n", chardiv(charmul(10, 12), 12)); return 0; }

Given these three file definitions, we can compile our project with this command line: cc main.c lib.c. The compiler now has enough information about our library to check the function declarations and the function calls against the interface specifications. This cc command separately compiles the two C programs and then links the resulting object files into one a.out executable.

The above example raises a question. Why write <stdio.h> but "charlib.h"? This follows from an odd convention of the C preprocessor. When the preprocessor sees angle brackets as quotation marks, it looks for the quoted file name somewhere on the C system include directory search path. On Unix-based systems, this typically begins with /usr/include and then, if your file is not found there, other files. If, on the other hand, the C preprocessor finds double quotes, it looks on a search path that, by default, begins with the current working directory. For small projects, if you store all the files in each project in the same directory and change to that directory while working on that project, the result works very well.

Makefiles for C programs

What about large projects? C was developed as a language for writing compilers and operating systems, usually very large programs. The developers of C at Bell Telephone Laboratories addressed this by creating a completely new tool, make. This is a general purpose tool for building software, regardless of language, so long as each build step can be done with shell commands. The input to make is a makefile that documents the interconnections between the files that make up a project, and more specifically, what shell commands to run in order to build each file from the files on which it rests. Here is a makefile for our little example:

A makefile for the C project

# Makefile a.out: main.o charlib.o cc -o a.out main.o charlib.o main.o: main.c charlib.h cc -c main.c charlib.o: charlib.c charlib.h cc -c charlib.c

Each non-indented line in the makefile (aside from comments that begin with a pound sign) identifies a make target followed by a list of files needed to build that target. If make finds that the target needs rebuilding, either because it is missing or out of date, it will first make sure that each of the needed files is available, and then it will execute the shell commands that were indented under that target in order to build that target. This process is recursive: To build a.out, make may need to build main.o and charlib.o, and to build each of these, other things may need to be built.

While make usually does the right thing, the syntax has one horrible pitfall: Shell commands must be indented by tabs. Spaces and tabs are not equivalent in this context. Some versions of make try to fix this "feature," but this just creates incompatabilities.

The shell commands in the above makefile contain a number of command line options on the cc commands. The cc -c command means "just compile the program, producing an object file, don't try to link it into an executable." The cc -o xxx command means "produce the executable in a file named xxx." When cc is used with a list of files with .o suffixes, it knows that these are object files and it should just use the linker.

If the current directory contains a makefile, for example, a file named Makefile, the default name, then you can type just make with no arguments and it will build the first target listed in that makefile, if it can. Note that makefiles do not have a dotted suffix when used on Unix-based systems. In the context of our little example, make will build a.out from main.c, charlib.c and charlib.h, constructing charlib.o and main.o along the way. Type make followed by the name of a specific target to build just that target.

Make looks at the date of last edit while it works, and it understands that if you edited some file, all of the files that depend on that file will need to be rebuilt. So, after you make the example project, if you edit main.c and then run make again, it will recompile main.c and redo the final linkage step to make a.out, without rebuilding charlib.o

Note that make was developed for use with C programs, and it contains a number of features that are C specific. By default, it knows that if a file named x.o is needed and a file named x.c exists, it can use the cc -c command to make it. C programmer can write shorter makefiles by careful use of these features. We have only scratched the surface of what make does.
 

The path from source code to executable object code

source code	main.c	charlib.h	charlib.c
compiled by	cc -c main.c		cc -c charlib.c
object code	main.o	stdio.o	charlib.o
linked by	cc -o a.out main.o charlib.o
executable		a.out

 
The above figure summarizes all of the files involved in building our project, in boxes, and the shell commands executed to translate each file into a file closer to the final product. Note that charlib.h is an implicit input to both of the cc -c commands because both main.c and charlib.c include it.

Also note one file that was never mentioned above, stdio.o. When we run the linker, either the C linker or the Hawk linker, the linker always searches the system library for any library routines needed by the code being linked. The C main program in our example used printf, and the linker will find this, quite possibly in an object file called stdio.o that is embedded in a larger library of object files called stdlib. The detailed organization of this library is not the focus here, but the linkers we are using all have options that suppress linkage with the standard library in the rare event that is needed.
 

Separate Assembly in SMAL

In C, all identifiers declared at the outer nesting level in a program are implicitly global unless declared to be static. In SMAL, on the other had, the default is that all identifiers are purely local to the source file in which they are declared. A SMAL identifier may be declared to be global by using explicit INT and EXT directives. INT X says that the symbol X defined internally in this source file is to be globally visible (it definitely does not mean integer). If X is not given a value in this file, it is an error.

EXT X says that the definition of the symbol X is external to this source file. This source file must not give X a value. Some other source file must contain the declaration INT X and that source file must define a value for X.

To continue this chapter's running example, we will construct SMAL Hawk source files and a makefile that are parallel to the C code already given. We'll begin with a SMAL Hawk header file:

An assembly language header file

; charlib.h -- a character arithmetic library EXT CHARMUL ; expects R3,R4, 8-bit bytes to multiply ; returns R3, the product R3*R4, one byte EXT CHARDIV ; expects R3,R4, 8-bit bytes to divide ; returns R3, the quotient of R3/R4 as one byte

 
Header files in assembly language are a distinctly weaker tool than in C. The SMAL version of the charlib.h header file cannot give the types of the parameters and return values in any form that the SMAL assembler can enforce, but it can document this information for human readers in comments. Given this header file, we can now write the SMAL version of charlib.a:

Note that the header file does not have a TITLE directive, just a first-line comment. This is because, by default, header files are not listed in the assembly listing file.
 

An assembly language subroutine library

TITLE "charlib.a -- a character arithmetic library" USE "hawk.h" USE "stdlib.h" INT CHARMUL RETAD = 0 ARSIZE = 4 CHARMUL: ; expects R3,R4, 8-bit bytes to multiply ; returns R3, the product R3*R4, one byte STORES R1,R2 ADDSI R2,ARSIZE LIL R1,TIMESU JSRS R1,R1 ; product = R3 * R4 TRUNC R3,8 ADDSI R2,-ARSIZE LOADS PC,R2 ; return product % 256 INT CHARDIV RETAD = 0 ARSIZE = 4 CHARDIV: ; expects R3,R4, 8-bit bytes to divide ; returns R3, the quotient R3/R4, one byte STORES R1,R2 ADDSI R2,ARSIZE LIL R1,DIVIDEU JSRS R1,R1 ; quotient = R3 / R4 TRUNC R3,8 ADDSI R2,-ARSIZE LOADS PC,R2 ; return quotient % 256

 

There are several things to note here: First, unlike C, SMAL does not have a distinctive form of quotation to indicate that a header file is in the system library. Instead, SMAL searches for the file in the current directory first, and if it does not find it there, it searches the SMAL Hawk system directory.

Second, charlib.a did not use the charlib.h header file because we needed to use INT directives in charlib.a while the header file gave EXT directives. Had charlib.a included a use directive for charlib.h, there would have been a number of error messages because it is illegal to declare the same symbol to both be EXT and INT.

Third, the C program merely declared the return types of the functions to be unsigned char, leaving it to the compiler to make sure that the value is truncated to the size allowed by that type. In the SMAL code, we had to explicitly truncate the results of calling the multiply and divide routines.
 

An assembly language main program

TITLE "main.a -- demonstrate use of charlib.a" USE "hawk.h" USE "stdio.h" USE "ascii.h" USE "charlib.h" INT MAIN RETAD = 0 ARSIZE = 4 MAIN: ; expects nothing, returns nothing STORES R1,R2 ADDSI R2,ARSIZE LIS R3,10 LIS R4,12 LIL R1,CHARMUL JSRS R1,R1 ; t = charmul(10, 12) LIS R4,0 LIS R4,12 LIL R1,CHARDIV JSRS R1,R1 ; t = chardiv(t, 12) LIS R4,0 LIL R1,PUTDEC JSRS R1,R1 ; putdec(t, 0) LEA R3,TEXT LIL R1,PUTSTR JSRS R1,R1 ; putstr(" = 10\n") TRUNC R3,8 ADDSI R2,-ARSIZE LOADS PC,R2 ; return TEXT: ASCII " = 10",LF

This main program works the same as the C one given earlier, but it uses more header files. With more header files, it makes sense to try to organize them. We put system header files first, followed by application ones. Application header files are the only ones the makefile mentions, so they must stand out when writing or checking the makefile. In each group, more important headers come first, and related ones are kept together. So, we put ascii.h with stdio.h because we only use control characters in in the output string.

A makefile for the SMAL project

# Makefile link.o: main.o charlib.o hawklink -o link.o main.o charlib.o main.o: main.a charlib.h smal main.a charlib.o: charlib.a smal charlib.a

Notice that the overall structure of the makefile is the same for the assembly language and C versions of our little project. The shell commands have changed, but they do analogous things. The only substantial change is that charlib.o does not depend on charlib.h because that header file was not used by charlib.a.

Abstractions with a single instance

Before advancing to full-scale objects, it's useful to look at a degenerate case, where there is just one instance of the object. Many object-oriented languages allow you to define a class where the class itself is a single logical object. This is done in languages like C++, Java and related languages, by using private static fields for the data, which is manipulated by static methods. The separate compilation tools of C and SMAL provide natural support for this type of single-instance abstraction. In the following subsections, we'll use a stack as an example, giving code for a stack in C and an assembly language.
 

A stack in C

Within any separately compiled C file, variables and functions declared static are private to that file, while other global declarations are potentially visible everywhere. So, our stack.a code will include static definitions for the data representing the stack and non-static (that is, public) definitions of the functions that implement logical methods applicable to the stack object.

A stack header file in C

/* stack.h -- an array implementation of a stack */ void stack_push(int i); int stack_pop();

The above header file is deliberately minimal. Most real uses of stacks require other functions, or methods, if you prefer object-oriented terminology. At the very least, there ought to be a way to test for an empty stack and some action to take in the event of stack overflow. These are trivial to add, but we'll ignore them here because or focus is on the framework, not the details. If we wanted to add public fields to our stack abstraction, we could simply declare them here, as global variables visible to any code that includes this header file.
 

A stack implementation in C

/* stack.c -- an array implementation of a stack */ #include "stack.h" #define STACKSIZE 1000 static int stack[STACKSIZE]; static int sp = 0; void stack_push(int i){ stack[sp] = i; sp = sp + 1; } int stack_pop(){ sp = sp - 1; return stack[sp]; }

This code is deliberately minimal. Production versions of this code ought to include defenses against popping from an empty stack and against pushing on a full stack. Ideally, these should raise or throw exceptions, but we have not yet discussed exceptions in C or assembly language, so we'll have to defer this issue.

In the stack implementation given here, note that the variables that representat the stack are both declared to be static. Static global variables in C are private to the source file in which they are declared. This means that if, at some later time, someone wants to change the representation of this stack, for example, so it uses a linked list of elements, all the changes required will be local.

Programs that use stack.c can only access the stack through the interface declared in stack.h. This forces outside code to use the stack abstraction, with only the stated access functions. The implementation is effectively hidden inside stack.c, just in the way that the implementation of a class is can be hidden by the use of private fields in languages like Java.

If we did not declare the stack pointer sp in the above example to be static, we could put the declaration int sp in some other source file, and the linker would automatically make all references to that variable refer to the exact same memory location as is used for the sp declared in stack.c. If you really want a global variable to be shared between a large number of different source files, it is best to put the declaration in a header file so that all the source files see exactly the same declaration. While some linkers do type checking across separately compiled source files, they frequently do it poorly, for example, by checking the number of parameters, but not their types, or by enforcing only the simplest of type models.

The same stack in assembly language

There are several details in the following code worth comment. First, we could have used two separate COMMON declarations, one for STACK and one for SP. In effect, that is what C does with variables that are not declared to be static. The SMAL assembler provides only one tool for allocating global variables, the COMMON directive. If we want to allocate static variables that are not shared, what we need is a convention for naming the common block that holds those variables. What we've done here is use the file name as a prefix, and then bundle all of the private globals needed by that file into one common. Fields of this common are addressed as fields of a record.

A partial stack implementation in SMAL

TITLE "intmuldiv.a, integer multiply and divide" USE "hawk.h" INT STACK_PUSH INT STACK_POP STACKSIZE= 1000 COMMON STACKCOM,SCOMSIZE SP = 0 ; the first word of stackcom STACK = 4 ; the remainder of stackcom SCOMSIZE= STACK+(STACKSIZE<<2) LC = . . = STACKCOM+SP W 0 ; sp = 0 . = LC STACK_PUSH: ; expects R3 -- i, the value to push ; uses R4 -- pointer to stackcom ; R5 -- working copy of sp ; R6 -- address of stack array LIL R4,STACKCOM LOADS R5,R4 ; -- sp LEA R6,R4,STACK ; -- &stack[0] ADDSL R5,R6,2 ; -- &stack[sp] STORES R3,R5 ; stack[sp] = i LOADS R5,R4 ; -- sp ADDSI R5,1 STORES R5,R4 ; sp = sp + 1 JUMPS R1 ; return

The second argument on the COMMON directive gives the size of the desired statically allocated memory block. This information is passed to the linker, which does the actual allocation. Here, we declared the size using a pattern similar to the one we used for activation records. Each field of the COMMON block has a symbolic name, and the block size SCOMSIZE is given last.

The linker guarantees that each COMMON block begins at a word-aligned address, and if multiple source files happen to contain COMMON directives with the same name, they should all declare the same size; the best way to guarantee this is to put the declarations for shared COMMON blocks in a header file, the same advice that applies to shared global variables in C.

The code following the declaration of the fields of the COMMON initializes the SP field. This form of load-time initialization works for any statically allocated variable. We simply set the assembly origin to that variable, assemble the desired value into memory, and then restore the assembly origin to what it was before the initialization. The object code carries this information to the loader, and it is the loader itself that does the actual initialization.

To reference a field of the COMMON block, we load a register with the block's address and then reference fields in exactly the same way we reference fields of any record. Where we reference local variables in the activation record relative to R2, we reference fields of the COMMON block relative to some other register. Here we used R4. Because all fields of the common have static addresses, all of the addressing arithmetic can be done by the linker.

Getting the address of a field of a COMMON block

LEA R6,R4,STACK

LIL R6,STACKCOM+STACK

These two approaches to addressing fields of a COMMON on the Hawk take exactly the same amount of space in memory The difference is that one does its addition at run-time while the other does its addition at assembly and linkage time. On the most likely implementation of the Hawk, one using pipelined execution, these two instructions would be most likely to run at exactly the same speed; we will discuss this later.
 

Object Oriented Notations

At this point, it should be clear that any object, say a stack, is represented by some memory locations to hold the variables that compose the representation of the object, and that the methods of a class are simply subroutines that operate implicitly on that object. In the special case where there is just one instance of the object, it can be statically allocated and initialized by the loader. In the fully general case where there are potentially an unbounded number of object instances, it must be allocated on the heap and initialized by run-time code.

Objects in C

Suppose we want to create multiple stacks? Languages like Python or Java allow multiple instances of a class to be created, and when we call the code implementing methods of the stack class, we tell the code which object it is supposed to act on. In a language such as C++, Java or Python, if we needed to work with two stacks, a and b, we might write a.push(b.pop()) if we want to pop an item off of stack b and push it onto stack a.

Object-oriented dot notation such as a.push(1) becomes particularly critical whe the class of a is polymorphic, for example, if we have some stacks that use an array implementation and others that use a linked list. If a is not from a polymorphic class, we might just as well write stack_push(a,1). We used an underscore to separate the class name from the method name because underscores are legal parts of an identifier in C. The result of this conversion is that methods no-longer have any special status, they are just global functions or subroutines that happen to take a first argument that is of some particular type.

Object oriented versus conventional calls

Object oriented		Conventional
a.push(b.pop())		stack_push(a,stack_pop(b))

The point is, so long as polymorphism is not involved, the mechanisms we have already discussed in the context of the stack example are sufficient. The next step is to package the data required by the stack. To do this in C, we use a struct declaration. A struct in C is a collection of fields much like the fields of a class instance. Each field may be of a different type, and each field has a name. Here is a C definition of a struct allowing multiple instances of a stack:

A C struct representing one stack

struct one_stack { int sp; int stack[STACKSIZE]; };

Given this declaration, if we have a struct one_stack object named s, then s.sp, is the stack pointer field of s and s.stack[0] is the bottommost item on the array stack of s. Of course, we want a handle on our stack, that is, a light-weight way to reference a stack without makeing a copy every time we want to move that reference. This is done in C with pointers. If p is a pointer to a struct one_stack object, then we can refer to the stack pointer field as either (*p).sp or as p->sp.

The former notation is clunky but self explanatory. The * operator, as a prefix, applies only to pointers and means dereference that pointer or "follow it to the thing it points to", while the dot has its usual meaning for field selection. The -> notation seems to have come later as a short-hand to eliminate large numbers of parentheses.

The next problem we face in C is how to hide fields of the record from users of our stack abstraction. We will do this by putting only limited information in the header file, while putting all of the information in the implementation. Here is the stack header file we will use:

A C header file allowing multiple stacks

/* stack.h -- interface allowing multiple stack instances */ struct one_stack; typedef struct one_stack * stack; stack stack_constructor(); void stack_push( stack this, int i ); int stack_pop( stack this );

Here, we used a forward declaration of struct one_stack in order to tell the compiler that there is such data type without giving any details. This allows us to declare the type stack to mean pointer to a struct one_stack, and it allows us to declare a collection of functions that take and return such pointers. Users of stacks who include this header file can use stacks freely, but they have no access to the details of what a stack is. Only in stack.c where the actual implementation of stacks is given will we finish the declaration of struct one_stack.

With only a single instance of a stack, the previous version could rely on the linker to do the construction. With multiple dynamically created instances, we need an explicit constructor that returns a newly allocated and initialized stack. There is no reason to use any particular formal parameter name inside any function, but here, we used this for the first parameter because this parameter is the object that would be referenced as this inside a Java method. This header file supports the following stack implementation:
 

A partial C implementation allowing multiple stacks

/* stack.c -- implementation allowing multiple stack instances */ #include <stdlib.h> #include "stack.h" #define STACKSIZE 1000 struct one_stack { int sp; int stack[STACKSIZE]; }; stack stack_constructor() { stack this = malloc(sizeof(*stack)); this->sp = 0; return this; } void stack_push( stack this, int i ) { this->stack[this->sp] = i; this->sp = this->sp + 1; };

The constructor given here begins by calling malloc (defined in stdlib.h) to get enough memory to hold one stack instance. The sizeof function is not really a function; rather, it is a compile-time operator that gets the memory requirements of any data type, in bytes. On a 32-bit machine, for example, sizeof(int) is 4. Here, note that sizeof(stack) is 4, but sizeof(*stack) is the size of the object pointed to by that type, that is, the same as. sizeof(struct one_stack).

The malloc function returns a value of type void*, that is, pointer to an object of no particular type. C allows void* pointers to be assigned to any pointer type, and it allows any pointer type to be assigned to a void* variable. This is dangerous, because it allows all type checking to be defeated, but users of malloc rely on this feature.

There is no particular need for a destructor, because users of stack objects may directly call free to dispose of them when they are no-longer needed. The parameter type expected by free is void*, so it is legal to pass a stack or any other pointer type to free.

This code illustrates an important scope rule: Fields of a C struct have their own scope. There is no confusion betwee the global declaration of stack as a data type (a pointer to a struct one_stack), and the local declaration of stack as a field of struct one_stack.
 

Objects in assembly language

A SMAL header file allowing multiple stack instances

; stack.h -- interface allowing multiple stack instances EXT STACK_CONSTRUCTOR ; expects nothing ; returns R3 -- the handle for one stack object EXT STACK_PUSH ; expects R3 -- the handle for a stack object ; R4 -- i, the integer to push ; returns nothing EXT STACK_POP ; expects R3 -- the handle for a stack object ; returns R3 -- i, the integer popped from the stack

 

Note that the header file for the C version declared the type one_stack while there is nothing analogous to that here, except for comments indicating that the parameters are stack handles. Assembly languages have no more concept of type than they have concept of parameters to subroutines. It is up to the programmer to document types and parameters, but the language itself does nothing to help enforce any of the rules mentioned in those comments.

A SMAL stack implementation

TITLE "Stack implementation" USE "stdlib.h" STACKSIZE= 1000 ; the size of each stack ; fields of a stack object SP = 0 ; an integer stack pointer STACK = 4 ; a stack of STACKSIZE words OBJSIZE = STACK+STACKSIZE ; size of one object INT STACK_CONSTRUCTOR ; activation record format RETAD = 0 ARSIZE = 4 STACK_CONSTRUCTOR: ; expects nothing ; returns R3 -- the handle for one stack object STORES R1,R2 ADDI R2,R2,ARSIZE LIL R3,OBJSIZE LIL R1,MALLOC JSRS R1,R1 ; this = malloc( objsize ) STORE R0,R3,SP ; this->sp = 0 ADDI R2,R2,-ARSIZE LOADS PC,R2 ; return this INT STACK_PUSH STACK_PUSH: ; expects R3 -- the handle for a stack object ; R4 -- i, the integer to push ; returns nothing LOAD R5,R3,SP ; -- this->sp LEA R6,R3,STACK ; -- &this->stack[0] ADDSL R5,R6,2 ; -- &this->stack[this->sp] STORES R4,R5 ; this->stack[this->sp] = i LOAD R5,R3,SP ; -- this->sp ADDSI R4,1 STORE R4,R3,SP ; this->sp = this->sp + 1 JUMPS R1 ; return

The constructor given here exactly parallels the code for the C version. In the single-instance version of the stack abstraction, allocation and initialization, the key jobs of an object constructor, were all done by the loader. Here, we rely on run-time code to first allocate the object and then perform the assignments needed to initialize it.

The most notable thing about the stack push operation given here is that it is essentially the same as the code given for the statically allocated single-stack version of the code. The static version is one instruction longer, but every call to this version requires one extra parameter to be passed. That is the only performance penalty we pay for access to a dynamically allocated object, aside from the cost of allocation.

Polymorphism

Generally, C and assembly language programmers stop here. Most problems can be solved with either a single instance of a class or with multiple instances that share common implementation. Even C++, Java and Python programmers, when they design new classes, frequently use only one implementation. The standard libraries used with those languages are quite different. These libraries are full of polymorphic classes, that is, abstract classes with multiple compatible implementations.

Consider, for example, the class stream of characters. Opening a file creates an instance of either subclass input_stream or output_stream, depending on whether the file was opened for input or output, and there might be a string to stream constructor that, given a string, returns a read-only stream that delivers successive characters of that string, and also a stream to string constructor that creates a string containing all of the text read from some stream. The file model of Unix is built on such a stream abstraction, even though it was originally exposed to users through the C library, which is distinctly not an object-oriented library.

For another example, all of the implementations of the stack of integers abstraction given above used an array with a stack pointer. Another equally useful implementation uses a linked list, where the push operation adds an element to the head of the list and the pop operation removes and returns an element. From the outside, a user of stacks may not be able to tell which implementation is being used, except perhaps if the user does careful performance measurements. In languages that inherit the object model of Simula '67, these two implementations can coexist in user programs, and code can be written that works equally well with both implementations.

The first and most obvious requirement for polymorphic data objects is that each object must contain some data to indicate which implementation it uses. For example, a polymorphic stack object could begin with a field indicating whether it is a linked-list stack or an array stack, and every call to a stack method could begin by testing this field to see which implementation to use. To the extent that systems in the early 1960s supported any kind of polymorphism, this was the only way it was done. By the end of that decade, the far more elegant (but perhaps difficult to understand) approaches outlined below emerged.

Polymorphism in C

In the code that follows, we use function pointers, that is, variables that point to functions. These are not as complex as lambda abstraction in languages like Java and Python, because the λ mechanism not only allows a function to be passed, but also creates bindings of some or all of the variables used in that function.

A C header file for a polymorphic stack abstraction

/* stack.h -- polymorphic stack interface specification */ struct one_stack; /* use only to implement subclases */ typedef struct one_stack * stack; struct one_stack; void (*push)(stack,int); int (*pop)(stack); }; #define stack_push(s,i) s->push(s,i) #define stack_pop(s) s->pop(s)

This header file corresponds to what you would declare as an abstract class in a language like Java. It has no implementation, because the implementations are expected to be provided by the subclasses that provide various implementations of the class. What it does do is tell the user of stacks, regardless of their implementaiton, that every stack has two fields, push, a pointer to the function that implements the push method, and pop, a pointer to the function that implements the pop method. We could add other public fields shared by all stack objects as fields of one_stack.

The format of the declaration of a function pointer in C and languages descended from C is not very well designed. The identifier being declared is hidden inside parentheses in the middle of the declaration.

As the comment suggests, struct one_stack should never be instantiated. No constructor is provided, but unfortunately, we cannot prevent a stupid programmer from creating one.

We also included two macros in this header file, stack_push and stack_pop. These macros package the awkward format of a call to a method, so that users need to mention the object just once, instead of having to mention it twice. Without this macro, for example, we would have to write mystack->pop(mystack) where, in languages like Java and Python, we would just write mystack.pop().

• mystack->pop ... is required in order to transfer control to the right pop function, and

• ... pop(mystack) is required in order to tell the pop function which stack it is operating on.

Given this set of definitions, the next challenge is to create a second header file defining the interface to one specific implementation of stacks, a subclass of the abstract class we have already implemented. This header file will declare the array-stack type and functions that implement the methods of that type.

The interface to a specific stack implementation

/* arraystack.h -- stacks implemented with arrays */ /* always do an #include "stack.h" before including this */ struct one_array_stack; typedef struct one_array_stack array_stack; stack array_stack_constructor(); void array_stack_push(stack a, int i); int array_stack_pop(stack a);

The interface is a little strange because an array_stack_constructur doesn't construct an array_stack, it constructs a stack, and the functions that implement the methods of an array_stack take parameters of type stack and not array_stack. This is due to the fact that C has weak but still significant type rules, and this is the best we can do under those rules. The net result is code that will break spectacularly if you accidentally pass a linked_list_stack to a function in array_stack.

Also notice the comment asking that any code that does #include "arraystack.h" first do #include "stack.h". Failing to do this will result in an error because arraystack.h assumes that type stack is already defined. We could have put the line #include "stack.h" at the start of arraystack.h, but then a program that used both arraystack.h and liststack.h would end up including stack.h twice. This style can lead to circular #include loops. There are mechanisms to fix this, but they are ugly.

Partial implementation of the array-stack subclass

/* arraystack.c -- implementing stacks with arrays */ #include <stdlib.h> #include "stack.h" #include "arraystack.h" #define STACKSIZE 1000; struct one_array_stack { struct one_stack prefix; int sp; int stack[STACKSIZE]; }; stack array_stack_constructor() { array_stack this = malloc(sizeof(*array_stack)); this->prefix.push = array_stack_push; this->prefix.pop = array_stack_pop; this->sp = 0; return (stack)this; } void array_stack_push(stack a, int i) { array_stack this = (array_stack) a; this->stack[this->sp] = i; this->sp = this->sp + 1; }

In the above, note the use of casting. Inside the constructor an array stack is allocated and initialized, but before return, the pointer to it is cast to type stack in order to conform with the interface specification. Similarly, the stack pointer that is passed to the push routine is first cast to type array_stack before use. Aside from the use of casting, the code for array_stack_push is identical to the code for stack_push when there was no polymorphism, and the only changes to the constructor have to do with the prefix field.

Also note that struct one_array_stack begins with struct one_stack, so that anyone following a stack pointer will see a one_stack object, and the constructor initializes both fields of this prefix. So long as the implementation of every subclass begins this way, the basic method dispatching code given in the #define directives in stack.h will work. The overall structure created by the constructor is summarized in the following diagram:

The data structure for a polymorphic stack

Polymorphism in assembly language

A partial SMAL header file for a polymorphic stack

; stack.h -- polymorphic stack interface specification ; every stack, regardless of implementation, starts with these fields PUSH = 0 ; address of the push code POP = 4 ; address of the pop code STACKSZ = 8 ; size of the basic prefix ; calls to the push code ; expects, R3 -- the handle for the stack object ; R4 -- i, the integer to push ; returns nothing

Notice that the above header file is mostly comments. Where C enforces rules about declaring parameter types and return-value types, all we can do in assembly language is write comments describing these. The rest of the header file, describing the interface to the pop code, is left as an exercise. In the C code given previously, we also provided #define statements that packaged and illustrated how to call each method of this polymorphic class. We could also add comments to the header file giving this, although the cod may be close to being self-evident:

An example polymorphic stack method call

LOAD R3,R2,MYSTACK ; -- parameter 1 and object handle LOAD R4,R2,MYVALUE ; -- parameter 2, the value to push ADDI R2,R2,ARSIZE LOAD R1,R3,PUSH ; -- get the pointer to the method code JSRS R1,R1 ; mystack.push(myvalue) ADDI R2,R2,-ARSIZE

The most notable thing about this code is that it contains exactly the same number of instructions as the code to call a separately assembled subroutine. The only change is the replacement of an LIL instruction that gets the statically determined address of the code with a LOAD instruction to get the address out of the object itself. We did replace a load-immediate with a load instruction, which is to say, the code does one more memory reference, but considering the flexibility that polymorphism gives us in our programs, the cost is startlingly low.

There is almost nothing needed in the polymorphic version of the arraystack.h file, just an EXT directives for the constructor, and optionally EXT directives for the other methods, although they can all be accessed through the objects created by the constructor. The code for the constructor is more interesting.

The declaration of the fields of an array-stack in the implementation we will give is ugly, at best. Up to now, we have been describing record structures using explicit constants for the offset of each field. This works fine when the fields are of fixed size, and all of the records we've described up to this point had one-word fields, except for the various array implementations of stacks, where the record had a single "elastic" field at the end. The size of that field, of course, had to be taken into account in just one place, the overall size of the record.

Now, we have a record representing an array-stack object where the size of the prefix of the record is unknown; it depends on STACKSZ, a constant exported from stack.h that depends on the space occupied by what we called the prefix of the record in our C code, or what a Java programmer would call the superclass. This means that the location of each field in an array stack must be adjusted relative to the already-declared fields.

Partial SMAL Hawk implementation of an array-stack

TITLE "Array stack implementation" USE "stdlib.h" USE "stack.h" STACKSIZE= 1000 ; fields of an array-stack object ; fields from "stack.h" are implicit here SP = STACKSZ ; an integer stack pointer STACK = SP+4 ; a stack of STACKSIZE words OBJSIZE = STACK+STACKSIZE ; size of one object INT ARRAY_STACK_CONSTRUCTOR ; activation record format RETAD = 0 ARSIZE = 4 ARRAY_STACK_CONSTRUCTOR: ; expects nothing ; returns R3 -- the handle for one stack object STORES R1,R2 ADDI R2,R2,ARSIZE LIL R3,OBJSIZE LIL R1,MALLOC JSRS R1,R1 ; this = malloc( objsize ) LEA R4,ARRAY_STACK_PUSH STORE R4,R3,PUSH ; this->push = array_stack_push LEA R4,ARRAY_STACK_POP STORE R4,R3,POP ; this->pop = array_stack_pop STORE R0,R3,SP ; this->sp = 0 ADDI R2,R2,-ARSIZE LOADS PC,R2 ; return this

The constructor given here uses LEA instructions to get the addresses of the subroutines that implement the methods. These use pc-relative addressing, so the methods must be declared nearby, in the same source file. If they are declared externally, we'd need to use LIL instructions.

The code for ARRAY_STACK_PUSH is not given here because it is identical to the code for the non-polymorphic STACK_PUSH already given

A Compact Polymorphic Data Structure

A serious shortcoming of the polymorphic class implementation suggested above arises when a class has a large number of methods. Consider the case in a language like Java, where every class has a to_string method and an equals method, and instances of class Integer have 10 methods, 6 of which are definitely polymorphic because they are shared by all subclasses of Number. If we used the methodology outlined above for implementing polymorphic classes, we would augment every 32-bit integer with at least 6 method pointers plus whatever the overhead is for each object on the heap. The story is similar in Python.

That is, for each useful variable in our programs, languages like Java would impose an memory overhead that easily approachs a factor of 10 if they used the approach outlined above to implement polymorphism. Fortunately, there is an alternative.
 

A compact polymorphic class implementation

The alternative approach involves a more complex data structure, moving the record of method pointers out of the object. Instead, all objects of each class begin with just a single pointer to the class descriptor. The descriptor is a constant record; for our purposes, what matters is that it holds all of the method pointers, but it may also hold structural information needed by the memory manager and other information to support the object model of the language.

C header file for compact polymorphic stack

/* stack.h -- compact polymorphic stack interface specification */ struct one_stack; /* use only to implement subclases */ typedef struct one_stack * stack; struct stack_descriptor { /* every subclass has one of these */ void (*push)(stack,int); int (*pop)(stack); } struct one_stack; struct stack_descriptor * descriptor; }; #define stack_push(s,i) s->descriptor.push(s,i) #define stack_pop(s,i) s->descriptor.pop(s)

The header file giving the interface to our compact polymorphic stack has one big addition, struct stack_descriptor, giving the layout of the class descriptor layout that must be provided by each implementation of the stack.

We still have the option of adding public fields that are shared by all stack objects to struct one_stack, but in the absence of such fields, this struct has been reduced to just one field, a pointer to the descriptior.

As in the first polymorphic stack, we have provided stack_push and stack_pop macros. These are slightly more complex than the versions given previously, but to see the actual cost, we need to translate one of these to assembly language.

SMAL Hawk code to push on a compact polymorphic stack

LOAD R3,R2,MYSTACK ; -- param 1, object handle LOAD R4,R2,MYVALUE ; -- param 2, value to push ADDI R2,R2,ARSIZE LOADS R1,R3 ; -- get this stack's descriptor LOAD R1,R1,PUSH ; -- get the pointer to method JSRS R1,R1 ; mystack.push(myvalue) ADDI R2,R2,-ARSIZE

The most noteworthy thing about this code is that it takes just one more machine instruction per call than the original code given above for a polymorphic call, and because we put the pointer from the object to its descriptor as the first field of the object, we were able to use short-indexed addressing on the Hawk instead of the more expensive long form. Even the C code doesn't hint at the low cost of this implementation of polymorphism.

A good C++ compiler should be able to generate code comparable to the above for any call to a method of a polymorphic class. When the method being called can be statically determined, that is, when the compiler can figure out which subclass is actually being used, the compiler has the option of directly calling the method without following a pointer to the descriptor.

The header file given for the first version of arraystack.h will work just as well with this verison, since nothing in that header file mentions how we have handled polymorphism. The constructor, however, has to change because it must now provide a specific instance of struct stack_descriptor for use by all instances of one_array_stack.
 

A partial C implementation of a polymorphic stack

/* arraystack.c -- implementation of an array stack */ #include #include "stack.h" #define STACKSIZE 1000 struct one_array_stack { struct one_stack prefix; int sp; int stack[STACKSIZE]; }; const static struct stack_descriptor descriptor = { .push = array_stack_push, .pop = array_stack_pop }; stack array_stack_constructor() { arrray_stack this = malloc(sizeof(*array_stack)); this->prefix.descriptor = &descriptor; this->sp = 0; return (stack)this; }

In the above, descriptor is declared to be static so that it cannot be seen from any other source file, and it is declared to be const so that it cannot be modified. On many machines, this means that the descriptor will be stored in with the program code, initialzed by the loader before it is marked read-only so that it cannot be changed. In later chapters, we will discuss how read-only restrictions can be enforced on regions of memory using the memory management unit.

All versions of C allow structures to be initialized by listing the values of the fields inside curly braces. In the original version of C, the values of the fields were simply given in order. ANSI Standard C, released in 1999, added the ability to name the structure fields being initialized, as is done here.

Finally, note that the C code for the push and pop routines given for the previous polymorphic stack implementation would work identically with this implementation.

Generics

C++ and Java support generic classes, while the code given above, both for simple and polymorphic stacks, supported just one abstract type, stacks of integers. This seems limiting.

In both C++ and Java, all instances of objects are on the heap, and all code that manipulates objects does so by passing object handles. As we have seen, object handles are just pointers in C and assembly language, so if we create an abstraction that can accept any pointer to an object as a parameter, we have created a generic object.

C has a special type, void* that, read narrowly, means "pointer to nothing." The library routine malloc returns a void * pointer because it has no clue about the type of the object it is allocating, only the number of bytes to allocate. Every time we allocated an object using malloc we had to cast that object to our desired type, for example by using (array_stack)malloc(...).

We can use casting in C to build generic classes. To build a generic stack, for example we declare our stack to hold void* objects, so if s is a generic stack and o points to some object, we call s.push((void*)o) and when we call pop, we will get back a void* pointer that we must then cast to the pointer type of the object we pushed.

If we have been pushing only one pointer type, then all the pointers we pop will refer to objects of that type, and there is no need to do any chacking. The type rules of Java and C++ automatically enforce this when you, for example, create a stack of strings from a generic stack class and the string class. The language prevents you from pushing anything but a string on that stack, and it knows that everything popped from that stack will therefore be a string.

Hawk code is even less constrained by any concept of type than C. The PUSH and POP code we have written above works with any 32-bit quantity, whether that quantity is an integer or a pointer to some object. It is up to the programmer to prove, with no help from the programming environment, that either everything pushed on the stack is from the same class, or that everything pushed includes an indicator of the class to which it belongs so that it can be correctly classified after it is popped.