[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: XML design of ((a and b) or c)

• From: Rick Marshall <rjm@z...>
• To: Ken North <kennorth@s...>
• Date: Fri, 15 Dec 2006 16:45:23 +1100

Hi Ken

The point here is quite subtle and VERY important.

Let's just take "a AND b" or "a & b" to reduce the overloading of the 
word and.

Now if a and b are atomic and & is commutative the the order of 
evaluation is unimportant and optimisers can play around to suit themselves.

However, if a or b are not atomic and the calculation of either has side 
effects then "a & b" is no longer commutative and optimisers cannot stop 
the calculation on detection of a or b being false.

Unless of course we agree to use slightly different mathematics: "a & b" 
is not commutative; it is evaluated left to right; and evaluation stops 
if a is false. This can then be extended to "a & b & c ...".

Now the "a & b" of computer languages is fundamentally different to the 
"a & b" of mathematics although they degenerate to the same thing if a 
and b are atomic.

The order of processing of elements in XML is therefore important if XML 
is to be used to represent computing structures as opposed to 
mathematical structures. If XML didn't preserve the order of evaluation 
then the XML would have to be first used to model a stack and that 
vocabulary used to model the mathematics.

Fortunately documents are even more sensitive to order of evaluation so 
that isn't a problem - order of elements must be preserved (but not 
attributes ;) )

However the other side effect is also interesting and important - the 
ability to not evaluate something once a condition has been determined 
(or  indeed force evaluation). At the moment I believe XSLT is required 
for that.

Rick

Ken North wrote:
> Leigh Klotz wrote:
>> the question here is whether the evaluation of AND
>> and OR stopped once the value became determined,
>> or whether they evaluated all arguments.  If evaluation
>> stops, then AND and OR can be used as
>> control constructs.
>
> Whether the language was COBOL, FORTRAN, Algol, C or other compiled 
> languages, it eventually ended up as executable instructions. The 
> heart of the matter is the order of execution.
>
> If our pseudo-code is IF ((a AND b) OR c) ...
> then you'd see instructions something like this:
>
>        L       R7, a                 ; load a into register 7
>        L        R8, b
>        AND  R7, R8
>        BNZ  20$                   ; if true
>         TST  c                       ; test the c bits
>         BNZ  20$
> 10$:
>          ...
>          ...
> 20$:  ...
>
> 2. Now assume you used an optimizing compiler and the pseudo-code was:
>
> IF ((a AND b AND c AND d) OR e)
>
> It would put the e test first:
>
>         TST  e                       ; test the e bits
>         BNZ  20$                   ; if true
>        L       R7, a                 ; load a into register 7
>        L        R8, b
>        ...   and so on
>
> 3. Now assume the pseudo-code is IF ((a AND b) XOR c) ...
> Because it's an exclusive OR, you need to test both sides because it's 
> true when only one side is true.
>
>
>
>
>
> ======== Ken North ===========
> www.WebServicesSummit.com
> www.SQLSummit.com
> www.GridSummit.com
>
>
> _______________________________________________________________________
>
> XML-DEV is a publicly archived, unmoderated list hosted by OASIS
> to support XML implementation and development. To minimize
> spam in the archives, you must subscribe before posting.
>
> [Un]Subscribe/change address: http://www.oasis-open.org/mlmanage/
> Or unsubscribe: xml-dev-unsubscribe@l...
> subscribe: xml-dev-subscribe@l...
> List archive: http://lists.xml.org/archives/xml-dev/
> List Guidelines: http://www.oasis-open.org/maillists/guidelines.php
>

• Follow-Ups:
  • RE: XML design of ((a and b) or c)
    • From: "Michael Kay" <mike@s...>
  • Re: XML design of ((a and b) or c)
    • From: Tei <oscar.vives@g...>

• References:
  • RE: XML design of ((a and b) or c)
    • From: "Klotz, Leigh" <Leigh.Klotz@x...>
  • Re: XML design of ((a and b) or c)
    • From: "Ken North" <kennorth@s...>