HN 日本語サマリー

← 一覧へ戻る
プログラミング

グローバルプロパティのためのローカル推論

Local Reasoning for Global Properties (tratt.net)

21 pointsby mpweiher2 コメント

要約

AIがコード生成能力を高める中、ローカルなコード片は高品質でも、プログラム全体のグローバルな理解を必要とするコード生成には苦労する傾向があります。この記事では、ローカルな推論から驚くべきグローバルプロパティの保証を可能にするプログラミング言語設計の例として、Rustのマルチスレッドプログラミングにおけるデータ競合の静的エラー化に焦点を当て、そのメカニズムを解説しています。

全文翻訳

Local Reasoning for Global Properties

この2、3年、私は「AIは新しい種類のプログラミング言語から恩恵を受けるだろうか?」という問いを繰り返し受けてきました。私の答えは「おそらくそうではない」でしたが、少なくともこれまではその答えは有効でした。AIは、あなたが想像できるほぼすべてのプログラミング言語で、大量のコードを生成できるようになっています。

技術が進歩し、その特性がより明確になってきた今、私の答えは変わりました。私の経験では、AIは、少なくとも現在のところ、しばしば高品質な局所的な(例えば、関数単位の)コード片を生成しますが、プログラム全体を理解する必要があるコードの生成を求められると、しばしば苦労します。これを最も容易に確認できるのは、不必要な防御的チェックの蔓延です。これらは無害に見えますが、コードの後の読者が発生しうると考える状態の数を指数関数的に増加させ、それに伴うあらゆる有害な影響を引き起こす可能性があります。

おそらくこの苦労はすぐに克服されるでしょうが、もしそうならない場合、私たちは再びプログラミング言語の設計に助けを求めることになるかもしれません。この投稿の目的は、プログラミング言語がどのように、あるいはどのようにすべきか、この問題に対処しようとするかを具体的に予測しようとすることではありません¹。むしろ、より基本的な問いに答えたいと思います。局所的な推論によって、驚くべき大域的な性質についての保証を得ることができる、プログラミング言語設計の良い例は存在するのでしょうか?

背景

私はプログラミング言語でかなりの収入を得てきたので、それらの重要性を強調することに個人的な関心があります。しかし、プログラミング言語が私たちの生産性や、作成するソフトウェアの信頼性にいくらか影響を与えると信じてはいますが、それらが決定的な違いを生むという証拠はあまりありません。

これは単に「違いを証明する良い実験ができなかった」という意味ではありません。それも事実ですが!むしろ、「悪い」言語で多くの「良い」ソフトウェアが作成され、「良い」言語で多くの「悪い」ソフトウェアが作成されてきました。使用されたプログラミング言語が、そのような結果の主な要因であった可能性は低いと思われます。

これに対する最も単純な議論は、ユーザーが必要とするすべてを、理解可能で信頼性の高い方法で実行するソフトウェアを作成するには、複雑なプログラミング言語機能の専門知識よりも共感が必要であるということです。よりニュアンスのある見解については、以前にソフトウェアの性質について考えをまとめたことがあります。

これは、プログラミング言語が全く違いを生み出さないと言っているわけではありません。私がアセンブラからPythonやCのような「高水準」言語でのプログラミングに移行したとき、私の生産性は大幅に向上し、より大きなソフトウェアに取り組めるようになったと感じました。理由は単純です。アセンブリは、あまりにも多くの低水準の詳細に対処することを私に強いるため、より重要な高水準の全体像を常に忘れてしまいます。作成できたソフトウェアの違いは、驚くべきものでした。

残念ながら、そのような大きな改善が繰り返される可能性は低いことに徐々に気づきました。私は、ゆっくりと、そして不器用に、フレッド・ブルックスのシルバーバレットはないという議論を再発明していました。

ソフトウェア生産性の過去の大きな進歩のほとんどは、ハードウェアの制約、扱いにくいプログラミング言語、マシン時間の不足など、偶発的なタスクを不当に困難にしていた人工的な障壁を取り除くことから来ています。ソフトウェアエンジニアが現在行っていることのどのくらいの割合が、本質的なものに対して偶発的なものに費やされているのでしょうか?もしそれが全体の9/10以上でなければ、すべての偶発的な活動をゼロ時間に縮小しても、桁違いの改善は得られません。

