Login [Register]
Don't have an account? Register now to chat, post, use our tools, and much more.
The fall-through optimization is rather non-pythonic, so I doubt this exact implementation stands any chance of being integrated into python, but I've always wondered why there is no switch statement in python, since I find it quite readable, and shorter.

Although, for porting over other software, this obviously has great value.
There is no switch statement because Guido is doesn't want them in python. A lot of people want them, and there is really no good reason why not to have them, but Guido says so.
Pseudoprogrammer wrote:
Sorry I don't have the code but I thought elfi and kllr might be interested.


I was more interested in the code I wrote, that is some sexy, yet horrifying, Python - and now I miss writing Python.

KermMartian wrote:
Well, well, well, sounds like I was right after all, then!


Eh, maybe, maybe not. I wonder if Guido would respond to an internal email...

Quote:
There is no switch statement because Guido is doesn't want them in python. A lot of people want them, and there is really no good reason why not to have them, but Guido says so.


It's more that nobody has shown why you need them - just because people want it doesn't make it a good addition. Switches tend to be rather verbose syntactically and they are very rarely a good solution to whatever problem you are having. This is why Java totally half-assed switches, for example.
Well, it is a bit more concise than a chain of if-else statements. While in every case you can work around not having it, there is the occasional case where it really is the best option.
Kllrnohj wrote:
It's more that nobody has shown why you need them - just because people want it doesn't make it a good addition. Switches tend to be rather verbose syntactically and they are very rarely a good solution to whatever problem you are having. This is why Java totally half-assed switches, for example.


There's one very good reason to have them, a couple decent reasons, and no terribly compelling reasons not to.

Switches generally suggest the use of indexed jump tables, which are almost always more efficient than the straightforward implementation of if/else constructions as sequential conditional branches. On top of this, there are a number of cases where fall through provides methods of cutting back on code repetition that would be significantly less straightforward with if/else (which was the motivation for my original post in this thread). The significance (or presence) of added verbosity is going to be highly use-case specific, but pure fall through cases are quickly (in the number of cases/clauses) going to become LESS verbose than else if clauses, since "case :" is 6 characters, and "else if()" is 9 characters. Lots of "break;"s add to the verbosity, but verbosity either way is going to be amortized against the number of statements within each case/clause.

The only argument I've ever heard against them is that the default behavior of falling through is confusing. There are several possible responses to that -

  • It's not confusing at all once you understand that switches are stand-ins for indexed branch tables which pack the code segments end to end, so that falling through is the natural behavior to expect.
  • If you're designing a new language and it bugs you, just make breaking the default behavior, and require a "continue;" to fall through. I wouldn't do this, since I think fall through is quite sensible when you understand what switch statements are for, but I wouldn't be horrified by someone who did, either.
  • And my personal favorite: Don't be stupid, pay attention to the code you're writing.
elfprince13 wrote:
The only argument I've ever heard against them is that the default behavior of falling through is confusing. There are several possible responses to that -

  • It's not confusing at all once you understand that switches are stand-ins for indexed branch tables which pack the code segments end to end, so that falling through is the natural behavior to expect.
  • If you're designing a new language and it bugs you, just make breaking the default behavior, and require a "continue;" to fall through. I wouldn't do this, since I think fall through is quite sensible when you understand what switch statements are for, but I wouldn't be horrified by someone who did, either.
  • And my personal favorite: Don't be stupid, pay attention to the code you're writing.
C# took a similar route to your second bullet, where you can't do fall-through to non-empty blocks (but you still need "break"). However, you can do "goto case whatever" to go to a specific case in the switch block. Also, "And my personal favorite: Don't be stupid, pay attention to the code you're writing." is wonderful Smile
elfprince13 wrote:
Switches generally suggest the use of indexed jump tables, which are almost always more efficient than the straightforward implementation of if/else constructions as sequential conditional branches.


Suggest, but don't necessarily use - and for interpreted languages like Python, almost certainly won't use indexed jump tables or be efficient anyway.

