Does Go have `undefined behaviour` ?

[Dave Cheney]

In reading about C/C++ and its compilers, a common complaint is the
liberal use of the words `undefined behavior ` in the relevant
specifications. The concept of undefined behavior is simultaneously
reviled by those debugging C/C++ applications, and very important to
optimizing compiler writers. Some references even claim that this term
is overused in the current specifications, implying that the authors
were somewhat lax in their job.

The term `undefined behavior` or even `undefined` appears nowhere in
the Go spec (either 1.0 or tip), which I interpret to be a good thing.

My questions are:

* does the lack of documented undefined behavior improve the safety of
Go as a language (assuming a conforming compiler and runtime) ?

* what trade offs, possibly in performance, or compiler speed or
design, were necessary to avoid undefined behavior in Go programs ?

Cheers

Dave

[Rémy Oudompheng]

The conversion of float64 to uint8 has undefined behaviour for values
outside (0, 255) and is a frequent source of annoyance.

Rémy.

2013/1/23, Dave Cheney <da...@cheney.net>:

> --
>
>
>

[Dan Kortschak]

In the section, Order of evaluation there is an item that is undefined (not specified).

Order of evaluation

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.

For example, in the assignment

y[f()], ok = g(h(), i()+x[j()], <-c), k()

the function calls and communication happen in the order f(), h(), i(), j(), <-c, g(), and k(). However, the order of those events compared to the evaluation and indexing of x and the evaluation of y is not specified.

a := 1
f := func() int { a = 2; return 3 }
x := []int{a, f()}  // x may be [1, 3] or [2, 3]: evaluation order between a and f() is not specified

Floating-point operations within a single expression are evaluated according to the associativity of the operators. Explicit parentheses affect the evaluation by overriding the default associativity. In the expression x + (y + z) the addition y + z is performed before adding x.

Also, I was justing reading a bug report today that showed that the temporal position of range checking is not defined [1].

[1] http://code.google.com/p/go/issues/detail?id=4627

Apologies for html. Not at desk.

Dan

--

[Donovan Hide]

The term `undefined behavior` or even `undefined` appears nowhere in
the Go spec (either 1.0 or tip), which I interpret to be a good thing.

It's not undefined, but it is arguably "loosely" defined:

http://golang.org/ref/spec#Select_statements

If multiple cases can proceed, a uniform pseudo-random choice is made to decide which single communication will execute.

Full disclosure of the pseudo-random algorithm would remove "uncertainty" :-)

[Dave Cheney]

>> If multiple cases can proceed, a uniform pseudo-random choice is made to
>> decide which single communication will execute.
>
>
> Full disclosure of the pseudo-random algorithm would remove "uncertainty"

I thought that was the idea. If people can predict the behavior, they
will write code that assumes it. Maps deliberately randomise iteration
order to enforce this concept.

[Donovan Hide]

I thought that was the idea. If people can predict the behavior, they
will write code that assumes it. Maps deliberately randomise iteration
order to enforce this concept.

Good point. I suppose this highlights the need for a SortedMap and PrioritySelect in the standard library for people like me who want non-random behaviour :-)

[Daniel Morsing]

On Wed, Jan 23, 2013 at 11:00 AM, Dave Cheney <da...@cheney.net> wrote:
> In reading about C/C++ and its compilers, a common complaint is the
> liberal use of the words `undefined behavior ` in the relevant
> specifications. The concept of undefined behavior is simultaneously
> reviled by those debugging C/C++ applications, and very important to
> optimizing compiler writers. Some references even claim that this term
> is overused in the current specifications, implying that the authors
> were somewhat lax in their job.
>
> The term `undefined behavior` or even `undefined` appears nowhere in
> the Go spec (either 1.0 or tip), which I interpret to be a good thing.
>
> My questions are:
>
> * does the lack of documented undefined behavior improve the safety of
> Go as a language (assuming a conforming compiler and runtime) ?

Somewhat. Even though a C implementation can choose any behavior when
it encounters a NULL dereference, one that causes demons to fly out of
your nose instead of crashing would probably not be very widely used.
Most of the places where go defines behavior that is undefined in C,
it defines it to what you'd expect a reasonable C implementation to
do.

>
> * what trade offs, possibly in performance, or compiler speed or
> design, were necessary to avoid undefined behavior in Go programs ?

The biggest one is probably the range check on indexes. For index
heavy programs, that can hurt performance quite a bit.

>
> Cheers
>
> Dave
>
> --
>
>

[Ian Lance Taylor]

On Wed, Jan 23, 2013 at 2:19 AM, Rémy Oudompheng
<remyoud...@gmail.com> wrote:
> The conversion of float64 to uint8 has undefined behaviour for values
> outside (0, 255) and is a frequent source of annoyance.

In standardese "undefined behaviour" is a term of art. It explicitly
means that if the undefined part of the program is executed, anything
at all may happen. What that means in practice is that the compiler
may transform a program that uses undefined behaviour into something
completely unexpected and in fact unpredictable. It's difficult to
overemphasize how strange this can get. For example, this function in
C
int f(int x) { return 0x7ffffff0 < x && x + 32 < 0x7fffffff; }
while seemingly meaningful, relies on the specific behaviour of signed
overflow, which is undefined in C/C++. GCC will compile this into a
function that always returns 0. For a more exotic example, while I
don't have a complete function on hand, I've seen cases where "if (x)
A; else B;" were compiled to execute neither A nor B when x was a C++
bool variable that held a value other than true or false. That kind
of thing seems impossible to non-compiler writers.

Anyhow, all that is simply to say that the conversion of float64 to
uint8 in Go is not undefined behaviour. It is implementation defined
behaviour, which is very different and much more controlled.
Implementation defined behaviour means that the program always behaves
normally, but the specific value that you get may differ in different
implementations. That is not the same as undefined behaviour where
quite literally anything can happen.

Go has much less undefined behaviour than C/C++. That is a deliberate
choice. Pretty much all cases that are undefined in C/C++ are fully
specified or implementation defined in Go. However, Go does have
undefined behaviour: if your program has a race condition, the
behaviour is undefined. If you have a race condition you can see
inconsistent and seemingly impossible states in your program.

Ian

> 2013/1/23, Dave Cheney <da...@cheney.net>:
>> In reading about C/C++ and its compilers, a common complaint is the
>> liberal use of the words `undefined behavior ` in the relevant
>> specifications. The concept of undefined behavior is simultaneously
>> reviled by those debugging C/C++ applications, and very important to
>> optimizing compiler writers. Some references even claim that this term
>> is overused in the current specifications, implying that the authors
>> were somewhat lax in their job.
>>
>> The term `undefined behavior` or even `undefined` appears nowhere in
>> the Go spec (either 1.0 or tip), which I interpret to be a good thing.
>>
>> My questions are:
>>
>> * does the lack of documented undefined behavior improve the safety of
>> Go as a language (assuming a conforming compiler and runtime) ?
>>
>> * what trade offs, possibly in performance, or compiler speed or
>> design, were necessary to avoid undefined behavior in Go programs ?
>>
>> Cheers
>>
>> Dave
>>
>> --
>>
>>
>>
>

> --
>
>

[Ian Lance Taylor]

On Wed, Jan 23, 2013 at 2:21 AM, Dan Kortschak
<dan.ko...@adelaide.edu.au> wrote:
> In the section, Order of evaluation there is an item that is undefined (not
> specified).

This again is, in standardese, implementation defined, not undefined.

Ian

[Ian Lance Taylor]

On Wed, Jan 23, 2013 at 2:00 AM, Dave Cheney <da...@cheney.net> wrote:
>
> * what trade offs, possibly in performance, or compiler speed or
> design, were necessary to avoid undefined behavior in Go programs ?

The ones that come to mind are:

* Signed integers wrap on overflow, which reduces the scope of loop
optimizations.

* Out of bounds accesses on arrays panic in a controlled way,
requiring explicit runtime checks.

* Nil pointer references panic in a controlled way, requiring explicit
nil pointer checks in some cases, such as when dereferencing a pointer
to a very large struct.

* Signed integer division of the minimum integer by -1 is well
defined, requiring explicit checks on x86 to avoid a processor
exception.

* Shifts by large values are well defined, requiring runtime checks on
the shift amount.

Ian

[wenpeng]

I just get a `undefined behavior' in godoc in 

pkg/container/ring  :

func (r *Ring) Do(f func(interface{}))

Do calls function f on each element of the ring, in forward order. The behavior of Do is undefined if f changes *r.

[Dan Kortschak]

Thanks, Ian. Yes Dave corrected my misunderstanding off-list.

In the world of real numbers this is the difference between 1/0 and 0/0.

Dan

[Dave Cheney]

Thanks Ian. Those replies are very useful and helped me clarify my thoughts on the subject.