<div dir="ltr">JohnR good morning to you.<div><br><div>Thank you for your long and thoughtful contribution.</div><div>It sums up most of the criteria in the discussion.<br><div><br></div><div>> Prof. Wirth intended that IF-ELSIF-ELSIF-ELSE statement chains be used when the subset is sparse. . .</div></div><div><br></div><div>I think that is how most people understand and use it today. but sometimes a case is more readable.</div><div><br></div><div>Here are some quotes from my Scott 'Programming Language Pragmatics' book, </div><div>besides the speed facts you already quoted:</div><div>---</div><div><div>The case statements of Algol W and its descendants provide alternative syntax for</div><div>a special case of nested if . . . then . . . else . When each condition compares the</div><div>same integer expression to a different compile-time constant . . .</div></div><div><br></div><div><div>   Rather than test its expression sequentially against a series of possible values,</div><div>the case statement is meant to compute an address to which it jumps in a single</div><div>instruction. . . .</div></div><div><br></div><div><div>. . . . ..  it can decide which form of target code to generate. For the sake</div><div>of simplicity, most compilers employ only some of the possible implementations.</div><div>Many use binary search in lieu of hashing. Some generate only indexed jump tables;</div><div>others only that plus sequential testing. Users of less sophisticated compilers may</div><div>need to restructure their case statements if the generated code turns out to be</div><div>unexpectedly large or slow.</div></div><div><br></div><div><div>. . . . . More significantly, languages differ in whether they</div><div>permit label ranges, whether they permit (or require) a default ( else ) clause, and</div><div>in how they handle a value that fails to match any label at run time.</div><div>   Standard Pascal does not permit a default clause: all values on which to take</div><div>action must appear explicitly in label lists. It is a dynamic semantic error for</div><div>the expression to evaluate to a value that does not appear. Most Pascal compilers</div><div>permit the programmer to add a default clause, labeled either else or otherwise ,</div><div>as a language extension. Modula allows an optional else clause. If one does not</div><div>appear in a given case statement, then it is a dynamic semantic error for the</div><div>tested expression to evaluate to a missing value. Ada requires arm labels to cover</div><div>all possible values in the domain of the tested expression's type . . .</div></div><div><br></div><div>--------</div><div>So </div><div>1. it does appear that an ELSE is a valued addition to a case statement. Compiler implementations </div><div>    of any laguage in general gravitate towards it. Also your statement :</div><div> "The programmer will presumably also have provided a friendlier error mechanism than a raw error trap."</div><div>    points that way.</div><div>2. The Ada implementation is there because Ada encourages subranges like Pascal.</div><div>    But in practice the 'Others' arm functions as a catch all.</div><div>3. I did a short comparison and although a jumptable is theoretically the fastest, </div><div>    it needs some associated code that makes most smallish case statements, at least on RISC,</div><div>    as fast with a binary search algorithm. Only in biggish case statements (like in ORS.Mod for instance) </div><div>    will you notice a difference. </div><div>    And then there is the space implication on small machines for a table, as you observed.</div><div><br></div><div>> the hybrid case of dense subsubsets. . . .</div><div>This is basically search tree with page lookup. There is certainly merit in that for big data handling, but</div><div>we are talking Oberon on micro controllers here. </div><div>One thing has been missing from the discussion so far, that is: </div><div>"How does the average user use this feature."</div><div>I think the biggest I have seen is in industrial ethernet comms packages. (PC to microcontroller board etc.)</div><div>And there, if speed is really an issue, one could certainly do page lookup first, say with a case of ranges, </div><div>which is fast in the construction I have cooked up.</div><div><br></div><div>Ok thats enough talk for today.</div><div><br></div><div>Cheers,</div><div><br></div><div>j.</div><div><br></div><div><br></div><div><br></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Nov 21, 2015 at 9:26 AM, John R. Strohm <span dir="ltr"><<a href="mailto:strohm@airmail.net" target="_blank">strohm@airmail.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">After watching this discussion, here's my read:<br>
<br>
Consider first the problem of selecting an action according to the value of a variable whose type consists of a set of possible selector values, as a (small) subset of the integers.<br>
<br>
Prof. Wirth intended that IF-ELSIF-ELSIF-ELSE statement chains be used when the subset is sparse, that is, there are many values not handled, and CASE statements be used when the subset is dense (no holes).  The CASE statement in Oberon-07 does not admit a DEFAULT (ELSE) value, indicating that giving it an invalid (missing) selector value is an error.<br>
<br>
If one were seriously contemplating implementing the CASE statement as  an IF-ELSIF-ELSIF-ELSE chain, one would of course be advised to employ a binary search technique, rather than a linear search technique.  However, COMMA, this is the sort of "optimization" ("pessimization") decision that should be made by the programmer, not the compiler.  It is trivial to show that a linear IF-ELSIF-ELSIF-ELSE chain takes O(N) time, a binary chain takes O(log2 N) time, and a branch table takes O(1) time.  This goes back to the "start by generating good code" philosophy.<br>
<br>
Now, since Oberon does not provide subrange types (as PASCAL did), a CASE statement implementation must necessarily start by verifying that the selector variable's value is in the range specified by the individual branch selector values.  If it is out of range, an error trap is taken.  (If the compiler does flow analysis, and the programmer is intelligent, the compiler won't need to generate this check, as the programmer will already have done it, and the compiler now knows that the value must be in range.  The programmer will presumably also have provided a friendlier error mechanism than a raw error trap.)  This is of course trivial, no harder than verifying that a subscript is in range.<br>
<br>
Yes, the programmer certainly could use large selector value ranges, with most cases "missing".  Using a branch table approach would generate large branch tables, with most values taking error traps.  "Doctor, it hurts when I do this."  "Well, don't do that!"<br>
<br>
One would, in the hybrid case of dense subsubsets forming a sparse subset, expect the programmer to "hybridize" his code, allowing sparse blocks of dense subsets, using IF-ELSIF-ELSIF-ELSE chains to select the block, and individual CASE statements to handle the dense subset in each block.<br>
<br>
--John R. Strohm<br>
<br>
-----Original Message----- From: Chris Burrows<br>
Sent: Friday, November 20, 2015 10:33 PM<br>
To: 'ETH Oberon and related systems'<div><div class="h5"><br>
Subject: Re: [Oberon] Numerical CASE Statements in Project Oberon<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
-----Original Message-----<br>
From: Oberon [mailto:<a href="mailto:oberon-bounces@lists.inf.ethz.ch" target="_blank">oberon-bounces@lists.inf.ethz.ch</a>] On Behalf Of<br>
John Stout<br>
Sent: Friday, 20 November 2015 12:40 AM<br>
To: <a href="mailto:oberon@lists.inf.ethz.ch" target="_blank">oberon@lists.inf.ethz.ch</a><br>
Subject: Re: [Oberon] Numerical CASE Statements in Project Oberon<br>
<br>
Jan<br>
<br>
I wasn't suggesting that we NOT implement it, just that compiling it<br>
(implementing it) to a series of compiled IF THEN statements may be<br>
more in keeping with NW's view.<br>
<br>
</blockquote>
<br>
I have not been able to find any NW reference that advocates implementing CASE by emulating IF THEN ELSE. Every such reference I am aware of advocates the use of jump tables. e.g.<br>
<br>
Project Oberon (2005), 12.2 Code Patterns:<br>
<br>
"Case statements serve to select a statement sequence from a set of cases according to an index value. Selection is represented by a direct branch to the selected case; the CASE instruction takes the branch distance from a table using the indexed addressing mode. We conclude from the following code that missing cases yield a table entry leading to a trap instruction (BPT 16). The table of offsets is located in the module's area for constants."<br>
<br>
Compiler Construction (2005), 11.3:<br>
<br>
"Consider the implementation of the case statement of Oberon (see Appendix A.2). Its essential property is that it uses a table of jump addresses for the various cases, and an indexed jump instruction."<br>
<br>
An Oberon Compiler for the ARM Processor (2007), 15. The Case Statement<br>
<br>
"The case statement serves to select a statement according to an integer, just as an element is selected from an array. This helps to avoid long cascades of if-elsif statements and increases efficiency. However, case statements are recommended only if the set of selectable statements is reasonably large. The compiler generates an internal array of the labels of the component statements. The specific jump address (label) is chosen by the index specified in the case clause."<br>
<br>
Regards,<br>
Chris Burrows<br>
<br>
CFB Software<br>
<a href="http://www.astrobe.com" rel="noreferrer" target="_blank">http://www.astrobe.com</a><br>
<br>
<br>
--<br>
<a href="mailto:Oberon@lists.inf.ethz.ch" target="_blank">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>
<br></div></div>
---<span class=""><br>
This email has been checked for viruses by Avast antivirus software.<br>
</span><a href="https://www.avast.com/antivirus" rel="noreferrer" target="_blank">https://www.avast.com/antivirus</a><div class="HOEnZb"><div class="h5"><br>
<br>
--<br>
<a href="mailto:Oberon@lists.inf.ethz.ch" target="_blank">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>
</div></div></blockquote></div><br></div>