Is this if statement being evaluated?

[member 428835]

Line 7 in the code below seems to remove an element from stack, but why is this happening since it's just checking a condition? I'm pretty shocked I don't have to remove the previous char from stack myself.

def isValid(s):
    stack = []
    dict = {"]":"[", "}":"{", ")":"("}
    for char in s:
        if char in dict.values():
            stack.append(char)
        elif stack == [] or dict[char] != stack.pop():
            return False
    return stack == []
if __name__ == "__main__":
    s = "{([[{}]])}"
    print(isValid(s))

 

[jedishrfu]

Doesn't the pop remove the char from the stack?

 

[FactChecker]

In order to check the condition, the stack.pop() operation is applied, which removes an element from the stack. If you want to compare without removing it, you should reference it directly without pop.

 

[member 428835]

In order to check the condition, the stack.pop() operation is applied, which removes an element from the stack. If you want to compare without removing it, you should reference it directly without pop.

Okay, so despite this being in a conditional, it is being executed...did not know that, but good to know for future work. Thanks!

 

[PeterDonis]

Line 7 in the code below seems to remove an element from stack, but why is this happening since it's just checking a condition?

stack.pop() is not just checking a condition; that method mutates the object (by removing the popped item).

despite this being in a conditional, it is being executed

Why would you expect it not to be? Calling a method does whatever the method does. There aren't two versions of the method, one for use in conditionals and one for other uses.

 

[member 428835]

Yep, makes sense. Thanks!

 

[pbuk]

Okay, so despite this being in a conditional, it is being executed...did not know that, but good to know for future work. Thanks!

Why would you expect it not to be? Calling a method does whatever the method does. There aren't two versions of the method, one for use in conditionals and one for other uses.

But note that not all of a compound condition expression is always executed: in the example code stack.pop() is only executed if stack == [] evaluates to False.

For this reason (among others) it is usually not a good idea to include code with side effects in a condition expression.

 

[FactChecker]

But note that not all of a compound condition expression is always executed: in the example code stack.pop() is only executed if stack == [] evaluates to False.

For this reason (among others) it is usually not a good idea to include code with side effects in a condition expression.

Good advice, especially if you don't want to become an expert in the details of the language's operator priorities.
Is it true that the condition evaluation of an 'elif' stops with the first true? Does it depend on whether parenthesis appears in the condition? The Python precedence of a function call is very high (second after parenthesis).

 

[anorlunda]

Is it true that the condition evaluation of an 'elif' stops with the first true? Does it depend on whether parenthesis appears in the condition? The Python precedence of a function call is very high (second after parenthesis).

Might it depend on the implementation of the release you're using?
Worse, might the answer change in a future release?
Might it depend on optimization settings?

Unless the language specification itself details expression evaluation, it is dangerous to make assumptions.

 

[PeterDonis]

Is it true that the condition evaluation of an 'elif' stops with the first true?

In Python, the logical operators and and or are "short cut", meaning they stop evaluating clauses as soon as the final result is known (so at the first false for and and the first true for or). Not all languages do that, but most do because it obviously saves time.

Unless the language specification itself details expression evaluation

The Python language specification does explicitly say what I said above:

https://docs.python.org/3/reference/expressions.html#boolean-operations

 

[PeterDonis]

Might it depend on the implementation of the release you're using?
Worse, might the answer change in a future release?
Might it depend on optimization settings?

All of these would be bad ideas from a language design perspective. I'm not aware of any language that has done any of these with regard to the evaluation of logical expressions.

 

[PeterDonis]

Does it depend on whether parenthesis appears in the condition? The Python precedence of a function call is very high (second after parenthesis).

What I said (and referred to in the Python docs) in post #10 is for binary expressions. What particular binary expressions result from parsing a given line of code will obviously depend on whether and where there are parentheses, as well as default operator precedence.

 

[pbuk]

Is it true that the condition evaluation of an 'elif' stops with the first true?

No, not at all. What is happening is that in the expression A or B, B is only evaluated if A is false (if A is true then the expression will be true regardless of whether B evaluates to true or false). Similarly in the expression A and B, B is only evaluated if A is true (if A is false then the expression will be false regardless of whether B evaluates to true or false).

This needs to be flowed down into brackets so even with a simple and commonplace expression like (A or (B and C)) you cannot tell what evaluates and what doesn't without building a mental truth table. Simple real world example:

if (item.isStockItem() or (item.isOnBackOrder() and item.getInStockDate() < leadTime)):

Any side effects in item.getInStockDate() or item.isOnBackOrder() would not be obvious to predict.

 

[FactChecker]

The Python language specification does explicitly say what I said above:

https://docs.python.org/3/reference/expressions.html#boolean-operations

