[Oberon] Numerical CASE Statements in Project Oberon (was: RISC.img)

[Jan de Kruyf]

Here are some thoughts regarding the numerical CASE implementation.:

I have looked at the execution cost of a jumptable, and I have looked at
the cost of a binary search algorithm.

It appears that for up to about 10 case arms the average execution time
might well be even. ( I am not good at detailed execution time calculations
for binary search)

But this is only in the case with a specially constructed piece of code. It
would basically be an IF THEN ELSiF construct that starts comparing with
the case arm at the root of a binary search tree which is constructed out
of the case arms.

The search time of a binary tree increases roughly with log2 of the number
of nodes, so it is always substantially cheaper than a straight IF THEN
ELSiF.

There is an added advantage: ranges are very easy to implement. Basically
all values that you see in your code have a node in the tree. The search
algorithm lands on a leaf that is NOT a node when the case value is not in
the tree. That node will be marked ( and will generate a branch) if it is
within a range that was specified in an arm, otherwise it will generate a
branch to the CASE ELSE.


If anybody has some thoughts about this, or perhaps has a different
algorithm. Please feel free to comment.

Cheers,

j.



On Sat, Nov 7, 2015 at 5:38 PM, Jan de Kruyf <jan.de.kruyf at gmail.com> wrote:

> Hallo Chris,
> Thanks you for your answer
>
> > Don't even think about implementing it unless you are planning to do it
> properly -
>
> Didnt read anything like that in the License :)
> Perhaps say "I will not even think of using it, or voting for it -"
>
> If that is what you meant: you are most welcome, ha ha.
>
> Now for more serious matters:
>
> I have constructed smallish compilers before. I do understand the flow of
> the O7 Risc compiler. I have not done a CASE construction before, but I do
> understand the different ways of doing it.
>
> You might have noticed that I like to work in public, mostly because my
> brain is not as nimble any more as it once was, so every extra pair of eyes
> helps. So if I am going to do this I would expect lots of sound input, like
> yours,  from the community. I am sure that in that way most issues will be
> gracefully resolved.
>
> > RISC6
> Pray, send me the documentation. By the way, I feel seriously limited in
> any Oberon environment by the fact that nobody uses a version control
> system. I do not find that conductive to clean working. Finding something
> is forever a hit and miss game.
>
> > constant performance
> I am aware of
> a. a direct jumptable
> b. a binary search in the jump table
> c. hashing the index.
> d. combinations of those to be decided upon at compile time.
>
> For the time being I was getting my stuff together for item b. -- c. is
> often more trouble than it is worth and a. makes for a big table in the
> case of a range.  But perhaps I might consider making a combination of a
> and b. I have not finished my think or gotten enough input from the
> community yet.
>
> > However, if constant performance overhead is . . .
> Sure there are many ways to do things, I was triggered by the elegance and
> ease of the CASE statement. I have often used it in preference to anything
> else, for clarity.
>
> > I can't see anywhere in the report that states that "when not all cases
> are catered for . . .
> That statement should have been thought through a bit more.
> In any case:
> The green book (O-2) says  (A.5.9)
> . . . . the symbol ELSE is selected, if there is one. Otherwise it is
> considered as an error.
>
> i.e I would suspect a trap at runtime if a CASE was not resolved and there
> was no ELSE.
>
> In Ada all possible values of the input variable must be covered in the
> CASE statement (including the optional ELSE), otherwise the compiler will
> complain. (Remember in Ada a type can have a range of valid values
> specified, this is not so in Oberon)
> So in other words: the ELSE statement would be a way of complaining
> gracefully that the CASE is not complete, or that there is an exceptional
> condition, as we also often use it in an IF THEN construct.
>
> A partial parse of an Oberon source file comes to mind:
>
> CASE sym OF
> a : ...
> | b : ...
> | c : ...
> else
>      GetSym;
> END;
>
> At the moment (in the absence of a numerical case) this type of construct
> is handled by IF THEN ELSE in the O-7 compiler.
>
>
> > but that is all I can think of for now,
> Thanks again for your input. And I am sure other people will also have
> something to contribute here.
>
> Cheers,
>
> j.
>
>
> On Sat, Nov 7, 2015 at 3:03 PM, Chris Burrows <chris at cfbsoftware.com>
> wrote:
>
>> >
>> > From: Oberon [mailto:oberon-bounces at lists.inf.ethz.ch] On Behalf Of
>> > Jan de Kruyf
>> > Sent: Friday, 6 November 2015 8:37 PM
>> > To: Paul Reed; ETH Oberon and related systems
>> > Subject: Re: [Oberon] RISC.img
>> >
>> > 2. Question:
>> > I see that the 'numerical' CASE implementation is missing in ORP.Mod,
>> > although it is in the language spec and although we might reasonably
>> > expect people to port programs from O2 to O7.
>> >
>> > Would it be in the interest of the community for me to try and
>> > implement that part, at least for constant labels?
>> >
>>
>> Don't even think about implementing it unless you are planning to do it
>> properly - a half-baked solution would be worse than none. e.g. I would
>> expect a complete solution to include the implementation of a RISC6 (or
>> RISC5.1 maybe?) processor which has indexed-branch statements.
>>
>> > I am aware that 1. a table driven CASE might take up some codespace
>> > and 2. that coding it as an IF THEN ELSIF THEN will bring no speed
>> > advantage. But at the same time there are many instances where a CASE
>> > statement is easy to write and convenient to read.
>> >
>>
>> Apart from 'convenience' an advantage of table-driven CASE over IF THEN
>> ELSIF is that each case usually has a constant performance overhead - there
>> is no preferential treatment for any of the cases. This contrasts with IF
>> THEN ELSIF ladders where it takes longer to reach statements at the end to
>> execute them than those at the beginning.
>>
>> However, if constant performance overhead is a requirement it does not
>> necessarily need the existence of a 'numerical' CASE. Another possible way
>> of achieving a constant performance overhead with Oberon is to use an array
>> of procedures where each array element corresponds to each case label.
>>
>> >
>> > 3. Question:
>> > Why does the numerical CASE have no ELSE part anymore in O7. It is a
>> > very convenient error catcher. (i.e. when not all cases are catered
>> > for, the program does not silently fall through without warning.)
>> >
>>
>> I can't see anywhere in the report that states that "when not all cases
>> are catered for, the program silently falls through without warning". That
>> is not necessarily a correct assumption - one alternative possibility might
>> be to raise an error. Other error-handling behaviour including how to
>> handle duplicate labels, descending ranges etc. etc. would also need to be
>> specified for a complete solution. Implementation limits would also need to
>> be specified e.g. minimum / maximum value of labels etc.
>>
>> There might be other considerations but that is all I can think of for
>> now,
>>
>> Regards,
>> Chris
>>
>> Chris Burrows
>> CFB Software
>> http://www.astrobe.com
>>
>>
>>
>>
>> --
>> Oberon at lists.inf.ethz.ch mailing list for ETH Oberon and related systems
>> https://lists.inf.ethz.ch/mailman/listinfo/oberon
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.inf.ethz.ch/pipermail/oberon/attachments/20151109/f70a5f89/attachment.html>