[comp.lang.c] C problem, order of evaluation

null@diku.dk (Niels Ull Jacobsen) (04/09/90)

0Q

7#
Hello world!
I'm having a slight problem.
I need to make an expression of the type:

"( stack[++sp]= exp , stack[sp -= N])", where exp contains N "stack[++sp]"'s.

The expression is supposed to have the value of the right side of the
assignment, and to push this on the stack as well. The expression is to be a
part of a function argument, and can therefore not contain any local block
declarations.

I have the traditional problem of order of evaluation. The above construct 
will only work, if the lval is evaluated before the right side.
Unfortunately, this is NOT guaranteed. I can make a construct, which will
work, if the right side is evaluated first, and I can even make a construct,
which will work, if I know that the order of evaluation for two assignments
is always the same. However, even this is not guaranteed by an optimizing
compiler.

The construct, which would work if the order was homogenous:

"(stack[++sp]=exp, stack[sp -= N] = stack[sp])".

What I want to avoid is:

"(stack[++sp]=MARK, stack[sp]=exp,
  stack[sp -= N] == MARK ? stack[sp]=stack[sp+N]:stack[sp])"

, where MARK is a value, that exp cannot evaluate to. 

I also want to avoid introducing "global" temporary variables, as exp can it
self contain expressions of this type. I can not just use
stack[sp+1],...,stack[sp+N] in exp, as this will do bad things for my
garbage collection.


Does anyone have a smart solution for this problem?

In case you're interested, this is to be a part of the code generated by a
(subset of)Scheme to C compiler, that I'm writing. The final compiler will
be a part of an automated compiler generation system, using partial
evaluation.

                        Niels Ull Jacobsen,
                        Inst. of Datalogy, U of Copenhagen,
                        null@diku.dk
                        (Speaking from the void ..)


-- 
               Niels Ull Jacobsen, Inst. of Datalogy, U of Copenhagen.
               null@diku.dk
               (Speaking from the void ..)

ckp@grebyn.com (Checkpoint Technologies) (04/10/90)

In article <1990Apr8.185047.7385@diku.dk> null@diku.dk (Niels Ull Jacobsen) writes:
>I need to make an expression of the type:
>
>"( stack[++sp]= exp , stack[sp -= N])", where exp contains N "stack[++sp]"'s.
>
>The expression is supposed to have the value of the right side of the
>assignment, and to push this on the stack as well. The expression is to be a
>part of a function argument, and can therefore not contain any local block
>declarations.

As long as that comma is really the comma *operator* and not the
function argument separator, then the order of evaluation of your
subexpressions *is* guaranteed.  The left expression is evaluated first,
the comma declares a sequence point (which means that all side effects
are completed), and then the right hand side is evaluated, which becomes
the result of the whole expression.  The order is defined in both K&R C
and ANSI C.

Now, if your comma really is a function argument separator, then the
order of evaluation is not guaranteed, and your concerns are justified.
If your two subexpressions are supplying two parameters to a single
function call then you're screwed.  There's no way to make them evaluate
left-to-right in all cases, and in fact it's common to evaluate function
arguments right-to-left, because on many machines that's the order in
which they are pushed onto the stack as they become function arguments.

This seems to be a commonly misunderstood thing.  There are a few
operators whose order of evaluation *is* guaranteed, and the comma
operator is one of them.  Others are && and ||, these are always
performed left to right with a sequence point in between. There may be
others I don't remember right now. Oh, yes, the "conditional" operator ?
: is guaranteed left to right (sort of); the condition expression is
evaluated first, then a sequence point is declared, then one
of the subexpressions is evaluated but not the other.

ckp@grebyn.com (Checkpoint Technologies) (04/10/90)

In article <19539@grebyn.com> ckp@grebyn.UUCP (Checkpoint Technologies) writes:
>In article <1990Apr8.185047.7385@diku.dk> null@diku.dk (Niels Ull Jacobsen) writes:
>>I need to make an expression of the type:
>>
>>"( stack[++sp]= exp , stack[sp -= N])", where exp contains N "stack[++sp]"'s.
>>
>>The expression is supposed to have the value of the right side of the
>>assignment, and to push this on the stack as well. The expression is to be a
>>part of a function argument, and can therefore not contain any local block
>>declarations.
>
> [ then I talk about the comma operator, completely missing the point ]

OOPS - I misread the question.  Well, what I said about comma is true,
even if you weren't asking about it...

