Re: Jump tables and OOP in Oberon

Ram Meenakshisundaram wrote:
>
> Also, Oberon has an IS statement that returns TRUE or FALSE if a variable
> is inheriated from a particular type. That is if variable x is of type C and
> type C is inheriated by type A, then the following would return true:
>
> IS(x, A)
>
> How can this be implemented the most efficent way? I was think about creating
> a pointer for each Object. Each pointer Object will point to its parent.
> Each Object variable would have a pointer to its Object pointer. To determine
> if a variable is of type X, one only needs to traverse through the object
> tree and see if the variable's object pointer is the same as the one specified
> in the IS command. The only problem I can see with this implementation is
> that it requires:
>
> (z + 1) * 4 bytes, for each Object type defined and z is the number of
> variables declared as that Object.
>


There was an article in ACM TOPLAS that gave a way to test whether the
type of a variable is an extension of another type, without using a loop.
It uses a little more storage than the method you describe.


The reference is


                author = "Norman H. Cohen",
                title = "Type-Extension Type Tests Can Be Performed In Constant
                                              Time",
                journal = acm:toplas,
                volume = "13",
                number = "4",
                pages = "626--629",
                month = oct,
                year = "1991",
                abstract = "Wirth's proposal for type extensions includes an
                                              algorithm for determining whether a give value belongs
                                              to an extension of a given type. In the worst case,
                                              this algorithm takes time proportional to the depth of
                                              the type-extension hierarchy. Wirth describes the loop
                                              in this algorithm as ``unavoidable,'' but in fact, the
                                              test can be performed in constant time by associating a
                                              ``display'' of base types with each type descriptor.",


and


                author = "N. Wirth",
                title = "Reply to ``Type-Extension Type Tests Can Be Performed
                                              In Constant Time''",
                journal = acm:toplas,
                volume = "13",
                number = "4",
                pages = "630",
                month = oct,
                year = "1991",
                sjb = "Agrees with Cohen's proposal and notes that it doesn't
                                              suffer from the problems of a ``display'' for
                                              procedures i.e. that they need to be updated at
                                              run-time.",
--

Return to the comp.compilers page.
Search the comp.compilers archives again.