[Oberon] Numerical CASE Statements in Project Oberon

[Jan de Kruyf]

Hallo John (again)

I finally read your code properly, it looks quite good. And it is easily
build without writing a compiler section for it
by using hi level IF THEN etc. It will give the same code I am sure, from
what I read in the present compiler.

So we can have a shoot out and get some statistics I would say :) since
your case selection will be very slightly faster for very small case
statements., or where there is a skew to the very low end of the range of
labels.

Other than that I diligently read the Project Oberon book just now on the
matter, since you claim to speak for the master. But I found that in the
O-2 compiler he made as big a mess building a jump table, as I do building
a bin tree. On top of it he limits himself of necessity to 128 case
constants / ranges while I am theoretically unlimited. (not that it will
ever make a difference of course) But at that kind of sizes his should run
much faster, and probably on average eat more program memory.

cheers,

j.



On Thu, Nov 19, 2015 at 4:10 PM, John Stout <JSS at kgv.ac.uk> wrote:

> Jan
>
> I wasn't suggesting that we NOT implement it, just that compiling it
> (implementing it) to a
> series of compiled IF THEN statements may be more in keeping with NW's
> view.
>
> Suppose we have (taken from the Oberon-07 report):
>
> CASE k OF
>  0: x := x + y
>  | 1: x := x − y
>  | 2: x := x * y
>  | 3: x := x / y
> END
>
> This would compile, using IF THEN equivalents, to code like this (I've
> assumed that R14 is a base register):
>
> LDR0, R14, k_offset
> SUBR1, R0, 0
> BNECase_1
> code for x := x + y
> BEnd_Case
> Case_1:
> SUBR1, R0, 1
> BNECase_2
> Code for x := x - y
> BEnd_Case
> Case_2:
> SUBR1, R0, 2
> BNECase_3
> Code for x := x * y
> BEnd_Case
> Case_3:
> SUBR1, R0, 3
> BNEEnd_Case
> Code for x := x / y
> End_Case:
>
> This is simple and clear. There is a clear maximum execution path length.
> Adding label ranges is a bit longer, but still (I think) simple and clear,
> e.g.,
>
> CASE k OF
> 0 .. 10: x := x − y
>  | 11 .. 1000: x := x * y
>  | 1001 .. 2047 : x := x / y
> END
>
> could compile to something like this:
>
> LDR0, R14, k_offset
> SUBR1, R0, 0
> BLTCase_1
> SUBR1, R0, 10
> BGTCase_1
> code for x := x - y
> BEnd_Case
> Case_1:
> SUBR1, R0, 11
> BLTCase_1
> SUBR1, R0, 1000
> BGTCase_2
> Code for x := x * y
> BEnd_Case
> Case_2:
> SUBR1, R0, 1001
> BLTCase_1
> SUBR1, R0, 2047
> BNEEnd_Case
> Code for x := x / y
> End_Case:
>
> This will work even for very large ranges. The size of the generated code
> (no data needed) depends on the number of cases, not the range of the
> constants in the case label list or case label range.
>
> Adding label lists:
>
> CASE k OF
> 0, 10: x := x − y
>  | 11, 1000: x := x * y
>  | 1001, 2047, 19 : x := x / y
> END
>
> could compile to something like this:
>
> LDR0, R14, k_offset
> SUBR1, R0, 0
> BEQC_1
> SUBR1, R0, 10
> BNECase_1
> C_0:code for x := x - y
> BEnd_Case
> Case_1:
> SUBR1, R0, 11
> BEQC_1
> SUBR1, R0, 1000
> BNECase_2
> C_1:Code for x := x * y
> BEnd_Case
> Case_2:
> SUBR1, R0, 1001
> BEQC_3
> SUBR1, R0, 2047
> BEQC_3
> SUBR1, R0, 19
> BNEEnd_Case
> C_3:Code for x := x / y
> End_Case:
>
> John
>
> >> Am 16.11.2015 um 09:31 schrieb Jan de Kruyf <jan.de.kruyf at gmail.com>:
> >>
> >> Yes,
> >> The old man has been right most of the time, I agree. And I will have
> >> a royal battle to reduce the compiler construction back down to
> >> Wirthian elegance, that I also realize. But at the same time the code
> >> I produce is very elegant and sweet. On the basis of that I would say
> >> you are wrong in your statement that IF THEN can be made as efficient
> >> as a good case construct. Besides, a Case statement allows ranges
> >> like A..Z, a..z and so on, this has never been part of IF THEN, while
> >> in a properly constructed bin-tree it resolves itself.
> >>
> >> So since Wirth was first and foremost a teacher all his life, we
> >> could say that there are 2 learning opportunities here 1. to produce
> >> fast code.
> >> 2. to construct an elegant way of doing so.
> >>
> >>  I think that the master himself also realized the issues you and I
> >> are bringing up, and did not see his way out of the predicament yet.
> >> And since he is about 80 now and since he still got a few irons in
> >> the fire this was left for a bit.
> >>
> >> Lastly Dijkstra taught that you should never limit yourself because
> >> of inefficient machines. But you should strive to generalize any
> >> language design solution to as many cases as possible, even if that
> >> slows your program execution down a bit. There were big arguments in
> >> the Algol design meetings about that. Some people then felt that you
> >> had to live with the equipment given and use it as efficiently as
> >> possible. Wirth no doubt knows that whole history even better than I
> >> do. In the mean time of course, the machine limitations of those days
> >> (it was the time of the vacuum tubes) have been solved a hundred
> >> times over, but we still are trying to live with the language
> limitations of some of the older languages.
> >> Ergo the numerical case statement is in the O-7 language report, but
> >> is has not been implemented yet.
> >>
> >> So I feel fully justified implementing it. The way how to, we can
> >> talk about. If the Oberon community is alive and well ten I am sure
> >> that the last word has not been spoken yet.
> >>
> >>
> >> Enjoy your day
> >>
> >> j.
> >>
>
> [King George V Logo]
> John Stout
> Management Information Systems Coordinator
> Tel: 01704 530601
> E-Mail: JSS at kgv.ac.uk
> Web: www.kgv.ac.uk
>
>
> Information contained in this e-mail is intended for the use of the
> addressee only and is confidential.  Any dissemination, distribution,
> copying or use of this communication without prior permission of the
> addresseeis strictly prohibited.
>
> Every effort has been made to ensure that any attachment to this mail does
> not contain virus. King George V College has taken every reasonable
> precaution to minimise this risk, neither it nor the sender can accept
> liability for any damage which you sustain as a result of software viruses.
> You should carry outyour own virus checks before opening any attachments.
>
> [Think Before You Print]
> --
> 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/20151119/c7c293b5/attachment.html>