Recent

Author Topic: How is "not condition1 and condition2" evaluated?  (Read 2805 times)

lucamar

  • Hero Member
  • *****
  • Posts: 2020
Re: How is "not condition1 and condition2" evaluated?
« Reply #30 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)
Turbo Pascal 3 CP/M - Amstrad PCW 8256 (512 KB !!!) :P
Lazarus 2.0.2/2.0.4  - FPC 3.0.4 on:
(K|L)Ubuntu 12..16, Windows XP SP3, various DOSes.

ASerge

  • Hero Member
  • *****
  • Posts: 1408
Re: How is "not condition1 and condition2" evaluated?
« Reply #31 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?

lucamar

  • Hero Member
  • *****
  • Posts: 2020
Re: How is "not condition1 and condition2" evaluated?
« Reply #32 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.
Turbo Pascal 3 CP/M - Amstrad PCW 8256 (512 KB !!!) :P
Lazarus 2.0.2/2.0.4  - FPC 3.0.4 on:
(K|L)Ubuntu 12..16, Windows XP SP3, various DOSes.

ASerge

  • Hero Member
  • *****
  • Posts: 1408
Re: How is "not condition1 and condition2" evaluated?
« Reply #33 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.

BrunoK

  • Full Member
  • ***
  • Posts: 181
  • Retired programmer
Re: How is "not condition1 and condition2" evaluated?
« Reply #34 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);
Lazarus trunk r. 59978/03.01.2019 (+/- patches regarding enabled, TScrollBar, TCursorImage). FPC 3.0.4 32 bits. (+heaptrc with leaked ClassName+Revisited TList) , Windows 10 Pro x64 (v. 1903)

lucamar

  • Hero Member
  • *****
  • Posts: 2020
Re: How is "not condition1 and condition2" evaluated?
« Reply #35 on: July 14, 2019, 10:30:30 pm »
Fact is it explicitely warns against this in the language reference:
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;
« Last Edit: July 14, 2019, 10:37:52 pm by lucamar »
Turbo Pascal 3 CP/M - Amstrad PCW 8256 (512 KB !!!) :P
Lazarus 2.0.2/2.0.4  - FPC 3.0.4 on:
(K|L)Ubuntu 12..16, Windows XP SP3, various DOSes.

BrunoK

  • Full Member
  • ***
  • Posts: 181
  • Retired programmer
Re: How is "not condition1 and condition2" evaluated?
« Reply #36 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.
Lazarus trunk r. 59978/03.01.2019 (+/- patches regarding enabled, TScrollBar, TCursorImage). FPC 3.0.4 32 bits. (+heaptrc with leaked ClassName+Revisited TList) , Windows 10 Pro x64 (v. 1903)

Kays

  • Full Member
  • ***
  • Posts: 182
  • Whasup!?
    • KaiBurghardt.de
Re: How is "not condition1 and condition2" evaluated?
« Reply #37 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: “[…] operators of the same precedence shall be left associative.” Wirth originally stated (PDF page 24): “Sequences of operators of the same precedence are executed left to right.”
« Last Edit: July 15, 2019, 01:19:20 am by Kays »
Yours Sincerely
Kai Burghardt

Peter H

  • Jr. Member
  • **
  • Posts: 57
Re: How is "not condition1 and condition2" evaluated?
« Reply #38 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.


« Last Edit: July 15, 2019, 12:05:25 am by Peter H »

rnfpc

  • Jr. Member
  • **
  • Posts: 91
Re: How is "not condition1 and condition2" evaluated?
« Reply #39 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
« Last Edit: July 15, 2019, 05:15:41 am by rnfpc »

Thaddy

  • Hero Member
  • *****
  • Posts: 8928
Re: How is "not condition1 and condition2" evaluated?
« Reply #40 on: July 15, 2019, 09:36:29 am »
That's the same order I wrote....
Most people that want to use threading should learn to patch their jeans first: use a needle.

howardpc

  • Hero Member
  • *****
  • Posts: 3150
Re: How is "not condition1 and condition2" evaluated?
« Reply #41 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:
  • operator
  • operand
  • left parenthesis
  • right parenthesis
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
  • Level 1: "and"
  • Level 2: "or", "xor"
  • Level 3: comparison operators ("=", "<>", ">", ">=" etc.)
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 ...

Thaddy

  • Hero Member
  • *****
  • Posts: 8928
Re: How is "not condition1 and condition2" evaluated?
« Reply #42 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)
« Last Edit: July 15, 2019, 11:59:20 am by Thaddy »
Most people that want to use threading should learn to patch their jeans first: use a needle.

wp

  • Hero Member
  • *****
  • Posts: 6234
Re: How is "not condition1 and condition2" evaluated?
« Reply #43 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.
Lazarus trunk / fpc 3.0.4 / all 32-bit on Win-10

440bx

  • Hero Member
  • *****
  • Posts: 1129
Re: How is "not condition1 and condition2" evaluated?
« Reply #44 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.
« Last Edit: July 15, 2019, 12:47:07 pm by 440bx »
using FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.