Computer Science Canada

Are there any (side-effect) languages that guarantee commutative add?
Author:  btiffin [ Sat Aug 06, 2011 3:02 am ]
Post subject:  Are there any (side-effect) languages that guarantee commutative add?
Usually we assume + is commutative.

a + b = b + a

But with languages that support functions with side e, and things like
code:

int
func(int *n)
{
    *n += 1;
     return n;
}

int a = 1;
a + func(&a)  is not equal  to func(&a) + a

The question came up as OpenCOBOL is about to get user defined functions, and pass BY REFERENCE is the default, functions can have side-effects by definition and spec.

Bankers may not like COMPUTE amount = f(a) + b not ALWAYS being equal to COMPUTE amount = b + f(a).

Curious if the board feels that this is entirely "caveat amplificator", developer beware, or is it something worth pestering the good folk working on ISO J4/PL22.4 COBOL 20xx standards about? Non-nerd verifiable computational audits are one of the reasons COBOL runs banks. This seems to lead COBOL away from 'trusted arithmetic', but maybe it's assumed by all and sundry when side effects are possible?

And the original question, aside from purely functional programming, are side effect computations ALWAYS in breach of the trust in commutative arithmetic?

Cheers
Author:  mirhagk [ Sat Aug 06, 2011 8:45 am ]
Post subject:  RE:Are there any (side-effect) languages that guarantee commutative add?
I think this may be an issue for some, however it has always been terrible programming practice to alter a variable on the same line that you use it. For instance the above in C++ might have a+func(&a) == func(&a)+a in some compilers and not equal in others.

The compilers for most languages attempt to optomize code, and a single line of code, while ensuring bedmas, can not be assumed to be run in that specific order (other than if statements).
Author:  Tony [ Sat Aug 06, 2011 1:16 pm ]
Post subject:  RE:Are there any (side-effect) languages that guarantee commutative add?
I think that even Java's spec does not guarantee the order of operation for a chain of additions. This makes compiler writing more flexible (more choices in parsing methods) and allows for more optimizations.
Author:  DemonWasp [ Sat Aug 06, 2011 8:21 pm ]
Post subject:  Re: Are there any (side-effect) languages that guarantee commutative add?
Java's specification is pretty damned specific about the order in which operations must be carried out. See: http://java.sun.com/docs/books/jls/third_edition/html/expressions.html#15.7

However, the guarantee provided can be summarized (sort of, and probably inaccurately) that things happen left-to-right at any given "level" of evaluation. This means that Java does NOT guarantee that a + func(a) == func(a) + a, because, for example:

code:
int a = 1;
System.out.printf ( "%d\n", (a=3) + a );

a = 1;
System.out.printf ( "%d\n", a + (a=3) );


will print:

code:
6
4


In the first case, Java's spec says that it happens as follows:

code:
a = 3;
take value of previous statement (3) as left operand to +
take value stored in 'a' (3) as right operand to +
add, store result as argument[1] for printf()


In the second case, Java says:

code:
take value stored in 'a' (1) as left operand to +
a = 3;
take value of previous statement (3) as right operand to +
add, store result as argument[1] for printf()


This means that although Java's operations are NOT commutative, you can reason about them very easily:

code:

int a = 1;
int b = 2;

int value = a + a++ + ++a + b + (b=2) + (b=3);

System.out.printf ( "value = %d, a = %d, b = %d\n", value, a, b );


Try to figure that out. Then, highlight this to see the answer [ value = 12, a = 3, b = 3 ]
Author:  btiffin [ Sat Aug 06, 2011 8:54 pm ]
Post subject:  Re: Are there any (side-effect) languages that guarantee commutative add?
I've been testing various languages here and I've broken commutative properties with all of them. Not in and of itself a problem usually, caveat amplificator. But COBOL deals with financials in the large, still in production 50 years later BECAUSE is has very few points of developer beware notwithstanding it's '50 years old' and compiler designs have moved on, sometimes even improving.

We are discussing rejecting 'spec' and current 20xx standard in OpenCOBOL FUNCTION-ID support, and just enforcing BY CONTENT call frames and disallowing side effects that have any chance of confusing 'standard arithmetic' or other not the COBOL way side effects with inline functions.

Ok, I made that sound like I'm more involved than I am ... I just get emails from the lead developer and nod my head like I know what's going on every once in a while. Smile

Cheers
Author:  Tony [ Sat Aug 06, 2011 8:59 pm ]
Post subject:  RE:Are there any (side-effect) languages that guarantee commutative add?
Hah, so Java does specify the order. Interesting. It does say not to rely on this part of the spec though:
Quote:

It is recommended that code not rely crucially on this specification.
Author:  DemonWasp [ Sat Aug 06, 2011 11:49 pm ]
Post subject:  Re: RE:Are there any (side-effect) languages that guarantee commutative add?
Tony @ Sat Aug 06, 2011 8:59 pm wrote:
Hah, so Java does specify the order.


Well...sort of. Java specifies in which order operand must be retrieved (and hence, sub-expressions, sub-assignments, method-calls, etc). It does not specify the order of repeated operators at the same precedence level (at least, not that I know of), so for example a + b + c could be (a+b)+c or a+(b+c).

Since it compiles to a stack-based language, and the value for the leftmost operator must be determined first, I expect that the stack would have the rightmost operator on the top and the leftmost towards the bottom. That means that the addition would -- probably, and I'm guessing -- happen as: a + ( b + c ). It should be possible to observe this through examining bytecode. The only place I can see this being important is in floating point math, where 4.0 * ( myFloat / 8.0 ) and ( 4.0 * myFloat ) / 8.0 have radically different results, varying between myFloat / 2.0, becoming -Infinity or +Infinity; Java at least makes it clear that this operation cannot be rewritten as myFloat / 2.0, unless it can be proven at compile-time to always produce the same result.


To address the original question, I'm pretty sure you can break commutativity in any language that allows side effects. If you can assign to the value of a variable, and also reference the value of that variable, then to preserve commutativity, you would have to determine some total ordering for evaluating the value of the operands. That is, you would have to determine a way to "sort" all the operands such that you could calculate the values in a deterministic way. Keep in mind that you can have multiple members with the same name in most languages. This total ordering must remain exactly the same on all possible machines, in all possible environments, etc to prevent a networked application from running afoul of the variation.

Somehow, I doubt that any such total ordering would be very helpful to humans reading the code. Worse, it could (depending on implementation) break expected behaviour:

code:

if ( foo() && bar() ) {
    put "baz"
}


In many languages, that code should first evaluate foo(); only if the result is true must bar() be evaluated. However, there are plenty of possible orderings that would place bar() above foo(), such as alphabetical ordering. You can probably imagine that the ternary operator would be a disaster -- which of these methods get called, assuming the missile is still sitting on the launch pad?

code:

hasMissileArrivedAtTarget() ? detonateNuclearWarhead() : moveTowardsTarget();


Well, if we chose the alphabetical ordering, then we called detonateNuclearWarhead() first.

The completely unambiguous, universally agreed-upon method of writing this code is unwieldy and verbose (and is required when writing safety-critical systems, as for nuclear missiles, but probably not the FooBar application):
code:

if ( foo() ) {
    if ( bar() ) {
        put "baz"
    }
}

if ( hasMissileArrivedAtTarget() ) {
    detonateNuclearWarhead();
} else {
    moveTowardsTarget();
}
Author:  btiffin [ Sun Aug 07, 2011 11:24 pm ]
Post subject:  Re: Are there any (side-effect) languages that guarantee commutative add?
Ok, next question.

Would you 'pay' more for a open implementation of a language that guaranteed commutative properties or allowed BY REFERENCE modification of function arguments?

I'm voting we keep OpenCOBOL, BY CONTENT (a reference to a copy of the argument) which helps guarantee arithmetic (and other sanities) but does close some coding avenues.
It'll make things like FUNCTION inc(A) unfeasible aside from usage like COMPUTE A = FUNCTION inc(A), which kinda defeats the purpose of in place increment. COBOL has always had CALL with BY REFERENCE argument modification but those calls are procedural and not in-line like User Defined Functions will be.

Opinions?

Keep in mind that COBOL is usually targeted at money people and management more than hip coders. (Umm, of course I'm hard at work trying to change that view, but the view is there nonetheless and is a strength of a 50 year old language design.)

====
By the way DemonWasp. I first guessed value = 11. The real answer confused me a little bit as I ran out of counting fingers so it took two reads through. Wink

But ... along with this thread, should a bank run code like that?
====

Cheers
Author:  Tony [ Sun Aug 07, 2011 11:45 pm ]
Post subject:  RE:Are there any (side-effect) languages that guarantee commutative add?
"by content" will not actually make any of those guarantees, as a pointer can be passed "by content", and have the destination modified by the function.
Author:  DemonWasp [ Mon Aug 08, 2011 7:37 am ]
Post subject:  Re: Are there any (side-effect) languages that guarantee commutative add?
As Tony pointed out, it's a little bit more involved to ensure that function(A) doesn't have side effects. If another term in the expression is a reference to an instance variable (not sure what that is in COBOL), and function(A) changes that value, it can be unclear which value is used -- the original, or the modified value. That is, this is always implicitly passed by reference. Alternatively, global scope is always available, even if discouraged.

Of course, nobody writing banking software or missile-control software should ever be writing statements like these. The key is making it easy to avoid doing it by accident, and preventing function arguments from being modified is one step in that direction. Alternatively, if it is clear that the function call intends to modify those values from reading the call (not the declaration), it might be acceptable.

I would go so far as to say that almost no professional programmer should ever write a line like that. I just thought it was neat that it was fully specified what value it should return.

As far as verification goes, I'm sure that banking people can handle order of operations being a little different than pen-and-paper math, as long as it is thoroughly specified. Perhaps a training course is in order.


btiffin @ Sun Aug 07, 2011 11:24 pm wrote:
...I first guessed value = 11. The real answer confused me a little bit ... it took two reads through. Wink


Your confusion illustrates my point. Even though Java specifies exactly what value that expression should have, it can be difficult to reason about. Obviously, this kind of code should not make it past code review, but preventing it at the language level is going to prevent you from doing something useful somewhere else. And, if you're going to allow it, you really should specify exactly what it does (I'm glaring at C and C++ here).

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy