July 5, 2017#34 Programming Theory

---

Object Orientation in 6502

I feel as though my abilities at 6502 assembly are progressing fairly quickly. I'm a pretty experienced programmer in higher level languages, such as Objective-C, Javascript and PHP, as well as C. But when I first started programming seriously in 6502 I was having a hard time seeing how to accomplish things that are quite common in higher level languages. Things like strings, arrays, structures, functions and objects. What you have available when coding in 6502 ASM is just so incredibly low-level, you have nothing but an open expanse of memory and a handful of simple instructions.

But, I made a lot of progress which I've blogged about earlier, especially in regards to pointers and structures. The next frontier, in my opinion, is learning how to program in an object-oriented style. In higher level languages the compiler or the interpreter itself constrains what you can do. But, these constraints are arbitrary. A computer can jump through any spaghetti mess that you can throw at it. The constraints are there to force you to follow certain design and organizational patterns. The point of organizing your code either functionally or objectively is because it is a good practice that leads to cleaner code that is easier to understand and maintain and that has fewer bugs as a result.

So, when we code in 6502 asm we're not constrained by a compiler to follow any particular good practice. But that doesn't mean we can't apply, as a matter of personal discipline, the organizational principles of object-orientation to our assembly, and then reap the benefits that come from that design. Let's first go over the theory and the terminology so we know what the benefits are in principle. And then after that we'll get into the meat and potatoes of exactly how these principles can be applied in 6502 asm.

What is object-orientation? The Theory.

There are usually four principles that object-oriented design is meant to meet. These are:

• Encapsulation
  
  
• Abstraction
• Polymorphism
  
  
• Inheritance

I separate these into encapsulation, and then abstraction and polymorphism, and lastly inheritance, because I find it difficult to separate abstraction and polymorphism into distinct principles. They seem to overlap and feed into one another that makes them hard to discuss individually.

Encapsulation

Encapsulation is to me the most important of the four. Rather than having some global data that any code anywhere in the program can see and change, you instead wrap up bundles of related data and hide them behind code that you have to call to get at that data. The distinction between an object and a structure gets really thin when you don't have a compiler constraining what code can work on what data.

A structure, as I've discussed before is a block of data with the possibility of being composed of smaller and different data types. A structure collects data of varying types together that are related to each other. The sub-types are laid out in such a way that the start of each sub-type within the structure has a known offset from wherever the structure as a whole starts in memory. I believe the example I used was a record of a person. A person may have a name, year of birth, height, social security number, gender, etc. These different data can be put together such that you only maintain a pointer to a person and then access the subtypes as offsets into person. So, if you know the struct starts at $8000, and name is at $02, then name is at $8000,$02, and gender might be at $8000,$06, etc. The 6502 is pretty good at this, because it offers the indirect indexed addressing mode. You set the .Y register to the offset of the sub type you want, and put a pointer to the start of the struct somewhere in zero page.

Structs are really great, but then you need routines that know how to operate on the layout of a particular type of struct. You might have person records, and job records, which are structured differently. You'd run into a huge problem if you called a routine that was designed to operate on a person struct but you passed it a job struct. What objects do is take structs one step further, and make some of the struct's properties pointers to routines that are capable of operating on that very type of struct. A bit head spinning at first, by very clever when you think about it.

The encapsulation separates the design of the object from the programmer who might later try to use the object in their own code. Why would anyone want to do that? Well, we'll see that eventually when I post in more detail about the object-oriented nature of the widget toolkit. But in short, you want the designer of the operating system to create some objects that are useful. Then you want a programmer who doesn't directly collaborate with the OS designer, but just reads an API document, to be able to write his own application that makes use of the object. Then, here's the real magic, you want the OS designer to be able to change, improve and expand the capabilities of the OS's objects. And you want the third-party programmer's application not only to not break, but to automatically gain new functionality, effectively for free.

If the third party programmer had complete knowledge of the internal layout of the structure and thus hardcoded direct manipulations of that structure, then his code would break if the OS designer changed the object's internal layout. In order to avoid this problem it is important that the programmer does not directly manipulate the encapsulated data. In 6502 we cannot enforce that the programmer doesn't violate the principle of encapsulation, but we can certainly honor the notion that the data ought to be encapsulated and simply restrain ourselves from direct manipulation.

Abstraction and Polymorphism

In order to understand how it is possible to work with an object whose properties are all encapsulated it is necessary to move on and discuss how objects work. The ideas of abstraction, inheritance and polymorphism will all start to blur in this description.

