Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!ut-sally!utah-cs!donn
From: donn@utah-cs.UUCP (Donn Seeley)
Newsgroups: net.lang.c
Subject: Re: Expression sequencing query
Message-ID: <3926@utah-cs.UUCP>
Date: Thu, 25-Sep-86 11:44:26 EDT
Article-I.D.: utah-cs.3926
Posted: Thu Sep 25 11:44:26 1986
Date-Received: Thu, 25-Sep-86 18:48:51 EDT
References: <760@oakhill.UUCP> <111@titan.UUCP> <353@cullvax.UUCP> <111@unido.UUCP> <8200006@ztivax.UUCP>
Organization: University of Utah CS Dept
Lines: 44

I sure thought that someone would finally read the manual and see where
the 'problem' was, but I guess I was wrong...  Section 7 of the C
reference manual:  '... [T]he order of evaluation of expressions is
undefined,' except in specific cases: '&&', '||', ',' and '?'.  These
cases together with the precedence rules define a partial ordering on
evaluations.  Let's look at an example:

	a = ((b=1),b) + ((b=2),b) + ((b=3),b)
	  1    2  3   4    5  6   7    8  9

I've numbered the operators in the expression to indicate the
subexpressions.  Here is the transitive closure of the set of ordered
pairs which defines the partial ordering:

 <2,1>  <2,4>  <3,4>  <5,1>  <5,6>  <6,1>  <6,7>  <8,1>  <8,9>  <9,7>
 <2,3>  <3,1>  <4,1>  <5,4>  <5,7>  <6,4>  <7,1>  <8,7>  <9,1>

(Notice that '[e]xpressions involving a commutative and associative
operator ... may be rearranged arbitrarily', which actually reduces the
number of orderings -- <4,7> isn't in the set for this reason.) Notice
that <2,5>, <2,8> and <5,8> are not in the set; the expressions 2, 5,
and 8 ('b=1', 'b=2' and 'b=3') may be evaluated in any order.  Thus 'a'
may have any value between 3 and 9, inclusive, after this statement is
executed.

Actually my favorite order-of-evaluation bug appeared in some poor
user's code to add an array of N ints:

	int array[N] = { ... };
	int *R = &array[0];
	int sum = *R++ + *R++ + *R++ + *R++ + *R++ + ... + *R++;

This worked (believe it...  or not!) with the Ritchie compiler on
the PDP11 and failed miserably under the PCC on a VAX.

Wondering what code Lattice C generated to get a == 7,

Donn Seeley    University of Utah CS Dept    donn@utah-cs.arpa
40 46' 6"N 111 50' 34"W    (801) 581-5668    decvax!utah-cs!donn

PS -- I suppose you've noticed that I've oversimplified the treatment
of 4 and 7 in the example, since the commutative/associative rule
causes an ambiguity (e.g. 3 must be done before one of 4 or 7, since
3 may be reordered under 7 in the expression tree)...