7
$\begingroup$

When mentioning operator precedence for AND / OR, I explained it wrongly. I re-explained it properly using the idea of binding: the operator "binds tightly" to the two expressions immediately on either side.

My incorrect explanation was based on me thinking of a complex expression as a tree, with AND as the root. For example, this fake expression:

expr1 OR expr2 AND expr3

behaves as if there are parentheses around expr2 AND expr3, but the "tree view of precedence" with AND being "more" would put the parentheses around the OR expression. I didn't explain my wrong idea to the students, but it is an error that I sometimes make in my thinking - it makes sense to me!

Is there a better way of explaining precedence to avoid this ambiguity than to say "it binds tightly"?

I encountered this when teaching SQL, but the question is not really about Boolean operators or Math, it is about Precedence in general as implemented in many languages. (If I had been showing a math example I would have unconsciously followed the rules of Algebra, but Booleans are not as common in my life.) A common synonym for Precedence is "Order Of Operations", but in SQL there is not supposed to be an 'order'. This is especially so with Booleans, because they just yield T/F and so there is no sense of left-to-right or anything.

$\endgroup$
  • $\begingroup$ What do you mean by “in SQL there is not supposed to be an 'order'” and “they just yield T/F and so there is no sense of left-to-right or anything”? $\endgroup$ – Sasha Jul 27 '17 at 10:48
  • 1
    $\begingroup$ And what's the problem with explaining precedence of logical operations in the same way as explaining precedence of arithmetic operations? With a + b * c we first calculate b * c and only then a + … — the same with a OR b AND c we first calculate b AND c and only then a OR …. $\endgroup$ – Sasha Jul 27 '17 at 10:51
  • $\begingroup$ @Sasha I confused myself because SQL is based on the relational model (set theory) which is less like programming (time sequence of commands and operations in order) and more like math (timeless / instantaneous expression of result), so there was no reason to talk about whether AND / OR is applied 'first', only which is more 'important'. Boolean operations do not 'care' if you do the left or right expression first, because, "who's on first?" Nobody! The Query Processor is free to rearrange whatever you type in any old way it wants anyhow. So that is why I visualized a tree and confused myself. $\endgroup$ – user737 Jul 27 '17 at 15:16
  • 1
    $\begingroup$ @nocomprende, «boolean operations do not 'care' if you do the left or right expression first» — but other operations (e.g. integer arithmetic) do not 'care' either (why do you differ boolean operations from others?). $\endgroup$ – Sasha Jul 27 '17 at 16:26
  • $\begingroup$ Incidentally, SQL is not relational. It violates the relational model in non-trivial ways. There are zero popular databases that truly follow the relational model. Something to remember when you read nonsensical statements about the obsolescence of the relational model in these days of "noSQL" databases. For more on this I refer you to SQL and Relational Theory. $\endgroup$ – Wildcard Jul 28 '17 at 3:35
5
$\begingroup$

Actually, your tree explanation is fine, except that it is the low precedence operators closer to the root. In Java, the "." operator is the strongest/highest and the assignment operators are the lowest precedence. The arithmetic operators are all higher precedence (bind tighter) than the booleans, with && having higher precedence than ||

A semi-official list is here: http://operator-precedence.com/java

In fact many compilers will translate an expression (the entire program, in fact) into a tree structure either explicitly or implicitly.

But, "binding tightly" is pretty traditional for an explanation also. The scope of an operator is limited by the end of the expression or the occurrence of a lower precedence operator. Therefore the RHS of the OR in your example is the end of the expression, but the LHS of the AND is bounded by the OR operator.

In the tree explanation work from lower to higher. In the "binding tightly" work from the higher to the lower precedence operator.


Odd historical note: To a logician, AND is logical "multiplication" and OR is logical "addition", hence the typical relationship in programming languages.

However, Pascal took that idea a bit too far and OR had the same precedence as addition with AND having the same precedence as multiplication, requiring parentheses in many more expressions than you would like.

On the other hand, having to write things explicitly in a programming language is usually a good thing as it lessens the likelihood of an oversight error.

