Go の仕様を K Framework で書いたら、Go コンパイラのバグが 2 つ見つかった話

Go の仕様を K Framework で書いたら、Go コンパイラのバグが 2 つ見つかった話

はじめに

こんにちは、koheです。

Go のコンパイラ(gc)のバグを 2 つ報告し、どちらも修正されました。

  • golang/go#81696:make の長さと容量の引数が、逆の順番で評価される
  • golang/go#81697:for i, _ := range *p だけが、nil で panic する

見つけたのは、Go の executable semantics(言語の意味を、実際にプログラムを動かせる形で定義したもの)を K Framework で書き、仕様から作ったテストを Go と突き合わせている途中でした。

この研究の前半は、国際会議 SEKE 2026 で論文として発表し、Best Paper Award の 2 位をいただきました。2 つのバグは、そのあとも研究を続けるなかで見つけたものです。

この記事では、まず 2 つのバグをクイズで見てもらいます。そのあと、K Framework、Go を K で書くこと、SEKE の論文、バグを見つけた流れ、バグの中身の順に書きます。

クイズ:このプログラムは何を出力する?

問題 1

f は、引数を表示してそのまま返す関数です。最後に、作った slice の長さと容量を表示します。

Go
package main

func f(x int) int { print(x); return x }

func main() {
	s := make([]int, f(1), f(3))
	print(len(s), cap(s))
}

問題 2

p は nil の array pointer です。A と B の違いは , _ だけです。

Go
// A
var p *[3]int
for i := range *p {
	print(i)
}
Go
// B
var p *[3]int
for i, _ := range *p {
	print(i)
}

答え

手元の Go 1.27.3 で実行した結果です。

仕様どおりなら

Go 1.27.3

問題 1

1313(f(1) → f(3) の順に呼ばれる)

3113(f(3) が先に呼ばれる)

問題 2 の A

012

012

問題 2 の B

012

nil pointer dereference で panic

※ print は標準エラーに出力します。問題 1 は、インライン化を止める -gcflags=-l を付けると 1313 になります。

どちらも、仕様に照らすと Go の動きのほうが間違っていました。なぜそう言えるのかは、後半で説明します。

K Framework とは

K Framework は、プログラミング言語の semantics を rewrite rule で定義するためのフレームワークです。定義を書くと、その言語のインタプリタとして実際にプログラムを動かせます。C、Java、JavaScript、Python、Ethereum の EVM などの semantics が K で書かれています。

書くものは、大きく 3 つです。

書くもの

中身

syntax

言語の文法。BNF に近い書き方で書く

configuration

実行中の状態。次に実行する計算(<k>)、メモリ、スレッドなどを cell の入れ子で表す

rule

rewrite rule。「状態がこの形なら、こう書き換わる」

定義を kompile でコンパイルすると、krun でその言語のプログラムを動かせます。同じ定義から、状態の探索や証明の道具も使えます。

いちばん簡単な例:足し算と掛け算だけの言語

整数の足し算と掛け算だけができる言語を、K で書いてみます。ファイルは calc.k の 1 つだけです。

k
module CALC-SYNTAX
  imports INT-SYNTAX

  syntax Exp ::= Int
               | "(" Exp ")"    [bracket]
               > Exp "*" Exp    [left, seqstrict]
               > Exp "+" Exp    [left, seqstrict]
endmodule

module CALC
  imports CALC-SYNTAX
  imports INT

  syntax KResult ::= Int

  configuration <k> $PGM:Exp </k>

  rule I1:Int * I2:Int => I1 *Int I2
  rule I1:Int + I2:Int => I1 +Int I2
endmodule

1 + 2 * 3 と書いたファイル sample.calc を用意して、動かします。

Bash
kompile calc.k
krun sample.calc
<k>
  7 ~> .K
</k>

<k> cell に 7 だけが残りました。~> は「そのあとで」、.K は「空」の意味で、計算が 7 で終わったことを表しています。

上の定義に書いたのは、次のことだけです。

  • syntax:式は、整数か、* か、+。> は優先順位(* が先にまとまる)、left は左結合
  • configuration:<k> cell が 1 つ。$PGM に、読み込んだプログラムが入る
  • rule:両側が整数になった * と + を、整数の計算(*Int、+Int)の結果に書き換える
  • seqstrict:引数を左から順に評価してから、rule を使う。KResult ::= Int で、「整数はもう評価済み」と教えている

