3つの基本構造

ウィキペディア小見出し辞書

3つの基本構造

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/11 01:22 UTC 版)

「goto文」の記事における「3つの基本構造」の解説

「goto文有害説」は、ほとんどの場合、「構造化定理」（en:Structured program theorem）に結びつけて主張されたものだと信じられている。構造化定理は、 連接 (sequence): 文1; 文2 選択 (selection): if 式 then 文1 else 文2 fi 繰返し (iteration): do 文 od という、「3つの基本構造」によって、フローチャートで記述された計算可能な関数は、全て表現できる、というものである。この定理の意味する所は、チャーチ＝チューリングのテーゼと同じようなものである。すなわち、計算可能な関数について、それを計算するチューリングマシンを構成することもできるし、ラムダ計算によって計算することもできるし、帰納的関数として定義することもできる、といったことと同様に、フローチャートでも、あるいは「3つの基本構造」の組み合わせによってでも表現できる、ということである。 そのようにして表現されたものが人間にわかりやすいか否かについては触れられていないにもかかわらず、「この理論に従えばgotoを除去できる」（これは正しい）、「ゆえにわかりやすいプログラムになる」（これは正しくない）というのが、「goto文有害説」であるとして信じられるようになったため、そういったような記述がしばしば見られる。 構造化定理に従って「gotoの無いプログラム」に書き換えたプログラムが実際のところどのようなものであるのかは、英語版記事の en:Structured program theorem#Single-while-loop, folk version of the theorem に示されている。クヌースは「go to 文を用いた構造的プログラミング」の中で、これと同様のプログラムを示し「これですべての goto 文を除去できたわけであるが，実際にはすべての構造を失ってしまっている．」と述べ、構造化定理が示すことは、全くの「非構造化プログラミング」であることを警告した。