ループを確実にする仕組み

Question

私は大学にいたときに、David Parnasのゲスト講義を受けました。その中で、ループ（whileループ、forループなど）がある時点で安全に終了することを保証するために使用されるメカニズムについて述べました。彼はそれが何であるかを誰も知らなかったという事実を嘲笑した。悲しいことは何年も後に私はどちらも知らないということだ。誰がこのメカニズムが呼ばれているか知っていますか？

Answer 1

彼の専門分野（正当な正当な証明が含まれています）から判断すると、私は彼がloop variantを意味していると思います。これはループ終了を証明する一般的なテクニックです。

Answer 2

この質問は非公式です。

あなたが知っているポストコンディションを作る、つまりカウンターを増やしたり、ループ内のカウンターに触れたり、ヒットするのを最大限に抑えたりする以外に、ループが終了するようにするための装置はありません。

ループが長すぎるかどうかを確認するためにタイマーまたは別の構造を作成することもできます。

パルナスは何を意味していましたか？論理に干渉しない、または適切な事後条件を設計するだけのループへの普遍的な出口？

Answer 3

ループが無事に終了することを保証するために多くの方法があります。

1. は最高、
2. 他の人が真剣に運動し

として残されている無限大にそれを書いてはいけません安定した、完全にテストされた終了条件（つまり、別の反復または終了を実行するかどうかをチェックするコード）を持つことです。

あなたが説明した内容は、解決策のないよく知られた問題であるhalting problemに非常によく翻訳される可能性があります。

また、Google検索では、David Parnasがリムリック大学で働いていることが明らかになりました。あなたはそれらを呼び出して、彼と話をすることができます。私は彼があなたはまだ彼が戻ってあなたを教えから学ぶしようとしている:)

Answer 4

あなたのゲスト講師は、Cycle Detectionに無限ループを検出する方法を参照されている可能性があり嬉しくなると確信しています。

This blog postは、リンクリスト内の無限ループの検出を記述する。興味深いことに、Wikipediaの記事と同じ用語を使用しています。