Besides, that's the compiler's problem, not mine as a developer.

Quote:
On top of this, there are a number of cases where fall through provides methods of cutting back on code repetition that would be significantly less straightforward with if/else (which was the motivation for my original post in this thread).


That's a good indication you should be using methods or classes, not more code inside a single control structure.
Kllrnohj wrote:
Suggest, but don't necessarily use - and for interpreted languages like Python, almost certainly won't use indexed jump tables or be efficient anyway.

They might not be quite as efficient as an indexed jump table, but a good implementation should still be O(1), or in some rare cases O(log(n)), rather than O(n) in the number of cases. I wouldn't even mind a language that allowed you to optionally specify your own hash function to use with its switch construction.

Kllrnohj wrote:
Besides, that's the compiler's problem, not mine as a developer.

Software developers who don't care about complexity are the root of all evil. A compiler's job should not be altering the asymptotic complexity of your code.

Quote:
That's a good indication you should be using methods or classes, not more code inside a single control structure.
elfprince13 wrote:
I wouldn't even mind a language that allowed you to optionally specify your own hash function to use with its switch construction.


Why on earth would you want that? So you can spend more time in the hash function than doing a small handful of ifs?

Quote:
Software developers who don't care about complexity are the root of all evil. A compiler's job should not be altering the asymptotic complexity of your code.


Your argument for switches hinges on the compiler altering the complexity of your code - so good job being hypocritical there. A switch is still multiple ifs, and most often implemented as multiple ifs. It *can* be made into a jump table by the compiler, just like if/else if/else if can also be made into a jump table by the compiler.

O(1) vs. O(N) when N < 10 also isn't all that significant. Optimizing for O() is misleading anyway - computers aren't the ideal machines big O notation assumes.

And let's make one thing clear since you seem a bit confused, switches are only faster than if/else if *IF AND ONLY IF* they get optimized as an index jump table, which doesn't happen as often as you think. Only happens if your using ints and those ints are consecutive, which will happen exactly never in Python ('int' is a class/object, not a primitive), and pretty rarely in most circumstances anyway.
Kllrnohj wrote:

Why on earth would you want that? So you can spend more time in the hash function than doing a small handful of ifs?

To give you control to make appropriate decisions based on the scenario. There are many hash functions you could write that would take hardly any time at all to execute, but which a compiler might not be smart enough to figure out.

Quote:

Your argument for switches hinges on the compiler altering the complexity of your code - so good job being hypocritical there. A switch is still multiple ifs, and most often implemented as multiple ifs. It *can* be made into a jump table by the compiler, just like if/else if/else if can also be made into a jump table by the compiler.

No. A switch, abstractly, is a multiway branch, in some cases the compiler doesn't know how to implement as such concretely, and must then fall back on sequential branching.

Quote:
O(1) vs. O(N) when N < 10 also isn't all that significant.

because nobody ever writes switches with a large number of cases?

Quote:
Optimizing for O() is misleading anyway - computers aren't the ideal machines big O notation assumes.

O RLY. I'm pretty sure big O notation doesn't assume an "ideal machine", just "for n large enough". Cases where O() really would be misleading for reasonable n (1.0000000001^n vs n^100000) pretty much don't show up.

Quote:
And let's make one thing clear since you seem a bit confused, switches are only faster than if/else if *IF AND ONLY IF* they get optimized as an index jump table, which doesn't happen as often as you think. Only happens if your using ints and those ints are consecutive

False. There are a good number of cases where the compiler can fall back on a O(log(n)) tree jump table before it has to fall back to sequential access.

Quote:
which will happen exactly never in Python ('int' is a class/object, not a primitive),

I'm not sure how this is relevant. Python int's are still well-ordered.

Quote:
and pretty rarely in most circumstances anyway.

Which is why being able to specify your own expression to generate the hash could be advantageous. Though, I guess technically, you can do this all the time, your cases just get a little obscured.