The crucial step that separates a struct from an object is that an object contains properties that point to routines that are designed to act upon itself and to understand the internal layout of its own structure. This allows the third party programmer to not need to write his own code that manipulates the encapsulated data.

Instead, the documentation specifies a handful of "publicly" known offsets, typically to routines, which in object parlance are called "methods." The programmer then takes a pointer to the object, and looks up a method, and calls the method. The method is given access to a pointer to its own structure, and the method, which was written by the OS designer, operates on the internals of the struct to change the data, retrieve some data for the user, or perform some other function.

So, encapsulation hides the data of the object from the programmer, and instead presents publicly known method offsets. The methods of an object are always known to operate on the object they belong to. So you never need to worry about accidentally calling a routine but passing it the wrong type of record. This design pattern, encapsulating the data and only accessing that data by calling methods which operate on the structure, essentially defines what it means to be an object. However, the relationship between objects is where abstraction, inheritance and polymorphism come into the picture.

The collection of public methods that an object has are known as its interface. They are the calls by which third party code engages with and interacts with the object. But what if you had two different objects, with different encapsulated properties and different internal behaviors, but which exposed exactly the same interface? Well, this is where you get abstraction and polymorphism. What's the difference between abstraction and polymorphism? Well, lots of people ask that question and I'm not 100% certain myself. But I can take a stab at it.

Let's say we have two objects, one that represents a person. Internally the person has a property that stores their date of birth as an offset in seconds since the unix epoch. The other object represents a company, and stores the founding date of the company as a string in YYYY-MM-DD format. But they both have a method called "Start Year". When called, the person object returns 1981, and the company object returns 1975. These two figures can be compared to each other, even though the true underlying data representation is radically different and not directly comparable. The methods thus serve to abstract the underlying data structure, and the third party program that makes use of these classes does not need to know or worry about the internal representations of the data.

Polymorphism is similar, but I think it relates to abstracting behavior, which allows one object to seamlessly substitute for another. So, imagine you have a program and it wants to log error messages. There could be three different types of objects, which each have a "log" method, that take a string for message text. But one of those logger objects emails the message text, another prints it to a printer, and another appends it to a log file. The third party program doesn't actually care which logger object is given to it, it will use and interface with all three in exactly the same way. But the result of the substituting one for another is that a completely different form of output will take place behind the scenes. This is what "polymorph"-ism means, one interface manifests in "many forms."

Inheritance

Abstraction and polymorphism are about how you can use different types of objects in similar ways. Inheritance, then, is about deriving a type of object from a more primitive class of object, such that they have at least some part of their interface in common, which allows for their substitution.

It's important to define here the difference between a class and an object. A class is a description or a prototype of an object. An object is thus an instance of a class. The difference is similar to the definition of a structure, and an actual instance of the structure in memory. The definition of the structure may be that it has 5 properties, 2 bytes wide each. When you want to make an instance of the structure, you effectively just allocate some memory that is the size of the structure, 10 bytes in this case. After that you may want to initialize that memory by assigning known values to each of the 5 properties. Now you have this 10 bytes of memory that are an instance of the structure. Your code could make hundreds or thousands of instances of the structure by allocating another 10 bytes for each new instance.

Objects work essentially the same way. Except that in higher level languages their initialization is performed automatically by a standard method which is known as its constructor. High level languages typically allow you to create an instance of an object with the new keyword. So new Person; would allocate memory the size of Person. Then automatically initialize that memory using a routine which is defined as the constructor for the Person class. The instantiation process automatically assigns all the method pointers to all the routines that are declared as that Class's methods. The constructor method is generally responsible for initializing all the other data properties. And what is returned to the caller is a pointer to the initialized memory of the new instance. After this, we'll look at how we can implement this behavior in 6502.

Inheritance is a design pattern whereby classes are hierarchically related to each other. For example, imagine you have a class that represents a piece of paper. It may have properties such as width, height, thickness, and color. You might then have a subclass of paper called lined paper. Lined paper actually has all of the properties of paper, but it adds extended properities such as line color, line thickness, line spacing, top margin and bottom margin. And you might have a third class that is also a subclass of paper called music paper. This has all the properties of paper, but none of the extra properties of lined paper, and instead offers its own extended properties such as base or treble lines, and how many rows of notation.

Further, beyond just the subclasses sharing the properties of the superclass, the superclass (paper in this case) also implements some methods, such as draw. When you draw a piece of paper it just clears out a rectangle on the screen proportional to its width and height properties. The two subclasses however also have the draw method, but their draw method is more sophisticated but derivative. So, when a lined paper object is instantiated, its draw method pointer is setup to call the draw routine declared for the lined paper subclass. However, when draw is called on a lined paper object, internally that routine can call the original draw rouine for its super class, paper. Paper's draw routine then does its thing, reads the width and height and clears out the rectangle with the correct paper color. After the superclass's draw method completes, the lined paper's draw method only needs to implement the extended functionality. It draws on top of the paper's colored rectangle according to the extended properties defining the lines.

That is really cool. In other words, when you want to implement lined paper, it is not necessary to reinvent the entire wheel and reduplicate the base drawing code. Instead a subclass extends a superclass. Or we say that the subclass inherits from the superclass. The fact that the subclass inherits from the superclass means that an instance of lined paper IS an instance of paper. And so any code that expects to be operating on a paper object should work just fine if it is instead given a lined paper or a music paper object.

---

So much for theory, what about the 6502?

Effectively, an object, an instance of a class, is a struct where some properties are pointers to methods. And a struct is just a block of memory the appropriate size, which is accessed using indirect indexing where the index offsets are declared by name. What does that mean?

Well, let's take the indexing by name part first. In our source code we will declare a block of labels like this:

The above is not an object, it's a struct definition. This is the sort of code that I use to declare the definition of a structure. Notice that p_size has been manually set to the the size of the whole collection. 2 for name, 1 for sex, 1 for height, 2 for year of birth. We need 6 bytes total for an instance of the person struct. To create one of these in memory we need to rely on our memory manager (and here). In fact, object oriented code essentially requires a memory manager, which is something that I wasn't anticipating when I originally discussed what a memory manager would be useful for. We ask the memory manager to allocate space the size of p_size. We get back a 16-bit pointer to somewhere in memory and that's where our struct is.

Next, we might want to initialize the struct's properties to known defaults. In order to do indirect indexing the 6502 requires that the pointer be in zero page, so we'll stick the pointer into say $fb-$fc, which we've defined as the ptr. Then we set the .Y register to an offset by using one of the struct property declarations and away we go. Here's how this might look in code.

So, that's what we might do in our code to go from a definition of a struct to an instantiated and initialized instance of a struct. And I've posted at length about structs before. The thing to note here is that a struct is not an object. The biggest problem with this code from an object oriented point of view is that the data is not encapsulated, the implemetation is not abstracted, there are no methods which act upon this data, and so polymorphism isn't possible, etc. But, what this does show is how we use those declared offsets to index properties of the struct, by name,¹ through a pointer. This part of it is essential to how we'll use objects.

Next, let's look at some real world examples that take structs and move them into the world of objects. I've been working on an object-oriented widget toolkit that will standardize the UI and making building fancy hierarchical "graphical"-like user interfaces easy and consistent. I say graphical-like because the toolkit works the way you expect a modern GUI to work, but in C64 OS it is implemented in the text-based video mode, because it's the only way to get super fast and snappy results on the stock c64. Don't be disheartened though, most c64 video games use text-mode to produce fantastic looking and very fast results and the user doesn't even realize it is text mode, thanks to customizable character sets and smooth scrolling.

Okay, so let's take a look at these two spec sheets. They are preliminary, they'll probably change as I build out the functionality needed to support certain types of behavior such as drag and drop, but I have begun coding the essential drawing behavior around how they are presented above. I'll go into much more detail in a future post about how the widget toolkit is supposed to work, for the purposes of this post I only want to show real world examples of how to structure objects that feature inheritance, encapsulation, polymorphyism and abstraction, and how to do that in 6502.

We have here a set of 6 classes: view, scroll, split, label, button and input. Eventually I will be adding more, but I see these as a good start, they will let me compose some pretty interesting user interfaces. These objects are arranged hierarchically, such that they all inherit from view. For this reason, it is appropriate to refer to all of them as "views", because although only the root view is actually called "view", they are all subtypes of the essential view. Here's what the hierarchy of inheritance for these 6 classes looks like.

So, as we can see, view is the root object from which the other toolkit sub-views descend. Let's look at view in detail for a moment and see what properties it has and how its original spec sheet translates into code.

So, you can see that from the spec sheet, the size (or width) of each element has been translated into offsets from 0. The properites of view offset from zero, because view is the root object.

