[Oberon] Numerical CASE Statements in Project Oberon

[Jan de Kruyf]

Hey John
You now really did a lot of hard work.

Let me see if I can explain in a simple way what I am trying to compile to
(and I am into revising the code at the moment, but everything is in fits
and starts, because I also have to chase customers)

first a linear list is constructed => the case list.

the case list consists of a series of  CaseLabelLists

Each CaseLabelList starts with 3 instructions

CMP x, y  ; x being the variable and y the first case constant
BLT 'some place 1'
BGE 'some place 2'

then comes the 'statement sequence' for the case arm (or CaseLabelList if
you like) so the code will fall through on x = y
and at the end of this sequence:
BRA 'place beyond the case statement'

so this then would be a basic single label case.
--------
for any extra comma separated case label there is

CMP x, y  ; x being the variable and y this case constant
BLT 'some place 1'
BGE 'some place 2'
BEQ 'case arm statement sequence'     ;that has been compiled in the basic
single label case above

and for the 2nd value in a range the same 4 instructions are placed, so a
2nd value is like any case constant in a case arm.

This sums up the complete code for one CaseLabelList.
By the way x is preloaded in Wirth's compiler and if you dont nix the
register it will stay loaded.

------
So now I am left with 4 issues:
someplace1
someplace2
whattodo inside a range, i.e not at the endpoints which _are_ defined and
coded.
whattodo when not found

To solve that, I (with the bin tree in my mind) went for counsel to old
Knuth
page 412 of volume 3 (2nd edition), he has a clever search tree
construction there;
where any 'not-found' is a leaf of the tree (i.e furthest away from the
root)
So if I land there in my search, I am in not-found land or perhaps inside a
range,
since the endpoints of a range are defined as nodes in the tree.
(note that I am not talking code anymore, but how to connect the code
blocks.)

Not-found-land is easy: just branch to ELSE or to END CASE. And you dont
_have_ to go
down all the way to the leaf, it can be folded back into 'someplace 1 or 2'
in the node above.

And what about a range? . . . .
Well, it can be shown that Knuth's bin tree above can be flattened into a
sorted linear list as follows:
[0]  (1)  [1]  (2)  [2]  (3)  [3]

(1) being the lowest case label, (2) the next and so on.
And [1] representing the interval between 1 and 2, and so on.
so the [] nodes are the 'notfound' or 'range'  intervals. At the same time
they form the leafs of the bin tree.

So when I parse case (2) and it is the beginning of a range, then at the
same time I construct [2] which gets a reference to the 'case arm statement
sequence' address. And this address can be folded back again into the node
above in the same way as in the 'not-found' instance.

Left are the someplace 1 and 2 that dont have a value yet:

While I parse I insert every node / leaf  () [] pair into a sorted linear
list, so the list becomes [0]  (1)  [1]  (2)  [2]  (3)  [3].  This is the
case list. (see above)
Then I join the case list into a binary search tree and from that tree I
know where each branch in the code ( BLT, BGE) must point.

All that is left now is to patch the branch before the code, to point to
the root's CMP and all is kosher.

============

All this looks complex of course, since I more or less tried to describe
the thought process leading to where I am, but in code it looks quite
streamlined and is easily understood, since I refactored until it fell in
place properly. No ifs and buts and gotos, just nice generalized code.

And now at the end of this long story I must thank you for engaging,
because while describing I found an oversight in my thinking:
I do know that I cannot accomodate a separate label case within a range,
but I did _not_ take inverse ranges into account, and knowing programmers,
somebody will manage to break a compilation with that, and it is silent too
at the moment.

thanks again

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/200f13f3/attachment.html>