Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 1335] ファイルの概要

このコミットは、Go言語の初期の仕様書である doc/go_spec.txt に変更を加えています。具体的には、Go言語における整数型のオーバーフロー挙動と、その機械表現に関する記述を明確化し、以前のTODO項目を解消することを目的としています。Go言語の設計思想において、未定義動作を極力排除し、予測可能な挙動を保証するための重要な一歩です。

コミット

closing a TODO:
- define integer overflow as wrap-around
- be more specific about machine representation

DELTA=54  (34 added, 7 deleted, 13 changed)
OCL=20870
CL=21070

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/9dfb2ea7af3b8a580c0281776f4881995d9d82a4

元コミット内容

このコミットは、Go言語の仕様書 doc/go_spec.txt の内容を更新し、特に以下のTODO項目を解消しています。

  • 整数オーバーフローの挙動をラップアラウンドとして定義すること。
  • 機械表現についてより具体的に記述すること。

これにより、Go言語の整数演算の挙動がより明確になり、プログラマが予測可能なコードを書けるようになります。

変更の背景

Go言語は、その設計初期段階から「シンプルさ」「安全性」「効率性」を重視していました。特に、C言語などで問題となりがちだった「未定義動作 (Undefined Behavior)」を極力排除し、言語の挙動を明確に定義することが重要な目標の一つでした。

このコミットが行われた2008年12月時点では、Go言語の仕様はまだ策定途上にあり、多くの設計上の決定がなされていました。その中で、整数演算におけるオーバーフローの挙動は、プログラムの安全性と移植性に直結する重要な課題でした。以前の仕様では、整数オーバーフローが発生した場合の挙動が「未定義」とされており、これはコンパイラが予期せぬ最適化を行ったり、異なる環境で異なる結果を生じたりする可能性をはらんでいました。

このコミットは、この「未定義動作」を解消し、Go言語の整数演算が常に予測可能な挙動を示すように、仕様を明確化することを目的としています。特に、符号なし整数についてはラップアラウンドを保証し、符号付き整数についても決定論的な挙動を定義することで、プログラマが安心してコードを書ける基盤を築いています。

前提知識の解説

Go言語の仕様書 (doc/go_spec.txt)

Go言語の仕様書は、言語の構文、セマンティクス、標準ライブラリの挙動などを公式に定義するドキュメントです。Go言語のコンパイラやツールは、この仕様書に基づいて実装されます。このコミットが対象としている doc/go_spec.txt は、Go言語の初期の仕様書であり、言語の根幹をなす部分の定義が行われていました。

整数オーバーフロー (Integer Overflow)

コンピュータの整数型は、有限のビット数で数値を表現します。例えば、8ビットの符号なし整数 (uint8) は0から255までの値を表現できます。この最大値を超えて加算を行ったり、最小値を下回って減算を行ったりすると、表現可能な範囲を超えてしまいます。この現象を「オーバーフロー」と呼びます。

  • 符号なし整数 (Unsigned Integers): 負の値を表現せず、0以上の値のみを扱います。オーバーフローした場合、通常は「ラップアラウンド (Wrap-around)」と呼ばれる挙動を示します。例えば、uint8で255に1を加えると0に戻ります。これはモジュロ演算 (modulo 2^n) と同じ挙動です。
  • 符号付き整数 (Signed Integers): 正の値と負の値を扱います。通常、最上位ビットを符号ビットとして使用し、負の数は「2の補数表現 (Two's Complement)」で表現されます。符号付き整数のオーバーフローは、未定義動作となる言語も多く、予測が難しい場合があります。

2の補数表現 (Two's Complement)

コンピュータで負の整数を表現する最も一般的な方法です。ある数値 x の2の補数は、x のビットを反転させ（1の補数）、それに1を加えることで得られます。この表現の利点は、加算器が符号なし整数と符号付き整数の両方で同じように機能し、減算も加算として扱える点にあります。

未定義動作 (Undefined Behavior)

プログラミング言語の仕様において、特定の状況下でのプログラムの挙動が定義されていない状態を指します。未定義動作が発生すると、プログラムは予期せぬ結果を生じたり、クラッシュしたり、セキュリティ上の脆弱性を引き起こしたりする可能性があります。Go言語は、C/C++などの言語で頻繁に発生する未定義動作を極力排除する設計思想を持っています。

技術的詳細

このコミットは、Go言語の整数演算におけるオーバーフローの挙動を、以下の点で明確に定義しています。

  1. 整数型の具体的な範囲の明記: doc/go_spec.txt の「Numeric types」セクションにおいて、uint8, uint16, uint32, uint64 および int8, int16, int32, int64 の各型が表現できる具体的な数値範囲が追記されました。これにより、各型の容量がより明確になりました。

    • uint8: 0 to 255
    • int8: -128 to 127
    • ...など

  2. 整数表現の明確化: 整数型が「通常のバイナリ形式で表現され、nビット整数はnビット幅である」こと、および「負の符号付き整数は2の補数で表現される」ことが明記されました。これは、Go言語が特定のハードウェアアーキテクチャに依存せず、標準的な整数表現を採用していることを示しています。

  3. 整数オーバーフローの挙動の定義: これがこのコミットの最も重要な変更点です。新たに「Integer overflow」というセクションが追加され、以下の挙動が定義されました。

    • 符号なし整数 (Unsigned Integers): +, -, *, << の各演算は、その符号なし整数型のビット幅 n に対して「モジュロ 2^n」で計算されます。これは、オーバーフロー時に上位ビットが破棄され、値がラップアラウンドする（例: 255 + 1 = 0）ことを意味します。Goのプログラムは、このラップアラウンド挙動に依存してコードを書くことが許容されます。

    • 符号付き整数 (Signed Integers): +, -, *, << の各演算は、合法的にオーバーフローする可能性があります。しかし、その結果の値は、符号付き整数の表現（2の補数）、演算、およびオペランドによって「決定論的に定義される」とされています。重要なのは、オーバーフローの結果として「例外は発生しない」という点です。 この定義は、コンパイラが「オーバーフローが発生しない」という仮定に基づいて最適化を行うことを禁止しています。例えば、「x < x + 1 が常に真である」という仮定は、符号付き整数のオーバーフロー時には成り立たないため、コンパイラはこの仮定に基づく最適化を行ってはならないと明記されています。これは、C/C++などで未定義動作が原因で発生する予期せぬ最適化挙動をGoが回避するための重要な設計判断です。

  4. 未定義動作に関する記述の削除: 以前の仕様にあった「例外的な条件（結果が数学的に定義されていない、または表現可能な値の範囲外である場合）が発生した場合、挙動は未定義である。例えば、整数のアンダーフローやオーバーフローの挙動は定義されていない。」という記述が削除されました。これは、今回のコミットで整数オーバーフローの挙動が明確に定義されたため、この記述が不要になったことを示しています。

  5. シフト演算子と単項演算子の明確化: シフト演算子 (<<, >>) について、「x << 1 は x*2 と同じ」、「x >> 1 は x/2 を負の無限大に切り捨てたものと同じ」という具体的な説明が追加されました。 単項演算子 (+, -, ^) についても、特に ^x (ビットごとの補数) が m ^ x (ここで m はすべてのビットが1に設定された値) と定義されることが明確化されました。

これらの変更により、Go言語の整数演算は、その挙動が完全に予測可能となり、プログラマはより安全で堅牢なコードを記述できるようになりました。

コアとなるコードの変更箇所

このコミットの主要な変更は、doc/go_spec.txt ファイルに集中しています。

  1. TODO項目の削除と完了マークの追加:

    --- a/doc/go_spec.txt
+++ b/doc/go_spec.txt
@@ -41,8 +41,6 @@ Todo's:
 [ ] need to talk about precise int/floats clearly
 [ ] iant suggests to use abstract/precise int for len(), cap() - good idea
     (issue: what happens in len() + const - what is the type?)
-[ ] need to be specific on (unsigned) integer operations: one must be able
-	to rely on wrap-around on overflow
 [ ] what are the permissible ranges for the indices in slices? The spec
  	doesn't correspond to the implementation. The spec is wrong when it
  	comes to the first index i: it should allow (at least) the range 0 <= i <= len(a).
@@ -95,6 +93,8 @@ Decisions in need of integration into the doc:


 Closed:
+[x] need to be specific on (unsigned) integer operations: one must be able
+	to rely on wrap-around on overflow
 [x] global var decls: "var a, b, c int = 0, 0, 0" is ok, but "var a, b, c = 0, 0, 0" is not
  	(seems inconsistent with "var a = 0", and ":=" notation)
 [x] const decls: "const a, b = 1, 2" is not allowed - why not? Should be symmetric to vars.

    [ ] need to be specific on (unsigned) integer operations: one must be able to rely on wrap-around on overflow というTODO項目が削除され、Closed: セクションに [x] 付きで追加されました。

  2. 目次への「Integer overflow」の追加:

    --- a/doc/go_spec.txt
+++ b/doc/go_spec.txt
@@ -182,6 +182,7 @@ Contents

 		Operators
 			Arithmetic operators
+			Integer overflow
 			Comparison operators
 			Logical operators
 			Address operators

    「Arithmetic operators」の下に「Integer overflow」が追加されました。

  3. 整数型の具体的な範囲の追加:

    --- a/doc/go_spec.txt
+++ b/doc/go_spec.txt
@@ -986,20 +987,32 @@ The following list enumerates all platform-independent numeric types:

 	byte     same as uint8 (for convenience)

-	uint8    the set of all unsigned 8-bit integers
-	uint16   the set of all unsigned 16-bit integers
-	uint32   the set of all unsigned 32-bit integers
-	uint64   the set of all unsigned 64-bit integers
+	uint8    the set of all unsigned  8-bit integers (0 to 255)
+	uint16   the set of all unsigned 16-bit integers (0 to 65535)
+	uint32   the set of all unsigned 32-bit integers (0 to 4294967295)
+	uint64   the set of all unsigned 64-bit integers (0 to 18446744073709551615)

-	int8     the set of all signed 8-bit integers, in 2's complement
-	int16    the set of all signed 16-bit integers, in 2's complement
-	int32    the set of all signed 32-bit integers, in 2's complement
-	int64    the set of all signed 64-bit integers, in 2's complement
+	int8     the set of all signed  8-bit integers (-128 to 127)
+	int16    the set of all signed 16-bit integers (-32768 to 32767)
+	int32    the set of all signed 32-bit integers (-2147483648 to 2147483647)
+	int64    the set of all signed 64-bit integers (-9223372036854775808 to 9223372036854775807)

 	float32  the set of all valid IEEE-754 32-bit floating point numbers
 	float64  the set of all valid IEEE-754 64-bit floating point numbers
 	float80  the set of all valid IEEE-754 80-bit floating point numbers

+Integer types are represented in the usual binary format; the value of
+an n-bit integer is n bits wide. A negative signed integer is represented
+as the two's complement of its absolute value.
+
+<!--
+The representation of signed integers and their exact range is
+implementation-specific, but the set of all positive values (including zero)
+of a signed integer type is always a subset of the corresponding unsigned
+integer type (thus, a positive signed integer can always be converted into
+its corresponding unsigned type without loss).
+-->
+
 Additionally, Go declares a set of platform-specific numeric types for
 convenience:

    各整数型の定義に、具体的な数値範囲が括弧書きで追加されました。また、整数が通常のバイナリ形式で表現され、負の符号付き整数が2の補数で表現されることが追記されました。

  4. 未定義動作に関する記述の削除:

    --- a/doc/go_spec.txt
+++ b/doc/go_spec.txt
@@ -1592,11 +1605,6 @@ c is an ideal number? Is len(a) of type int, or of an ideal number? Probably
 should be ideal number, because for fixed arrays, it is a constant.\n -->

-If an exceptional condition occurs during the evaluation of an expression
-(that is, if the result is not mathematically defined or not in the range
-of representable values for its type), the behavior is undefined. For
-instance, the behavior of integer under- or overflow is not defined.\n
-
 Operands
 ----\n

    整数オーバーフローの挙動が未定義であるという記述が完全に削除されました。

  5. 整数オーバーフローの挙動の定義と演算子の明確化:

    --- a/doc/go_spec.txt
+++ b/doc/go_spec.txt
@@ -2129,12 +2137,31 @@ right operand. They implement arithmetic shifts if the left operand is a signed
 integer, and logical shifts if it is an unsigned integer. The shift count must
 be an unsigned integer. There is no upper limit on the shift count. It is
 as if the left operand is shifted "n" times by 1 for a shift count of "n".
+Specifically, "x << 1" is the same as "x*2"; and "x >> 1" is the same as
+"x/2 truncated towards negative infinity".

-The unary operators "+", "-", and "^" are defined as follows:
+For integer operands, the unary operators "+", "-", and "^" are defined as
+follows:

 	+x                          is 0 + x
 	-x    negation              is 0 - x
-	^x    bitwise complement    is -1 ^ x
+	^x    bitwise complement    is m ^ x  with m = "all bits set to 1"
+
+
+Integer overflow
+----
+
+For unsigned integer values, the operations "+", "-", "*", and "<<" are
+computed modulo 2^n, where n is the bit width of the unsigned integer type
+(§Arithmetic types). Loosely speaking, these unsigned integer operations
+discard high bits upon overflow, and programs may rely on ``wrap around''.
+
+For signed integers, the operations "+", "-", "*", and "<<" may legally
+overflow and the resulting value exists and is deterministically defined
+by the signed integer representation, the operation, and its operands.
+No exception is raised as a result of overflow. As a consequence, a
+compiler may not optimize code under the assumption that overflow does
+not occur. For instance, it may not assume that "x < x + 1" is always true.

 Comparison operators

    シフト演算子と単項演算子の定義がより具体的になり、そして最も重要な「Integer overflow」セクションが追加されました。このセクションで、符号なし整数と符号付き整数のオーバーフロー挙動が詳細に定義されています。

コアとなるコードの解説

このコミットの核となる変更は、Go言語の仕様書に整数オーバーフローの挙動を明示的に定義した点です。

  • 整数型の範囲の明確化: 各整数型が表現できる具体的な数値範囲を仕様書に記載することで、プログラマは各型の限界を正確に把握できるようになりました。これは、オーバーフローの可能性を考慮したコード設計の基礎となります。
  • 符号なし整数のラップアラウンド保証: 符号なし整数に対する加算、減算、乗算、左シフト (<<) が「モジュロ 2^n」で計算されることが明記されました。これにより、オーバーフローが発生した場合に値がラップアラウンドすることが保証され、プログラマはこの挙動を前提としたロジックを安全に実装できます。例えば、ハッシュ計算やビットマスク操作などでこの特性を利用できます。
  • 符号付き整数の決定論的オーバーフロー: 符号付き整数についても、同様の演算でオーバーフローが発生しうるものの、その結果は「決定論的に定義される」とされました。これは、C/C++のようにオーバーフローが未定義動作となることで、コンパイラが予期せぬ最適化を行ったり、異なる環境で異なる結果を生じたりする問題を回避するためのGoの重要な設計判断です。Goでは、オーバーフローしても例外は発生せず、2の補数表現に基づいた予測可能な結果が得られます。
  • コンパイラ最適化の制約: 「コンパイラはオーバーフローが発生しないという仮定に基づいてコードを最適化してはならない」という記述は非常に重要です。これにより、例えば x < x + 1 のような一見自明な条件式が、符号付き整数のオーバーフロー時には偽になる可能性があるため、コンパイラがこの事実を無視して最適化を行うことを防ぎます。これは、Goが未定義動作を排除し、予測可能な実行を保証するための具体的なメカニズムです。

これらの変更は、Go言語が「シンプルで安全、かつ予測可能な言語」であるという設計哲学を具現化する上で不可欠なものでした。

関連リンク

参考にした情報源リンク

  • Go言語の公式ドキュメントおよび仕様書
  • 整数オーバーフロー、ラップアラウンド、2の補数表現に関する一般的なコンピュータサイエンスの知識
  • C/C++における未定義動作と最適化に関する情報
  • GitHubのコミット履歴と差分表示
  • Robert Griesemer氏のGo言語における貢献に関する情報