We can keep arguing if you want, but it's not terribly likely you'll convince me to side with Guido van Rossum over Donald Knuth and Peter Naur. The fact remains that Python doesn't provide a method to request a multiway branch within a single sequence of instructions. You can use arrays of function references to kind of hack it together, as -w-e- -b-o-t-h- I did, but without local namespace injection, it's a bit tacky to read/write. On the other hand, you have all sorts of mostly elegant-looking implementations which preserve the fall through behavior, but without actually using a multiway branch, there's not much point. The exceptional variety, the for loop variety, and your implementation (I just went back and read through it again, didn't notice that the first time, because the usage looked clean) all have this shortcoming.
elfprince13 wrote:
To give you control to make appropriate decisions based on the scenario. There are many hash functions you could write that would take hardly any time at all to execute, but which a compiler might not be smart enough to figure out.


So make a hash table that maps whatever you want to functions - bam, done.

Quote:
No. A switch, abstractly, is a multiway branch, in some cases the compiler doesn't know how to implement as such concretely, and must then fall back on sequential branching.


Abstractly, yes, but in reality it's just a series of if/else ifs because CPUs don't have a "switch" style instruction.

Quote:
because nobody ever writes switches with a large number of cases?


People write crappy code all the time, doesn't mean you should make it easier for them to write crappy code.

Quote:
O RLY. I'm pretty sure big O notation doesn't assume an "ideal machine", just "for n large enough". Cases where O() really would be misleading for reasonable n (1.0000000001^n vs n^100000) pretty much don't show up.


No, they assume there's no such thing as caches, branch prediction, and that all operations magically take the exact same amount of time.

Quote:
False. There are a good number of cases where the compiler can fall back on a O(log(n)) tree jump table before it has to fall back to sequential access.


I cannot find a shred of evidence of this hypothetical tree jump table, care to actually back that claim up with anything at all?

Quote:
I'm not sure how this is relevant. Python int's are still well-ordered.


Because you can override equals, and more importantly you can replace equals on specific instances of int. You can't do jump tables if you don't know how the compare works.

Quote:
We can keep arguing if you want, but it's not terribly likely you'll convince me to side with Guido van Rossum over Donald Knuth and Peter Naur.


Donald Knuth and Peter Naur? Where have they published their feelings on switches, and Python's lack of them?
Kllrnohj wrote:
Abstractly, yes, but in reality it's just a series of if/else ifs because CPUs don't have a "switch" style instruction.

Indirected branches are supported on a wide variety of platforms. The complexity issue comes from the time/memory tradeoffs needed to map inputs to jump destinations.

Quote:
No, they assume there's no such thing as caches, branch prediction, and that all operations magically take the exact same amount of time.

Caches and branch prediction usually improve the use of big-O as a measure of complexity for moderately sized n (i.e., they diminish the size of the constant factors being ignored). As long as all instructions take a constant amount of time, the CPI variation is going to be not terribly relevant to large n. Let's say addition takes 5 cycles, and division takes 100. An O(n^2) algorithm that calculates the sums of all input pairs is going to be slower than an O(n) algorithm that divides each input by the next for n>20.

Quote:
I cannot find a shred of evidence of this hypothetical tree jump table, care to actually back that claim up with anything at all?

I've stepped through them in GDB before (after having disassembled a program compiled from C), and I know the JVM provides an O(log(N)) lookupswitch instruction as well as an O(1) indexed switch, and NEVER resorts to O(N) (so much for "Java totally half-assed switches"). And apparently C# produces CIL that might be any one of the three (but not favoring the O(N) implementation except for small N).

Quote:
Because you can override equals, and more importantly you can replace equals on specific instances of int. You can't do jump tables if you don't know how the compare works.

I'm still not sure how this is relevant to a claim that "you can't do switches with Python ints".

Quote:
Donald Knuth and Peter Naur? Where have they published their feelings on switches, and Python's lack of them?