Well, then, you're using ++sp many times in the same expression it
seems, once on the left side ("stack[++sp] = ..."  and several times on
the right. This is not gonna work.  But I do have a suggestion.

I presume you're building a stack machine, such that a stack operator
takes several stack arguments, pops them, and writes one stack result
in their place.  Try doing it this way:

( sp += N, stack[sp] = exp)

where exp contains several instances of stack[sp-C],
   where each C is a negative offset to the argument you wish.

Now this expression exp contains no side effects and therefore it's
order of evaluation is unimportant.  The stack 'pop' operation is
performed first.  The value of this expression will be the value stored
into the 'result' stack location, which is what you wanted, and it's why
I put the stack pointer modify operation first.

karl@haddock.ima.isc.com (Karl Heuer) (04/10/90)

In article <19539@grebyn.com> ckp@grebyn.UUCP (Checkpoint Technologies) writes:
>In article <1990Apr8.185047.7385@diku.dk> null@diku.dk (Niels Ull Jacobsen) writes:
>>"( stack[++sp]= exp , stack[sp -= N])", where exp contains N "stack[++sp]"'s.
>
>As long as that comma is really the comma *operator* and not the
>function argument separator, then the order of evaluation of your
>subexpressions *is* guaranteed....

I think the problem was with the multiple references to `sp' on the left side
of the comma.  Niels: am I correct in assuming that
	(stack[++sp] = stack[++sp] + stack[++sp], stack[sp -= 2])
is an example of the generated code?

My recommendation is to force your translator to generate code like
	(++sp, stack[sp] = stack[sp+1] + stack[sp+2])
instead.  That's the only way to be sure that the compiler knows what you're
talking about.

Karl W. Z. Heuer (karl@ima.ima.isc.com or harvard!ima!karl), The Walking Lint

null@rimfaxe.diku.dk (Niels Ull Jacobsen) (04/11/90)

karl@haddock.ima.isc.com (Karl Heuer) writes:

>In article <1990Apr8.185047.7385@diku.dk> null@diku.dk (Niels Ull Jacobsen) writes:
>>I need to make an expression of the type:
>>
>>"( stack[++sp]= exp , stack[sp -= N])", where exp contains N "stack[++sp]"'s.
>>
>>The expression is supposed to have the value of the right side of the
>>assignment, and to push this on the stack as well. The expression is to be a
>>part of a function argument, and can therefore not contain any local block
>>declarations.


>I think the problem was with the multiple references to `sp' on the left side
>of the comma.  Niels: am I correct in assuming that
>	(stack[++sp] = stack[++sp] + stack[++sp], stack[sp -= 2])
>is an example of the generated code?

>My recommendation is to force your translator to generate code like
>	(++sp, stack[sp] = stack[sp+1] + stack[sp+2])
>instead.  That's the only way to be sure that the compiler knows what you're
>talking about.

Thank you, but your assumption is wrong. I am not making a stack machine, so
the arguments will not be on the stack. The exp could itself contain
expressions of this type. I could have an expression like :

      (stack[++sp] = g((stack[++sp] = make_cons(x,y), stack[sp -= 0]),
                       (stack[++sp] = make_cons(x,z), stack[sp -= 0])),
       stack[sp -= 2])

The stack is actually only used to keep track of the cons-cells for the garbage collection.

>Karl W. Z. Heuer (karl@ima.ima.isc.com or harvard!ima!karl), The Walking Lint

In article <19539@grebyn.com> ckp@grebyn.UUCP (Checkpoint Technologies) writes:

>Well, then, you're using ++sp many times in the same expression it
>seems, once on the left side ("stack[++sp] = ..."  and several times on
>the right. This is not gonna work.  But I do have a suggestion.

>I presume you're building a stack machine, such that a stack operator
>takes several stack arguments, pops them, and writes one stack result
>in their place.  Try doing it this way:

>( sp += N, stack[sp] = exp)

>where exp contains several instances of stack[sp-C],
>   where each C is a negative offset to the argument you wish.

Thank you, but that won't work either, see above.

               Niels Ull Jacobsen, Inst. of Datalogy, U of Copenhagen.
               null@diku.dk
               (Speaking from the void ..)

diamond@tkou02.enet.dec.com (diamond@tkovoa) (04/11/90)

In article <1990Apr10.195822.14808@diku.dk> null@rimfaxe.diku.dk (Niels Ull Jacobsen) writes:

>      (stack[++sp] = g((stack[++sp] = make_cons(x,y), stack[sp -= 0]),
>                       (stack[++sp] = make_cons(x,z), stack[sp -= 0])),
>       stack[sp -= 2])

My stack just overflowed.  Let's try color coding.

>      (stack[++sp] = g((stack[++sp] = make_cons(x,y), stack[sp -= 0]),
        black brown      RRed  red                   orange           yellow

>                       (stack[++sp] = make_cons(x,z), stack[sp -= 0])),
                         GGrn  green                 blue              violet

>       stack[sp -= 2])
        gray     white

OK.
The red side effect (updating sp) must be completed before the orange comma's
sequence point.
The green side effect must be completed before the blue sequence point.
However, the yellow comma is not an operator and is not a sequence point.
Therefore green,red,orange,blue is a legal evaluation order.  (And many others.)
In fact, RRed and GGrn may be the same element of stack.

The brown side effect must be completed before the violet sequence point.
However, this may occur before, after, or intermixed with red, green, etc.

Gray and white are safe.  They leave the correct value in sp, and they fetch
the correct element of stack.  However, the correct element of stack might
not have been the target in assigning to black.

You asked for a fix to black, brown, gray, and white.  It might be possible.
However, red and green cannot be fixed.  You have to hack your expression
generator.

Now I'm going color-blind.

-- 
Norman Diamond, Nihon DEC     diamond@tkou02.enet.dec.com
This_blank_intentionally_left_underlined________________________________________

ckp@grebyn.com (Checkpoint Technologies) (04/11/90)

In article <1990Apr10.195822.14808@diku.dk> null@rimfaxe.diku.dk (Niels Ull Jacobsen) writes:
>
>      (stack[++sp] = g((stack[++sp] = make_cons(x,y), stack[sp -= 0]),
>                       (stack[++sp] = make_cons(x,z), stack[sp -= 0])),
>       stack[sp -= 2])
>
>The stack is actually only used to keep track of the cons-cells for
>the garbage collection.

Hmm... Sticky.  Something else to note is that a function call declares
a sequence point, therefore side effects are completed.  I see you're
calling g() above, so any (single) sp++ in the function arguments is
guaranteed to be done before the function call .. but there's no
relation between that and the calculation of the lvalue of the result
from the function call, so this may not help.

Hopefully your compiler will see that "sp -= 0" is a non-operation and
not generate any subtraction.  Philosophical question: is this still a
side effect?  Since this was generated from a preprocessor I assume that
0 may be a non-zero value in some cases, in which case...

Unfortunately I don't think I see an answer without temporary variables
and separate statements.