krun --depth N を使うと、N 回書き換えたところで止めて、途中の状態を見られます。

書き換えた回数

<k> の中身

0

1 + 2 * 3

1

2 * 3 ~> 1 + □

2

6 ~> 1 + □

3

1 + 6

4

7

※ □ は、計算した値を戻す穴です。実際の出力では #freezer_+_... という形で表示されます。

+ の左は 1 で、もう評価済みです。そこで、右の 2 * 3 を先に取り出して 6 にし、穴に戻してから、足し算の rule で 7 にしています。この「引数を左から順に評価する」を宣言しているのが seqstrict です。あとで出てくる Go の make の定義にも、同じものを使っています。

※ K 7.1.313(公式の Docker イメージ)で動かして確かめました。

Go の semantics の rule

Go の semantics の rule も、形は同じです。論文に載せた rule を 1 つ見てみます。unbuffered channel で、送信と、すでに待っている受信が出会ったときの rule です(論文用に簡略化したものです)。

k
rule <thread> ...
       <k> chanSend(CId, V) => .K ... </k>
     ... </thread>
     <channels> ...
       CId |->
         chanState(S,
                   ListItem(RecvTid)
                   RecvRest,
                   R)
         => chanState(S, RecvRest, R)
     ... </channels>
     <thread> ...
       <tid> RecvTid </tid>
       <k> waitingRecv(CId) => V ... </k>
     ... </thread>

電卓の例と違って、cell がいくつも出てきます。この 1 つの rule で、次の 3 つが同時に起きます。

  • 送信側のスレッド:chanSend(CId, V) を終える(.K は「何も残らない」)
  • channel:待っている受信者の列から RecvTid を外す
  • 受信側のスレッド:待ち(waitingRecv)が、受け取った値 V に変わる

Go の仕様が文章で書いている「送信と受信がそろったときに通信が起きる」を、状態の書き換えとしてそのまま書けます。

Go を K で書く

K で書いた Go の semantics は、0xkohe/go-semantics-k で公開しています。

状態の持ち方

goroutine ごとの thread cell と、共有のメモリ、関数、channel の cell

goroutine ごとに <thread> cell を 1 つ持ち、その中に、次に実行する計算、変数の環境、型の環境、defer のスタックを入れました。メモリ、関数の定義、channel の状態は、すべてのスレッドで共有します。

スレッドは順序のない集まりとして持つので、どのスレッドが次に進むかは決めていません。goroutine の実行順が決まらないことを、そのまま表しています。

仕様の 1 文を、rule 1 つにする

書くときは、仕様の文と rule がなるべく 1 対 1 で対応するようにしました。今回の 2 つのバグに関係する部分を見てみます。

1 つ目は for range です。仕様には「最後の iteration variable が _ なら、それを省いたのと同じ」とあります。これを、そのまま rewrite rule にしています。

k
rule <k> for ((I:Id , Blank:Id , .IdentifierList) := range E:Exp) B:Block
      => for ((I , .IdentifierList) := range E) B ... </k>
  requires Id2String(Blank) ==String "_" [priority(30)]

for i, _ := range E を、for i := range E に書き換える rule です。書き換えたあとは、「iteration variable が 1 つで、長さが定数なら、range expression を評価しない」という別の rule が使われます。

k
rule <k> for ((I:Id , .IdentifierList) := range E:Exp) B:Block
      => enterScope(I := 0 ~> rangeIntLoop(I, 0, rangeConstantLength(E, TE, TD), int, B)) ... </k>
     <tenv> TE </tenv> <typeDefEnv> TD </typeDefEnv>
  requires notBool isKResult(E) andBool rangeConstantLength(E, TE, TD) >=Int 0

型から長さ(rangeConstantLength)だけを求め、E そのものは評価せずに 0 から 長さ - 1 まで回します。

2 つ目は make の構文です。

k
syntax Exp ::= "make" "(" SliceType "," Exp ")"           [seqstrict(2)]
             | "make" "(" SliceType "," Exp "," Exp ")"   [seqstrict(2,3)]

seqstrict(2,3) は、「2 番目と 3 番目の引数を、左から順に評価してから先に進む」という指定です。長さを先に、容量を後に評価します。

どちらも、rule としては当たり前のことしか書いていません。ただ、K で書くとこの当たり前がそのまま動くので、実装との差がはっきり出ます。

※ 上の 3 つは、Issue に書いたスナップショット(ba97042)の range-collection.k と collection.k から引用しました。

SEKE 2026 で発表した論文

この研究の前半は、SEKE 2026(The 38th International Conference on Software Engineering and Knowledge Engineering)で発表しました。2026 年 10 月に、カナダのトロントでの現地開催とオンライン開催を組み合わせて開かれた国際会議です。論文は、トロントの会場で発表しました。

論文の中身

対象は、Go のうち並行処理を中心にしたサブセットです。

区分

含むもの

中心

goroutine、channel(buffered / unbuffered、close、nil channel)、select、defer / panic / recover、closure

支える機能

pointer、interface、method、struct

対象外

複数の package、generics、string の完全な semantics など

Go を K で書いた先行研究には、Zhao らの K-Go があり、言語のより広い範囲を扱っています。この論文では、select の細かい動きと、defer / panic / recover に重点を置きました。

検証には、specification-anchored differential testing を使いました。同じプログラムを 2 つの実装で動かして比べる differential testing を、仕様の文に紐づけて行うものです。

その後の研究:テストを広げて、食い違いを見つける

論文のあとも研究を続け、semantics の範囲を広げました。整数の型、string、名前付きの slice 型などです。あわせて、仕様から作ったテストを約 900 件(Issue に書いたスナップショットの時点で 897 件)に増やし、Go のソースに入っている公式のテスト(test/ ディレクトリ)の一部も、K で動かすようにしました。

differential testing の流れ。公式テストで K の不足を見つけ、仕様を読んでテストを足し、Go と K で動かして比べる。食い違ったら仕様に戻って判断する

流れは次のとおりです。

  1. 公式のテストや既存のテストで、K の足りないところを見つける
  2. 関係する仕様を読み、K の rule と、境界の条件を確かめるテストを足す
  3. 同じプログラムを Go と K で動かし、食い違いを見つける
  4. 仕様に戻って、どちらが正しいかを判断する
  5. Go 側を疑うときは、Go だけで対照の実験をする

報告の直前に全体を動かしたときの内訳はこうでした。

結果

件数

一致

707

一部だけ一致

23

K が未対応

163

判断がついていない

2

Go 側の動きが仕様と違う

2

最後の 2 件が、今回のバグです。

食い違いが出たときに気をつけたのは、Go も K も正解とみなさないことです。Go は比べる相手であって、正しさの基準ではありません。基準はあくまで仕様の文です。食い違いのほとんどは K 側の誤りか未対応で、それは K を直します。仕様を読み直しても Go の動きが説明できないときだけ、Go 側を疑います。

※ ランダムなプログラムを大量に作る fuzzing や、K の証明の機能で見つけたわけではありません。仕様の読み取りと、テストの条件選びは手で行っています。