I would interpret the document as you stated above. I like the rule, but it does make an operator precedence table difficult to position the 'or' clearly. An operator precedence table that I saw puts the 'or' at a very low precedence, which I think is confusing. So one must read the official documentation carefully to get it right.

 

[PeterDonis]

I like the rule, but it does make an operator precedence table difficult to position the 'or' clearly. An operator precedence table that I saw puts the 'or' at a very low precedence, which I think is confusing.

Operator precedence in Python is further down on the same page I linked to before:

https://docs.python.org/3/reference/expressions.html#operator-precedence

It looks much more complicated than it actually is; the intent is that the default operator precedence should match how humans would naturally interpret the expression. So, for example, x in a or x in b parses as you would naturally read it, with the "in" taking precedence over the "or" so the expression is equivalent to (x in a) or (x in b). Putting the Boolean operators at low precedence makes sense, because you want to be able to use them to compare sub-expressions as in the above example.

Also, if you're not sure how an expression would be evaluated, you can always use explicit parentheses to make sure.

 

[pbuk]

Also, if you're not sure how an expression would be evaluated, you can always use explicit parentheses to make sure.

Yes but note that there is nothing you can do to make Python evaluate (i) the RHS of an or if the LHS is True; or (ii) the RHS of an and if the LHS is False. If you want to do this...

# you can rewrite
if (aExpression or bExpression):
# as
aValue = aExpression
bValue = bExpression
if (aValue or bValue):

 

[FactChecker]

It looks much more complicated than it actually is; the intent is that the default operator precedence should match how humans would naturally interpret the expression. So, for example, x in a or x in b parses as you would naturally read it, with the "in" taking precedence over the "or" so the expression is equivalent to (x in a) or (x in b). Putting the Boolean operators at low precedence makes sense, because you want to be able to use them to compare sub-expressions as in the above example.

But that simple precedence does not seem to apply to elsif true or f(z) if the call to f(z) is not done. The 'or' has higher precedence than that call to the function f(x), which normally has higher precedence.

Also, if you're not sure how an expression would be evaluated, you can always use explicit parentheses to make sure.

I totally agree with this. I would always recommend using parenthesis to force the precedence that you want rather than depending on obscure (to me) rules.

 

[PeterDonis]

But that simple precedence does not seem to apply to elsif true or f(z) if the call to f(z) is not done. The 'or' has higher precedence than that call to the function f(x), which normally has higher precedence.

Operator precedence is not the same thing as code execution. Operator precedence is applied during parsing--transforming textual source code to the actual code to be executed (in this case Python byte code). So, for example,

a * b + c * d

would get parsed to something like

push a
push b
binary_multiply
push c
push d
binary_multiply
binary_add

while

a * (b + c) * d

would get parsed to something like

push a
push b
push c
binary_add
binary_multiply
push d
binary_multiply

(It might help to know that the Python byte code interpreter is a stack-based virtual machine, and that binary opcodes pop the top two values off the stack, apply the operation, and push the result back on the stack.)

However, things like whether or not a binary operation is a short-circuit operation are not part of parsing, they are part of code execution. So, for example, the code

True or object.method()

would get parsed to something like

push True
unary_boolean_eval
jump_if_True done
push object
push method_name
get_attribute
call_function
:done

In other words, the short-circuit behavior of the or operator is part of code execution and cannot be changed no matter how you rearrange the source code or the operator precedence. The above block of pseudo-byte code is how every or operator gets parsed, no matter how it occurs in an expression or what its relative precedence is.

This is, as @pbuk said, one good reason why you should not put operations that have side effects inside expressions that might short-circuit during code execution.

 

[pbuk]

But that simple precedence does not seem to apply to elsif true or f(z) if the call to f(z) is not done. The 'or' has higher precedence than that call to the function f(x), which normally has higher precedence.

This is not about precedence, f(x) would still be evaluated before or (i.e. with a higher precedence) if it were evaluated at all.

I totally agree with this. I would always recommend using parenthesis to force the precedence that you want rather than depending on obscure (to me) rules.

But you cannot use parentheses here, this is not syntactically correct:

if (aExpression (or bExpression)):

Instead you need to do something like in my post above.

rather than depending on obscure (to me) rules.

You need to make it so that this is not obscure to you: this is called short-circuiting and I can't think of a language in common use today that doesn't implement and (or && or whatever) and or (or || or whatever) this way.

Better still just don't use functions with side effects in conditional expressions in any language as already advised and you won't come unstuck.

 

[pbuk]

Operator precedence is not the same thing as code execution...

Haha, you beat me to it!

 

[pbuk]

I can't think of a language in common use today that doesn't implement and (or && or whatever) and or (or || or whatever) this way.

There's a table here which confirms this. I can't believe I forgot about Visual Basic (and VBA): that cost me a day of chargeable time debugging someone else's mess at least once. The only other significant ones seem to be

