On 10/15/12 12:40 PM, Anton Ertl wrote:
> The EuroForth 2012 proceedings and the individual papers and/or
> presentation slides are now available
I found your paper on Duck Typing to be well done and pertinent.
It is encouraging to see Duck Typing explored in this manner. I
personally believe that Duck Typing for a Forth objects extension holds
advantages (I've discussed them before and won't repeat them now).
A few initial observations/questions:
In Figure 1: it appears that the dispatch tables for every class defined
contains an xt cell for every message defined. There are four classes:
object, A, A1, and B. There are two messages: foo and bar. So there
are a total of 4 x 2 = 8 cells total used for the method xts:
Figure 1: (abbreviated)
object A A1 B
foo xt xt xt xt
bar xt xt xt xt
But the code for the classes show that there are just 4 methods used not
counting the not-understood xts:
:: foo ." foo-A" ;; \ first method
\ foo is inherited from class A \ second method
:: bar ." bar-A1" ;; \ third method
:: foo ." foo-B" ;; \ fourth method
So couldn't the number of cells used be reduced to four?:
object A A1 B
foo xt xt xt
I believe I understand that the other xts are intended to be used for
1) Provide a "message not understood" development debugging mechanism.
2) Allow for a possible default method in the case of a not understood
But 1) could be done by maintaining a count of methods for each class
and checking that count during method execution. This check is
analogous to an array check and would only be done during development.
Removing the check for production code would restore the run time
The need for 2) I think was questioned by several people. Maybe it's a
good thing. I don't know. Perhaps it could be optional?
Regardless, Figure1': represents one dispatch table sixe reduction
technique that Vitek and Horspool call table trimming. I use it in FMS.
But perhaps I don't fully understand the implications for the overall
dispatch scheme used in objects2 and this trimming may not work there.
Also, I am assuming that all message names have global scope, which
seems like the best way to go, IMO.
Regarding sparse dispatch tables, it seems that with the "unhashed
general selector" scheme that you present in the paper (which is
essentially the scheme used in the dispatch table version of FMS) it can
be important to pay attention to the number of different message names
used and also the order of class definitions with those names. To
illustrate with an extreme example: This only applies to a table
trimming scheme as I show in Figure 1': above. If one first defines a
class X using 100 message names then a table with 100 cells (100 xts) is
needed for X. If one then defines a class Y that uses only one message
name, but it is a different name from any of the 100 in class X, then Y
will have 101 dispatch table cells with the first 100 cells empty. Had
class Y been defined first it would have had only 1 cell, and class X
defined second would have had 101 cells. A savings of 101 cells simply
by changing the order of class definition.
Btw, there is a fairly simple way to "compress" the 100 empty cells in
class Y, had Y been defined after X, but I won't get into that now.
Also, and I believe this is important but often overlooked, message
names in OOP are simple generic verbs and can (should be) re-used as
often as practicable. This "best practice" will minimize the number of
message names and pay off in fewer names to remember and significantly
smaller dispatch table sizes. I have seen message names used like PUT
and PUT$ when PUT would have sufficed for both.
In section 8 of your paper you mention that FMS "seems to be based on a
compressed table". This is true, only for the dispatch table version,
and uses a scheme like I mentioned for compressing the 100 empty cells
in class Y above. But the latest FMS dispatch table package in FLAG is
a Multiple Inheritance(MI) OOP package. Because of this, extra
information must be carried in the tables. Any size/speed comparisons
to this version should also have MI capability for an apples-to-apples
analysis. The MI capability necessarily leads to somewhat larger tables
(hence the use of compression) and somewhat slower late binding speed
due to the extra information that must be retrieved. This size and
speed trade-off may or may not be important to the user.
I should also mention that a linked list approach with multiple "bins"
for the linked lists can provide a surprisingly efficient late binding
mechanism for both size and speed. The linked list version of FMS uses
a scheme with several important improvements over that used by McKewan
Again, a very good paper. It has provided some new and useful insight
to me. Hopefully we can continue to converge on the best ideas for
Forth OOP, like Duck Typing, and how best to implement them.