Not python specifically, but
Donald Knuth, Structured Programming with go to Statements wrote:
Multiway branching is an important programming technique which is all too often replaced by an inefficient sequence of if tests. Peter Naur recently wrote me that he considers the use of tables to control program flow as a basic idea of computer science that has been nearly forgotten; but he expects it will be ripe for rediscovery any day now. It is the key to efficiency in all the best compilers I have studied.
elfprince13 wrote:
Caches and branch prediction usually improve the use of big-O as a measure of complexity for moderately sized n (i.e., they diminish the size of the constant factors being ignored). As long as all instructions take a constant amount of time, the CPI variation is going to be not terribly relevant to large n. Let's say addition takes 5 cycles, and division takes 100. An O(n^2) algorithm that calculates the sums of all input pairs is going to be slower than an O(n) algorithm that divides each input by the next for n>20.


Exactly - we don't have big Ns in this case, we have small Ns. If your switch has 20 cases, you're code sucks and you're doing it wrong.

Quote:
I've stepped through them in GDB before (after having disassembled a program compiled from C), and I know the JVM provides an O(log(N)) lookupswitch instruction as well as an O(1) indexed switch, and NEVER resorts to O(N) (so much for "Java totally half-assed switches"). And apparently C# produces CIL that might be any one of the three (but not favoring the O(N) implementation except for small N).


Java did half-assed switches - that statement was about using the switch, not how it's implemented. That's also still not a tree, so again - back that up y0.

Stepping through it does not mean the compiler produced it. Nesting switches are a common optimization if you want to do a switch with a group of common cases + a group of uncommon cases.

Quote:
I'm still not sure how this is relevant to a claim that "you can't do switches with Python ints".


Then read it again - slowly this time.

Quote:
Not python specifically, but
Donald Knuth, Structured Programming with go to Statements wrote:
Multiway branching is an important programming technique which is all too often replaced by an inefficient sequence of if tests. Peter Naur recently wrote me that he considers the use of tables to control program flow as a basic idea of computer science that has been nearly forgotten; but he expects it will be ripe for rediscovery any day now. It is the key to efficiency in all the best compilers I have studied.


How people use computers, how we program them, and how they are implemented have changes just slightly during the past 40 years. And nobody has removed jump tables, you can still totally do that even with Python. You can't do them with preserved locals, but neither of those two argued specifically for that.
Kllrnohj wrote:
If your switch has 20 cases, you're code sucks and you're doing it wrong.

Just because you program for cellphones, which only have 15 or so keys, doesn't mean nobody else needs to handle big-boy keyboard input ever.

Quote:
That's also still not a tree, so again - back that up y0.

It's still a binary search, which is going to behave pretty similarly to the trees of conditional branches that GCC uses in some cases.

Quote:
Stepping through it does not mean the compiler produced it. Nesting switches are a common optimization if you want to do a switch with a group of common cases + a group of uncommon cases.

See previous. GCC does this.

Quote:
How people use computers, how we program them, and how they are implemented have changes just slightly during the past 40 years.

Which is to say, a sizeable percentage of software engineers have turned into lazy shits who are unconcerned with effective use of their hardware, on the assumption that it's fast enough and smart enough to allow them to get away with anything.

Quote:
You can't do them with preserved locals, but neither of those two argued specifically for that.

No, that's just good language design.
elfprince13 wrote:
Just because you program for cellphones, which only have 15 or so keys, doesn't mean nobody else needs to handle big-boy keyboard input ever.


Keyboard input is not handled with a switch statement on any platform that I'm aware of (it's called a key *map* for a reason). Care to try again?

Quote:
Which is to say, a sizeable percentage of software engineers have turned into lazy a who are unconcerned with effective use of their hardware, on the assumption that it's fast enough and smart enough to allow them to get away with anything.


20 years ago called, they want their argument back (see: assembly vs. C)

And remember we're talking about *PYTHON* here - clearly you've already decided to take development efficiency over language efficiency.

Quote:
No, that's just good language design.


Labels and gotos are not good language design.
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 2 of 2
» All times are GMT - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement