Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #88572 > unrolled thread
| Started by | jonas.thornvall@gmail.com |
|---|---|
| First post | 2015-04-07 02:44 -0700 |
| Last post | 2015-04-09 16:28 +0300 |
| Articles | 5 on this page of 125 — 25 participants |
Back to article view | Back to comp.lang.python
Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 02:44 -0700
Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 09:29 -0400
Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 07:10 -0700
Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 10:26 -0400
Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 00:34 +1000
Re: Best search algorithm to find condition within a range Denis McMahon <denismfmcmahon@gmail.com> - 2015-04-07 14:29 +0000
Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 07:36 -0700
Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 00:49 +1000
Re: Best search algorithm to find condition within a range Grant Edwards <invalid@invalid.invalid> - 2015-04-07 15:05 +0000
Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 11:23 -0400
Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 01:37 +1000
Re: Best search algorithm to find condition within a range MRAB <python@mrabarnett.plus.com> - 2015-04-07 17:02 +0100
Re: Best search algorithm to find condition within a range MRAB <python@mrabarnett.plus.com> - 2015-04-07 16:00 +0100
Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 08:43 -0700
Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 08:51 +1000
Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 11:46 +1000
Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 11:04 -0400
Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 09:06 -0600
Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 08:47 -0700
Re: Best search algorithm to find condition within a range Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2015-04-07 20:06 -0400
Re: Best search algorithm to find condition within a range Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-04-08 12:49 +1200
Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 08:36 +1000
Re: Best search algorithm to find condition within a range Cameron Simpson <cs@zip.com.au> - 2015-04-08 08:51 +1000
Re: Best search algorithm to find condition within a range Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2015-04-07 20:01 -0400
Re: Best search algorithm to find condition within a range albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-18 18:08 +0000
Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-19 23:02 +1000
Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-19 17:56 +0300
Re: Best search algorithm to find condition within a range Gene Heskett <gheskett@wdtv.com> - 2015-04-19 11:17 -0400
Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-20 12:53 +1000
Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-19 14:52 -0400
Re: Best search algorithm to find condition within a range Paul Rubin <no.email@nospam.invalid> - 2015-04-19 13:44 -0700
Re: Best search algorithm to find condition within a range albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-25 14:49 +0000
Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 09:18 -0700
Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 08:32 -0600
Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 08:40 -0700
Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 12:33 -0400
Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 10:07 -0700
Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 11:44 -0600
Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 10:38 +1000
Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 11:18 +1000
Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-08 08:37 -0600
Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 23:19 -0700
Re: Best search algorithm to find condition within a range Mel Wilson <mwilson@the-wire.com> - 2015-04-08 13:39 +0000
Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-08 07:56 -0700
Re: Best search algorithm to find condition within a range Mel Wilson <mwilson@the-wire.com> - 2015-04-08 17:33 +0000
Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-08 12:28 -0700
Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-08 12:36 -0700
Re: Best search algorithm to find condition within a range Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-04-08 21:28 +0100
Re: Best search algorithm to find condition within a range Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-04-08 21:29 +0100
Re: Best search algorithm to find condition within a range Terry Reedy <tjreedy@udel.edu> - 2015-04-07 14:55 -0400
Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 13:19 -0600
Re: Best search algorithm to find condition within a range Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-07 20:27 +0100
Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 15:35 -0700
Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 20:38 -0400
Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 17:35 -0600
Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-08 00:28 -0700
Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-08 08:35 -0600
Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-08 00:35 -0700
Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 05:25 +1000
Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 13:28 -0600
Re: Best search algorithm to find condition within a range Serhiy Storchaka <storchaka@gmail.com> - 2015-04-07 23:57 +0300
Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 10:18 +1000
Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-08 07:31 +0300
Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 14:15 -0600
Re: Best search algorithm to find condition within a range Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-04-07 21:42 +0100
Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 08:55 +1000
Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 17:30 -0600
Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 08:57 +1000
Re: Best search algorithm to find condition within a range Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-04-08 12:59 +1200
Re: Best search algorithm to find condition within a range Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-04-08 02:39 +0100
Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 23:12 -0700
Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 11:49 +1000
Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-09 12:32 +1000
Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-09 12:39 +1000
Re: Best search algorithm to find condition within a range wxjmfauth@gmail.com - 2015-04-08 23:14 -0700
Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 22:50 -0700
Re: Best search algorithm to find condition within a range wxjmfauth@gmail.com - 2015-04-07 23:07 -0700
Re: Best search algorithm to find condition within a range wxjmfauth@gmail.com - 2015-04-07 23:18 -0700
Re: Best search algorithm to find condition within a range Denis McMahon <denismfmcmahon@gmail.com> - 2015-04-08 17:27 +0000
Re: Best search algorithm to find condition within a range wxjmfauth@gmail.com - 2015-04-08 10:50 -0700
Re: Best search algorithm to find condition within a range BartC <bc@freeuk.com> - 2015-04-08 22:22 +0100
Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 01:06 +0300
Re: Best search algorithm to find condition within a range Chris Kaynor <ckaynor@zindagigames.com> - 2015-04-08 17:01 -0700
Re: Best search algorithm to find condition within a range BartC <bc@freeuk.com> - 2015-04-09 10:19 +0100
Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 13:00 +0300
Re: Best search algorithm to find condition within a range Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2015-04-09 13:57 +0200
Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 15:45 +0300
Re: Best search algorithm to find condition within a range Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2015-04-09 14:56 +0200
Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-09 09:19 -0400
Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 16:33 +0300
Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 16:49 +0300
Re: Best search algorithm to find condition within a range Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2015-04-09 15:57 +0200
Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 00:08 +1000
Re: Best search algorithm to find condition within a range Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2015-04-09 16:53 +0200
Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 01:02 +1000
Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-09 08:12 -0700
Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 01:21 +1000
Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 01:36 +1000
Re: Best search algorithm to find condition within a range MRAB <python@mrabarnett.plus.com> - 2015-04-09 17:40 +0100
Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-09 07:54 -0700
Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-09 09:03 -0600
Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-09 08:21 -0700
Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-09 10:23 -0600
Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 01:11 +1000
Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 01:34 +1000
Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 02:15 +1000
Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 02:36 +1000
Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 03:49 +1000
Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 19:25 +0300
Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 02:43 +1000
Re: Best search algorithm to find condition within a range Grant Edwards <invalid@invalid.invalid> - 2015-04-09 16:53 +0000
Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 03:00 +1000
Re: Best search algorithm to find condition within a range Grant Edwards <invalid@invalid.invalid> - 2015-04-09 17:44 +0000
Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 03:41 +1000
Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 04:07 +1000
Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 21:14 +0300
Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 21:11 +0300
Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 20:43 +0300
Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 03:35 +1000
Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 03:56 +1000
Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 23:18 +1000
Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 23:41 +1000
Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 21:15 +0300
Re: Best search algorithm to find condition within a range Rustom Mody <rustompmody@gmail.com> - 2015-04-10 09:39 -0700
Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 16:28 +0300
Page 7 of 7 — ← Prev page 1 2 3 4 5 6 [7]
| From | Steven D'Aprano <steve+comp.lang.python@pearwood.info> |
|---|---|
| Date | 2015-04-10 23:18 +1000 |
| Message-ID | <5527cda8$0$12981$c3e8da3$5496439d@news.astraweb.com> |
| In reply to | #88748 |
On Fri, 10 Apr 2015 03:56 am, Chris Angelico wrote:
> On Fri, Apr 10, 2015 at 3:35 AM, Steven D'Aprano
> <steve+comp.lang.python@pearwood.info> wrote:
>> It's not so much the undefined behaviour part that gets me. That's bad
>> enough. But the concept that having the compiler ignore what you write in
>> the source code because you've accidentally hit some undefined part of
>> the spec *is a feature* rather than a horrible, horrible design flaw that
>> blows my mind.
>
> In Python, you can create an assert with a side effect. This is
> something you should never do,
"Never" is a bit strong. There's nothing wrong with:
assert log("some message") or condition
for example.
> and the compiler is free to optimize that side effect out.
Not really. The compiler is free to not execute the assertion at all, which
is not the same thing. A Python compiler which determined that log() always
returned None, and optimized the assertion to "assert condition", would be
buggy.
> Is that outright malicious? The only difference
> is that in Python, it's well-defined - you can *depend* on that code
> being optimized out under certain specific conditions, rather than it
> depending on the compiler.
There's more to my complaint than just that. In Python, the side-effects of
optimizing assert are localised to the assert statement. That's good! But
in C, the compiler can and will throw away more than assertions. Any chunk
of code could be thrown away, including code that should execute *before*
the undefined behaviour. You have spooky action at a distance and time
travel.
Explaining this requires a bit of set up, and I'm going to steal it from
Raymond Chen, whose blog is awesome despite him working for the Evil
Empire. (Not Google, the other one. No, not Apple. The one that used to be
scary. No, not IBM, more recently than that. Yes, Microsoft, that's the
one!) If you want to read about it in the original C, here it is:
http://blogs.msdn.com/b/oldnewthing/archive/2014/06/27/10537746.aspx
Suppose you write this function in Python:
def value_or_fallback(thingy):
print("The value of thingy is %d" % thingy)
return int(thingy) if thingy is not None else 42
`value_or_fallback` is buggy, because %d of None is an error. In actual
Python, the semantics of this are completely well defined: a runtime
TypeError. But in BizarroPython, that operation is undefined behaviour. So
the compiler can optimize that to:
def value_or_fallback(thingy):
print("The value of thingy is %d" % thingy)
return int(thingy)
BizarroPython can reason that if `thingy` is None, the first line (the print
call) is already performing undefined behaviour, so the compiler can do
anything, including act as if `thingy` is not None.
To put it another way, the compiler knows that if thingy is None, the print
call will crash before reaching the return call, so it can ignore the error
checking around the return. If thingy is None, the error checking will
never get the chance to run. If thingy isn't None, the error checking is
superfluous. (If this reasoning seems dubious to you, it's because it is.)
So far, this isn't too surprising. If we don't think too hard about it, we
might even consider this to be reasonable behaviour. But now the undefined
behaviour of `value_or_fallback` infects everything it touches, and allows
BizarroPython free reign to brutalise your code with a rusty shovel.
def unwitting(door_is_open):
if door_is_open:
walk_on_in()
else:
ring_bell()
# wait for the door to open using the fallback value
fallback = value_or_fallback(thingy)
wait_for_door_to_open(fallback)
BizarroPython can optimize this entire function to:
def unwitting(door_is_open):
walk_on_in()
The compiler observes that if `door_is_open` is false, the else branch
always performs undefined behaviour. Therefore, the entire else branch can
be treated as dead code.
Now let's start travelling in time:
def keep_checking_door():
while True:
response = input("Is the door open?")
if len(response) != 1:
return None
door_is_open = response == 'Y'
unwitting(door_is_open)
Our BizarroPython compiler may reason that "if door_is_open is false, then
the behaviour is undefined" and compile the function as if it were this:
def keep_checking_door():
while True:
response = input("Is the door open?")
if len(response) != 1:
return None
door_is_open = response == 'Y'
if not door_is_open:
os.abort() # Dumps core.
walk_on_in()
All this is well and good, if your intention was to crash faster. But if
you're trying to debug the crash, you have lost a valuable debugging hint.
If you thought you could debug your code by tracing it in your head, or on
paper, you've got a nasty surprise waiting. If you reason that since the
bell never gets rung, the bug causing the crash must be somewhere *before*
the call to ring_bell, but that's not the case. The bug occurs after
ring_bell, and propagates "backwards in time" to crash the application
before reaching the buggy code.
Obviously this isn't *actual* time travel, a less provocative phrase is the
one used by the C standard:
However, if any such execution contains an undefined operation,
this International Standard places no requirement on the
implementation executing that program with that input (not even
with regard to operations preceding the first undefined operation).
I prefer to call it time travel.
> (At least, I think that's the case. Is it
> legal for a Python implementation to fully evaluate asserts and then
> simply not raise the exception?)
The documented semantics of assertions in Python, like most (all?) other
languages which have them, is that assertions either run or don't run. What
doesn't happen is for them to run but suppress any exceptions. That would
be pointless: all the expensive of running the test, without the benefit of
seeing whether the test fails or not.
Could another language work the way you suggest? Well sure, another language
might define assertions any way they like, just as it might use "if x in
sequence" as a loop statement and have a rule that print() outputs to
stdout except on public holidays, when it outputs to a temporary file in
your home directory. There's no limit to how foolish languages could be.
> Take this example:
>
> def spam(lst):
> assert lst[0] < lst[1]
> # carry on with the rest of the code
>
> If lst is a Python list, this is side-effect free. But what if it
> isn't? What if __getitem__ actually mutates the object? The assertion
> can be dropped, and the getitem calls not made. Is that a horrible,
> horrible design flaw in Python, or is it an ill-designed object that
> does things that programmers should be allowed to assume never happen?
Neither. This is perfectly reasonable behaviour, side-effects or not.
assert can be considered syntactic sugar for this:
# assert expression
if assertions_enabled:
if expression: raise AssertionError
If expression happens to have side-effects, the fact that it isn't evaluated
when asserts are disabled is no more surprising, or horrible, than the fact
that expression won't be evaluated here:
if False:
print(expression)
(In Python's case, `assertions_enabled` is actually the read-only built-in
dunder variable __debug__.)
--
Steven
[toc] | [prev] | [next] | [standalone]
| From | Chris Angelico <rosuav@gmail.com> |
|---|---|
| Date | 2015-04-10 23:41 +1000 |
| Message-ID | <mailman.206.1428673324.12925.python-list@python.org> |
| In reply to | #88781 |
On Fri, Apr 10, 2015 at 11:18 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Fri, 10 Apr 2015 03:56 am, Chris Angelico wrote:
>
>> On Fri, Apr 10, 2015 at 3:35 AM, Steven D'Aprano
>> <steve+comp.lang.python@pearwood.info> wrote:
>>> It's not so much the undefined behaviour part that gets me. That's bad
>>> enough. But the concept that having the compiler ignore what you write in
>>> the source code because you've accidentally hit some undefined part of
>>> the spec *is a feature* rather than a horrible, horrible design flaw that
>>> blows my mind.
>>
>> In Python, you can create an assert with a side effect. This is
>> something you should never do,
>
> "Never" is a bit strong. There's nothing wrong with:
>
>
> assert log("some message") or condition
>
> for example.
>
>
>> and the compiler is free to optimize that side effect out.
>
> Not really. The compiler is free to not execute the assertion at all, which
> is not the same thing. A Python compiler which determined that log() always
> returned None, and optimized the assertion to "assert condition", would be
> buggy.
All you're saying is that, if the compiler optimizes out the side
effect, it must also remove the assertion. Doesn't change the fact
that it's something it's allowed to do.
> Suppose you write this function in Python:
>
> def value_or_fallback(thingy):
> print("The value of thingy is %d" % thingy)
> return int(thingy) if thingy is not None else 42
>
>
> `value_or_fallback` is buggy, because %d of None is an error. In actual
> Python, the semantics of this are completely well defined: a runtime
> TypeError. But in BizarroPython, that operation is undefined behaviour. So
> the compiler can optimize that to:
>
> def value_or_fallback(thingy):
> print("The value of thingy is %d" % thingy)
> return int(thingy)
>
> BizarroPython can reason that if `thingy` is None, the first line (the print
> call) is already performing undefined behaviour, so the compiler can do
> anything, including act as if `thingy` is not None.
In other words, the definition of "undefined behaviour" is "something
the programmer will never do". So if one branch of a condition is
undefined, the compiler can rightly assume that you will never execute
that branch, and optimize it out. Here's a C++ example that I actually
ran into at one point, ported brutally to Python:
class TreeNode:
def __init__(self, payload):
self.left = self.right = None
self.payload = payload
def walk(self, func):
if self.left: self.left.walk(func)
func(self.payload)
if self.right: self.right.walk(func)
(Omitting all the stuff about how they get linked together into a tree
as that's not significant here.)
Now, this works fine. But I thought to myself, there's duplication of
checks for null pointers - why not put that into just one place! And
wrote the walk function like this:
def walk(self, func):
if self is None: return
self.left.walk(func)
func(self.payload)
self.right.walk(func)
(It doesn't look like much here, but imagine dozens of places
elsewhere as well that used to have to go "if node: node.walk(f)" and
now just go "node.walk(f)".)
In C++, a null pointer still has its proper type, so calling walk() on
it would indeed come through to this function, unlike in Python where
None is a completely separate type. But it's illegal to call methods
on null pointers, so the compiler quite correctly optimized out the
initial check. But try taking this just on its own, without the
explanatory lead-up; would you ever expect that a method would be
called with self set to None? Of course not. Sure you _could_, but it
doesn't make sense, so you wouldn't.
> To put it another way, the compiler knows that if thingy is None, the print
> call will crash before reaching the return call, so it can ignore the error
> checking around the return. If thingy is None, the error checking will
> never get the chance to run. If thingy isn't None, the error checking is
> superfluous. (If this reasoning seems dubious to you, it's because it is.)
No, it's not dubious reasoning. You've violated a contract with the
compiler by requesting something that's undefined, ergo all bets are
off.
> So far, this isn't too surprising. If we don't think too hard about it, we
> might even consider this to be reasonable behaviour. But now the undefined
> behaviour of `value_or_fallback` infects everything it touches, and allows
> BizarroPython free reign to brutalise your code with a rusty shovel.
>
>
> def unwitting(door_is_open):
> if door_is_open:
> walk_on_in()
> else:
> ring_bell()
> # wait for the door to open using the fallback value
> fallback = value_or_fallback(thingy)
> wait_for_door_to_open(fallback)
What's thingy here? Is that meant to be None?
> BizarroPython can optimize this entire function to:
>
> def unwitting(door_is_open):
> walk_on_in()
If you do indeed call value_or_fallback with None as its argument,
then yes, that's quite correct.
> Now let's start travelling in time:
> [chomp example]
>
> All this is well and good, if your intention was to crash faster. But if
> you're trying to debug the crash, you have lost a valuable debugging hint.
> If you thought you could debug your code by tracing it in your head, or on
> paper, you've got a nasty surprise waiting. If you reason that since the
> bell never gets rung, the bug causing the crash must be somewhere *before*
> the call to ring_bell, but that's not the case. The bug occurs after
> ring_bell, and propagates "backwards in time" to crash the application
> before reaching the buggy code.
This is where stuff gets distinctly weird, yes. Welcome to the
debugging of optimized code. All sorts of "obvious expectations" go
out the window. There's no guarantee that your code will be executed
in any semblance of the order it was written in, and things can affect
each other in ways that you wouldn't have predicted.
>> (At least, I think that's the case. Is it
>> legal for a Python implementation to fully evaluate asserts and then
>> simply not raise the exception?)
>
> The documented semantics of assertions in Python, like most (all?) other
> languages which have them, is that assertions either run or don't run. What
> doesn't happen is for them to run but suppress any exceptions. That would
> be pointless: all the expensive of running the test, without the benefit of
> seeing whether the test fails or not.
Of course it's pointless, but I was wondering whether or not it's
legal. I was assuming it wasn't legal, and you're supporting that
belief.
>> Take this example:
>>
>> def spam(lst):
>> assert lst[0] < lst[1]
>> # carry on with the rest of the code
>>
>> If lst is a Python list, this is side-effect free. But what if it
>> isn't? What if __getitem__ actually mutates the object? The assertion
>> can be dropped, and the getitem calls not made. Is that a horrible,
>> horrible design flaw in Python, or is it an ill-designed object that
>> does things that programmers should be allowed to assume never happen?
>
> Neither. This is perfectly reasonable behaviour, side-effects or not.
>
> assert can be considered syntactic sugar for this:
>
> # assert expression
> if assertions_enabled:
> if expression: raise AssertionError
Yes, it's better defined. Doesn't change the fact that a lot of people
would be surprised if this happened.
And, in fact, *are* surprised when suppressing assertions breaks their
code. But it's not the suppression of assertions that broke their
code; their code was already broken. If your C code triggers any form
of undefined behaviour, *your code is already broken*. The compiler's
optimizations do not change this.
ChrisA
[toc] | [prev] | [next] | [standalone]
| From | Marko Rauhamaa <marko@pacujo.net> |
|---|---|
| Date | 2015-04-09 21:15 +0300 |
| Message-ID | <87oamxb2w2.fsf@elektro.pacujo.net> |
| In reply to | #88743 |
Steven D'Aprano <steve+comp.lang.python@pearwood.info>: > It's not so much the undefined behaviour part that gets me. That's bad > enough. But the concept that having the compiler ignore what you write > in the source code because you've accidentally hit some undefined part > of the spec *is a feature* rather than a horrible, horrible design > flaw that blows my mind. Similar reasoning is applied successfully (albeit dangerously) by Hotspot, Oracle's Java engine when optimizing multithreading. If natural code can be successfully optimized with such assumptions, more power to the optimizers. However, what we have here is the banning of very natural modulo arithmetic in favor of very questionable optimization gains. I want the wrapping semantics of integers and routinely exploit it in my code. I want the integer semantics of enums and want to gracefully handle range overflows. I don't want the compiler to intervene and screw my code because it thinks it's broken in the first place. > Of course not all C programmers are cowboys. Linux Torvalds has a > reputation for a zero-tolerance attitude towards kernel bugs, and a > take-no-prisoners attitude to anyone who might break userspace code > due to changes in the kernel. But I think that the vast number of > C/C++ exploitable bugs is proof that most C coders lack either the > skill or inclination to write correct C code. Even the Linux kernel > contains bugs. Things were bad enough in the old days of classical C > compilers, but modern C optimizing compilers may actively counteract > your code as you have written it. How that isn't considered an > outright malicious act, I don't know. I actually guess the point here is to permit optimizations in code written by complete newbs. The standard allows the optimizer guess the "real" intentions of the programmer and remove the performance deficiencies (a newb would use ints and imagine they are ideal integers). It's a win-win: the newbs are happy for having written performant code and the optimizers can feel they've accomplished heroic performance improvements. The sad result is that the value of C is diminished in the hands of the experienced programmers. Marko
[toc] | [prev] | [next] | [standalone]
| From | Rustom Mody <rustompmody@gmail.com> |
|---|---|
| Date | 2015-04-10 09:39 -0700 |
| Message-ID | <01f558cb-4e04-467a-a7a2-d6d13d5c6aea@googlegroups.com> |
| In reply to | #88743 |
On Thursday, April 9, 2015 at 11:05:54 PM UTC+5:30, Steven D'Aprano wrote: > On Fri, 10 Apr 2015 02:25 am, Marko Rauhamaa wrote: > > > Chris Angelico: > > > >> As far as it's concerned, it's impossible for a CPU register to > >> arbitrarily change without notice. It's equally impossible for the > >> addition of two positive signed integers to result in a negative > >> integer. > > > > The standard says that any program that takes a signed integer out of > > its valid range is broken and deserves anything that happens to it. > > > > I say it's the standard that is broken. > > It's not so much the undefined behaviour part that gets me. That's bad > enough. But the concept that having the compiler ignore what you write in > the source code because you've accidentally hit some undefined part of the > spec *is a feature* rather than a horrible, horrible design flaw that blows > my mind. There is something from Dijkstra (cant find the details ATM) that come to mind: How should a programmer think of writing a program that contains an ∞ loop? Imagine sitting in a room next to the computer... with no windows or doors... Just the computer When the programmer feeds the program to the computer he has to wait (that's WAIT) for the computer to print out the result before the door opens. And so if the machine 'hangs' so does the programmer!! In short when you do what you shouldn't do, there's no limit to the penalty. Dijkstra may strike many people as a nut, however I remember on the DOS machines on which I grew up, if the program crashed so did the OS -- switching on/off (the wall-plug!) was considered normal and acceptable behavior. If you were not so lucky you could lose the contents of the disk. And then there were horror stories of monitors getting fried by wrong refresh rates etc.
[toc] | [prev] | [next] | [standalone]
| From | Marko Rauhamaa <marko@pacujo.net> |
|---|---|
| Date | 2015-04-09 16:28 +0300 |
| Message-ID | <878ue1zb0a.fsf@elektro.pacujo.net> |
| In reply to | #88713 |
Alain Ketterlin <alain@dpt-info.u-strasbg.fr>: > Marko Rauhamaa <marko@pacujo.net> writes: > >> Alain Ketterlin <alain@dpt-info.u-strasbg.fr>: >> >>> No, it would not work for signed integers (i.e., with lo and hi of >>> int64_t type), because overflow is undefined behavior for signed. >> >> All architectures I've ever had dealings with have used 2's-complement >> integers. Overflow is well-defined, well-behaved and sign-independent >> wrt addition, subtraction and multiplication (but not division). > > You are confused: 2's complement does not necessarily mean modular > arithmetic. See, e.g., > http://stackoverflow.com/questions/16188263/is-signed-integer-overflow-still-undefined-behavior-in-c Ah, ok, I misunderstood your point. However, what I meant originally is that the given uintX_t implementation would work even if it were given intX_t arguments, and the returned uintX_t can be assigned to an intX_t variable safely. Marko
[toc] | [prev] | [standalone]
Page 7 of 7 — ← Prev page 1 2 3 4 5 6 [7]
Back to top | Article view | comp.lang.python
csiph-web