The first two elements are 1 byte wide each. The first is a node type. Every class in the toolkit will be assigned a type id that allows either the OS designer's own code, or third party code, to easily identify the object type. It is here called a node type but we'll see more about how why that is and how it is useful in a future post about the toolkit. The second element is a generic id. This allows the developer to arbitrarily tag up to 255 different objects to easily identify specific ones, we'll also see in a future post how this is useful.

The following 7 properties describe the view's render size and positional characteristics. I won't go into the details of how these work here, other than to say that the last of these properties is a resize mask. It is one byte, for 8 bit flags. The flags define which of the top/bottom and left/right sides should be honored and which ignored. Notice that top, bottom, left, right, width and height are all 2 bytes, or 16-bits each. This allows a view's height, for example, to be up to 65535 lines high.

Remember, that all the toolkit objects descend from view. That means that the metrics properties of view will be automatically inherited by all other view subclasses. These are the properties that define how every view in the entire toolkit are sized and resized.

The next three properties are link pointers, allowing views to be hierarchically arranged. Every view is linked to its sole parent, or container view, via the view_prnt pointer. Every view has the ability to be pointed to its first child, via view_chld. And the view_nsib is a pointer from a view to its next sibling. If a parent view wishes to iterate over all of its child views, it starts by getting a reference to its first child, and then traverses down the list of its siblings. Again, because all views inherit from this root view, all views can be plugged together using these link pointers.

Object Methods

Still we only have properties. Even though some properties are pointers to other nodes, we have actually already seen this with plain structs. The next four properties however are very interesting. They are pointers to four methods.

The first, view_draw, is the method that is called by the system's main event loop during a screen redraw phase if something has marked the screen as dirty. The view object's draw routine simply clears out a square (both the character map and color map) that is defined as its draw region by its parent view. We'll get into much more detail about how this works in a future post, because it's a huge topic.

But view does something slightly more than this. It also iterates over its children, refines its own region bounds to the region into which the child should draw, and then calls the child's own draw routine. It repeats this for all of its children. This allows the child to draw its specific appearance overtop of the area just cleared out by its parent. Note that this draw behavior is also recursive, because the view's children are also views which may have their own children, and so on down the view hierarchy.

Polymorphism is absolutely critical to how this works. The view's own draw routine knows that each child view must have a draw routine. But it doesn't care whether the child is another view view, or if it is a subclass of view. It doesn't care what the output of its child's drawing is going to be, only that it can ask it to draw itself. This is the very definition of polymorphism.

Let me briefly say what the other 3 method pointers do before describing how the methods are selected and called.

These three: view_mouse, view_kcmd, and view_kprnt should sound very familiar if you've read this post. If you care about this stuff, I highly recommend you go read that post first. These methods match the three basic event types that are generated by C64 OS's extended KERNAL. Mouse events, Keyboard Command events, and Keyboard Printable Text events. For mouse events, whichever view object is clicked² becomes the first view to receive the mouse event. It does this simply by calling the view_mouse method of the clicked view. The implementation can then use a system call to read the details of the mouse event. However, by default, the view class doesn't have any particular behaviour for any type of mouse activity. So view's implementation is simply to call its parent view's view_mouse routine. Thus, each view up the hierarchy has an opportunity to handle the mouse activity.

The two keyboard event types, however, are dispatched on a principle of focus. One view is allowed to be in focus at a time. So the system maintains a pointer to the view in focus. If you click on an input, for example, the input's own mouse handling routine will tell the system to make it the view object with focus. After that point, when a keyboard event is generated, it is delivered to the focus view first, by calling the focus view's view_kcmd or view_kprnt method. Then, these methods behave just like view_mouse. If the focus view handles that type of keyboard event it can do something with it. Otherwise, it passes it up the hierarchy by calling the same method on the parent view.

Calling Object Methods

The question is, how to call the object methods. The first thing to note is that an object always has access to a pointer that points to itself, to its own data structure. That pointer is typically referred to as the this pointer. And so how pointers work on the 6502/6510 is pretty important. Pointers, for use in indirect indexed (or indexed indirect) addressing have to be in zero page. But that makes zero page a giant global variable space for everything going on in C64 OS. Much the same way there is only one stack. This is partially what makes the 6502 so ill-suited for premptive multitasking. On bigger CPUs, even the 65816, each process can have its own stack and its own zero page (known as direct page.) However, C64 OS is not multitasking so the only real worry we need to have is that the interrupt routine not use the same zero page addresses that are reserved for use by regular programs.

Next, we want to define a system global, or at the very least toolkit global, zero page address to be used as the currently executing object's this pointer. Toolkit internally uses $fb-$fc. But as I get further along in development I might change this to something lower that is usually only used by the BASIC rom, which C64 OS patches out.

