PROPOSAL: Multiple switch expressions and case ranges

[Pinku Surana]

Let me try to answer some questions:

1) How do you compile the switch statement?

I've updated my proposal to include more info, though the techniques are
well known for switch statements and pattern matchers. The main thing I do
not know is when will the JIT create a jump table for a small, dense range
of numbers. The switch is compiled into bytecodes to implement search by
branching, but when a subset fits the JIT's idea of "small" then the
compiler should use the switch bytecode. It's not rocket surgery. ;-)

2) Why doesn't this proposal have more fancy stuff in it?

Project Coin is for "small" changes, and I think these changes are small
from the programmer's perspective. More importantly, the many dozens of
attempts to add pattern matching to Java-like languages have been extremely
complex. Take a look at active patterns in F# or JMatch's modes. For
example, adding a type check to this proposal suddenly introduces multiple
dispatch problems:

TypeB is-a TypeA;
TypeB obj1, obj2 ;
switch (obj1, obj2) {
  case TypeA x, TypeB y: f(x,y) ;
  case TypeB y, TypeA x: g(x,y) ;
}

Without multiple switch expressions, adding type checks is much simpler and
could generate vastly better code than a sequence of instanceof calls. But
that's another proposal.


- Pinku


On Thu, Mar 5, 2009 at 8:15 PM, Reinier Zwitserloot <reinier at zwitserloot.com
> wrote:

> This proposal does not appear to be complete. As you yourself mention,
> attempting to switch on [0 .. 1000000000] would generate an enormous
> class file. Also, your first desugaring example, which rewrites a
> multi-switch statement to nested switch statements, is certainly not a
> trivial operation. Where's the specification (and preferably some
> example code) on how the compiler is supposed to get from the sugar to
> the desugar? Perhaps this is an error in the Project Coin form, but
> all proposals should list chapter and verse of the JLS entries that
> need to be updated, which neccessarily includes a complete and
> detailed treatment on how the compiler is supposed to do the job. A
> single example desugaring isn't good enough.
>
> Any proposal that includes words like 'If XYZ is too big', is
> neccessarily not ready for this mailing list (as a proposal. It's fine
> as a request for comments and help). When does a range become too big?
> Could you explain the impact on size vs. lookup speed and make a solid
> recommendation for the right size to switch over?
>
> There's no need to update reflection APIs; you can't get at method
> code with them. You have to update the internal AST API, which you
> could list for completeness sake, but I don't think that's the intent
> of the Project Coin form (though, most proposals so far do mention it.
> I feel its not neccessary because 99% of all project coin proposals I
> can even think of require it. It's kind of implied when you say
> "Language Change Proposal"). JNI, the javadoc tool.
>
> I sort of like where this proposal is going, but as you yourself
> mentioned, the power of match/case in languages like Scala and Haskell
> is scary, and thus this proposal needs to be well aware of how java
> might some day get there, and be sure that we don't close future
> avenues early by screwing up now. I think this idea is probably out of
> scope, but I'll let Joe Darcy and friends be the judge of that. At the
> very least I would expect this system to work with Comparables,
> assuming the input and both range ends are all Comparable-compatible
> with each other (as provided by generics). Matching on type is also a
> relevant usecase in my opinion, so even if your proposal doesn't add
> it, you may want to include a rough sketch just to show that your
> syntax won't get in the way of a future expansion.
>
>
>
>  --Reinier Zwitserloot
>
>
>
> On Mar 5, 2009, at 23:16, Pinku Surana wrote:
>
> > Has the switch statement in C languages evolved much since the '80s?
> > I'm
> > envious of the case/match expression in functional languages and
> > looking for
> > simple ways to make 'switch' more powerful.
> >
> >
> >
> > AUTHOR(S): Pinku Surana
> >
> > OVERVIEW
> >
> > FEATURE SUMMARY:
> >
> > Extend the switch statement to support multiple switch expressions
> > and case
> > ranges.
> >
> > MAJOR ADVANTAGE:
> >
> > It is syntactic sugar that makes it easier to write/read complex
> > logic. This is one small aspect of the vastly more powerful match or
> > case expression in functional languages.
> >
> > MAJOR BENEFIT:
> >
> > Better readability for complex cases, and potentially better
> > performance relative to if statements.
> >
> > MAJOR DISADVANTAGE:
> >
> > Requires changes to compiler.
> >
> > ALTERNATIVES:
> >
> > It can currently be implemented with if statements.
> >
> > EXAMPLES
> >
> > Show us the code!
> >
> > SIMPLE EXAMPLE: Show the simplest possible program utilizing the new
> > feature.
> >
> > switch (c) {
> >  case ['a'..'z']: return "lower case" ;
> >  case ['A'..'Z']: return "upper case" ;
> >  default: return "something else" ;
> > }
> >
> > ADVANCED EXAMPLE: Show advanced usage(s) of the feature.
> >
> > switch (suit, value) {
> >  case [SPADE..CLUB],       [2..10]  : return "black low-value card" ;
> >  case [HEART..DIAMOND], [2..10]  : return "red low-value card" ;
> >  case _,                             [11..14]: return "face card" ;
> > }
> >
> > DETAILS
> >
> > SPECIFICATION: Describe how the proposal affects the grammar, type
> > system,
> > and meaning of expressions and statements in the Java Programming
> > Language
> > as well as any other known impacts.
> >
> > * The lexer will need to support underscore ('_') and ".."
> > * The parser rules for switch statements must be changed.
> >
> >  SwitchStatement:
> >      switch (Expression [, Expression]*) SwitchBlock
> >
> >  SwitchLabel:
> >      case CaseExpressions :
> >      default :
> >
> >  CaseExpressions:
> >      CaseExpression
> >      CaseExpressions , CaseExpression
> >
> >  CaseExpression:
> >      _
> >      ConstantExpression
> >      [ ConstantExpression .. ConstantExpression ]
> >      EnumConstantName
> >      [ EnumConstantName .. EnumConstantName ]
> >
> > * Semantic rules:
> >  - The number of CaseExpressions must equal the number of
> > expressions in
> > the SwitchStatement
> >  - The underscore ('_') means "don't care"
> >  - In [ c1 .. c2], c1 should be less than c2
> >  - The types of the constants/enums must match the type of the
> > expression
> > in the same position
> >  - If the range of constants/enums overlap between case arms, then
> > raise an
> > error.
> >
> > COMPILATION:
> >
> > Simple desugaring transformations:
> >
> > ----------------------------------
> >     switch (e1, e2) {
> >       case C1, C2: stmt1 ;
> >       case C3, _: stmt2 ;
> >       default: stmt3 ;
> >     }
> >     ==>
> >     x = e1 ;
> >     y = e2 ;
> >     switch (x) {
> >       case C1: switch (y) {
> >                  case C2: stmt1 ;
> >                  case C4: stmt2 ;
> >                  default: stmt3 ;
> >                }
> >            break ;
> >       case C3: stmt2 ;
> >            break ;
> >       default: stmt3 ;
> >     }
> > -----------------------------------
> >     case [V1 .. Vn] : stmts ;
> >     ==>
> >     case V1:
> >     case V2:
> >     ...
> >     case Vn: stmts ;
> > -----------------------------------
> >
> >
> > Both of these could blow up in code size. Therefore, a better
> > implementation of the switch would compile down to gotos to the
> > correct statement block. This is why proper compiler support would
> > be nice.
> >
> > For case ranges, if the range is too big then turn into an if
> > statement:
> > "if (x >= V1 && x <= V2)".
> >
> >
> > TESTING: How can the feature be tested?
> >
> > Normal compiler testing.
> >
> > LIBRARY SUPPORT: Are any supporting libraries needed for the feature?
> >
> > None
> >
> > REFLECTIVE APIS: Do any of the various and sundry reflection APIs
> > need to be
> > updated? This list of reflective APIs includes but is not limited to
> > core
> > reflection (java.lang.Class and java.lang.reflect.*),
> > javax.lang.model.*,
> > the doclet API, and JPDA.
> >
> > The reflection APIs will need to return a list of switch expressions
> > and case constants. Also, new expression nodes must be added for
> > ranges and for the "don't care" underscore.
> >
> > OTHER CHANGES: Do any other parts of the platform need be updated too?
> > Possibilities include but are not limited to JNI, serialization, and
> > output
> > of the javadoc tool.
> >
> > Don't think so.
> >
> > MIGRATION: Sketch how a code base could be converted, manually or
> > automatically, to use the new feature.
> >
> > I think this would be difficult because the logic would be obscured
> > in if
> > statements.
> >
> > COMPATIBILITY
> >
> > BREAKING CHANGES: Are any previously valid programs now invalid? If
> > so, list
> > one.
> >
> > None.
> >
> > EXISTING PROGRAMS: How do source and class files of earlier platform
> > versions interact with the feature? Can any new overloadings occur?
> > Can any
> > new overriding occur?
> >
> > Should be backwards compatible.
> >
> > REFERENCES
> >
> > EXISTING BUGS: Please include a list of any existing Sun bug ids
> > related to
> > this proposal.
> >
> > URL FOR PROTOTYPE (optional):
> >
> > If there's interest, I can cook up a prototype with Polyglot.
> >
>
>
>