世界を動かす技術を、日本語で。

より良いプログラマーになるために、頭の中で小さな証明を書こう

概要

  • コードを書く速度正確さ を向上させる実践的な思考法の紹介
  • 「頭の中で証明をスケッチする」 という習慣の重要性
  • モノトニシティイミュータビリティ など、設計上の考慮点
  • 前提条件・事後条件・不変条件 によるロジックの検証法
  • 変更の影響範囲 を限定し、既存動作の安定性を保つ工夫

コードを書く際の思考法とその効果

  • 難しい問題 に取り組む際は、 自分のコードが意図通り動作するか を頭の中で証明する習慣
  • フローを妨げずにオンラインで実施 するには、 練習と経験 が必要
  • この思考法が身につくと、1回または2回の試行で動くコード が書けることが多くなる
  • 明確な手法は人それぞれ だが、いくつかの代表的な考え方を紹介

モノトニシティ(単調性)の活用

  • モノトニックな処理 は「一方向にしか進まない」特性を持つ
  • チェックポイント の実装例:スクリプトの進捗をディスクに保存し、クラッシュ後も未完了のタスクから再開可能
  • LSMツリー のようなデータベース構造体は、 操作履歴の蓄積と単調増加 を活用
  • Bツリー との比較で、 直感的な理由付けのしやすさ を確認
  • イミュータビリティ (不変性)も類似の考え方で、 値の変更禁止による予期せぬ動作の排除

前提条件・事後条件による検証

  • 前提条件(pre-condition) :関数実行前に成立しているべき条件
  • 事後条件(post-condition) :関数実行後に成立しているべき条件
  • これらに基づく単体テストの着想やassertionの導入 による堅牢性向上
  • 前提・事後条件が曖昧な場合も発見できる利点

不変条件(インバリアント)の維持

  • 常に成立すべき条件 を「不変条件」として定義
  • コードを原子的なステップに分割し、それぞれが不変条件を保つことを確認
  • ダブルエントリー会計の会計等式 のような古典的インバリアントの例
  • ライフサイクルメソッドやリスナー による状態同期の実装
  • 実行経路が少ない場合の推論のしやすさ

変更の隔離と影響範囲の管理

  • 既存システムを壊さずに拡張・修正する ことがソフトウェア開発の重要な「クラフト」
  • 「ブラスト半径」 という考え方で、変更の影響範囲を限定
  • 構造的な「ファイアウォール」 による変更の波及防止
  • Nerve のクエリエンジンを例に、 依存フィールドの過剰取得と後処理で設計変更を最小限に抑える方法
    • クエリプランナーとクエリエグゼキュータ間の境界 で変更を封じ込め
    • 本質的なロジックは未変更のまま、既存動作の信頼性確保
  • Open-Closed Principle にも通じる考え方

まとめ

  • 頭の中で証明をスケッチする習慣 は、 バグの早期発見と高品質なコード の実現に直結
  • モノトニシティ、イミュータビリティ、不変条件、前提・事後条件、変更の隔離 といった思考パターンを活用
  • 設計・実装時の思考フレームワーク として、日々意識的に使いこなすことが重要

Hackerたちの意見

ああ、関連性があって意外とシンプルな例があるよ:二分探索。二分探索とそのバリエーションである最左端・最右端の二分探索は、ループ不変条件について考えないと正しくコードを書くのが意外と難しいんだ。ループ不変条件のアプローチを[1]で説明したけど、例のPythonコードはできるだけ明確で普通の英語に近いものにしたよ。『Programming Pearls』の著者であるジョン・ベントリーは、IBMのプロのプログラマーたちに普通の二分探索を書く課題を出したんだけど、彼らの実装の90%にバグがあったんだ。最も多かったのは、うっかり無限ループに入ってしまうことだったみたい。公平に言うと、当時は整数オーバーフローに対して明示的に対策を講じる必要があったけど、それにしても驚くべき数字だね。[1]: https://hiandrewquinn.github.io/til-site/posts/binary-search...

確かに、インデックスに関して非常に気難しい例を選んでるね。エラーなしで書くのが一番難しい基本アルゴリズムの一つだと思う。ホーアのパーティションと同じくらい難しい。

2006年のGoogleの研究論文では、「ほぼすべて」のバイナリサーチ(とマージソート)の実装にバグが含まれていると指摘されていて(何十年も前から)、それを考えると90%はすごいことだと思う。 https://research.google/blog/extra-extra-read-all-about-it-n...

有名なバイナリサーチのバグについては本で知ってたし、非常に慎重にバグのない実装を書こうとしたんだけど、結局バグが出ちゃった。:) 幸いにも、マンニングの早期アクセスプログラムのおかげで、印刷前に修正できたよ。

二分探索を一度だけ使うんじゃなくて、何度も使うように書く確率ってどれくらい?

C++の標準ライブラリでは、二分探索を部分分けの問題として表現してるんだ。つまり、述語が偽から真に変わるインデックスを見つけるってこと。これは自分にとって役立つね。

正しい証明を書くのは難しいよね。プログラムの検証も難しい。個人的には、手作業でやってるならあまりメリットはないと思う。言語やコードベースに合わせたイディオム的なコードを書くと、不変条件や前後条件について考える必要がほとんどなくなることが多いよ。R. パイクとB. W. カーニハンの『The Practice of Programming』をチェックしてみて。モットーは「シンプルさ、明確さ、一般性」。これが日常の仕事で本当に役立つと思う。ちょっと関連する話だけど…競技プログラミングは、コードが正しいことを確実にするための正しい技術を教えるのが意外と得意だよ。これを身につけないと、特定の段階を超えるのは難しい。

最初の段落をひっくり返してみて:適切な抽象化(つまり「言語やコードベースに対するイディオム的なコード」)がプログラムの検証を簡単にするんだ。適切に抽象化されたプログラムを手作業で作っているなら、ループ不変条件や前後条件について考えるメリットはほとんどないよ。なぜなら、そのレベルの一般性では存在しないから。正しい証明は正しいコードから直接導かれるんだ。

ここには強く反対するよ。OPが言いたかったのは、完全で形式的な証明を考えることじゃないと思う。自分のコードがどんな論理的特性を満たしているのか、例えばどんな不変条件が成り立つべきかを理解しようとすることが、コードの理解をずっと楽にして、恐怖感を減らすことにつながるよ。

競技プログラミングのその技術について詳しく教えてくれない?本当に興味があるんだ! :)

正しいプログラムを書くことに代わるものはないよ、どんなに難しくてもね。正しいプログラムが欲しいなら、正しく書かなきゃダメだよ。

証明の最も基本的なアイデアは、何かが真である理由を説明することなんだ。小さなミスを避けることじゃなくて、方向性が正しいかどうかが大事なんだよ。

Hacker Newsで議論の続きを見る