バグ 1:make の長さと容量が、逆の順番で評価される(#81696)

見つけた経緯

名前付きの slice 型(type S []int)に対応する作業で、make について次のことを確かめるテストを足しました。

  • 長さと容量の扱い
  • 引数を評価する回数
  • 引数を評価する順番

そのうちの 1 つがこれです。

Go
package main

type S []int

func f(x int) int { print(x); return x }

func main() {
	s := make(S, f(1), f(3))
	print(len(s))
	print(cap(s))
}

Go は 3113、K は 1313 を出しました。最後の 13 は長さと容量なので、違うのは先頭の 2 文字、つまり f(1) と f(3) が呼ばれる順番です。

正直に書くと、最初は K が間違っていると思っていました。テストの期待値を書くときに Go の出力 3113 をそのまま写していて、K がそれに合わないので、K を直すつもりでいました。

仕様の評価順の節を読み直して、考えが変わりました。

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, receive operations, and binary logical operations are evaluated in lexical left-to-right order.

— The Go Programming Language Specification - Order of evaluation

関数の呼び出しは、書いた順(左から右)に評価されます。make の引数だからといって、この規則から外れるとは書かれていません。f(1) が先で、K の 1313 が正しいことになります。

Go だけで確かめる

Go 側を疑うので、K を使わずに Go だけで確かめました。Go 1.26.8、1.27.1、開発版(devel)の 3 つで、コンパイルのフラグを変えて動かした結果です。

ビルドの設定

結果

既定

f(3) が先

-gcflags=-N(最適化なし)

f(3) が先

-gcflags=-l(インライン化なし)

正しい順番

-gcflags='-N -l'

正しい順番

3 つのバージョンで同じ結果でした。

インライン化(inlining)は、関数の呼び出しを、その関数の本体で置き換える最適化です。gc は小さな関数を自動でインライン化します。たとえば f(3) は、print(3) をしてから 3 を使う、という形に展開されます。呼び出しのコストがなくなるうえ、展開した先でさらに最適化できるようになります。-gcflags=-l を付けるとインライン化が止まり、//go:noinline を付けた関数はインライン化されません。

インライン化を止めると直るので、f がインライン化されることが関係していそうだとわかります。f に //go:noinline を付けた場合や、f(1) と f(3) を前の文で別々に評価した場合も、正しい順番になりました。

原因

make の評価順のバグ。容量が定数とわかると、容量の式が make の前処理に移され、長さより先に実行されていた

Go チームの Keith Randall さんが、原因を escape analysis の最適化だと突き止めてくれました。

escape analysis は、値が関数の外へ出ていく(escape する)かを調べる解析です。出ていかない値は、ヒープではなくスタックに置けます。slice なら、容量が定数でわかれば、その大きさの領域をスタックに取れます。

  1. f がインライン化されると、容量の f(3) の値が定数 3 だとわかる
  2. 容量が定数なら、slice をヒープではなくスタックに置ける。そこで、容量を定数 3 に置き換える
  3. ただし f(3) には副作用(表示)があるので、消さずに make の前処理(init)に移して残す
  4. この前処理は、make の引数を評価するより前に走る。その結果、容量の f(3) が、長さの f(1) より先に実行される

3 の「副作用を残す」は、以前の別のバグ(副作用が消える問題)への対応として入ったものでした。副作用は残すようになったものの、長さの式との順番までは考えられていなかった、ということです。

修正(CL 839725)では、長さの式に副作用があるときは、この最適化をしないようにしました。

※ その後、別の方から、同じあたりの最適化で append(f(), make([]T, g())...) の副作用が消えるバグ(#83209)も報告されています。

バグ 2:for i, _ := range *p だけが panic する(#81697)

見つけた経緯

こちらは、K 側のバグから始まりました。

Go の公式テストに、nil の array pointer p で for i := range (*p) を回すもの(test/fixedbugs/issue73476.go)があります。Go では正常に終わるのに、K では nil の参照で panic していました。これは K の誤りなので、K を直しました。

直すときに、周りの条件を確かめるテストを 24 件足しました。iteration variable なし、添字だけ、添字と値、最後が _、range expression に関数呼び出しや channel の受信を含むもの、などです。そのうちの「最後が _」のケースで、今度は逆の食い違いが出ました。K は 012 を出して正常に終わり、Go は panic しました。

Go だけで確かめると、こうなりました(Go 1.26.8、1.27.1、開発版のどれでも同じ)。

p は nil の *[3]int

結果

for i := range p

012

for i, _ := range p

012

for i := range *p

012

for i, _ := range *p

panic

*p と書いて、最後に _ を付けたときだけ panic します。

仕様の 2 つの文

仕様の for range の節には、次の 2 つの文が続けて書かれています。

If the last iteration variable is the blank identifier, the range clause is equivalent to the same clause without that identifier.

The range expression x is evaluated before beginning the loop, with one exception: if at most one iteration variable is present and x or len(x) is constant, the range expression is not evaluated.

— The Go Programming Language Specification - For statements with range clause

1 つ目は「最後の iteration variable が _ なら、それを省いたのと同じ」。2 つ目は「range expression はループの前に評価する。ただし、iteration variable が 1 つ以下で、x か len(x) が定数なら評価しない」です。

p が *[3]int なら、len(*p) は型から決まる定数 3 です。

仕様の 2 つの文をつなげると、for i, _ := range *p は *p を評価しない。gc は _ も iteration variable として数え、*p を評価して panic していた

2 つの文をつなげると、for i, _ := range *p は for i := range *p と同じです。iteration variable は 1 つで、長さは定数なので、*p は評価しません。nil を参照しないので、012 を出して終わるはずです。

仕様には、ちょうどこの形の例まで載っています。

Go
var testdata *struct {
	a *[7]int
}
for i, _ := range testdata.a {
	// testdata.a is never evaluated; len(testdata.a) is constant
	// i ranges from 0 to 6
	f(i)
}

コメントには「testdata.a は評価されない」とあります。ところが、この例も手元の Go では panic します。

コンパイラのバグか、仕様の問題か

この Issue は、議論が面白い方向に進みました。

まず Keith Randall さんは、「iteration variable が 2 つあるので評価される。今の動作で正しい」と返してくれました。2 つ目の文だけを見れば、そう読めます。

私が 1 つ目の文と仕様の例を示すと、こう返ってきました。

Good point, the spec is fighting with itself here.

— golang/go#81697

仕様の文どうしがぶつかっている、という認識です。あわせて、仕様の例が Go 1.25 から panic するようになっていたこともわかりました。

次に、Go の設計者の 1 人である Robert Griesemer さんが、両方の考え方を挙げました。

  • _ を省略と同じにすれば、人や gofmt のような道具が、前後を見ずにコードを簡単にできる
  • 今の動作にも理由がある。たとえば var _ = (*p)[0] は、結果を _ に捨てても nil で panic する

そのうえで、「_ は省略と同じ」の文を仕様から消す案を出しました。この 1 年ほどこの動作だったので、既存のプログラムには影響しない、という理由です。

これに反対したのが Russ Cox さんです。

I would argue strongly for for x, _ := range and for x := range having identical meanings.

— golang/go#81697

理由として挙げていたのは、次の点です。

  • , _ は panic の確認ではない。確認したいなら、はっきり書くべき
  • コードを簡単にする規則は単純であるべき
  • Go 1.24 までは、この 2 つは同じ動作だった。互換性のためにも戻すべき
  • この規則を最初に仕様に入れたときの例が、まさに for x, _ := range だった。2 つの規則を組み合わせて使う意図だったはず

Griesemer さんは、これを受けて提案を取り下げました。仕様はそのままにして、コンパイラを直すことになりました。

修正(CL 837325)は、type checker(types2 と go/types)で、最後の _ を iteration variable として数えないようにするものです。原因は、Go 1.25 で入った「len() の引数の副作用を必ず評価する」変更でした。この変更で、, _ の場合まで range expression を評価するようになっていました。

executable semantics を書いてわかったこと

2 つのバグは、性質が少し違います。

#81696(make)

#81697(range)

何がずれていたか

実装が仕様からずれていた

仕様の文どうしの組み合わせ方が、読み手によって割れた

決め手

評価順の節

仕様の別の文と、仕様の例

直した場所

escape analysis の最適化

type checker(仕様はそのまま)

修正までの日数

報告から 5 日

報告から 2 日

#81697 のほうは、K で書いていたから見えた面があると思います。K では「_ は省略と同じ」と「定数長なら評価しない」が、別々の rule として同時に動きます。そのため、2 つを組み合わせた結果が、迷わず 1 つに決まります。人が仕様を読むときは、どちらか一方の文だけに目が行きがちです。

もう 1 つ、make の件でわかったのは、実装の出力を期待値にすると、間違いに気づけないことです。最初に Go の出力をそのまま期待値に写したせいで、危うく正しい K のほうを「直す」ところでした。differential testing では、どちらの出力も正解とみなさず、判断の基準を仕様に置く必要があります。

※ どちらのバグも、再現に必要なのは 10 行に満たないプログラムでした。実際のコードで踏むことは多くないと思いますが、仕様の境界を 1 つずつ確かめると、こういうものが出てきます。

手元の Go 1.27.3 では、まだどちらも再現します。修正は Go の開発版に入っているので、次のリリースからは直る見込みです。

K の semantics にも、まだ足りないところがあります。未対応のケースが 163 件あり、generics や複数の package は対象外です。今後は、対象を広げることと、K の状態探索や証明の機能を使った検証に進めたいと考えています。

おわりに

論文で作った semantics とテストの仕組みが、そのあとの研究で、実際の Go のバグ 2 件の修正につながりました。

仕様を executable semantics として書くと、仕様の文と実装の動きを、1 つずつ機械的に比べられます。今回はそこから、実装のずれと、仕様の文どうしの食い違いの両方が見つかりました。