Re: [Python-Dev] Switch statement
On Mon, Jun 12, 2006 at 11:33:49PM +0200, Michael Walter wrote:
Maybe "switch" became a keyword with the patch..
Regards, Michael
That's correct.
On 6/12/06, M.-A. Lemburg <mal@egenix.com> wrote:
Could you upload your patch to SourceForge ? Then I could add it to the PEP.
It's already up there :) I thought I sent that through in another e-mail, but maybe not: http://sourceforge.net/tracker/index.php?func=detail&aid=1504199&group_id=5470&atid=305470 Complete with documentation changes and a unit test.
Thomas wrote a patch which implemented the switch statement using an opcode. The reason was probably that switch works a lot like e.g. the for-loop which also opens a new block.
No, Skip explained this in an earlier e-mail: apparently some programming languages use a compile-time generated lookup table for switch statements rather than COMPARE_OP for each case. The restriction is, of course, that you're stuck with constants for each case statement. In a programming language like Python, where there are no named constants, the usefulness of such a construct might be questioned. Again, see Skip's earlier e-mails.
Could you explain how your patch works ?
1. Evaluate the "switch" expression so that it's at the top of the stack 2. For each case clause: 2.1. Generate a DUP_TOP to duplicate the switch value for a comparison 2.2. Evaluate the "case" expression 2.3. COMPARE_OP(PyCmp_EQ) 2.4. Jump to the next case statement if false 2.5. Otherwise, POP_TOP and execute the suite for the case clause 2.6. Then jump to 3 3. POP_TOP to remove the evaluated switch expression from the stack As you can see from the above, my patch generates a COMPARE_OP for each case, so you can use expressions - not just constants - for cases. All of this is in the code found in Python/compile.c. Cheers, Tom -- Tom Lee http://www.vector-seven.com ----- End forwarded message ----- -- Tom Lee http://www.vector-seven.com
Thomas Lee wrote:
On Mon, Jun 12, 2006 at 11:33:49PM +0200, Michael Walter wrote:
Maybe "switch" became a keyword with the patch..
Regards, Michael
That's correct.
On 6/12/06, M.-A. Lemburg <mal@egenix.com> wrote:
Could you upload your patch to SourceForge ? Then I could add it to the PEP.
It's already up there :) I thought I sent that through in another e-mail, but maybe not:
http://sourceforge.net/tracker/index.php?func=detail&aid=1504199&group_id=5470&atid=305470
Complete with documentation changes and a unit test.
Thanks. Please CC me on these emails. It would also help if your mailer wouldn't add Mail-Followup-To: python-dev@python.org to the messages, since then a Reply-All will not include any other folks on CC in this thread.
Thomas wrote a patch which implemented the switch statement using an opcode. The reason was probably that switch works a lot like e.g. the for-loop which also opens a new block.
No, Skip explained this in an earlier e-mail: apparently some programming languages use a compile-time generated lookup table for switch statements rather than COMPARE_OP for each case. The restriction is, of course, that you're stuck with constants for each case statement.
In a programming language like Python, where there are no named constants, the usefulness of such a construct might be questioned. Again, see Skip's earlier e-mails.
Could you explain how your patch works ?
1. Evaluate the "switch" expression so that it's at the top of the stack 2. For each case clause: 2.1. Generate a DUP_TOP to duplicate the switch value for a comparison 2.2. Evaluate the "case" expression 2.3. COMPARE_OP(PyCmp_EQ) 2.4. Jump to the next case statement if false 2.5. Otherwise, POP_TOP and execute the suite for the case clause 2.6. Then jump to 3 3. POP_TOP to remove the evaluated switch expression from the stack
As you can see from the above, my patch generates a COMPARE_OP for each case, so you can use expressions - not just constants - for cases.
All of this is in the code found in Python/compile.c.
Thanks for the explanation, but the original motivation for adding a switch statement was to be able to use a lookup table for the switching in order to speed up branching code, e.g. in parsers which typically use constants to identify tokens (see the "Problem" section of the PEP for the motivation). The standard if ... elif ... efif ... else: ... scheme already provides the above logic. There's really no need to invent yet another syntax to write such constructs, IMHO. -- Marc-Andre Lemburg eGenix.com Professional Python Services directly from the Source (#1, Jun 14 2006)
Python/Zope Consulting and Support ... http://www.egenix.com/ mxODBC.Zope.Database.Adapter ... http://zope.egenix.com/ mxODBC, mxDateTime, mxTextTools ... http://python.egenix.com/
::: Try mxODBC.Zope.DA for Windows,Linux,Solaris,FreeBSD for free ! ::::
M.-A. Lemburg wrote:
The standard
if ... elif ... efif ... else: ...
scheme already provides the above logic. There's really no need to invent yet another syntax to write such constructs, IMHO.
It's a DRY thing. The construct that a switch statement can replace actually needs to be written: v = ... if v == ...: ... elif v == ...: ... elif v == ...: ... else: ... The 'v =' part is replaced by 'switch' and the 'if v ==' and 'elif v ==' are all replaced by 'case'. A separate statement is also easier to document to say that order of evaluation of the cases is not guaranteed, and that the cases may only be evaluated once and cached thereafter, allowing us free rein for optimisations that aren't possible with a normal if statement. The optimisation of the if-elif case would then simply be to say that the compiler can recognise if-elif chains like the one above where the RHS of the comparisons are all hashable literals and collapse them to switch statements. It's also worth thinking about what a 'missing else' might mean for a switch statement. Should it default to "else: pass" like other else clauses, or does it make more sense for the default behaviour to be "else: raise ValueError('Unexpected input to switch statement')", with an explicit "else: pass" required to suppress the exception? The lack of a switch statement doesn't really bother me personally, since I tend to just write my state machine type code so that it works off a dictionary that I define elsewhere, but I can see the appeal of having one, *if* there are things that we can do with a separate statement to make it *better* for the purpose than a simple if-elif chain or a predefined function lookup dictionary. Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia --------------------------------------------------------------- http://www.boredomandlaziness.org
Nick Coghlan wrote:
M.-A. Lemburg wrote:
The standard
if ... elif ... efif ... else: ...
scheme already provides the above logic. There's really no need to invent yet another syntax to write such constructs, IMHO.
It's a DRY thing.
Exactly, though not in the sense you are suggesting :-) The motivation for the PEP 275 is to enhance performance when switching on multiple values with these values being constants. I don't want to repeat the discussion here. Please see the PEP for details: http://www.python.org/dev/peps/pep-0275/ Note that the PEP is entitled "Switching on Multiple Values". Adding a switch statement is only one of the two proposed solutions. My personal favorite is making the compiler smarter to detect the mentioned if-elif-else scheme and generate code which uses a lookup table for implementing fast branching. The main arguments for this solution are: * existing code can benefit from the optimization * no need for new keywords * code written for Python 2.6 will be executable by earlier Python versions as well
The construct that a switch statement can replace actually needs to be written:
v = ... if v == ...: ... elif v == ...: ... elif v == ...: ... else: ...
The 'v =' part is replaced by 'switch' and the 'if v ==' and 'elif v ==' are all replaced by 'case'.
Actually, there's one more contraint: the ... part on the right needs to be constant - at least if you use the same motiviation as in the PEP 275.
A separate statement is also easier to document to say that order of evaluation of the cases is not guaranteed, and that the cases may only be evaluated once and cached thereafter, allowing us free rein for optimisations that aren't possible with a normal if statement.
No need for any caching magic: the values on which you switch will have to be constants anyway.
The optimisation of the if-elif case would then simply be to say that the compiler can recognise if-elif chains like the one above where the RHS of the comparisons are all hashable literals and collapse them to switch statements.
Right (constants are usually hashable :-).
It's also worth thinking about what a 'missing else' might mean for a switch statement. Should it default to "else: pass" like other else clauses, or does it make more sense for the default behaviour to be "else: raise ValueError('Unexpected input to switch statement')", with an explicit "else: pass" required to suppress the exception?
Good point. I'd say it's a SyntaxError not to provide an else part. That way you leave the decision to raise an exception or not to the programmer.
The lack of a switch statement doesn't really bother me personally, since I tend to just write my state machine type code so that it works off a dictionary that I define elsewhere, but I can see the appeal of having one, *if* there are things that we can do with a separate statement to make it *better* for the purpose than a simple if-elif chain or a predefined function lookup dictionary.
The problem with a dispatch approach is that Python function or method calls take rather long to setup and execute. If you write things like parsers, you typically have code that only does very few things per switch case, e.g. add the data to some list - the function call overhead pretty much kills the dispatch approach compared to the O(n) approach using if-elif-chains. Dispatching is useful in situations where you do lots of complicated things for each case. The function call overhead then becomes negligible. -- Marc-Andre Lemburg eGenix.com Professional Python Services directly from the Source (#1, Jun 15 2006)
Python/Zope Consulting and Support ... http://www.egenix.com/ mxODBC.Zope.Database.Adapter ... http://zope.egenix.com/ mxODBC, mxDateTime, mxTextTools ... http://python.egenix.com/
2006-07-03: EuroPython 2006, CERN, Switzerland 17 days left ::: Try mxODBC.Zope.DA for Windows,Linux,Solaris,FreeBSD for free ! ::::
Raymond Hettinger wrote:
The optimisation of the if-elif case would then simply be to say that the compiler can recognise if-elif chains like the one above where the RHS of the comparisons are all hashable literals and collapse them to switch statements.
Right (constants are usually hashable :-).
The LHS is more challenging. Given:
if x == 1: p_one() elif x == 2: p_two() elif x == 3: p_three() else: p_catchall()
There is no guarantee that x is hashable. For example:
class X: def __init__(self, value): self.value = value def __cmp__(self, y): return self.value == y x = X(2)
That's a good point. The PEP already addresses this by retricting the type of x to a few builtin immutable and hashable types: ...the switching variable is one of the builtin immutable types: int, float, string, unicode, etc. (not subtypes, since it's not clear whether these are still immutable or not). -- Marc-Andre Lemburg eGenix.com Professional Python Services directly from the Source (#1, Jun 16 2006)
Python/Zope Consulting and Support ... http://www.egenix.com/ mxODBC.Zope.Database.Adapter ... http://zope.egenix.com/ mxODBC, mxDateTime, mxTextTools ... http://python.egenix.com/
::: Try mxODBC.Zope.DA for Windows,Linux,Solaris,FreeBSD for free ! ::::
M.-A. Lemburg wrote:
My personal favorite is making the compiler smarter to detect the mentioned if-elif-else scheme and generate code which uses a lookup table for implementing fast branching.
But then the values need to be actual compile-time constants, precluding the use of symbolic names, values precomputed a run time, etc. A new statement would allow us to simply document that the case values are *assumed* constant, and then the implementation could cache them in a dict or whatever. -- Greg
Greg Ewing wrote:
M.-A. Lemburg wrote:
My personal favorite is making the compiler smarter to detect the mentioned if-elif-else scheme and generate code which uses a lookup table for implementing fast branching.
But then the values need to be actual compile-time constants, precluding the use of symbolic names, values precomputed a run time, etc.
Good point.
A new statement would allow us to simply document that the case values are *assumed* constant, and then the implementation could cache them in a dict or whatever.
That would a very well hidden assignment of a "constantness" property to a symbol or expression. We'd also run into the problem of not knowing when to evaluate those case expressions, e.g. at function compile time, at run-time when first entering the switch statement, etc. -- Marc-Andre Lemburg eGenix.com Professional Python Services directly from the Source (#1, Jun 16 2006)
Python/Zope Consulting and Support ... http://www.egenix.com/ mxODBC.Zope.Database.Adapter ... http://zope.egenix.com/ mxODBC, mxDateTime, mxTextTools ... http://python.egenix.com/
::: Try mxODBC.Zope.DA for Windows,Linux,Solaris,FreeBSD for free ! ::::
On 15 Jun 2006, at 11:37, Nick Coghlan wrote:
... The lack of a switch statement doesn't really bother me personally, since I tend to just write my state machine type code so that it works off a dictionary that I define elsewhere,
Not trying to push more LISP into python or anything, but of course we could converge your method and the switch statement elegantly if only we could put whole suites into lamdbas rather than just single expressions :-) {"case1": lamdba : some-suite-lambda... , "case2": lambda : some-other-suite... }[switch-condition-expression]() Nicko
At 11:45 PM 6/15/2006 +0100, Nicko van Someren wrote:
On 15 Jun 2006, at 11:37, Nick Coghlan wrote:
... The lack of a switch statement doesn't really bother me personally, since I tend to just write my state machine type code so that it works off a dictionary that I define elsewhere,
Not trying to push more LISP into python or anything, but of course we could converge your method and the switch statement elegantly if only we could put whole suites into lamdbas rather than just single expressions :-)
As has already been pointed out, this 1) adds function call overhead, 2) doesn't allow changes to variables in the containing function, and 3) even if we had a rebinding operator for free variables, we would have the overhead of creating closures. The lambda syntax does nothing to fix any of these problems, and you can already use a mapping of closures if you are so inclined. However, you'll probably find that the cost of creating the dictionary of closures exceeds the cost of a naive sequential search using if/elif.
On 16 Jun 2006, at 00:49, Phillip J. Eby wrote:
At 11:45 PM 6/15/2006 +0100, Nicko van Someren wrote:
On 15 Jun 2006, at 11:37, Nick Coghlan wrote:
... The lack of a switch statement doesn't really bother me personally, since I tend to just write my state machine type code so that it works off a dictionary that I define elsewhere,
Not trying to push more LISP into python or anything, but of course we could converge your method and the switch statement elegantly if only we could put whole suites into lamdbas rather than just single expressions :-)
As has already been pointed out, this
1) adds function call overhead, 2) doesn't allow changes to variables in the containing function, and 3) even if we had a rebinding operator for free variables, we would have the overhead of creating closures.
Noted. I find (2) the most compelling issue. I was merely suggesting a succinct way to express the model that Nick Cohglan was espousing.
The lambda syntax does nothing to fix any of these problems, and you can already use a mapping of closures if you are so inclined. However, you'll probably find that the cost of creating the dictionary of closures exceeds the cost of a naive sequential search using if/elif.
The smiley was supposed to indicate that this was not an entirely serious suggestion; my apologies if the signal was lost in transmission. In the equivalent if/elif to a switch you're only comparing a single value against a set of pre-computed values, and expecting to only do half the tests, so it's almost certainly going to be quicker than sorting out the whole set of closures. I do however have a bug-bear about lambdas being restricted to single expressions, but maybe that's just me. Nicko
Phillip J. Eby wrote:
As has already been pointed out, this
1) adds function call overhead, 2) doesn't allow changes to variables in the containing function, and 3) even if we had a rebinding operator for free variables, we would have the overhead of creating closures.
The lambda syntax does nothing to fix any of these problems, and you can already use a mapping of closures if you are so inclined. However, you'll probably find that the cost of creating the dictionary of closures exceeds the cost of a naive sequential search using if/elif.
This brings me back to my earlier point - I wonder if it would make sense for Python to have a non-closure form of lambda - essentially an old-fashioned subroutine: def foo( x ): x = 0 sub bar: # Arguments are not allowed, since they create a scope x = y # Writes over the x defined in 'foo' bar() The idea is that 'bar' would share the same scope as 'foo'. To keep the subroutine lightweight (i.e. just a single jump and return instruction in the virtual machine) arguments would not be allowed. -- Talin
participants (8)
-
Greg Ewing -
M.-A. Lemburg -
Nick Coghlan -
Nicko van Someren -
Phillip J. Eby -
Raymond Hettinger -
Talin -
Thomas Lee