例外

そのため、何年も後の特定の文脈で、私が書く多くのソフトウェアの生産性に再び劇的な変化を経験したとき、私はあまりにも驚いて、ほとんどそれに気づきませんでした。ついに気づき、他の人々にその違いを説明しようとしたとき、彼らも困惑しているようでした。その文脈とは?Rustでのマルチスレッドプログラミングです。その経験が、プログラミング言語の将来の進むべき道についての私の意見を形成しているので、Rustがマルチスレッドプログラミングをいかに容易にするかという深い理由を納得させる必要があります。

具体的な例から始めましょう。現在読んでいるウェブサイトを構築するソフトウェアは、通常のシングルスレッドコードとして書きました。私が怠惰であること、そして私のウェブサイトがあまり大きくないことから、サイトを再構築するたびに、サイト全体が再構築されます。

しばらくすると、サイトを再構築するためにソフトウェアが必要とする一時停止が長すぎて、一部のページ(この投稿のような!)の編集が非効率的になることに気づきました。すぐにシングルスレッドの最適化を行いましたが、十分ではありませんでした。次に、これをマルチスレッド化するように書き直せば、一時停止時間を許容可能なレベルまで短縮できるだろうと推測しました。

ほぼすべての他のプログラミング言語で、ソフトウェアをマルチスレッド化するように書き直すのは daunting な作業だったでしょう。実際、マルチスレッドに関する私の過去の経験から、デバッグが困難なクラッシュにすぐに遭遇するだろうということがわかりました。そして、ほぼ間違いなく、数週間から数ヶ月にわたってつまずくべきそのような恐怖の長い尾があるでしょう。マルチスレッドプログラムを書くのをやめたのには十分な理由があります!

しかし、この特定のケースでは、パフォーマンスの問題を解決した書き直しは、5分もかかりませんでした。最初から正しく動作し、正しく動作し続けています。そして、その両方がそうなるだろうという完全な自信がありました。

これはどうして可能なのでしょうか?私はRustが大好きです。2015年から私のメイン言語です。しかし、それは完璧な言語ではありません。実際、私はその欠点について詳細に説明して人々を退屈させることができますし、そうしてきました。しかし、マルチスレッドに関しては、私がかつて想像もできなかったことを行っています。データ競合(つまり、調整されていない読み取り/書き込みで、2つのスレッドが予期せず互いに干渉する可能性があること)が静的なエラーになります。これは小さなことではありません。データ競合は、以前は、私がマルチスレッドプログラムを書こうとしたときに発生するエラーの圧倒的な原因でした²。

Rustがデータ競合を防ぐ仕組み

Rust³は、所有権型とSendおよびSyncトレイトの組み合わせによってデータ競合を防ぎます。Rustの仕組みを知っているなら、このセクションはスキップできます。Rustを知らない場合は、これらの機能の概要を可能な限り簡潔に、可能な限り簡略化して説明します。

所有権型に迷い込むこともありますが、私たちが知る必要があるのは次のことだけです。特定のオブジェクトには所有者がおり、その所有者はオブジェクトを読み書きできます。オブジェクトは他の所有者に移動でき、その時点で元の所有者はオブジェクトへのアクセスを失い、他の所有者がアクセスできるようになります。

Sendは「この構造体のインスタンスは現在のスレッドから別のスレッドに移動できる」(つまり、移動後、現在のスレッドはオブジェクトにアクセスできない)ことを意味します。Syncは「複数のスレッドが同時にこの構造体のインスタンスから読み取ることができる」ことを意味します。私たちの目的のために、Rustが構造体がSendおよび/またはSyncになるのが安全な時期を自動的に判断し、それらのトレイトを自動的に実装すると仮定できます。

この非常にシンプルなRustコードから始めましょう。

fn main() {
  let x = vec![1, 2];
  println!("{x:?}");
}

vec!で作成されたベクターはVec型のインスタンスを作成し、これはSendを実装しています。そのため、ベクターを別のスレッドに送信し、その別のスレッドにベクターを出力させることができます。

fn main() {
  let x = vec![1, 2];
  std::thread::spawn(move || println!("{x:?}")).join().ok();
}

std::thread::spawn(...)はRustで新しいスレッドを作成する方法です。move || ...は「クロージャ」(つまり無名関数)であり、新しいスレッドが開始されたときに実行されます。moveは、新しいスレッドが外部関数(つまりxが新しいスレッドに移動される)から参照されるすべてのデータの所有者になることを意味します。joinは、メインスレッドが新しいスレッドの完了を待つことを意味します。

メインスレッドがベクターへのアクセスを実際に失ったことがわかります。なぜなら、このコードは次のようになります。

fn main() {
  let x = vec![1, 2];
  std::thread::spawn(move || println!("{x:?}")).join().ok();
  println!("{x:?}");
}

次のコンパイル時エラーにつながります。

error[E0382]: borrow of moved value: `x`
 --> t.rs:4:14
  |
2 |   let x = vec![1, 2];
  |       - move occurs because `x` has type `Vec<i32>`, which does not implement the `Copy` trait
3 |   std::thread::spawn(move || println!("{x:?}")).join().ok();
  |                      -------            - variable moved due to use in closure
  |                      |
  |                      value moved into closure here
4 |   println!("{x:?}");
  |              ^ value borrowed here after move
  |
help: consider cloning the value before moving it into the closure
  |
3 ~   let value = x.clone();
4 ~   std::thread::spawn(move || println!("{value:?}")).join().ok();
  |

error: aborting due to 1 previous error

For more information about this error, try `rustc --explain E0382`.

まだ本格的なデータ競合を紹介する前に、Rustはすでに私に不正なことをするのを阻止しています!

エラーは、値をcloneすることを提案しています。経験豊富なRustプログラマーは、このアドバイスに注意しています。なぜなら、それはひどいパフォーマンスにつながる可能性があるからです。代わりに、オブジェクトをリファレンスカウンティング型Rcでラップしてみるのはどうでしょうか?そうすれば、両方のスレッド間で値を安全に共有できます。

fn main() {
  let x = std::rc::Rc::new(vec![1, 2]);
  std::thread::spawn(move || println!("{x:?}")).join().ok();
  println!("{x:?}");
}

しかし、残念ながらこれは次のエラーにつながります。

`Rc<Vec<i32>>` cannot be sent between threads safely

Rcインスタンスを別のスレッドに移動できない理由は、リファレンスカウンティングがスレッドセーフではない方法で行われているためです。幸いなことに、それをスレッドセーフに行うバリアントがあります。「アトミックリファレンスカウンティング」であるArcです。少し退屈な理由で、Arcをクローンする必要があります(幸いなことに、これは内部のベクターをクローンしません!)。

fn main() {
  let x = std::sync::Arc::new(vec![1, 2]);
  let y = std::sync::Arc::clone(&x);
  std::thread::spawn(move || println!("{y:?}")).join().ok();
  println!("{x:?}");
}

これはコンパイルされ、正常に実行されます。両方のスレッドが同じベクターから読み取り、同じものを出力します。最後に、Rustの標準的なRefCell型を導入して、それらのスレッド間での共有ミューテーションを有効にしてみましょう。

let x = std::sync::Arc::new(std::cell::RefCell::new(vec![1, 2]));

再びエラーが発生しますが、今回は送信(Send)ではなく共有(Sync)に関するものです。

error[E0277]: `RefCell<Vec<i32>>` cannot be shared between threads safely
...
    = help: the trait `Sync` is not implemented for `RefCell<Vec<i32>>`

おそらくこれが、データ競合を完全に導入しようとした最初の機会です。ここでもRustは私たちを止めました。スレッド間での共有ミューテーションの可能性を有効にしたい場合は、Mutexのような型を導入する必要があります。

fn main() {
  let x = std::sync::Arc::new(std::sync::Mutex::new(vec![1, 2]));
  let y = std::sync::Arc::clone(&x);
  std::thread::spawn(move || {
    y.lock().unwrap().push(3);
    println!("{:?}", y.lock());
  }).join().ok();
  println!("{:?}", x.lock());
}

これはコンパイルされ、正常に実行されます(1, 2, 3が2回出力されます)。

グローバルな推論の拡張

この時点で、読者はRustがデータ競合をプログラムに導入するのを防いでくれるという感覚を得られたことを願っています。重要なのは、Rustはこれのために新しい機能を追加する必要はなかったということです。所有権型とSendおよびSyncトレイトがあれば十分です。つまり、私はまだ「通常の」Rustプログラムを書いており、asyncプログラムを書いている場合のように、新しいサブ言語を使用する必要はありません。

Rustでマルチスレッドプログラムに役立つルールは、経験豊富なRustプログラマーにとっては自然で明白であるため、より深い真実を観察することを妨げる可能性があります。それは、Rustが私が局所的に推論できる方法で、私のプログラムにグローバルなデータ競合フリーのプロパティを強制しているということです。例えば、このプロパティは関数シグネチャのレベルで強制されます。

fn f<T: std::fmt::Debug>(x: T) {
  std::thread::spawn(move || println!("{x:?}")).join().ok();
}

fn main() {
  f(vec![1,2]);
}

Tを制約していないため、Rustはfの呼び出し元がSend可能なオブジェクトをfに移動したことを確信できません。そのため、2行目のspawnは次のエラーにつながります。

`T` cannot be sent between threads safely

これを機能させるには、fは呼び出し元に対して、渡されたオブジェクトが本当に他のスレッドに送信されることが許可されていることを要求する必要があります。構文は少し扱いにくいです。

fn f<T: std::fmt::Debug>(x: T) where T: Send + 'static {
  std::thread::spawn(move || println!("{x:?}")).join().ok();
}

fn main() {
  f(vec![1,2]);
}

これはコンパイルされ、実行されます!良いニュースは、fのシグネチャを見ることで、それを呼び出してもxに関するデータ競合が発生しないことを確実に知ることができるということです。したがって、このフラグメントはRcを使用したためコンパイルに失敗します。

f(std::rc::Rc::new(vec![1,2]));

しかし、それを次のように変更すると。

f(std::sync::Arc::new(vec![1,2]));

コンパイルされます。

なぜ大域的な推論がそれほど強力なのか

Rustに慣れていない方のために、コードフラグメントはここで終了することをお知らせします。多くの例を示したのは、次のステートメントを信じてもらえることを願っているからです。

所有権型、Send、およびSyncの組み合わせは、コードをローカルに見るだけで、マルチスレッドとデータ競合の影響についてグローバルに推論できることを意味します。

これは通常の静的型付け保証のように聞こえるかもしれません。結局、もし私が(例えば)Haskellプログラムを書いた場合、実行時に型エラーが発生しないことが保証されます。それは真実ですが、Haskellの通常の型システムは、それ自体では、Rustの並行コードがデータ競合から解放されるという保証を私に与えません。

別の言い方をすれば、Rustまで、私は標準的なプログラミング言語が過度の苦痛なしに強制できる唯一の大域的な性質は「実行時型エラーがない」⁴ことであると暗黙的に仮定していました。私は、エキゾチックまたは実験的な言語を使用する必要があり、それに伴う妥協はほとんどのプログラマーにとって受け入れられないだろうと考えていました。Rustのデータ競合の自由の保証は正確であり、ルールが損なわれたときの(ほとんどの)エラーは理解可能であり、全体的な結果は非常に使いやすい⁵です。

未来の言語

これで元のトピックに戻ることができます。中規模以上のプログラムでプログラミングが難しくなるのは、各ローカルな変更がバタフライであり、そのバタフライの羽ばたきの一部が遠くで大きな嵐(つまりバグ!)を引き起こすからです。

これは常に問題でした。たとえ最高の人間プログラマーでさえ、作業しているソフトウェアの大域的なビューを把握し、維持するのに苦労しています。しかし、現在、AIはさらに苦労することがよくあります。

AIに、明確に定義された仕様を持つ単一の関数を生成するように依頼すると、しばしば私よりも優れたコードを、より迅速に作成してくれるでしょう。AIに中規模のソフトウェアを生成させ、それを改良するように依頼すると、しばしば望ましくない結果が得られます。この点に関して、人々はコードの肥大化についてよく話しますが、それはより深刻な問題を見落としています。システムのグローバルビューは、しばしば不器用に、そして時には誤って、生成されたコードに捉えられています。この問題を最も容易に(ただし間違いなく唯一ではない!)見る方法は、AI生成コードが大量の防御的チェックを含みがちであるということです。

アサーションと防御的チェックはしばしば混同されますが、それらは非常に異なります。アサーションは、予期しない状況が観察されるとすぐにプログラムを中止します。それらは「この条件が満たされない場合、プログラマーはシステムの仕組みを誤解したか、システムの他の部分が間違っている」という考えをエンコードします。対照的に、防御的チェックはプログラムを中止しません。チェックが失敗した場合でも、実行は意図的に続行されます。したがって、防御的チェックは、「この条件が満たされるかどうかはわからないが、失敗した場合は、それを処理するための優雅な方法が欲しい」という考えをエンコードするものと考えるのが良いでしょう。

防御的チェックは、一見すると疑いの余地のない良いことのように思えます。現在の操作は早期に終了する傾向がありますが、プログラム全体は続行されます。しかし、良いことでもやりすぎることがあります。人間の書いたコードと同様に、AI生成コードの多くの防御的チェックは不要です(つまり、失敗しません)。

AI生成コードでよく見かける一般的な例は、「このリストは空であってはならない」というチェックですが、これはチェックに至るすべてのパスで(しばしば複数回)チェックされています。次のようなコードが一般的です。

def f(x):
  if len(x) == 0: return
  else: ... # do something with x

# fが呼び出される唯一の場所
for x in ...:
  if len(x) > 0: f(x)

この例では、fの防御的チェックはせいぜい不要です⁶⁷。

不要なチェックは邪魔であり、パフォーマンスを低下させ、コードを読む人々を特定の時点でのプログラムの状態について誤解させます。最後の点の有害さは、しばしば過小評価されます。プログラムが編集したい時点で状態A、B、Cになりうると考えるなら、3つの状態すべてを考慮する必要があります。実際には、それらの状態のうち2つが発生しない場合、努力を無駄にしただけでなく、後続の編集で考慮すべき状態の潜在的な指数関数的な爆発を作成したことになり、生産性と信頼性への影響はすべて伴います。

過去1年間でAIコード生成がどれほど急速に進歩したかを考えると、この問題がすぐに解決される可能性を排除するのは愚かでしょう。しかし、さらに1つか2つの大きなブレークスルーがない限り、AIは局所的には優れ、大域的には弱い状態を続ける可能性があります。その場合⁸、プログラミング言語に大域的な性質を強制するのを助けてもらうことへのインセンティブは、過去よりもはるかに強くなるでしょう。なぜなら、それを行うたびに、バグのクラス全体を削除できるからです。

この投稿で示したいのは、驚くべき大域的な性質、つまりデータ競合の自由が、純粋に局所的な推論を通じて強制できるということです。私にとって興味深いのは、これが重要なプログラミングタスクの多くを、プログラマーに追加の負担をほとんどかけずに、より信頼性の高いものにするということです。これは、プログラミング言語の設計によって同様に対処できる、他の望ましい大域的な性質が存在する可能性があるという希望を与えてくれます⁹。

しかし、現実的でなければなりません。私たちが望むすべてのグローバルプロパティを強制できるわけではありません。これらには、パフォーマンス、サブコンポーネントの分離、さまざまな種類の非干渉、リソースクリーンアップ、状態変更などに関する保証が含まれる可能性があります。それらのいくつかは間違いなく互いに競合するでしょう。いくつかは、価値があるにはあまりにも負担が大きいことが判明するでしょう。そして、いくつかは単に全く処理できないでしょう。

良いニュースは、関連性がある可能性のある多くの実験的なプログラミング言語機能¹⁰があるということです。例えば、エフェクトシステムは、ローカル推論を通じて、プログラムのどの部分が入出力を行うかといったことについて推論することを可能にします。現状では、これらのどれも、この投稿で説明したRustの機能と同じ規模でテストされていません。どれが勝者になるかを知ることは困難です。まだ考えられていない機能がどれだけあるかを知ることも不可能です。

しかし、実用的な将来のプログラミング言語が、より多くのグローバルプロパティに関する保証を持つプログラムを書くことを可能にすると現実的に想像するのに十分な証拠があります。プログラムを作成および変更する人は誰でも、または何であれ、これによって大幅に利益を得ることができます。個人的には、それが私たちにプログラムの構造方法を完全に再考することを可能にすることを願っています!

要約すると、最近まで、AIがプログラミング言語に対するインセンティブを変えるとは思っていませんでした。今、それらのインセンティブは変化しています。幸いなことに、それらのインセンティブを満たすことができるかもしれないという兆候がいくつかあります。十分なリソースを持つ誰かがこのレベルの野心を持っているかどうかは不明です。しかし、少なくとも1つの大企業が、そして2026年でさえ、これはほぼ間違いなく企業の資源を必要とするでしょうが、それをやろうとすることは私を驚かせないでしょう。私は彼らを事前に応援します。非常に興味深いプログラミング言語が登場するかもしれません!

2026-06-30 10:50 Older

新しいブログ投稿の更新情報が必要な場合は、MastodonまたはTwitterでフォローしてください。またはRSSフィードを購読するか、メール更新を購読してください。

Footnotes

1

これはプログラミング言語における活発な研究/設計分野であること、そしてAIコード生成がどのように変化するかを予測することは私の能力を超えていることの両方のためです。

☒

これはプログラミング言語における活発な研究/設計分野であること、そしてAIコード生成がどのように変化するかを予測することは私の能力を超えていることの両方のためです。

2

もちろん、デッドロックなど、他の種類の erreurs も発生する可能性があります。それでも、それらはデバッグが容易であり、私の経験でははるかに頻度が低いです。

☒

もちろん、デッドロックなど、他の種類の erreurs も発生する可能性があります。それでも、それらはデバッグが容易であり、私の経験でははるかに頻度が低いです。

3

技術的には「セーフRust」です。

☒

技術的には「セーフRust」です。

4

Ponyのような他の言語も、かなり異なるメカニズムを通じて同じ保証を提供しています。

☒

Ponyのような他の言語も、かなり異なるメカニズムを通じて同じ保証を提供しています。

5

Arc::cloneを十分に呼び出す傾向があり、それが醜いものになるという軽微な例外を除いて。

☒

Arc::cloneを十分に呼び出す傾向があり、それが醜いものになるという軽微な例外を除いて。

6

fが何をすべきかによっては、チェックは不正確である可能性さえあります。私は、要素の合計を出力すべきprint_sumのような関数を呼び出しましたが、空のリストに対しては何も出力しないのを見たことがあります!

☒

fが何をすべきかによっては、チェックは不正確である可能性さえあります。私は、要素の合計を出力すべきprint_sumのような関数を呼び出しましたが、空のリストに対しては何も出力しないのを見たことがあります!

7

勇敢なプログラマーはチェックを完全に削除するかもしれませんが、私はそれをアサーションとしてエンコードする傾向があります。

☒

勇敢なプログラマーはチェックを完全に削除するかもしれませんが、私はそれをアサーションとしてエンコードする傾向があります。

8

そしておそらくそうでない場合でも。人間がAI生成コードをレビューするだけの役割に追いやられたとしても、読んでいるコードに自信を持つことを容易にするために私たちができることは何でも役立つでしょう。

☒

そしておそらくそうでない場合でも。人間がAI生成コードをレビューするだけの役割に追いやられたとしても、読んでいるコードに自信を持つことを容易にするために私たちができることは何でも役立つでしょう。

9

この言語設計がどのようになるか、あるいはならないか、あるいはRustの影響を受けるかどうかさえ、私には全くわかりません。この投稿で私が述べている全体的なポイントは、私が動機付けの例として使用した特定の言語とは独立していると信じています。

☒

この言語設計がどのようになるか、あるいはならないか、あるいはRustの影響を受けるかどうかさえ、私には全くわかりません。この投稿で私が述べている全体的なポイントは、私が動機付けの例として使用した特定の言語とは独立していると信じています。

10

プログラミングへの形式手法の成長する外部統合については言うまでもありません。

☒

プログラミングへの形式手法の成長する外部統合については言うまでもありません。

Comments