What this means is that, whenever any toolkit object's method is running, it can expect to find itself pointed to by $fb-$fc. In code that interacts with the toolkit, we can use a variable this = $fb to get the flavor of an object. In order to call an object's method all we have to do is, back up the current this pointer to the stack and change the this pointer to point to the target object. Next, read the method pointer from the target object and write that pointer either into the address of an indirect jmp, or self-modding the two bytes following a JSR, and then JSR to the method. When the routine returns we restore the this pointer from the stack. All of this, by the way, could probably be wrapped up in a macro to make it feel a lot more like you're merely calling a child's method.

Let's see this in code.

The comments in the code make it pretty much self-explanatory. $fb is declared as this, so we can use this throughout the code knowing what we're talking about. The current object's this is shoved on the stack to back it up.

Next we use the .Y register as the indirect index through this, to grab a pointer to this object's child. The low byte is being transferred into .X instead of being written to this right away, because obviously, we need this to continue to be valid so we can read the high byte. After we've got both bytes, we write them both to this. This now points to the child object. But we want to call the child's draw routine. So we use .Y to reference the draw routine's offset. And read the pointer to it through this (which is now the child's this.) And write that draw routine's address to the JSR's argument.

Writing to the JSR's argument is a self-modification of code. I like it, because it's fast and clean. It doesn't port well to run from a ROM however, and you may feel dirty using it. Alternatively you could write the address to somewhere in ram that is reserved as the address of an indirect JMP. (JMP ()). And then just JSR to that JMP (). But, I like the self-mod. The draw routine for the child now assumes that the this pointer points at itself, which it does. And it may repeat the process to call the method of some other object.

When the routine returns, we can restore the this pointer from the stack. Now, if this is the very end of the routine and we don't care about restoring this, we could skip the backing up and restoring of this. Whether you need to depends on who is going to be calling this routine. If it's only ever called by some other object, then the this doesn't need to be restored. If it's ever going to be called by another routine of this object, then the this has to be restored.

A little preview of inheritance

I'm cognizant of how long this post is becoming, so I'm going to wrap it up with this last section, and save many of its details for a future post.

But, let's suppose we are implementing the label class. What does it mean for it to be a subclass of view? How does it inherit from view? Well, here's what its data structure would look like.

The comment indicates that it descends from view. And so each of its properties have their offsets prepended by "view_size+", which means their offsets follow all the offsets defined by view. And lastly, label_size is set equal to view_size plus the additional size of the properties added by label. That's very cool. If we were to go back and add an extra couple of properties to view, and adjust view_size accordingly, then everything that's been coded for label will automatically get the new correct offsets and size when reassembled.

If another class, say button, descends from label, then its definition does not need to reference view. Button simply prepends its property offsets with "label_size+". And it specifies its own size as button_size = label_size+... however big the additional button properties are. Again, that's really cool. Because we could even add an intermediate class between view and label. Label would have to be updated to change who it inherits from, but button doesn't have to be changed at all, since it would still inherit from label. Startin' to see some cool design benefits here.

I don't have space here to go into how these classes are instantiated, nor how their constructors work. But in my next post on this topic I'll cover how memory is allocated, how the nodetype id is assigned, how the constructor method is called, how the constructor assigns method pointers, and how subclasses are able to override and extend their superclass's constructor and other methods.

Once again, if you have questions, thoughts or corrections, please leave them in the comments section.

1. I should emphasize, "by name" is only at assemble time. Once assembled the program will have hard numeric offsets. If the OS designer changes the order of the properties or adds new properties to a superclass it would the property offsets of any subclass. The assembled program will no longer reference the correct offsets. One way to get around this is to have the program lookup the offsets at runtime before using them. However, there would be a speed penalty. [↩]
2. And how it is determined which view was beneath the mouse when the mouse was clicked is a huge topic for yet another post. But suffice it to say that it's the result of what is called hit testing. [↩]

Do you like what you see?

You've just read one of my high-quality, long-form, weblog posts, for free! First, thank you for your interest, it makes producing this content feel worthwhile. I love to hear your input and feedback in the forums below. And I do my best to answer every question.

I'm creating C64 OS and documenting my progress along the way, to give something to you and contribute to the Commodore community. Please consider purchasing one of the items I am currently offering or making a small donation, to help me continue to bring you updates, in-depth technical discussions and programming reference. Your generous support is greatly appreciated.

Greg Naçu — C64OS.com