Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: go 2: reduce unspecified behaviors of expression evaluation orders in multi-value assignments #27804

Open
go101 opened this issue Sep 21, 2018 · 23 comments

Comments

@go101
Copy link

commented Sep 21, 2018

(As this proposal is rejected, I change it as a Go 2 proposal instead.)

One feature of Go is multi-value assignments support. However, currently, the rules of the expression orders in one multi-value assignment are very not specified, which causes many ambiguities in practice. Please read this and this for details.

As a so called C+ language, one of the main goals of Go is to remove as many unspecified behaviors in C as possible, in particular for the unspecified behaviors which may be common encountered. So here I propose Go 2 should specify more on the expression orders in one multi-value assignment.

Currently, Go specification specifies:

At package level, initialization dependencies determine the evaluation order of individual initialization expressions in variable declarations. Otherwise, when evaluating the operands of an expression, assignment, or return statement, all function calls, method calls, and communication operations are evaluated in lexical left-to-right order.

By the rule, the following program must print 1 and 2 for y and z,
but the print result for x might be 0, 1 or 2. The standard Go compiler prints x as 2,
which is counterintuitive for most programmers.

package main

func main() {
	a, b := 0, 0
	f := func() int {
		a++
		b++
		return b
	}
	
	x, y, z := a, f(), f()
	println(x, y, z)
}

If we (or the compiler) rewrite the last multi-value assignment in the above example as

	x, y, z := func() int{return a}(), f(), f()

Then the print result should be 0 1 2 for sure. In other words, there are not any technical obstacles to evaluate expressions in a multi-value assignment by the from-left-to-right rule . The reason of why Go specification doesn't adopt this more specified rule might be related to code optimization consideration.

The bold line is my proposal.

[edit: the following content is moved to a new issue: https://github.com//issues/27821]

@gopherbot gopherbot added this to the Proposal milestone Sep 21, 2018

@gopherbot gopherbot added the Proposal label Sep 21, 2018

@ALTree ALTree added the Go2 label Sep 21, 2018

@go101

This comment has been minimized.

Copy link
Author

commented Sep 22, 2018

In fact, at least for the second rule modification, it is not essential to be "Go 2".

@go101 go101 changed the title proposal: go 2: reduce ambiguities of expression evaluation orders in multi-value assignments proposal: go 2: reduce unspecified behaviors of expression evaluation orders in multi-value assignments Sep 23, 2018

@go101

This comment has been minimized.

Copy link
Author

commented Sep 23, 2018

I separated the second part into a new issue: #27821

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Sep 24, 2018

The question is how much freedom the compiler should have to move code around.

Personally I'm comfortable with saying that if a single statement writes to a variable other than directly assigning to it, that the order of that write is explicitly unspecified with regard to any reads of the variable in the same statement. I think we can write a vet check for this--not a 100% accurate vet check, but one that catches cases like the above. I don't see this case as important in practice, as regardless of the rule that the language adopts this is confusing code, and there is never a reason to write code this way. I'm fine with a vet check that discourages confusing code.

@go101

This comment has been minimized.

Copy link
Author

commented Sep 26, 2018

The vet version proposal has been rejected, which is why this issue was created.

..., and there is never a reason to write code this way.

Yes, it should be viewed as a logic mistake when such code is written. But there are so many variations of such code that sometimes such mistakes are easy to make and hard to detect.

@bcmills

This comment has been minimized.

Copy link
Member

commented Sep 26, 2018

It seems like the root of the issue is that parts of the statement do not “happen before” other parts (according to the spec).

We normally use the race detector to flag operations that produce reads and writes without a happens-before relation. Could the race detector diagnose these issues too?

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Sep 26, 2018

Thanks for the pointer to #27098, I forgot about that. In that issue @alandonovan makes a similar comment to what @bcmills says.

I don't really agree that these mistakes are easy to make. Every example I see seems to me to be very convoluted. In particular, note that on your wiki page https://github.com/go101/go101/wiki/An-ambiguity-of-(or-dispute-on)-the-evaluation-order-of-LHS-(left-hand-side)-items-in-a-multi-value-assignment , which has examples that I agree are less convoluted, tip gccgo now behaves like gc for all your examples. That is, the difference between gccgo and gc really was a bug, although it took me a while to understand that; see #23188 (comment) and https://golang.org/cl/123155 .

@go101

This comment has been minimized.

Copy link
Author

commented Sep 26, 2018

@ianlancetaylor

... tip gccgo now behaves like gc for all your examples. That is, the difference between gccgo and gc really was a bug, ...

It looks you muddled the current issue and my another recent create issue: #27821. It is great that gccgo and gc will begin to agree on how the left items in a multi-value assignment should be evaluated.

The current proposal is to reduce expression evaluation orders in all the expressions in a multi-value assignment, including both left and right items (the corresponding wiki page is https://github.com/go101/go101/wiki/Some-evaluation-orders-in-multi-value-assignments-are-unspecified). In fact, I agree with @alandonovan on that the effort to implement the check in vet for such bad use cases may be not worth it. Maybe it is a good chance for me to write a special program to find such bad use cases, as I always want to practice on how to use the go.* standard packages.

I just don't know how large the impact is if the proposal is adopted.

@bcmills
I think the terminology “happen before” is used in concurrent programming, however the problem mentioned in the current issue is for a solo goroutine. So I think this is race detector unrelated.

@alandonovan

This comment has been minimized.

Copy link
Contributor

commented Sep 26, 2018

@go101 If you're willing to experiment, please try the dynamic analysis too (see #27821). I'd love to see what results it turns up.

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Sep 26, 2018

@go101 I don't think I muddled the issues. This issue starts with an explicit reference to two different wiki pages. I said that the statements in one of those references are no longer applicable.

I pointed that out as part of a larger claim: the kinds of code that would be fixed by addressing this issue are complex and convoluted. I am arguing that it doesn't really matter if you get implementation-defined behavior for complex and convoluted code. Fixing the order of evaluation to be exact for such code would hurt performance for all code while only helping with the kind of code that nobody actually writes.

In order to be convincing, I think you need to show some real code that people have written that accidentally and implicitly rely on the kind of order of evaluation that this issue is discussing.

@go101

This comment has been minimized.

Copy link
Author

commented Sep 26, 2018

@ianlancetaylor

This issue starts with an explicit reference to two different wiki pages.

I'm sorry, I forgot to remove one of them when splitting the original issue into two. I removed the second wiki page ref now.

@alandonovan
Aha, I don't have a concept on what is "dynamic analysis". I will google and study it. :)

@alandonovan

This comment has been minimized.

Copy link
Contributor

commented Sep 26, 2018

A static analysis is one that scrutinizes the source text of the program. A dynamic analysis is anything that runs the program (or a modified version of it): testing, the race detector, fuzzing, profiling, debugging, coverage, etc. Some tools combine static and dynamic elements: go test statically looks for TestABC functions and emits Go source files, then builds and runs them; go test -cover statically transforms the program to increment counters as it goes, then runs the modified version. Combined static/dynamic tools are generally called "dynamic" because the execution of the program typically dominates execution time, and carries the usual security implications.

The dynamic analysis I was referring to was the idea of statically transforming the program a[i] = f(x) to to save a and i before executing f(x) and then assert that they have not changed prior to executing the assignment.

@go101

This comment has been minimized.

Copy link
Author

commented Sep 27, 2018

Okay, got it. Thanks for explanation.

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Oct 16, 2018

One argument in favor of the current approach, which is to let the compiler decide the order of some operations, is that a statement like

x, y, z := a, f(), f()

is deliberately leaving the ordering to the compiler. If you want to specify the ordering, you should use separate statements.

@deanveloper

This comment has been minimized.

Copy link

commented Oct 30, 2018

@ianlancetaylor

A statement like ... is deliberately leaving the ordering to the compiler.

Humans (in English) read from left-to-right. If there is a list of expressions, I'd naturally expect them to be evaluated from left to right.

Every example I see seems to me to be very convoluted

Okay how about this one:
https://play.golang.org/p/fsMc91mDj1R

@alandonovan

This comment has been minimized.

Copy link
Contributor

commented Oct 30, 2018

I don't think anyone disputes that left-to-right evaluation order is natural and desirable, as it is the usual way to read Go---forget about English. The problem is that it is expensive to implement, or at least, has long been regarded as prohibitively expensive even for languages like Scheme that generally choose clarity and simplicity over raw performance. It would be interesting to measure the speed impact of constraining the execution order on some real Go programs, and if the conventional wisdom is not longer true, perhaps we could specify the evaluation order.

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Oct 30, 2018

Okay how about this one:

Personally I'm going to regard any single statement that both uses a variable and sets a variable, other than by putting it on the left-hand-side of an assignment, to be convoluted. Maybe it's just me.

@synth0

This comment has been minimized.

Copy link

commented Nov 30, 2018

@alandonovan why is it prohibitively expensive to implement left-to-right evaluation? Do you have any data/material you could link to?

I'm genuinely curious.

The example @deanveloper posted seems like an easy-to-make mistake.
There should at least be a vet rule for this.

@alandonovan

This comment has been minimized.

Copy link
Contributor

commented Nov 30, 2018

I don't have evidence, hence my weaselly choice of words ("has long been regarded as prohibitively expensive"). https://stackoverflow.com/questions/12540418/why-is-the-order-of-evaluation-for-function-parameters-unspecified-in-c gives a theoretical micro example of the flavor of the problem. This paper http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0145r3.pdf argues for changing C++ to specify left-to-right ordering. It claims effects on the order of 4% on the Spec benchmarks, but curiously both positive and negative. If even the C++ community is arguing for it, perhaps this is an idea whose time has come.

@bcmills

This comment has been minimized.

Copy link
Member

commented Nov 30, 2018

@ianlancetaylor

Personally I'm going to regard any single statement that both uses a variable and sets a variable, other than by putting it on the left-hand-side of an assignment, to be convoluted.

I agree, but it still seems inconsistent with the rest of the language: the rest of the Go spec biases toward (over-)specifying behaviors that I would also describe as “convoluted”. For example, NaN map entries and integer overflow don't panic, and even run-time operations that do panic are defined as recoverable control flow rather than program errors.

I agree with the sentiment that users shouldn't write convoluted code, but it seems strange to me that we should produce unspecified behavior for this particular convolution when we specify so many others.

@alandonovan

This comment has been minimized.

Copy link
Contributor

commented Nov 30, 2018

it seems strange to me that we should produce unspecified behavior for this particular convolution when we specify so many others.

I agree. If the reason was always "performance", we can measure whether that reason remains valid: it should be easy to benchmark the effect of a stronger spec by simply adding more memory ordering edges to the SSA representation.

@randall77

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Nov 30, 2018

@bcmills I see the examples you cite as significantly different. I'm not arguing that both setting and using a variable in the same statement should panic or should be undefined behavior. I'm saying that the behavior is well defined but unspecified, just as calling fmt.Println from two concurrently goroutines can print the lines in either order, but can't do any random thing.

That said, I'm fine with fully specifying the order of expression evaluation. I've always been fine with it. I was just pointing out one of the arguments in favor of the current situation.

@randall77

This comment has been minimized.

Copy link
Contributor

commented Nov 30, 2018

I agree that performance isn't a compelling motivation to leave the ordering unspecified. It would be nice to have data, though.

It should only matter in cases in which the spec is ambiguous about the ordering. And we've already asserted that writing such code is a bad idea anyway. And if performance is an issue, you can always rewrite your code to avoid the performance problem.

That said, I worry about cases like this:

var x int
func f() int {
    return x + g()
}

If we evaluate left-to-right, we need to load from x, spill it, call g, restore our spill, then do the add. The current compiler will call g first, then read x, eliminating the need for a spill.
It's only ambiguous in the case when g modifies x, which might be rare. But the compiler doesn't know that g does not modify x.

Does anyone have a specific proposal for the change in language spec? Maybe something like this would be good:

...when evaluating the operands of an expression, assignment, or return statement, all function calls, method calls, and communication operations are evaluated in lexical left-to-right order. After those operations have completed, all remaining expressions are evaluated in left-to-right order

The two-pass nature of this hopefully avoids the need for spills, by doing all spill-generating operations up front. (Some ops not in this list, like map operations and some type casts, also require spills because they call into the runtime. Oh well.)

We'd also presumably need some text about evaluating left-hand sides of assignments.

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Dec 1, 2018

I would be concerned that a two pass algorithm just makes things more complicated. I think if we're going to pin it down we should be as simple as possible: each expression is evaluated in order from left to right, inner to outer, subject to operator precedence and associativity. If there is a performance hit, take the hit.

I think that is approximately what Java does: http://web.deu.edu.tr/doc/oreily/java/langref/ch04_14.htm .

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
9 participants
You can’t perform that action at this time.