Lazarus

Programming => General => Topic started by: rnfpc on July 12, 2019, 09:09:53 am

Title: How is "not condition1 and condition2" evaluated?
Post by: rnfpc on July 12, 2019, 09:09:53 am
In the setting of "if", how is "not condition1 and condition2" evaluated?

It is evaluated as:

Code: Pascal  [Select][+][-]
  1. (not condition1) and condition2

or:

Code: Pascal  [Select][+][-]
  1. not (condition1 and condition2)

because: "(not false) and false" is false
but: "not (false and false)" is true.

Thanks for your insight.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: PascalDragon on July 12, 2019, 09:15:54 am
not has a stronger binding than and. Thus it's evaluated as (not condition1) and condition2.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: WooBean on July 12, 2019, 09:26:29 am
See Table 12.1: Precedence of operators at  https://www.freepascal.org/docs-html/ref/refch12.html#x139-16100012 (https://www.freepascal.org/docs-html/ref/refch12.html#x139-16100012)
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: Thaddy on July 12, 2019, 09:27:22 am
Actually all Boolean operators have equal weight and evaluation in Pascal is left to right, so not binds only to the first condition and and  binds the result to the second condition.
Sven is right, but maybe not clear enough.
Your own actual examples are exact and correct for that reason.
Some programmers therefor often use a style as suggested by Sven: even if the ( ) are not needed, like your first result, you may still want to use them for quicker readability.  The second example needs the brackets.
I am not one of those, but it is a valid solution and does not impact code generation.
[edit]
This also means that the documentation link above is not clear regarding precedence of Boolean operators. I will file a bug against it.

Reported as 0035834
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: PascalDragon on July 12, 2019, 09:55:11 am
See Table 12.1: Precedence of operators at  https://www.freepascal.org/docs-html/ref/refch12.html#x139-16100012 (https://www.freepascal.org/docs-html/ref/refch12.html#x139-16100012)
Ah, that's where the table I was looking for is.  :-[
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: Thaddy on July 12, 2019, 10:07:22 am
Ah, that's where the table I was looking for is.  :-[
Yes, I hope you agree precedence for Boolean operators is unclear.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: Kays on July 12, 2019, 12:22:38 pm
[…] evaluation in Pascal is left to right […]
FPC may re-arrange expressions though as it think it’s best. One heuristic is “evaluate more ‘complex’ sub-expressions first, and then turn to ‘simple’ sub-expressions.”

With the advent of and_then and or_else (extended Pascal) we can say “left to right” for those two.

I still don’t understand, how the precedence table (https://wiki.freepascal.org/Operator#operator_precedence) is equivocal. What is this “weight” you’re talking about?
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: ccrause on July 12, 2019, 12:33:17 pm
Actually all Boolean operators have equal weight and evaluation in Pascal is left to right, ...

Reference?  The FPC documentation agrees with the behaviour of the latest stable compiler:
Code: Pascal  [Select][+][-]
  1.   b1 := true;
  2.   b2 := true;
  3.   b3 := false;
  4.  
  5.   if b1 or b2 = b3 then
  6.     WriteLn('Unexpected')
  7.   else
  8.     WriteLn('Expected');
  9.  
  10.   if b3 = b2 or b1 then
  11.     WriteLn('Unexpected - left to right evaluation')
  12.   else
  13.     WriteLn('Expected based on precedence rules');

Title: Re: How is "not condition1 and condition2" evaluated?
Post by: Kays on July 12, 2019, 12:56:03 pm
[…]
= belongs to the category of “relational operators”, which comes third in precedence. I still don’t understand how and where any ambiguity may arise.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: Thaddy on July 12, 2019, 03:56:34 pm
What is this “weight” you’re talking about?
Quite simply, mathematical operators have a defined precedence. See here: https://en.wikipedia.org/wiki/Order_of_operations
These operators differ in weight.
Boolean operators do not have a defined precedence, they are all equal and their evaluation by the compiler is left to right.

Clear? (This is actually basics)

Whereas mathematical operators must all be evaluated because of weight - or order, if that is more clear to you - , Boolean operators can be shortcut once an impossibility is determined.

(To me it is really incomprehensible that some programmers do not understand Boolean logic)
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: glorfin on July 12, 2019, 04:31:37 pm
Actually all Boolean operators have equal weight and evaluation in Pascal is left to right, so not binds only to the first condition and and  binds the result to the second condition.
Well, unary operators have to have higher precedence.

In an expression
  a and not b
you have to evaluate "not b" before evaluation of "and".
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: lucamar on July 12, 2019, 06:24:01 pm
In an expression
  a and not b
you have to evaluate "not b" before evaluation of "and".

That is because to do otherwise makes no sense. You can't do "(a and not) b" just as you can't do "(a +-) b". There's no other option than "a and (not b)" and "a + (-b)".
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: glorfin on July 12, 2019, 06:37:10 pm
Yes, of course. But nevertheless, it means that "not" has precedence over other boolean operators, which contradicts earlier statement that they all are equal.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: lucamar on July 12, 2019, 07:38:35 pm
Yes, of course. But nevertheless, it means that "not" has precedence over other boolean operators, which contradicts earlier statement that they all are equal.

Not really. The boolean expression is parsed left to right. Iin this case, the parser sees the "and" so it expects:
Code: [Select]
boolean_expression and boolean_expressionso it examines things closely and finds "a" on the left and "not" on the right. That "not" cannot be by itself, so it looks a little more and decides that the right expression is "not b". Done.

The key here is that the "not" can't be interpreted alone: it introduces a new boolean expression. The net result is to make it look as if it had precedence, but it isn't really so.

Ah .. that is, of course, a very simplified explanation, not necessarily what the actual parser really does.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: Thaddy on July 12, 2019, 07:52:45 pm
Yes, of course. But nevertheless, it means that "not" has precedence over other boolean operators, which contradicts earlier statement that they all are equal.
No. You really do not understand this. Not has equal weight. a and not b will negate b. Basics. Real basics.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: Kays on July 12, 2019, 11:49:30 pm
[…] See here: https://en.wikipedia.org/wiki/Order_of_operations (https://en.wikipedia.org/wiki/Order_of_operations)
These operators differ in weight.
Yeah, I knew that, I simply never called it “weight” (and neither did the Wikipedia authors). For me weight is a concept from physics.
Boolean operators do not have a defined precedence, they are all equal and their evaluation by the compiler is left to right.
Huh??? That surprises me, though. Boolean operators are obviously mentioned in the precedence table in chapter “expressions” of the reference manual (https://www.freepascal.org/docs-html/ref/refch12.html), are they not?
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: lucamar on July 13, 2019, 01:08:36 am
Huh??? That surprises me, though. Boolean operators are obviously mentioned in the precedence table in chapter “expressions” of the reference manual (https://www.freepascal.org/docs-html/ref/refch12.html), are they not?

IIRC, those mentioned in that table are not the boolean operators but the bitwise (logical) ones. I may be wrong, though.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: Kays on July 13, 2019, 01:45:54 am
[…] IIRC, those mentioned in that table are not the boolean operators but the bitwise (logical) ones. I may be wrong, though.
Yeah, I had that idea, too, but that isn’t plausible, § Boolean operators (https://www.freepascal.org/docs-html/ref/refsu47.html): “Boolean operators can be considered as logical operations on a type with 1 bit size.” Ergo, you can just ignore the fact Pascal defines a dedicated Boolean data type and treat everything as integers, just as C does. The operator precedence table retains its validity.

PS: The documented operator precedence is concordance with ISO 7185 (http://www.pascal-central.com/iso7185.html#6.7.1%20General).
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: Thaddy on July 13, 2019, 09:58:10 am
I was a bit unclear myself: re-read my posts and replace Boolean with logical. That should suffice.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: BrunoK on July 13, 2019, 12:07:21 pm
Whatever the rules,
Code: Pascal  [Select][+][-]
  1.   if (b1 or b2) = b3 then
  2.  
  3.   if b3 = (b2 or b1) then
  4.  
parentheses to explicit the test precedence helps maintenance.

As a not 'superior logical' programmer it is how I have written those type of multi conditions for the last 30 years.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: glorfin on July 14, 2019, 02:02:42 am
a and not b will negate b.
This is perfectly unclear statement.
Obviously, here "a" will be evaluated, if it is false, no further processing continues and "false" is returned, because FPC, as far as I remember, uses lazy evaluation.
If "a" is true, it evaluates "not b"; if "not b" is false, it stops with "false" as result, otherwise "and" is evaluated and "true" returned.

Obviously, this is much more than just negation of b.
So, what did you want to say apart from being arrogant, as usually, is not clear.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: glorfin on July 14, 2019, 02:09:19 am
The net result is to make it look as if it had precedence, but it isn't really so.
If it always looks like it has precedence, maybe it is more simple to say that it has precedence? 
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: lucamar on July 14, 2019, 04:05:09 am
The net result is to make it look as if it had precedence, but it isn't really so.
If it always looks like it has precedence, maybe it is more simple to say that it has precedence?

When talking informally, yes, maybe; but in a technical forum one should strive to be as precise as one can. At least that's what I think.

For example, iin:
Code: [Select]
not a and b the fact that it means
Code: [Select]
(not a) and bis just an artifact of left-to-right parsing; parsed right-to-left it would mean:
Code: [Select]
not (a and b).
I don't think it will change tomorow (or ever, if for nothing else than backwards compatibility) but it might, and one has to be aware of it.

Or I may be completely wrong. It can happen too :)
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: PascalDragon on July 14, 2019, 11:41:49 am
a and not b will negate b.
This is perfectly unclear statement.
Obviously, here "a" will be evaluated, if it is false, no further processing continues and "false" is returned, because FPC, as far as I remember, uses lazy evaluation.
If "a" is true, it evaluates "not b"; if "not b" is false, it stops with "false" as result, otherwise "and" is evaluated and "true" returned.

Obviously, this is much more than just negation of b.
So, what did you want to say apart from being arrogant, as usually, is not clear.
The short hand evaluation of Boolean expression can be controlled using the $B directive. See here (https://www.freepascal.org/docs-html/current/prog/progsu4.html#x11-100001.2.4).

The net result is to make it look as if it had precedence, but it isn't really so.
If it always looks like it has precedence, maybe it is more simple to say that it has precedence?

When talking informally, yes, maybe; but in a technical forum one should strive to be as precise as one can. At least that's what I think.

For example, iin:
Code: [Select]
not a and b the fact that it means
Code: [Select]
(not a) and bis just an artifact of left-to-right parsing; parsed right-to-left it would mean:
Code: [Select]
not (a and b).
I don't think it will change tomorow (or ever, if for nothing else than backwards compatibility) but it might, and one has to be aware of it.

Or I may be completely wrong. It can happen too :)
The order of parsing will not change, because that's part of the Pascal standard (no matter if early Wirth's Pascal, ISO Pascal or Delphi language).
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: Peter H on July 14, 2019, 02:29:40 pm
Code: Pascal  [Select][+][-]
  1. program Project1;
  2.  
  3. begin
  4.  
  5. writeln (true or true and false);
  6. writeln (false and true or true);
  7. readln;
  8.  
  9. end.
  10.  
  11.  

This program prints "TRUE","TRUE" in FPC 3.3.1.
Same result in Delphi and in fpc 3.0.4.
So it seems the "and" operator has higher priority than "or".
(It is the same in C and in boolean algebra notation, "and" is treated as a multiplicative operator and has higher priority)
I am a little bit confused.
My book says all boolean operators have the same priority in pascal, but that doesnt seem true to me.
Obviously my book
 https://www.amazon.de/Lazarus-Essentials-Peter-Wolfinger/dp/198304508X/ref=sr_1_1?__mk_de_DE=%C3%85M%C3%85%C5%BD%C3%95%C3%91&keywords=lazarus+essentials&qid=1563114995&s=gateway&sr=8-1 (https://www.amazon.de/Lazarus-Essentials-Peter-Wolfinger/dp/198304508X/ref=sr_1_1?__mk_de_DE=%C3%85M%C3%85%C5%BD%C3%95%C3%91&keywords=lazarus+essentials&qid=1563114995&s=gateway&sr=8-1)
is in error here and my other two three books about pascal say nothing about this  :o
(Otherwise this is a very good book)
So, whats about the priority of "exor"? (I think it is equal to or, because thats the common convention)

So this means, if there is left to right short circuit evaluation, in this code:
Code: [Select]
writeln (false and foo_a() or foo_b());

foo_a() will not be called.
foo_b() will be called.

This stuff is a little bit confusing and many books and websites explain it wrong or not at all.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: jamie on July 14, 2019, 04:29:55 pm
years ago before sanity kicked in, ANDing two numbers meant multiplying them...

There was no such thing as a limit to a number, the size of the number was always infinite,

 So True * True  would be true..

 Since True in the compiler generates the initial value of 1 it kind of works out..

 but if two numbers were valid, them multiplying each other would always turn out valid other than 0.

 but as you know, multiply any number by 0 you get zero.

 so since in this thinking its logical to treat the AND as a multiplier when doing such things..
 
 remember a True is any number other than 0.

 In the computer world in the background the actual process isn't done that way because you could
end with a 0 results if you don't have some sort of overflow control taking place plus it would be
inefficient so they still keep with the old school math of order but process it logically in the background.

 That is the way I understand it from my old days of math (YEARS ago)…

Title: Re: How is "not condition1 and condition2" evaluated?
Post by: Peter H on July 14, 2019, 04:43:00 pm
In programs there is time.
Wirth tried to make pascal conform to mathematical notation.
But in mathematics and logic there is no time, there is no cause-effect relationship in boolean algebra.
So this try can be only partial successful, it is an impossible try....
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: Peter H on July 14, 2019, 05:21:38 pm
Code: Pascal  [Select][+][-]
  1. program Project1;
  2.  
  3.   function t1: boolean;
  4.   begin
  5.     t1 := True;
  6.     writeln('t1 was called');
  7.   end;
  8.  
  9.   function t2: boolean;
  10.   begin
  11.     t2 := True;
  12.     writeln('t2 was called');
  13.   end;
  14.  
  15. begin
  16.   writeln(t1 and False or t2);
  17.   writeln('Next try');
  18.   writeln(False and t1 or t2);
  19.  
  20.   readln;
  21. end.
  22.  

Output:

t1 was called
t2 was called
TRUE
Next try
t2 was called
TRUE


Short circuit evaluation means: Two logical equivalent expressions have identical results, but different (side) effect.  O:-)
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: jamie on July 14, 2019, 05:29:13 pm
Looks normal to me..

No mater the AND results you are ORing with a TRUE. so it will always be true

the AND operation is first which yields a FALSE then you OR with a TRUE because T2 is returning true.

so its One "OR" the Other!
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: ASerge on July 14, 2019, 08:37:41 pm
Output:

t1 was called
t2 was called
TRUE
It was a good idea if the compiler could optimize such code by removing the call to the t1 function, which does not affect the result. The side effect of calling a function here is still not guaranteed by the documentation.
In justification, we can say that Delphi behaves in the same way.
FPC:
Code: ASM  [Select][+][-]
  1. project1.lpr:19                           B := (t1 and False) or t2;
  2. 000000010000150E e84dffffff               call   0x100001460 <T1>   ; unnecessary function call
  3. 0000000100001513 84c0                     test   al,al              ; The result is even tested, but not used
  4. 0000000100001515 e896ffffff               call   0x1000014b0 <T2>
  5. 000000010000151A 84c0                     test   al,al
  6. 000000010000151C 7405                     je     0x100001523 <main+35>
  7. 000000010000151E 40b601                   mov    sil,0x1
  8. 0000000100001521 eb03                     jmp    0x100001526 <main+38>
  9. 0000000100001523 40b600                   mov    sil,0x0
  10. project1.lpr:20                           writeln(B);
Delphi:
Code: ASM  [Select][+][-]
  1. Project15.dpr.19: B := (t1 and False) or t2;
  2. 000000000040E8DF E80CFFFFFF       call t1             ; Here, too, unnecessary function call, but the result is immediately ignored
  3. 000000000040E8E4 E867FFFFFF       call t2
  4. 000000000040E8E9 84C0             test al,al
  5. 000000000040E8EB 7504             jnz Project1 + $31
  6. 000000000040E8ED 33C0             xor eax,eax
  7. 000000000040E8EF EB02             jmp Project1 + $33
  8. 000000000040E8F1 B001             mov al,$01
  9. 000000000040E8F3 8805E7A80000     mov [rel $0000a8e7],al
  10. Project15.dpr.20: writeln(B);
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: lucamar on July 14, 2019, 08:48:49 pm
Output:

t1 was called
t2 was called
TRUE
It was a good idea if the compiler could optimize such code by removing the call to the t1 function, which does not affect the result. The side effect of calling a function here is still not guaranteed by the documentation.

But it must call the function, mustn't it? Not because the possible side effectc (though that too) but to guarantee the  evaluation order? Although it may be alright to skip it in "unsafe optimizations" mode :)

Sometimes it's a little difficult to guess what "short-circuit" means when combined with all the other rules ... The moral here seems to be: "spare the parenthesis and ruin the program" :D (They wouldn't help here, though)
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: ASerge on July 14, 2019, 08:58:02 pm
but to guarantee the  evaluation order?
And where does it say that the operands of a binary operation should be calculated in the order of writing?
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: lucamar on July 14, 2019, 09:19:00 pm
but to guarantee the  evaluation order?
And where does it say that the operands of a binary operation should be calculated in the order of writing?

I would swore I have read it somewhere (in legit docs) but I'm unable to find it now, so I may be wrong :-[

Which is why I enunciated it as a question, BTW.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: ASerge on July 14, 2019, 09:49:32 pm
I would swore I have read it somewhere (in legit docs) but I'm unable to find it now, so I may be wrong :-[
In fact, it seems logical, otherwise it was difficult to predict the behavior of such an expression:
Code: Pascal  [Select][+][-]
  1. if Assigned(P) and (P^...)...
But for some reason in the documentation this was not explicitly mentioned.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: BrunoK on July 14, 2019, 10:16:26 pm
but to guarantee the  evaluation order?
And where does it say that the operands of a binary operation should be calculated in the order of writing?
somewhere it is documented : left to right evaluation.
Otherwise we would have trouble with
If assigned (someproc) then
  Someproc(param1,param2);
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: lucamar on July 14, 2019, 10:30:30 pm
Fact is it explicitely warns against this in the language reference (https://www.freepascal.org/docs-html/current/ref/refch12.html):
Quote from: Free Pascal Reference Guide
Remark: The order in which expressions of the same precedence are evaluated is not guaranteed to be left-to-right. In general, no assumptions on which expression is evaluated first should be made in such a case. The compiler will decide which expression to evaluate first based on optimization rules.

For some reason it never ociurred to me that it applied to boolean expressions precisely because of what you say about constructions of the style "if Assigned(AVar) and AVar.TestSomething then ..." which I (and most everyone, I guess) use with certain abandon ...

Otherwise we would have trouble with
If assigned (someproc) then
  Someproc(param1,param2);

There's no trouble in that! Though I know what you meant :)

Another common example, beyond the "if Assigned() and ..." is testing for a component Tag in an event handler:
Code: Pascal  [Select][+][-]
  1. if Sender.InheritsFrom(TComponent) and (TComponent(Sender).Tag <> 0) then begin
  2.   {...more code...}
  3. end;
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: BrunoK on July 14, 2019, 11:33:16 pm
If some of the high priests of FPC decided to change the left to right order of conditionals, FPC would be dead.
There are thousands of conditionals that expect left to right evaluation in Lazarus/FPC and it is also the way Delphi does it, or at least it was so in D3 up to the latest version I had.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: Kays on July 14, 2019, 11:45:10 pm
Code: Pascal  [Select][+][-]
  1. []
  2. writeln (true or true and false);
  3. writeln (false and true or true);
  4. []
  5.  
You are aware that constant expressions are evaluated at compile-time? The behavior may differ between compile-time and run-time.
[…] ANDing two numbers meant multiplying them... […]
Well, that’s still true: In electrical engineering the notation A⁢B (with invisible “times”) means A ∧ B.
If some of the high priests of FPC decided to change the left to right order of conditionals, FPC would be dead. […]
There’s no room for discussion: The ISO 7185 again defines (http://www.pascal-central.com/iso7185.html#6.7.1%20General): “[…] operators of the same precedence shall be left associative.” Wirth originally stated (http://www.pascal-central.com/docs/pascal1973.pdf) (PDF page 24): “Sequences of operators of the same precedence are executed left to right.”
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: Peter H on July 14, 2019, 11:45:33 pm
If evaluation from left to right is guaranteed, then optimization (which can change the order of evaluation) cannot be allowed.
(If partial operations are removed this is also a change of execution order  8) )
So I think, the compiler cannot optimize it away.
I assume even C++ doesnt do this, but I dont know.

Let me answer the original question of the OP with my own words:

"not a and b" is evaluated from left to right.
Because "not" has the higest priority, it binds to a and not to "a and b".

The evaluation order has nothing to do with the binding and assoziation order and priority.
The assoziation and binding is about the syntax, and the evaluation order is about the order in which separable subexpressions are executed. It is importan t to know this.

So the leftmost subexpression is "not a". First is a evaluated, (that means calculated or fetched then it is inverted.
then b is evaluated and then finally it is "anded" with the inverted value of a.

This means evaluation from left to right means the leftmost separable subexpression is evaluated (aka calculated)  first, with all possible side effects.

This all under the assumption that the default short circuit evaluation is used.
I do not know, if the order is still striktly left to right, if shortcircuit evaluation is disabled.


Title: Re: How is "not condition1 and condition2" evaluated?
Post by: rnfpc on July 15, 2019, 05:03:16 am
Following modification of function by @PeterH may be more helpful to analyze order:

Code: Pascal  [Select][+][-]
  1. {$mode objfpc}
  2. function t(i:integer): boolean;
  3.   begin
  4.     result:= True;
  5.     writeln('t(',i,') called');
  6.   end;
  7. begin
  8.   writeln('t(0) and t(1) and t(2) or t(3) and t(4) or t(5)');
  9.   writeln(t(0) and t(1) and t(2) or t(3) and t(4) or t(5));
  10.  
  11.   writeln('t(1) and not t(2) or t(3) and not t(4) or t(5)');
  12.   writeln(t(1) and not t(2) or t(3) and not t(4) or t(5));
  13.  
  14.   writeln('t(1) and t(2) or not t(3) and t(4) or t(5)');
  15.   writeln(t(1) and t(2) or not t(3) and t(4) or t(5));
  16.  
  17.   writeln('false or t(2) and t(3) and t(4)');
  18.   writeln(false or t(2) and t(3) and t(4));
  19.  
  20.   writeln('t(1) and not t(2) or not t(3) and t(4)');
  21.   writeln(t(1) and not t(2) or not t(3) and t(4));
  22.  
  23.   writeln('t(1) and not t(2) or not t(3) and t(4) or t(5)');
  24.   writeln(t(1) and not t(2) or not t(3) and t(4) or t(5));
  25.  
  26.   writeln('t(1) and not t(2) or t(3)');
  27.   writeln(t(1) and not t(2) or t(3));
  28. end.
  29.  

Output:
Code: Pascal  [Select][+][-]
  1. t(0) and t(1) and t(2) or t(3) and t(4) or t(5)
  2. t(0) called
  3. t(1) called
  4. t(2) called
  5. TRUE
  6. t(1) and not t(2) or t(3) and not t(4) or t(5)
  7. t(1) called
  8. t(2) called
  9. t(3) called
  10. t(4) called
  11. t(5) called
  12. TRUE
  13. t(1) and t(2) or not t(3) and t(4) or t(5)
  14. t(1) called
  15. t(2) called
  16. TRUE
  17. false or t(2) and t(3) and t(4)
  18. t(2) called
  19. t(3) called
  20. t(4) called
  21. TRUE
  22. t(1) and not t(2) or not t(3) and t(4)
  23. t(1) called
  24. t(2) called
  25. t(3) called
  26. FALSE
  27. t(1) and not t(2) or not t(3) and t(4) or t(5)
  28. t(1) called
  29. t(2) called
  30. t(3) called
  31. t(5) called
  32. TRUE
  33. t(1) and not t(2) or t(3)
  34. t(1) called
  35. t(2) called
  36. t(3) called
  37. TRUE
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: Thaddy on July 15, 2019, 09:36:29 am
That's the same order I wrote....
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: howardpc on July 15, 2019, 11:33:28 am
"evaluated" in this topic's subject is being interpreted in different ways by contributors to this thread.
There are two levels at which "left to right" 'evaluation' can be applied.

The first transformation of a boolean expression is the parsing operation which takes valid Pascal code and turns it into a sequence of 'atoms' - syntactic units which cannot be parsed any further in Pascal. The atom sequence is determined solely by the left-to-right convention of writing languages such as English and Pascal.
The outcome of this first parsing level of evaluation is a sequence of atoms of four sorts:It is at this evaluation level that a parser may raise an error if, say, parentheses present are not paired correctly.
The left to right sequence of
operand   operator   operand    operator   etc. is fixed and immutable
However, at the next stage of extracting meaning from the particular given combination of operator/operand/paretheses the left-to-right order of the parsed atoms may be overridden by the rules of operator precedence.
The unary operator "not" takes only one operand, the operand to its immediate right. The presence of parentheses may extend the scope of "not" beyond its immediate rightmost atom, so parentheses are at the same semantic level as "not", call it Level 0.
All other boolean operators are binary (taking two operands) and are at lower levels. They are combined strictly according to this order of precedence
At this stage of evaluation, operator precedence may override the left-to-right sequence of atoms.
Additionally, default short-circuit boolean evaluation means that often parsing/semantic combination and evaluation ends prematurely, allowing us to safely write
if Assigned(Sender) and (Sender as xxx).property ...
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: Thaddy on July 15, 2019, 11:52:24 am
That's not correct Howard. Hence the bug report against documentation. Pure Boolean operators are equal weight.
(Boole would probably have turned in his grave)
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: wp on July 15, 2019, 11:55:33 am
That's the same order I wrote....
Didn't you say that boolean expressions are evaluated from left to right and "and" and "or" have the same priority? Reply #3: "Actually all Boolean operators have equal weight and evaluation in Pascal is left to right"

I think rnfpc's code proves that this is not correct.

Look at the first expression:
Code: [Select]
t(0) and t(1) and t(2) or t(3) and t(4) or t(5).
Assuming left-to-right evaluation, and that AND and OR have the same "weight":

No disagreement that the left-most conditon, t(0), must be evaluated first. Its result is TRUE.
The next condition is an AND with t(1). Since the AND can turn a TRUE into a FALSE, t(1) must be evaluated.
The same with t(2) which is connected by an AND, too.
The next condition is an OR with t(3). Since the result of the expression is still TRUE and since the OR cannot change a TRUE any more, t(3) can be skipped.
Next, we have an AND with t(4) which must be evaluated for the same reason as before.
The final OR can be skipped again.

So, in total, the function t(0), t(1), t(2) and t(4) were called.

The program output tells, however, that t(4) was not called.

This can be understood if AND has a higher priority than OR. The expression can be rewritten like this
Code: [Select]
( t(0) and t(1) and t(2) ) or
 ( t(3) and t(4) ) or
 t(5)

Since the first part of the OR expression, (t(0) and t(1) and t(2)), already yields TRUE which cannot be changed by the next OR expression only t(0), t(1) and t(2) need to be evaluated.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: 440bx on July 15, 2019, 12:34:30 pm
This can be understood if AND has a higher priority than OR. The expression can be rewritten like this
Code: [Select]
( t(0) and t(1) and t(2) ) or
 ( t(3) and t(4) ) or
 t(5)

Since the first part of the OR expression, (t(0) and t(1) and t(2)), already yields TRUE which cannot be changed by the next OR expression only t(0), t(1) and t(2) need to be evaluated.
I've been reading this thread and wondering when someone was going to show that the "left to right" evaluation only applies to operators that have the same precedence and precedence varies among the Boolean operators.

The following is quoted directly from Jensen and Wirth's Pascal report (pages 148 through 151 with portions removed which do not affect the net result):
Quote
The  rules  of  composition  specify  operator  precedences  according to  four  classes  of operators.  The  operator  not  has  the  highest precedence,  followed  by  the  so-called  multiplying  operators, then  the  so-called  adding  operators,  and  finally,  with  the lowest  precedence,  the  relational  operators.  Sequences  of operators  of  the  same  precedence  are  executed  from  left  to right.  The  rules  of precedence  are reflected  by  the  following syntax:

<BNF syntax and examples removed>

<The operators are listed in order of precedence (highest precedence first)>

8.1.1.  The operator not
        The  operator  not denotes  negation  of  its  Boolean  operand.

8.1.2.  Multiplying operators
        <multiplying  operator>  ::=  *  |  /  |  div  | mod | and

8,1.3.  Adding operators
        <adding  operator>  ::=  +  |  -  | or

8.1.4.  Relational  operators
        <relational  operator>  ::=  =  |  <>  |  <  | <=  |  >=  |  >  | in

I've heard Kathleen Jensen and Niklaus Wirth had some knowledge of Pascal ;)


ETA:

Pure Boolean operators are equal weight.
Pure Boolean operators ? ... unlike the impure Boolean operators, those go to Church ? ... them Boolean sinners.

(Boole would probably have turned in his grave)
He is probably spinning by now.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: howardpc on July 15, 2019, 12:43:15 pm
Thaddy: what do you get with the following?
Code: Pascal  [Select][+][-]
  1.   WriteLn('[unvarnished outcome]          True or False and False ',True or  False and False);
  2.   WriteLn('[''and'' has precedence]       True or (False and False) ',True or  (False and False));
  3.   WriteLn('[left-to-right has precedence] (True or False) and False ',(True or  False) and False);
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: Zoran on July 15, 2019, 01:51:08 pm
In fact, it seems logical, otherwise it was difficult to predict the behavior of such an expression:
Code: Pascal  [Select][+][-]
  1. if Assigned(P) and (P^...)...
But for some reason in the documentation this was not explicitly mentioned.
It is really unclear in current docs, so I recently reported exactly this, then Michael updated the docs for 3.2 -- https://bugs.freepascal.org/view.php?id=35661 (https://bugs.freepascal.org/view.php?id=35661)
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: ASerge on July 15, 2019, 03:28:04 pm
It is really unclear in current docs, so I recently reported exactly this, then Michael updated the docs for 3.2 -- https://bugs.freepascal.org/view.php?id=35661 (https://bugs.freepascal.org/view.php?id=35661)
Thanks. In the repository "fpcdocs" in the file "ref.tex" there is an addition:
Code: LaTeX  [Select][+][-]
  1. A notable exception to this behaviour is the evaluation of boolean expressions:
  2. if short-circuit boolean evaluation is enabled (the default) then the
  3. compiler will evaluate from left to right, but will still respect
  4. precedence, i.e. in parts with equal precedence the left operand will always
  5. be evaluated before the right one. Thus, the following example:
  6. \begin{verbatim}
  7.  True or True and False
  8. \end{verbatim}
  9. will evaluate to \var{True}, because it is equivalent to
  10. \begin{verbatim}
  11.  True or (True and False)
  12. \end{verbatim}
  13. \end{remark}
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: rnfpc on July 15, 2019, 06:12:44 pm
Following functions are also useful to experiment:

Code: Pascal  [Select][+][-]
  1. {$mode objfpc}
  2. function t(i:integer):boolean;
  3.         begin
  4.         result:= true;
  5.         writeln('t(',i,') called');
  6.         end;
  7. function f(i:integer):boolean;
  8.         begin
  9.         result:= false;
  10.         writeln('f(',i,') called');
  11.         end;
  12. begin
  13.         writeln('not f(1) and t(2) or f(3)');
  14.         writeln(not f(1) and t(2) or f(3));
  15. end.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: Thaddy on July 15, 2019, 09:18:08 pm
Quote
He is probably spinning by now.
Permanently.... :)
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: VTwin on July 15, 2019, 10:11:17 pm
I've been reading this thread and wondering when someone was going to show that the "left to right" evaluation only applies to operators that have the same precedence and precedence varies among the Boolean operators.
...

I remember that, and remember finding it hard to remember (precedence of "and" vs "or"). :) So I use parentheses even when not needed.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: RedOctober on July 16, 2019, 04:00:43 am
I always use parenthesis in these cases.  It forces a precedence and is clear to read.  (Even if I don't "really" need them)
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: rnfpc on July 16, 2019, 05:19:42 am
From different tests, following seem to be the 'rules':

1. Evaluation is from left to right.
2. 'not' binds only to the next term, not beyond it. Hence 'not a or/and b' means '(not a) or/and b'. It does not mean 'not(a or/and b)'
3. Similarly, 'and' only binds to next term and not beyond, hence 'a and b or c' means '(a and b) or c' and not 'a and (b or c)'
4. Statement beyond 'or' is evaluated only if current value is false. If current value is true, evaluation of statement ends on encountering 'or'.
5. Term beyond 'and' is evaluated only if current value is true. If current value is false, control jumps beyond the term after 'and', putting current value there as false. (Evaluation of further terms will only occur if an 'or' is encountered).


Above is helping me for actual coding.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: lucamar on July 16, 2019, 05:54:40 am
I always use parenthesis in these cases.  It forces a precedence and is clear to read.  (Even if I don't "really" need them)

Yeah, I do that too except for very simple expressions. But know what? I've just realized that because of that I have never interiorized the precedence rules. I know them grosso-modo but I don't really grok them.

Which means one (more) thing for me to stop and study carefully :)
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: 440bx on July 16, 2019, 06:12:18 am
Which means one (more) thing for me to stop and study carefully :)
I think the simplest way of understanding the Boolean precedence rules is how Jensen & Wirth presented them in their Pascal report.

Basically (precedence-wise),

not is equivalent to the unary minus
and is equivalent to the multiplication operator (*)
or is equivalent to the addition operator (+)

The really significant difference between an arithmetic expression and a Boolean expression is that, in the case of an arithmetic expression it is normally necessary to fully evaluate it to determine the result.  In the case of a Boolean expression, there are many cases/constructions where it isn't necessary to evaluate the entire expression to determine the result.  IOW, in the case of Boolean expressions, partial evaluation is possible to determine the result, which is usually not possible in the case of arithmetic expressions.

As you and others stated, when in doubt, and/or for readability purposes, parentheses should be used.  It's usually a good idea to use them when the expression contains a mix of and(s) and or(s).  It makes the programmer's intention clear and the code logically cleaner.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: lucamar on July 16, 2019, 06:24:57 am
@440bx: That post just won a honor place in my "Important notes" file.  :D
Thanks.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: 440bx on July 16, 2019, 06:34:05 am
@440bx: That post just won a honor place in my "Important notes" file.  :D
Thanks.
My pleasure.  I hope other people find it helpful too.  The equivalences comes directly from Jensen and Wirth's presentation in their Pascal report.  IOW, we both owe them that clear, understandable explanation.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: PascalDragon on July 16, 2019, 09:03:51 am
That's not correct Howard. Hence the bug report against documentation. Pure Boolean operators are equal weight.
(Boole would probably have turned in his grave)
No, Howard is correct. See compiler/tokens.pas:
Code: Pascal  [Select][+][-]
  1.   { sub_expr(opmultiply) is need to get -1 ** 4 to be
  2.     read as - (1**4) and not (-1)**4 PM }
  3.   toperator_precedence=(
  4.     opcompare,
  5.     opaddition,
  6.     opmultiply,
  7.     oppower
  8.   );
  9.  
  10. { snip }
  11.  
  12. operator_levels:array[Toperator_precedence] of set of NOTOKEN..last_operator=
  13.       ([_LT,_LTE,_GT,_GTE,_EQ,_NE,_OP_IN],
  14.        [_PLUS,_MINUS,_OP_OR,_PIPE,_OP_XOR],
  15.        [_CARET,_SYMDIF,_STARSTAR,_STAR,_SLASH,
  16.         _OP_AS,_OP_IS,_OP_AND,_AMPERSAND,_OP_DIV,_OP_MOD,_OP_SHL,_OP_SHR],
  17.        [_STARSTAR] );
  18.  
As you can see _OP_OR is at a different level than _OP_AND.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: SymbolicFrank on July 16, 2019, 04:46:01 pm
4. Term beyond 'and' is always evaluated to find value of full expression, i.e. '... and ...'

I expect the term beyond 'and' only to be evaluated when the first expression is true.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: rnfpc on July 16, 2019, 05:05:47 pm
4. Term beyond 'and' is always evaluated to find value of full expression, i.e. '... and ...'

I expect the term beyond 'and' only to be evaluated when the first expression is true.
Yes, please see my modified list of rules.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: glorfin on July 18, 2019, 03:52:47 pm
The really significant difference between an arithmetic expression and a Boolean expression is that, in the case of an arithmetic expression it is normally necessary to fully evaluate it to determine the result.

Well, generally even for arithmetic it is not always necessary. Consider an expression: a*(b+c) where a = 0.

You don't have to evaluate b+c to know the result. But, while this is true for mathematics, compiler does not know beforehand what is a, hence cannot use this shortcut.
Title: Re: How is "not condition1 and condition2" evaluated?
Post by: 440bx on July 18, 2019, 04:31:30 pm
Well, generally even for arithmetic it is not always necessary. Consider an expression: a*(b+c) where a = 0.
That's correct.  That's why I stated "it is normally necessary...".  In the expression you used, as you pointed out, if the compiler could reliably determine that a = 0 then it wouldn't have to evaluate the expression to know the result will be zero.
TinyPortal © 2005-2018