In the RISC Vs. CISC thread on this forum, it diverged somewhat into a discussion on implementing something that is becoming increasingly popular in all areas of programming, including embedded systems (hence its applicability to the 65816): object oriented dispatching mechanisms.

Object orientation has proven its worth time and time again. To be fair, OO is, really, nothing more than modular programming taken quite literally and seriously, for the first time in comp-sci history. The only true innovation it offers distinct from MP is that of type inheritance, or more often called interface inheritance. Note that I'm distinguishing type from class. There can be a number of classes which all fulfill the same basic type. For my purposes, though it's not strictly true in a mathematical sense, a type can be thought of as a purely abstract base class.

However, today, inheritance is being seriously questioned as a valuable addition, as it's been proven that aggregation and delegation can do everything inheritance can, but the reverse isn't true. Indeed, most modern OO implementations now have either very tight control over implementation inheritance or refusing to support it at all, while still offering freely interface inheritance. Systems which lack support for implementation inheritance (e.g., COM and CORBA, the latter of which is becoming increasingly popular in embedded environments too) implement its equivalent with aggregation and delegation behind the scenes instead. Often these systems have dedicated support languages (e.g., IDL in both COM and CORBA) which hides these behind-the-scenes activities, but let's be realistic: in a tight embedded environment, you're probably going to want full control over the runtime of the system.

For this reason, and for the sake of general education, I think it's strongly desirable to explore how to perform object oriented dispatch that satisfies the requirement of high speed and/or low memory overhead (obviously, preferably both).

On other CPU architectures, objects often include a pointer to a "v-table" or "entry point vector", as CORBA calls the concept. I'll use CORBA's terminology, since it's easier to abbreviate: EPV. This is known as static dispatching, because everything needed to make it work is (conceptually) able to be pre-determined statically by the compiler.



This is literally how C++ works, and conceptually how CORBA works (the real details of how CORBA implements objects depends on the specific language binding, choosing to use the language's own mapping of objects if available. If not, as is the case with C, it defines a mapping-specific method of constructing objects).

There is an alternative approach as well, called dynamic dispatch, where the infrastructure to make method invokations work is not known a priori by a compiler, and hence must rely on run-time knowledge to work:



Notice in the class implementation for Bar (which we presume to be a subclass of Foo) that we "cherry-pick" the specific methods we recognize, then if not recognized, we just pass the request to the base class. This is how AmigaOS's BOOPSI, Objective-C, the C language mapping for CORBA, and Smalltalk all work.

Also notice how the dynamic dispatch system gives the class implementor the choice of how to implement the actual dispatch mechanism. Foo uses a table-lookup, like a statically dispatched EPV-based system, while Bar cherry-picks. There are advantages to both -- the former is comparatively fast, while the latter makes adaptability, flexibility, the ability to catch unimplemented methods, and even support for multiple implementation inheritance (in the Sather sense) much easier. For example, in Objective-C, you can create a CORBA-like remote-object system without the use of a dedicated IDL compiler, because the object proxies and skeletons needn't know a priori of a class' interface -- it learns this information dynamically.

In an object oriented system for embedded applications, there will typically be a strong ability to domain optimized the code so that most OO dispatches can be optimized to a simple subroutine call. This is obviously a strong goal, for all CPU architectures, not just the 65816. This is why C++ makes it relatively hard to use virtual methods ("If I have to type the virtual keyword ONE MORE TIME...."), to encourage a more static binding between an object's client and implementation for the sake of speed.

However, this won't always occur. OSes and device drivers are a prime example. Most OSes today offer what is called "device independent I/O", meaning that you can use the same interface (e.g., a file-like interface in the case of Unix, or a request block interface for VMS and AmigaOS) for most, if not all, devices, regardless of the kind of device. The problem is, however, you need to implement this interface with speed in mind, as when hacking hardware, real-time response is critical (consider sound-card modems for example!).

I posited in the RISC-vs-CISC article that the 6502 and 65816 really aren't engineered to support OOP in any real capacity, and I stick by that assessment. However, others have come up with good ideas for implementing the concept with various design tradeoffs which lend themselves towards certain applications.

You're really not going to make a dynamically dispatched system any faster than the sum of all its comparisons and failed branches, so the 6502/65816 is about as fast as any other CPU in its class for that. Therefore, the remainder of this thread will concentrate on statically-dispatched method invokations. The assumption is that method calls occur frequently enough to constitute a significant portion of runtime.

OK, that really sucked. I had this big write-up, and now it's gone, because my session timed out. I'm too tired to rewrite what I'd written, so it'll just have to come later. However, everything I was going to write can be found in the RISC Vs. CISC article anyway, so it's just a matter of distilling it.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Its always seemed to me that processor performance and memory size was the factor that held back OO. The idea was in the 60's but it didn't really reach the masses until PCs and workstations had enough memory to hold all the additional type and interface information needed to compile a strictly typed application.

Early OO languages gave you plenty of rope to hang yourself and I regularly saw C++ programmers hanging from the trees on major projects (and a few Smalltalk ones too!). Unfortunately 'patterns' came out five years after language giving people plenty of time to develop bad OO habits like multiple inheritance - although curiously this is what 'interface' style programming is all about, except with all abstract virtual functions.

Its always been the case that good programmers write decent code and use the facilities of langauge appropriately. Its the bad ones you have to worry about . Remember, you can write FORTRAN in any language.

All the C++ compilers I've used in the last 17 years have used the first approach (EPV) for derived classes (like your second example) but the 'vtable' (table of pointers to functions) would comprise of a mixture of foo and bar function addresses.

I've always avoided Objective-C - It breaks my 'don't learn to program in a language that only has one book about it' rule (although I did break the rule for BCPL - I was young and foolish at the time). I used to work with some people who wrote an investment banking trading system on NextStep with it. They thought being able to override any function (even ones in system libraries) was pretty cool but then went on to tell me how they spent days tracking down obscure bugs caused by poor overriding.

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

True to some extent, but not all of it; OO was researched in the 60s, but it wasn't solidified as a consistent, general-purpose coding technique until Smalltalk was released to the public in 76. Prior to that, the Simula language, designed for simulations, dominated the OO philosophy, and due to its bias, was really considered only for simulations.



They still do.



Umm...these are 1000% different concepts. Patterns exist independent of language; if you don't believe me, pick up "Design Patterns." Some examples are in Java, some in C++, but most are described in Smalltalk. None use multiple inheritance.

Moreover, design patterns are so language independent that I've successfully used them in non-OO languages. AmigaOS implements a number of patterns described in the "Gang-o-four's" book, yet is written entirely in C (except for AmigaDOS prior to release 2.04, which is written in BCPL). I've even identified my own pattern, though I have not formalized it yet. It basically says, if you have any kind of database, you need to offer at least three kinds of access functions if you want to eliminate headaches down the road: functions to add items to the database, to remove items from the database, and functions to query the state of the database. Seems pretty obvious, but you'll be amazed at how rarely this is fulfilled, and how often I've had to work triple-time to circumvent it. But I digress.



Interfaces are the realization by the academia and industry at large that OO didn't deliver on its components promise. This is because classes are not atomic enough. A class is both a type and a physical implementation. An interface is just a blueprint for a type.

Consider that your home probably has a large number of different tables. You have your kitchen table, I'm sure. But what about the nightstands next to your bed? Those can be used as tables, and often are. What about lone shelves or shelf overhangs? A lot of times, those are also used as tables. Then of course there are counters, which are just tables embedded into or bolted onto a wall.

Each of these kinds of objects exposes the same basic interface: a large, flat surface on which you put things on, and expect it to remain stable and sustain the weight. However, the specific classes are all different: a nightstand is not a kitchen table -- it's usually smaller, has no legs, and usually has two or more drawers in it underneath the platform. Also, you usually cannot expand a nightstand by inserting leaves, like you can with (e.g.) a dining room table.

So we can still say they're the same *type* of object, despite not being the same *class* of object.



I'm not talking about that. I'm expressly talking about dynamic dispatch. I thought I made that clear.



This is a bogus rule, because at the time, Objective-C had quite a few books on it. There was the original Cox book on it, then the one by NeXT, Inc. At the time, C++ was still a research project in AT&T Bell Labs, and was changing so fast that it couldn't even be approached by an ANSI committee.



And C++ fixes this . . . . . . how?

* object -- Something. Anything. Whatever you want. An object can represent something on the screen (e.g., a button inside a window), something intangible (a collection of other objects; e.g., the contents of a window).

* inheritance -- The ability to say that something is like something else, except for a set of specified differences. For example, a directory is like a file -- it has a filename, a creation datestamp, a modification datestamp, a set of permissions, a disk space quota, etc. It differs from a file in that you cannot open it or read from it in any streaming fashion. (Indeed, UNIX implements directories internally as structured files).

* binding -- The definition of this depends on context.

* type -- You cannot add an integer and a social security number -- the two are fundamentally different types, the sum of which is meaningless. You can, however, add a natural number to a floating point number -- this is a perfectly natural thing to expect, even if a natural number and floating point number are not of the same class. Which brings us to . . .

* class -- A specific kind of some type. As nebulous as it sounds, it's actually pretty concrete. You have soda cans and coffee cans, for example -- both are types of cans -- they both expose the same basic human interface, and can be used to hold some kind of contents.

* base class -- in the above can example, we can define can to be the base class for both soda and coffee cans. This base class serves as a foundation for categorization. A box, for example, is clearly not a can, despite being able to do the same basic kinds of things a can can do. For this reason, cans and boxes can each, in turn, be subclasses of a single container class.

* subclass -- a more detailed or specific kind of object. For example, soda cans and coffee cans are subclasses of cans. But Coca Cola cans and Pepsi cans are subclasses of soda cans. I have never heard of a Pepsi coffee can. Conversely, I have never heard of Sanka brand soda either.

Here is a good point to tie in classes with interfaces/types. With such a strict hierarchy of categorization, how does one account for all the different diet products out there? With inheritance, you can't -- unless you rely on multiple-inheritance, a god-awful hack that allows you to say that a DietCocaColaCan is both a SodaCan and a DietProduct, while still being able to share implementation details. That is, if I invoke the method UsesAspertame() on a diet coffee can object, but I didn't explicitly define it myself, the programming language needs to figure out how to invoke the right method! For this simple exercise, it usually gets it right. But what if I create a class that inherits from SankaCoffeeCan and DietChocolateBeverage? Sanka's implementation of UsesAspertame() will return FALSE, while DietChocolateBeverage's will return TRUE. How do we resolve this?

Interfaces are a means of supporting multiple interface inheritance, while still only supporting single implementation inheritance, thus providing a happy medium. I can inherit from the class that best solves the problem at hand, while still filling in the rest, as if I had full multiple inheritance available to me. Thus, I get to manually choose the result of UsesAspertame() because I have to either manually invoke Sanka's or DietChocolate's implementation, OR, just return the result myself.

At this point, I should point out that maybe I'm creating a whole new class hierarchy of deserts with this (e.g., let's call the new base class SomeStarBucksConcoction). This new class may not even be in the hierarchy for Cans nor for DietBeverages. Yet, because they still expose all the same interfaces, they are still of the same type as far as the client program is concerned.

Hopefully, this helps disambiguates single-inheritance, multiple-inheritance, and types.

* aggregation -- Extending behavior by creating a large crate of different objects, which are (behind the scenes of some client software module) preconfigured to work together. To use the example above, SomeStarBucksConcoction would be an aggregate object, since it would embed both a DietChocolate object and a SankaCoffeeCan object, preconfigured to work together, seamlessly. Extra credit to those who can successfully explain why inheritance is just a form of aggregation taking place behind the programmer's back.

* method -- I remember seeing a very clear explanation of why these are called 'methods,' and it's lost on me now. So I'll try to recall from memory. Basically, asking an object to do something is basically sending a message to the object. So:



shows the client sending PrintStatusOn() to myObject. How (the "method") this is done is dependent entirely on the object's class. Hence, the specific implementation that gets executed as a result of a message is called the method. The act of sending a message, since it results in its invokation, is also known as "invoking a method." The term "sending a message" is used often in Smalltalk circles while "invoking a method" is used heavily in C++/Java/C# circles, but they both mean precisely the same thing.

* a priori -- a Latin idiomatic phrase (of the same class as "de facto", or "et cetera") meaning "known ahead of time." In the context of compilers, this means that the compiler can either know or deduce critical information at compile-time, before the program is actually run.



No, this actually would be a run-time effect. A better example is this: a compiler will know "a priori" that a method's address will be the fourth entry in an EPV because it's the fourth item in the interface function list, as specified in the source code.

* Sather -- an object oriented programming language that, while never becoming very popular, proved worthy in its research results. It inspired the whole concept of splitting implementation and interfaces, thus providing the awakening academia/industry needed to finally realize the goal of component-driven software design.

* IDL -- Interface Description Language. A language that is used to make up for the lack of expressivity of traditional, statically compiled languages like C++, C, etc. for describing network communications protocols. For example, suppose we want to describe a filesystem as a set of C++ objects. This is relatively easy to do provided you use these objects within the program that's using them. But what if you want to access a filesystem remotely, e.g., across a network? You need to create different kinds of objects that fulfill the basic class definitions for files and directories, but translates the method invokations into network requests. You could do this work manually, but it's tedious. Why not instead just let a computer program auto-generate the code to manage the network connection for you instead? But, it doesn't know what you want until you tell it. That's the job of IDL -- to tell this special compiler what you want to expose via the network.

* object proxies and skeletons -- remember the IDL compiler discussed above, and how we expose a filesystem interface using it? Well, those "stand-in" objects that "look like" normal files and directories but really aren't are known as "proxies." On the opposite side of the network connection are "skeletons," which translate incoming network requests into local filesystem object method calls.

* domain optimization -- an example is better than a formal definition. If I write an OO program, and later learn that all of my method invokations can be resolved by simple subroutine calls, then it follows I really didn't need to use an OO language in the first place. I could just call subroutines instead, and avoid all the static and/or dynamic dispatch overhead. Another example: if I know that the output console will be 80 columns, then I don't need to write an output routine that auto-wraps paragraphs. I can pre-wrap the paragraphs at edit-time (e.g., as I'm entering the program) and never have to worry about it at run-time.

* edit-time -- when you're entering a program's code.

* compile-time -- when the compiler is parsing and generating code from your source code.

* load-time -- at the time the program is being loaded from disk and is being relocated/fixed-up in memory.

* run-time -- while the program is running.

THAT is OOP? I called it jump tables back then

_________________
"My biggest dream in life? Building black plywood Habitrails"

I think you should separate the concept of the container (the can) from the beverage into two classes. If you wanted to add soda bottles to this type heirarchy you would end up duplicating the implementation of beverage functions.

Its a good example of where aggregation can be used to make the business objects clearer and more reusable.

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

That's how the example is, as I read it.



I actually would like to try making a language someday that is purely aggregation/delegation based, just to see how it compares with traditional OOP languages. My hunch is that MOST programs wouldn't be too adversely affected. Ahh, if only I had the time.

No, jump tables alone does not make OOP. There is also an element of philosophy, as well as strongly modular design practices. Working with an object oriented programming language, you'll see that modular programming is virtually enforced by the compiler, even on sub-module units (which classes indeed are).

I have written quite a few OO programs in plain C (and even assembly language), and never once relied on a jump table (I cloned BOOPSI under Linux once, for example). I have also written quite a few procedural programs that were dominated by jump tables. AmigaOS libraries, for example, use jump tables to provide linkage with external modules. But, they are neither objects nor classes.

Like I said: OO is proper modular programming taken seriously and quite literally. Abstract data types are well defined, with a black-n-white clear distinction between interface (the class definition) and implementation (the actual code that backs one particular class definition). A program's lifetime in memory often is determined by how many objects it's responsible for implementing are still in memory. For example, with AmigaOS's BOOPSI system, when a class' object counter drops to zero, that piece of code is eligible for being unloaded from memory.

For example, consider a window. What can you do with a window? Well, you can draw its contents on the screen. You can accept mouse button events, and you can accept keyboard events (assuming it has focus). So we can probably define a "class" thusly (using an Oberon-line syntax, but it isn't Oberon):



So, yes, each class will have a jump table that consists of entries corresponding for ButtonDown, ButtonUp, MouseMoved, Redraw, Resized, and KeyboardFocus. But there inlies the key: each class has this jump table. There is no one jump table for all window entry points. This makes sense, since I could have several different types of windows: I could have pushbuttons, pop-up menus, or even complete applications like a calculator, or even a word processor, each of which will have different sets of jump tables.

I almost forgot: note that these jump tables do not exist in the objects themselves. I mean, they COULD if you really wanted to (this is how Unix implements file descriptors behind everyone's back, for example). But that'd be wasteful if you had TONS of objects lying around (e.g., in most word processors today, individual letters on the screen are objects!). Instead, you simply maintain a single jump table per-class, and have each object of that class refer back to its jump table (directly as in the case of C++, or indirectly). See the ASCII-art diagrams earlier in this thread.

As long as the client knows (a) how to get at the method pointers given only an object reference, and (b) that the object of the desired class is being used, then the desired results should occur upon invoking the method, even if the *precise* class isn't known in advance.

The other ability of OOP is to be able to express categorization relationships. The window defined above is adequate for things like check-boxes and pop-up menus, but what about individually labeled gadgetry, like push-buttons and desktop window frames? There are three ways of handling this. Windows solved this by just declaring all windows are labeled, and that primitive types of windows just ignores the label field. This is, in this case at least, acceptable, and memory overhead is negligable. But, not "mathematically pure".

To demonstrate the second approach, let's define a new class called LabeledWindow which subclasses, or extends, the core Window class functionality:



Notice how we declared a whole new type of object, by saying it is like Window, except it has a new data field, and two new methods associated with it. Hence, a LabeledWindow is a Window (proof: look at how it's laid out in memory, and you'll see the compiler internally uses aggregation to make this work, by first laying out a Window in memory first, then laying out the LabeledWindow-specific fields afterwards). Note that the reverse is not true -- not all Window objects are LabeledWindow objects.

And now, the third approach is that of aggregation:



Note that we need to replicate the interface of the Window. Fortunately, we can rely on delegation to get out of all the hard work:



Still a fair bit of typing, but it turns out that this is *almost* identical code to the inheritance method, and produces *exactly* the same layout in memory for the objects themselves.

Still, there is that small problem of what happens when you have LOTS of labels (e.g., a drop-down menu or pop-up menu, for example). How do you handle those? The answer is through a related concept called containment.



I think you can see where this is going, and how object oriented programming differs from plain-vanilla procedural or even jump-table programming (but, don't fret: note how OO builds on procedural, so procedural isn't going away any time soon). I'm babbling now, so I'll stop here.

tis ok, I was babbling that night too, but thanks. I THINK I am modularizing for my pinball program. It has a main event loop but does certain procedurals in sections of time. I had posted its conceptural in here somewheres...


gotten a phone call, people definitely wantthis puppy to be running...

_________________
"My biggest dream in life? Building black plywood Habitrails"

That's OK -- nothing wrong with working code. Don't mess with success.

And I'm not saying that OO is better than procedural. Remember that OO builds on top of procedural programming (eventually, let's admit it, someone somewhere does have to actually code a method!!).

OO is best used for:

1) when you think natively in terms of objects -- this only happens with practice really.

2) when you're dealing with a *LOT* of similar, but relatively rarely the exact same, kinds of objects. For example, a graphics drawing program might support lines, circles, text, pictures (either vector and/or bitmap), etc.

3) when you require a high-degree of open-ended expansion capability. E.g., GUIs (no GUI to date has been able to predict all possible programs and all possible widgets on the screen), device driver frameworks, art software plugins, word processing embedding or linking other documents, etc.

I've been thinking about how OO isn't really 65xx's strong point, and my best "general purpose" solution is about triple the cost of a combined subroutine call and return. dclxxvi (sorry if I misspelled it) came up with a speedier solution, but at the expense of general purposeness. It doesn't help that I don't have my databooks handy while I'm on vacation.

Depending on the context, a possible alternative would be a more table-driven approach, where a "class" (the template of a particular kind of object) is better known as a "schema," and individual "objects" are basically individual rows in a table/database. The 6502/65816 seem to excel at table lookup due to the ABS,X addressing mode. However, how polymorphism is handled isn't clear to me yet, unless we store both the EPV and the instance data in the table as fields as well. However, as explained above, tihs can be very wasteful of memory, especially if most rows will have the same values for that field.

Something to think about...

Hint: it's Roman. (I wish I could claim credit for thinking it up, but I ripped it off from an Entombed song. I even have a Entombed t-shirt with that across the top that I got at a concert around 1994 or so.)

Glad I could help.