$\endgroup$
  • $\begingroup$ My mistake was that I visualized a tree, thought of AND as 'higher' and described how it joined the larger parts together (which of course is wrong): expr1 OR expr2 joined with expr3... Why we draw 'trees' in CS with the root sticking up is beyond me! The student looked at the two examples and said, "so why are the results different?" and I went, Uh... and corrected myself the next day. They see me make mistakes a lot, and I don't even blush or stammer anymore. Sometimes I try to explain the origin of the mistake, so they avoid doing it also, other times I just "leave bad enough alone". $\endgroup$ – user737 Jul 27 '17 at 15:31
  • $\begingroup$ I'm guessing "root at top" is an artifact of working on blackboards with chalk in the days before bread came sliced. Easier to work that way and better use of the resource when the tree didn't fill the board. Just a guess, tho. If U R young, Google:blackboard. & maybe chalk too. And I suppose I've told a few whoppers in my time too. $\endgroup$ – Buffy Jul 27 '17 at 15:34
4
$\begingroup$

You can use an analogy of priority queues (maybe a hospital, if it isn't too gruesome; perhaps a queue for ordering work tasks)

A nurse doesn't need a patient to have some indicator that they are supposed to be treated before some other patients (these indicators are the parenthesis). There's simply a known treatment order, based on the urgency of the treatment.

If all patients need equally urgent treatment, then they are treated according to the order of their appearances (the ones who "check in" first are the ones treated first).

Nurses know how urgent a new patient's treatment is, and so does the compiler. For java, it goes like this:

1. postfix    expr++ expr--
2. unary  ++expr --expr +expr -expr ~ !
3. multiplicative * / %
4. additive   + -
5. shift  << >> >>>
6. relational < > <= >= instanceof
7. equality   == !=
8. bitwise AND    &
9. bitwise exclusive OR   ^
10. bitwise inclusive OR  |
11. logical AND   &&
12. logical OR    ||
13. ternary   ? :
14. assignment    = += -= *= /= %= &= ^= |= <<= >>= >>>=

(Taken from the Oracle Docs, numbering is mine. Originally has table)

In effect, the function and member call are before all other operators. So . is of precedence 0.

The nurse (compiler) knows in which order to actually treat (execute\write to bytecode) the various levels or urgency.

Different languages might have different ordering, but the analogy of a nurse ordering the treatment based on urgency would still hold. In the example you gave, it's more "urgent" to deal with the AND than it is with OR.

So in SQL, some operators are dealt with before others. Some operators require expressions on both sides, and some don't (select only needs from the right, while AND needs from both sides).

$\endgroup$
  • $\begingroup$ Actually, put the "." operator at position 0. y = x + foo.bar()++; for a functional method. $\endgroup$ – Buffy Jul 26 '17 at 18:41
  • $\begingroup$ @Buffy that list is specifically java. And it's irrelevant to the analogy... Oracle don't consider function and member calls as operators... $\endgroup$ – ItamarG3 Jul 26 '17 at 18:55
  • $\begingroup$ What they "consider" and how they operate are, then, perhaps different. See my example. The . (method resolution operator) is applied first and binds tightest, but yes, Java. The order of evaluation in y = x + foo.bar()++ is: ".", "++", "+" and finally "=". And "Oracle" isn't. =) (an oracle, that is) $\endgroup$ – Buffy Jul 26 '17 at 19:03
  • $\begingroup$ I noticed/remembered that Oracle owns MySQL and I blanched. Ugh $\endgroup$ – user737 Jul 28 '17 at 12:13
  • $\begingroup$ @nocomprende yep. MySQL belongs to oracle... $\endgroup$ – ItamarG3 Jul 28 '17 at 12:14
3
$\begingroup$

1st remind pupils of BIDMAS, they learn this is arithmetic class, around the age of 11years old. Though in programming it is usually BIMDAS. Though this only makes a difference when there are rounding errors.

When teaching boolean algebra, use a+b (or), a.b (and), as opposed to a∨b (or), a∧b (and). The second makes much more sense when relating boolean logic to set theory. However the first makes more sense when relating to algebra. The precedence is the same. All of the algebraic manipulations are the same, except 1+1=1. Now show that all of the rules in the book can be derived from these. Back this up by creating truth tables. Then practice. Then add de Morgan’s Theorem. Then practice.

When mixing logic, and arithmetic or any other complex combination (if you are not 100% sure, Or think that other will not be, or other languages do it differently, or you suspect that the may do, or just because you want to), then use parenthesis.

$\endgroup$
  • $\begingroup$ @no order of evaluation and precedents are different. Order of evaluation does not affect precedence. (You still get the expected result). It only changes behaviour if there are side effects; So if you are writing in a functional way, it will make no difference. (Removed from answer as not relevant) $\endgroup$ – ctrl-alt-delor Jul 27 '17 at 10:35
  • $\begingroup$ @richard, order of evaluation is different from precedence, but order of operations isn't. So the questioner's statement “a common synonym for ‘precedence’ is ‘order of operations’” is fully correct. Please, don't confuse “order of evaluation” (purely runtime concept) with “order of operations“ a.k.a. “operation/operator precedence” (mathematical and compile-time programming concept). $\endgroup$ – Sasha Jul 27 '17 at 11:03
  • $\begingroup$ @sasha, did I not say “order of evaluation and precedents are different”. And remove from answer? $\endgroup$ – ctrl-alt-delor Jul 27 '17 at 11:08
  • $\begingroup$ @richard, here — but I might misunderstand you. $\endgroup$ – Sasha Jul 27 '17 at 11:11
  • $\begingroup$ P.S.: I strongly oppose to teaching boolean algebra with precedence of conjunction higher than of disjunction. This makes students to perceive them as non-symmetric. When I was a student, our teacher was compelled to explicitly state that we should not regard conjunction as multiplication and disjunction as addition (even though we used same precedence and / notion) — because otherwise some of students could apply some laws only in half (e.g. “A∧(B∨C)=(A∧B)∨(A∧C)”, but not “A∨(B∧C)=…”). Though idea of replacing / signs with something else is great, as they really look too similar. $\endgroup$ – Sasha Jul 27 '17 at 11:29
0
$\begingroup$

Is there a better way of explaining precedence to avoid this ambiguity than to say "it binds tightly"?

The most unambiguous way to think about and explain precedence is by a context-free grammar (also known as a Backus–Naur form). The language of Boolean expression in the form of a context-free grammar follows.

expr0 ::= expr0 'OR' expr1 | expr1;
expr1 ::= expr1 'AND' expr2 | expr2;
expr2 ::= predicate | '(' expr0 ')';

expr0 is a Boolean expression; predicate is an atomic formula, an application of a predicate like “less than”. You see that the arguments of AND may be an AND-expression, a predicate application, or a bracketed expression, but never an OR-expression. The only way to insert an OR-expression inside an AND-expression is the way expr1expr2bracketsexpr0. Hence AND binds more tightly than OR. This defines precedence. Notice that this grammar also defines associativity; OR and AND are left-associative.

It is not possible to convey the whole theory of formal grammars in an answer. Any introductory textbook on automata theory, programming language semantics or implementation should contain this topic.

A common synonym for Precedence is "Order Of Operations", but in SQL there is not supposed to be an 'order'.

The fact that there is no order of operations in SQL is related to the semantics of SQL, while the question of precedence and associativity is related to syntax.

$\endgroup$
  • $\begingroup$ This is a good way to think about the topic once a student is sufficiently advanced in their studies, but I'm not sure what course of study would introduce automata theory and CFGs before introducing precedence. In our program, CFGs are introduced in the third year. $\endgroup$ – Ben I. Sep 10 '17 at 12:51
  • $\begingroup$ @Ben I. ♦: "what course of study would introduce automata theory and CFGs before introducing precedence" This material usually does not require knowledge of automata theory. It is where educators put it. Not my decision. $\endgroup$ – beroal Sep 10 '17 at 13:24
  • $\begingroup$ I believe that if a student can program, they can understand what I have written. It does not look advanced to me at all. I remember the online course "Paradigms of Computer Programming - Fundamentals" edx.org/course/… where syntax of Oz is defined by a context-free grammar. It is not the first course on programming, but it is basic, as is shown in its title. $\endgroup$ – beroal Sep 10 '17 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy