不動点とストライキの権限委任

コンパイルやプログラム解析（シンボリック計算全般においても、そうだと思います）における多くのタスクは、 x = f(x) という形の連立方程式の解を見つけることに帰着します。しかし、そのような不動点を見つけるアルゴリズムを定義するように求められたとき、私たちは「どの不動点を探しているのか？」と立ち止まって問うことはめったにありません。実際には、私たちは単調関数の不動点に関心を持つ傾向があります。すなわち、ある半順序 (prec) に対して、 a ≺ b ⇒ f(a) ≺ f(b) が成り立つ場合です。この条件は、かなり妥当な仮説であることに加え、通常はタルスキの不動点定理を利用することを可能にします。もし f の定義域（≺ を持つ）が完全束を形成する場合、f の不動点の集合もまた完全束を形成します！ その系として、≺ に関して最小の不動点と最大の不動点がそれぞれただ一つ存在することが保証されます。これは非常に有用です。なぜなら、通常は有用な meet（共通部分）と join（和集合）の演算を定義でき、完全束の恩恵を受けることができるからです。例えば、ある集合のべき集合である定義域の場合、順序関係として ⊂、join として ∪、meet として ∩ を使用できます。しかし、私が興味深いと感じるのは、どの不動点を見つけたいのかに注意を払わないとき、人間は問題に応じて、最小または最大の不動点に収束するアルゴリズムを、一貫して開発する傾向があるということです。まるで、私たち全員が、極端な不動点の一つを覆い隠す共通の盲点を持っているかのようです。 単純な例は、デッドバリュー（不要な変数）の除去です。プログラム中のそのような変数をどのように特定するかを人々に尋ねると、素朴な解決策は非常に似通ったものになる傾向があります。それらは、ある値がそれ自体不要な値の計算にのみ使用されている場合に、その値は不要であるという観察を利用します。ルーチンは、すべての値をライブ（使用されている）と仮定して開始し、不要な値を削除していきます。削除できるものがなくなるまで続けます。これらのアルゴリズムは、正しいが最適ではない（サイクルフリーのコードを除く）解に収束します。私たちは、可能な限り多くの不要な値を特定し、可能な限り多くの計算を削除したいと考えています。しかし、もしすべての値をライブと仮定して開始した場合、私たちのアルゴリズムは、次のようなコードの x のような、明らかに不要な値を特定することに失敗します。 for (...) x = x さらに特殊なケースを追加し続けることもできます。しかし、正しい（最も単純な）解決策は、デッドな値ではなく、ライブな値を特定しようとすることです。ある値は、ライブな値の計算に使用されている場合にライブです。さらに、戻り値やメモリへの書き込みは常にライブです。私たちのルーチンは、これらの後者の値のみがライブであると仮定して開始し、ライブな値が見つかるにつれてそれらを付加していきます。この場合、直感的な解決策は最大の不動点に収束しますが、私たちは最小の不動点を探しています。適切な初期値を設定することで、正しい不動点への収束が保証されます。このパターンの他の一般的な例としては、マーキングの代わりに参照カウントを行うことや、すべての値にトップタイプ（SBCLのようなもの）を初期割り当ててタイプ伝播を実行することなどが挙げられます。 私は最近、数学やコンピュータサイエンスの外部で不動点計算の用途を見つけました。ケベック州のほとんどの大学やCEGEPの学生組合は、この冬と春に大学の授業料の値上げに対する抗議を組織するために、ストライキの権限委任について投票する（またはすでに投票した）でしょう。州全体に数百のそのような組合があり、合計で約40万人の学生を代表しています。これらの組合の大多数は数百人（またはそれ以下）の学生で構成されており、少数の学生だけがストライキを行うのは逆効果だと感じる組合も多くあります。したがって、ストライキの権限委任には、他の学生がストライキの権限委任を保持している最小数、および関与する組合と大学またはカレッジの数に関する追加の下限に関する条件が一般的に含まれています。私の知る限り、これまでに採択されたすべての権限委任は単調です。すなわち、ストライキ組合の集合によって満たされる場合、そのすべての超集合によっても満たされます。タルスキの定理が適用されます（ここでも、学生組合の集合のべき集合上の (⊂, ∪, ∩) です）。どの不動点を探しているのでしょうか？ 私にとって明らかなのは、ストライキを行う学生組合の最大の集合を持つ不動点を探しているということです。状況によっては、最小の不動点は自明に空集合（または下限をまったく採用しなかったすべての組合）になる可能性があります。さらに、権限委任は通常、たとえば、少なくとも n0 人の学生を代表する組合が同じ権限委任を採用した場合、その権限委任を採用したすべての組合が同時にストライキを行うという説明とともに提示されます。私はコンピュータサイエンスの大学院生仲間に、彼らの権限委任を与えられたときにどの組合がストライキを行うべきかを決定するアルゴリズムをスケッチするように依頼しました。彼らは現在ストライキ中の学生組合の集合から開始し、すべての条件が満たされた組合を付加しました。そのようなアルゴリズムは最小の不動点に向かって収束します。例えば、それぞれ5,000人の学生で構成され、同じ10,000人のストライキフロアを持つ2つの組合がある場合、これらのアルゴリズムは両方の組合を、もう一方がストライキを行うのを待ってデッドロック状態にするでしょう。代わりに、私たちは（ストライキの権限委任を持つ）すべての組合がストライキを行っていると仮定して開始し、すべての条件が満たされていない組合を繰り返し削除していき、最大の不動点に到達するまで続けるべきです。これが純粋に理論的な懸念になるだろうと私は確信していますが、抽象数学が現実世界の状況を解釈するのに役立つ pretty neat なケースです。最適でない解に直感的に収束するこのパターンは、不動点を計算する際にしばしば現れるようです。それは必ずしも悪い選択ではありません。保守的な初期値は、より速い収束につながる傾向があり、中間的な解が常に正しい（実行可能である）という特性を持つことがよくあります。迅速な結果が必要な場合、最適でない解で妥協することが理にかなっているかもしれません。しかし、それは他の可能性を考慮できなかった結果ではなく、意図的な選択であるべきです。