• Fortran where the standard permits either short-circuited or eager operation (and so again the only consistent way to code is to avoid side effects in a conditional expression), and
• Kotlin where and/or are eager and &&/|| are short circuiting.

Note that where & and | are shown as eager operators in that table they generally perform a different operation, returning an integer being a bitwise binary and/or of the operands (which of course both have to be evaluated).

 

[PeterDonis]

This is not about precedence, f(x) would still be evaluated before or (i.e. with a higher precedence) if it were evaluated at all.

Actually, as the pseudo-byte code I posted earlier shows, the Boolean operators in Python don't even "evaluate" at all, at least not the way other binary operators do. There are no boolean_or or boolean_and byte codes. Instead, the Boolean operators expand to blocks of byte code that implement the short-circuiting algorithm.

Also note that the Python Boolean operators do not, in general, return Python booleans! The actual logic implemented in the byte code is:

For and, return the first argument if it is false, otherwise return the second.

For or, return the first argument if it is true, otherwise return the second.

Although the reason for this is simple--saving a possibly unnecessary call to the bool built-in on objects that aren't booleans, which could expand into an arbitrary amount of byte code since Python objects can define __bool__ magic methods--it trips up many people who are expecting the return values from Python boolean expressions to have the boolean type. (The best solution to that problem is to realize that the type of anything you're treating as a boolean actually doesn't matter, all that matters is how it evaluates. Also, experienced Python programmers will often take advantage of this property of the boolean operators to simplify code.)

 

[pbuk]

Yes all of that is true, and True

I think the Python documentation would be clearer for this if it used the concepts of 'truthy' and 'falsey' as is sometimes the convention elsewhere, thus:

• The expression x and y first evaluates x; if x is falsey, its value is returned; otherwise, y is evaluated and the resulting value is returned.
• The expression x or y first evaluates x; if x is truthy, its value is returned; otherwise, y is evaluated and the resulting value is returned.

I think I feel a geeky joke coming on...

 

[FactChecker]

This shows that even the lowest level of optimization can make the formal definition of a language complicated. IMO, that is why safety-critical programs are often not allowed to use the higher levels of optimization.
The higher optimization levels can make the language much harder to specify safe programming standards unless they are strictly controlled.

 

[pbuk]

This shows that even the lowest level of optimization can make the formal definition of a language complicated.

No, this is nothing to do with optimization, it is exactly in line with the specification of the language in the Python documentation linked above (and slightly misquoted by @PeterDonis) and is intentional behaviour which is, as I say, similar to many other languages.

 

[FactChecker]

No, this is nothing to do with optimization, it is exactly in line with the specification of the language in the Python documentation linked above (and slightly misquoted by @PeterDonis) and is intentional behaviour which is, as I say, similar to many other languages.

Yes. It puts a very low level of optimization into the language standard. The point is that it complicates what will or will not be executed. High levels of optimization aggravate the problem and are often disallowed.

PS. I'm not sure that I would say that the effect of the pop function is a "side effect" since its entire purpose is to remove an element.

 

[PeterDonis]

(and slightly misquoted by @PeterDonis)

I wasn't intending to quote directly, just to describe the logic that is implemented in the interpreter for each operator. AFAIK I described the logic correctly.

 

[PeterDonis]

I'm not sure that I would say that the effect of the pop function is a "side effect" since its entire purpose is to remove an element.

It's a side effect in the context of evaluating stack.pop() as a sub-expression of a logical expression. The value of the sub-expression is the element that is removed from the stack; but evaluating that element as part of evaluating the logical expression is a separate thing from removing the element from the stack.

A common precept of functional programming is that evaluation of expressions (which includes function calls that return a value) should be side effect-free and any mutation of state should be done by some kind of separate operation. In a language that strictly enforced that precept (which of course Python is not), if you wanted to both get the top element of the stack for evaluation and remove it, you would have to write something like this:

var = stack.top()
do stack.pop
if var == value:
    <...>

Here stack.top is a method call that returns a value for expression evaluation but does nothing else, and stack.pop would not be valid at all in an expression context (it would not return a value), and I have signaled that by putting the do in front of it.

 

[FactChecker]

It's a side effect in the context of evaluating stack.pop() as a sub-expression of a logical expression. The value of the sub-expression is the element that is removed from the stack; but evaluating that element as part of evaluating the logical expression is a separate thing from removing the element from the stack.

I'll buy that. By having the call serve two purposes, both returning and removing an element, it forces one of the two to be a side effect.

 

[FactChecker]

Operator precedence is not the same thing as code execution.

I see your point. The expression result mathematically depends on the operator precedence but is not affected by any shortcuts. The shortcuts are part of how the correct result will be efficiently arrived at and can change the side effects.