<div dir="ltr">Hey John<div>You now really did a lot of hard work.</div><div><br></div><div>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)</div><div><br></div><div>first a linear list is constructed => the case list.</div><div><br></div><div>the case list consists of a series of CaseLabelLists</div><div><br></div><div>Each CaseLabelList starts with 3 instructions</div><div><br></div><div>CMP x, y ; x being the variable and y the first case constant</div><div>BLT 'some place 1'</div><div>BGE 'some place 2'</div><div><br></div><div>then comes the 'statement sequence' for the case arm (or CaseLabelList if you like) so the code will fall through on x = y</div><div>and at the end of this sequence:<br></div><div>BRA 'place beyond the case statement'<br></div><div><br></div><div>so this then would be a basic single label case.</div><div>--------</div><div>for any extra comma separated case label there is</div><div><br></div><div><div>CMP x, y ; x being the variable and y this case constant</div><div>BLT 'some place 1'</div><div>BGE 'some place 2'</div></div><div>BEQ 'case arm statement sequence' ;that has been compiled in the basic single label case above</div><div><br></div><div>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.</div><div><br></div><div>This sums up the complete code for one CaseLabelList. </div><div>By the way x is preloaded in Wirth's compiler and if you dont nix the register it will stay loaded.</div><div><br></div><div>------</div><div>So now I am left with 4 issues:</div><div>someplace1</div><div>someplace2</div><div>whattodo inside a range, i.e not at the endpoints which _are_ defined and coded. </div><div>whattodo when not found</div><div><br></div><div>To solve that, I (with the bin tree in my mind) went for counsel to old Knuth</div><div>page 412 of volume 3 (2nd edition), he has a clever search tree construction there;</div><div>where any 'not-found' is a leaf of the tree (i.e furthest away from the root)</div><div>So if I land there in my search, I am in not-found land or perhaps inside a range, </div><div>since the endpoints of a range are defined as nodes in the tree.</div><div>(note that I am not talking code anymore, but how to connect the code blocks.)</div><div><br></div><div>Not-found-land is easy: just branch to ELSE or to END CASE. And you dont _have_ to go </div><div>down all the way to the leaf, it can be folded back into 'someplace 1 or 2' in the node above.</div><div><br></div><div>And what about a range? . . . .</div><div>Well, it can be shown that Knuth's bin tree above can be flattened into a sorted linear list as follows:</div><div>[0] (1) [1] (2) [2] (3) [3]</div><div><br></div><div>(1) being the lowest case label, (2) the next and so on.</div><div>And [1] representing the interval between 1 and 2, and so on.</div><div>so the [] nodes are the 'notfound' or 'range' intervals. At the same time they form the leafs of the bin tree.</div><div><br></div><div>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.</div><div><br></div><div>Left are the someplace 1 and 2 that dont have a value yet:</div><div><br></div><div>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)</div><div>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.</div><div><br></div><div>All that is left now is to patch the branch before the code, to point to the root's CMP and all is kosher.</div><div><br></div><div>============</div><div><br></div><div>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.</div><div><br></div><div>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:</div><div>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.</div><div><br></div><div>thanks again</div><div><br></div><div>j.</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Nov 19, 2015 at 4:10 PM, John Stout <span dir="ltr"><<a href="mailto:JSS@kgv.ac.uk" target="_blank">JSS@kgv.ac.uk</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Jan<br>
<br>
I wasn't suggesting that we NOT implement it, just that compiling it (implementing it) to a<br>
series of compiled IF THEN statements may be more in keeping with NW's view.<br>
<br>
Suppose we have (taken from the Oberon-07 report):<br>
<br>
CASE k OF<br>
0: x := x + y<br>
| 1: x := x − y<br>
| 2: x := x * y<br>
| 3: x := x / y<br>
END<br>
<br>
This would compile, using IF THEN equivalents, to code like this (I've assumed that R14 is a base register):<br>
<br>
LDR0, R14, k_offset<br>
SUBR1, R0, 0<br>
BNECase_1<br>
code for x := x + y<br>
BEnd_Case<br>
Case_1:<br>
SUBR1, R0, 1<br>
BNECase_2<br>
Code for x := x - y<br>
BEnd_Case<br>
Case_2:<br>
SUBR1, R0, 2<br>
BNECase_3<br>
Code for x := x * y<br>
BEnd_Case<br>
Case_3:<br>
SUBR1, R0, 3<br>
BNEEnd_Case<br>
Code for x := x / y<br>
End_Case:<br>
<br>
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.,<br>
<br>
CASE k OF<br>
0 .. 10: x := x − y<br>
| 11 .. 1000: x := x * y<br>
| 1001 .. 2047 : x := x / y<br>
END<br>
<br>
could compile to something like this:<br>
<br>
LDR0, R14, k_offset<br>
SUBR1, R0, 0<br>
BLTCase_1<br>
SUBR1, R0, 10<br>
BGTCase_1<br>
code for x := x - y<br>
BEnd_Case<br>
Case_1:<br>
SUBR1, R0, 11<br>
BLTCase_1<br>
SUBR1, R0, 1000<br>
BGTCase_2<br>
Code for x := x * y<br>
BEnd_Case<br>
Case_2:<br>
SUBR1, R0, 1001<br>
BLTCase_1<br>
SUBR1, R0, 2047<br>
BNEEnd_Case<br>
Code for x := x / y<br>
End_Case:<br>
<br>
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.<br>
<br>
Adding label lists:<br>
<br>
CASE k OF<br>
0, 10: x := x − y<br>
| 11, 1000: x := x * y<br>
| 1001, 2047, 19 : x := x / y<br>
END<br>
<br>
could compile to something like this:<br>
<br>
LDR0, R14, k_offset<br>
SUBR1, R0, 0<br>
BEQC_1<br>
SUBR1, R0, 10<br>
BNECase_1<br>
C_0:code for x := x - y<br>
BEnd_Case<br>
Case_1:<br>
SUBR1, R0, 11<br>
BEQC_1<br>
SUBR1, R0, 1000<br>
BNECase_2<br>
C_1:Code for x := x * y<br>
BEnd_Case<br>
Case_2:<br>
SUBR1, R0, 1001<br>
BEQC_3<br>
SUBR1, R0, 2047<br>
BEQC_3<br>
SUBR1, R0, 19<br>
BNEEnd_Case<br>
C_3:Code for x := x / y<br>
End_Case:<br>
<br>
John<br>
<span class=""><br>
>> Am 16.11.2015 um 09:31 schrieb Jan de Kruyf <<a href="mailto:jan.de.kruyf@gmail.com">jan.de.kruyf@gmail.com</a>>:<br>
>><br>
>> Yes,<br>
>> The old man has been right most of the time, I agree. And I will have<br>
>> a royal battle to reduce the compiler construction back down to<br>
>> Wirthian elegance, that I also realize. But at the same time the code<br>
>> I produce is very elegant and sweet. On the basis of that I would say<br>
>> you are wrong in your statement that IF THEN can be made as efficient<br>
>> as a good case construct. Besides, a Case statement allows ranges<br>
>> like A..Z, a..z and so on, this has never been part of IF THEN, while<br>
>> in a properly constructed bin-tree it resolves itself.<br>
>><br>
>> So since Wirth was first and foremost a teacher all his life, we<br>
>> could say that there are 2 learning opportunities here 1. to produce<br>
>> fast code.<br>
>> 2. to construct an elegant way of doing so.<br>
>><br>
>> I think that the master himself also realized the issues you and I<br>
>> are bringing up, and did not see his way out of the predicament yet.<br>
</span><span class="">>> And since he is about 80 now and since he still got a few irons in<br>
>> the fire this was left for a bit.<br>
>><br>
</span><span class="">>> Lastly Dijkstra taught that you should never limit yourself because<br>
>> of inefficient machines. But you should strive to generalize any<br>
>> language design solution to as many cases as possible, even if that<br>
>> slows your program execution down a bit. There were big arguments in<br>
>> the Algol design meetings about that. Some people then felt that you<br>
>> had to live with the equipment given and use it as efficiently as<br>
>> possible. Wirth no doubt knows that whole history even better than I<br>
>> do. In the mean time of course, the machine limitations of those days<br>
>> (it was the time of the vacuum tubes) have been solved a hundred<br>
>> times over, but we still are trying to live with the language limitations of some of the older languages.<br>
>> Ergo the numerical case statement is in the O-7 language report, but<br>
>> is has not been implemented yet.<br>
>><br>
>> So I feel fully justified implementing it. The way how to, we can<br>
>> talk about. If the Oberon community is alive and well ten I am sure<br>
>> that the last word has not been spoken yet.<br>
>><br>
>><br>
>> Enjoy your day<br>
>><br>
>> j.<br>
>><br>
<br>
</span>[King George V Logo]<br>
<span class="">John Stout<br>
Management Information Systems Coordinator<br>
Tel: 01704 530601<br>
E-Mail: <a href="mailto:JSS@kgv.ac.uk">JSS@kgv.ac.uk</a><br>
Web: <a href="http://www.kgv.ac.uk" rel="noreferrer" target="_blank">www.kgv.ac.uk</a><br>
<br>
<br>
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.<br>
<br>
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.<br>
<br>
</span>[Think Before You Print]<br>
--<br>
<a href="mailto:Oberon@lists.inf.ethz.ch">Oberon@lists.inf.ethz.ch</a> mailing list for ETH Oberon and related systems<br>
<a href="https://lists.inf.ethz.ch/mailman/listinfo/oberon" rel="noreferrer" target="_blank">https://lists.inf.ethz.ch/mailman/listinfo/oberon</a><br>
</blockquote></div><br></div>