구조화 프로그램 정리

Structured program theorem
NS 다이어그램(파란색)과 흐름도(녹색)를 사용하여 구조화된 프로그램 정리의 세 가지 기본 패턴(순서, 선택, 반복)을 그래픽으로 표현한다.

Böhm-Jacopini 정리라고도 불리는 구조화된 프로그램 정리는 프로그래밍 언어 이론의 결과물이다.[1][2] 그것은 제어 흐름 그래프(이 맥락에서 역사적으로 플로우차트라고 함)의 클래스가 세 가지 특정 방법(제어 구조)만으로 하위 프로그램을 결합하는 경우 계산 가능한 함수를 계산할 수 있다고 명시한다. 이것들은

  1. 한 하위 프로그램 실행 후 다른 하위 프로그램 실행(시퀀스)
  2. 부울식 값에 따라 두 개의 하위 프로그램 중 하나 실행(선택)
  3. 부울 식이 참인 경우 하위 프로그램을 반복 실행(이중)

그러나 이러한 제약조건을 따르는 구조화된 차트는 원래 프로그램이 프로그램 위치에 의해 나타내는 정보를 추적하기 위해 비트 형태의 추가 변수(원래 증명에서 추가 정수 변수에 저장)를 사용할 수 있다. 이 공사는 bm의 프로그래밍 언어 P′′에 근거한 것이었다.

그 정리는 구조화된 프로그래밍의 기초를 형성하는데, 이 프로그래밍 패러다임은 goto 명령을 회피하고 서브루틴, 시퀀스, 선택과 반복을 독점적으로 사용하는 것이다.

출처 및 변형

이 정리는 일반적으로 코라도 뫼와 주세페 자코피니에 의해 1966년 논문으로 인정된다[3]: 381 .[4] David Harrel은 1980년에 Böm-Jacopini 논문이 특히 구조화된 프로그래밍의 지지자들과 함께 "범용적인 인기"[3]: 381 를 누렸다고 썼다. Harel도 만들고, 신문 1980년까지 출판된 것이 큰 수를 검토한 후에, Harel은 Böhm–Jacopini 증거의 내용은 보통 본질적으로 s가 포함된 민속 정리로 잘못 그려져 있다고 주장했다는"그보다는 기술적인 스타일[는 1966년 Böhm–Jacopini 종이]때문에 것보다 더 자주 자세히 읽어 꼽았다"[3]:381지적했다rimpleresult, 그 자체로 폰 노이만과 클레네의 논문에서 현대 컴퓨팅 이론의 시초까지 추적할 수 있는 결과.[3]: 383

하렐은 또한 보다 일반적인 이름이 H.D.에 의해 제안되었다고 쓰고 있다. 1970년대 초 "구조 정리"로서의 밀스.[3]: 381

단시간 루프, 민속 버전의 정리

이 정리의 버전은 모든 원본 프로그램의 제어 흐름을 단일 글로벌로 대체한다. while 프로그램 카운터를 시뮬레이션하여 원래 비필수 프로그램의 가능한 모든 라벨(플로우차트 상자)을 살펴보는 루프. 하렐은 이 민중 정리의 기원을 추적하여 계산의 시작을 알리는 두 장의 논문에서 찾아냈다. 하나는 1946년 폰 노이만 건축에 대한 설명으로, 프로그램 카운터가 어떻게 작동하는지 잠시의 루프 관점에서 설명한다. 헤럴은 구조화된 프로그래밍 정리의 민속 버전에 의해 사용되는 단일 루프는 기본적으로 폰 노이만 컴퓨터에서 플로우차트의 실행을 위한 운영 의미론을 제공한다고 언급한다.[3]: 383 헤럴이 민속적인 정리 버전을 추적한 또 다른, 더 오래된 출처는 1936년부터의 스테판 클레네의 정상적인 형태 정리다.[3]: 383

도날드 크누스는 이러한 형태의 증명이 아래와 같은 유사문서로 귀결되는데, 이는 원본 프로그램의 구조가 이 변혁에서 완전히 상실된 것이라고 지적하며 비판했다.[5]: 274 마찬가지로 브루스 이안 밀스는 이 접근법에 대해 "블록구조의 정신은 언어가 아니라 스타일이다. Von Neumann 기계를 시뮬레이션함으로써, 우리는 블록 구조 언어의 범위 내에서 어떤 스파게티 코드의 동작을 생산할 수 있다. 그렇다고 스파게티가 되는 것을 막을 수는 없다."[6] 

p := 1 하는 동안에 p > 0 하다     만일 p = 1 그때         공연하다 스텝을 밟다 1 로부터 그 순서도         p := 결과로 초래된 후계자 스텝을 밟다 번호를 붙이다 의 스텝을 밟다 1 로부터 그 순서도 (0 만일 아니요. 후계자)     종지부를 찍다 만일     만일 p = 2 그때         공연하다 스텝을 밟다 2 로부터 그 순서도         p := 결과로 초래된 후계자 스텝을 밟다 번호를 붙이다 의 스텝을 밟다 2 로부터 그 순서도 (0 만일 아니요. 후계자)     종지부를 찍다 만일     ...     만일 p = n 그때         공연하다 스텝을 밟다 n 로부터 그 순서도         p := 결과로 초래된 후계자 스텝을 밟다 번호를 붙이다 의 스텝을 밟다 n 로부터 그 순서도 (0 만일 아니요. 후계자)     종지부를 찍다 만일 종지부를 찍다 하는 동안에

밥과 자코피니의 증거

Böhm과 Jacopini의 논문에 있는 증명은 흐름도의 구조에 대한 유도에 의해 진행된다.[3]: 381 그래프에 패턴 매칭을 채택했기 때문에, Böm과 Jacopini의 증명은 프로그램 변환 알고리즘으로서 실제로 실용적이지 못했기 때문에, 이러한 방향으로 추가 연구의 문을 열었다.[7]

시사점 및 개선점

Böhm-Jacopini 증명서는 소프트웨어 개발을 위해 구조화된 프로그래밍을 채택해야 하는지에 대한 문제를 해결하지 못했다. 부분적으로는 그 구조가 프로그램을 개선하기보다는 모호하게 만들 가능성이 높았기 때문이다. 오히려 토론의 시작을 알리는 신호탄이었다. 에드거 디크스트라의 유명한 편지인 "해롭다고 여겨지는 진술로 가라"가 1968년에 그 뒤를 이었다.[8]

일부 학자들은 Böhm-Jacopini 결과에 대해 청교도적인 접근법을 취했고 심지어 다음과 같은 명령도 있다고 주장했다. break 그리고 return 복음-자코피니 교정에서는 필요 없기 때문에 루프의 중간부터 잘못된 관행이므로, 모든 루프는 하나의 출구 지점을 가져야 한다고 주장했다. 이러한 순수주의적 접근방식은 파스칼 프로그래밍 언어(1968-1969년 설계)로 구체화되어 있으며, 1990년대 중반까지는 학계의 입문 프로그래밍 수업을 가르치기 위한 선호 도구였다.[9]

Edward Yourdon은 1970년대에 구조화되지 않은 프로그램을 자동화된 수단에 의해 구조화되지 않은 프로그램으로 바꾸는 것에 대한 철학적 반대도 있었다고 지적한다. 실용적인 대안은 그러한 변화들이 많은 기존 프로그램들에게 혜택을 주었다는 것이다.[10] 자동화된 변혁을 위한 첫 번째 제안 중에는 에드워드 애쉬크로프트와 조하르 마나의 1971년 논문이 있었다.[11]

Böhm-Jacopini 정리를 직접 적용하면 구조화된 차트에 추가 국지 변수가 도입될 수 있으며, 일부 코드가 중복될 수도 있다.[12] 후자 문제는 이런 맥락에서 루프와 반쪽 문제라 불린다.[13] 파스칼은 이 두 가지 문제 모두에 의해 영향을 받고 있으며 에릭 S가 인용한 경험적 연구에 의하면 영향을 받는다. 로버츠, 학생 프로그래머들은 배열에서 요소를 검색하는 함수를 쓰는 것을 포함한 몇 가지 간단한 문제들에 대해 파스칼에서 정확한 해결책을 만드는 데 어려움을 겪었다. 로버츠가 인용한 헨리 샤피로의 1980년 연구는 파스칼이 제공한 제어 구조만 사용했을 때, 대상자의 20%만이 정확한 해결책을 제공했지만, 루프의 중간에서 반품을 쓸 수 있다면 어떤 대상도 이 문제에 대해 잘못된 코드를 쓰지 않았다는 것을 발견했다.[9]

1973년, S. 라오 코사라주는 임의의 깊이의 루프로부터의 다단계 브레이크가 허용되는 한, 구조화된 프로그래밍에서 추가적인 변수를 추가하는 것을 피할 수 있다는 것을 증명했다.[1][14] 나아가 코사라주는 모든 정수 n에 대해 (추가 변수를 도입하지 않고) n 이하의 다단계 깊이를 가진 프로그램으로 다시 쓸 수 없는 다단계 깊이 n을 포함하는 프로그램이 존재한다는 점에서 오늘날 코사라주 계층이라고 불리는 엄격한 프로그램 계층이 존재함을 증명했다.[1] 코사라주는 BLISS 프로그래밍 언어의 다단계 브레이크 구조를 인용한다. 다단계 구분, 형식: leave label 키워드는 실제로 그 언어의 BLISS-11 버전에 소개되었다; 원래 BLISS는 단단계 휴식만을 가졌다. BLISS 언어군은 무제한의 허가를 제공하지 않았다. 자바 프로그래밍 언어도 나중에 이 접근법을 따를 것이다.[15]: 960–965

코사라주 논문의 보다 간단한 결과는 프로그램이 두 개의 뚜렷한 출구가 있는 루프를 포함하지 않는 경우에만 (변수를 추가하지 않고) 구조화된 프로그램으로 축소될 수 있다는 것이다. 환원성은 코사라주(Kosaraju)에 의해 느슨하게 말하면, 동일한 기능을 계산하고 원래 프로그램과 같은 "원리 작용"을 사용하며 술어를 사용하지만, 아마도 다른 제어 흐름 구조를 사용하는 것으로 정의되었다. (Böhm-Jacopini가 사용한 것보다 축소성에 대한 좁은 개념이다.) 이러한 결과에 영감을 받아, 사이클로매틱 복잡성의 개념을 도입한 그의 고도로 작성된 논문 6절에서, 토마스 J. 매카베는 쿠라토프스키의 비구조적 프로그램의 제어 흐름 그래프(CFG)에 대한 정리, 즉 프로그램의 CFG를 비구조적으로 만드는 최소한의 서브그래프(subgraph)의 아날로그에 대해 기술했다. 이 서브그래프들은 자연어로 매우 훌륭한 묘사를 가지고 있다. 다음 구성 요소:

  1. 루프에서 분기(루프 사이클 테스트 제외)
  2. 고리로 분기하여.
  3. 결정으로 분기(즉, if "f"로 분기)
  4. 결정에서 분기하여.

McCabe는 실제로 하위 그래프로 나타날 때 이 네 개의 그래프가 독립적이지 않다는 것을 발견했는데, 이는 프로그램이 구조화되지 않기 위한 필요하고도 충분한 조건이 CFG가 이 네 개의 그래프 중 세 개의 하위 집합 중 하나를 하위 그래프로 갖는다는 것을 의미한다. 그는 또한 만약 비구조화 프로그램이 이 네 개의 하위 그래프 중 하나를 포함하고 있다면, 그것은 네 개의 그래프 세트와 또 다른 구별되는 것을 포함해야 한다는 것을 발견했다. 이 후자의 결과는 구조화되지 않은 프로그램의 제어 흐름이 어떻게 흔히 "스파게티 코드"라고 불리는 것에 얽히게 되는지 설명하는 데 도움이 된다. McCabe는 또한 임의의 프로그램이 구조화된 프로그램의 이상과 얼마나 멀리 떨어져 있는지를 수량화하는 수치적 측정을 고안했다. McCabe는 그의 측정이 본질적인 복잡성이라고 말했다.[16]

구조화 프로그래밍을 위해 금지된 그래프의 맥케이브의 특성화는 최소한 Dijkstra의 D 구조가 구성 블록으로 간주된다면 불완전한 것으로 간주될 수 있다.[17]: 274–275 [clarification needed]

1990년까지 기존 프로그램에서 gotos를 제거하는 동시에 대부분의 구조를 보존하는 방법을 제안하는 경우가 꽤 있었다. 또한 이 문제에 대한 다양한 접근방식은 위에서 논의한 민속 정리처럼 출력을 피하기 위해 단순한 튜링 등가성보다 엄격한 등가성의 여러 개념을 제안했다. 선택된 동등성 개념의 엄격성은 필요한 최소한의 제어 흐름 구조를 지시한다. Lyle Ramshaw가 쓴 1988년 JACM 논문은 그 시점까지 그 분야를 조사하고 있으며, 또한 그 나름대로의 방법을 제안하고 있다.[18] 램쇼의 알고리즘은 예를 들어 일부 자바 디컴파일러에서 사용되었는데, 이는 자바 가상 머신 코드에 오프셋으로 표현되는 대상이 있는 분기 명령이 있기 때문이지만, 고수준 자바 언어는 다단계만 가지고 있기 때문이다. break 그리고 continue 진술서[19][20][21] 암마르구엘라트(1992)는 싱글 엑시트 시행으로 거슬러 올라가는 변환 방법을 제안했다.[7]

코볼에 적용

1980년대 IBM 연구원인 할란 밀스는 COBOL 코드에 구조 알고리즘을 적용한 COBOL 구조설비의 개발을 감독했다. 밀스의 변신은 각 절차에 대해 다음과 같은 단계를 수반했다.

  1. 절차의 기본 블록을 식별하십시오.
  2. 각 블록의 진입 경로에 고유한 레이블을 할당하고 각 블록의 출구 경로에 연결된 진입 경로의 레이블로 레이블을 지정하십시오. 절차에서 반환하려면 0을 사용하고 절차의 진입 경로에는 1을 사용하십시오.
  3. 절차를 기본 블록으로 구분하십시오.
  4. 하나의 출구 경로의 대상인 각 블록에 대해 해당 블록을 해당 출구 경로에 다시 연결하십시오.
  5. 절차에서 새 변수를 선언하십시오(참조용으로 L이라고 함).
  6. 연결되지 않은 각 나머지 출구 경로에서 L을 해당 경로의 레이블 값에 설정하는 문을 추가하십시오.
  7. L로 표시된 진입 경로 라벨과 프로그램을 실행하는 선택 문으로 결과 프로그램을 결합한다.
  8. L이 0이 아닌 한 이 선택문을 실행하는 루프를 생성한다.
  9. L to 1을 초기화하고 루프를 실행하는 시퀀스를 생성한다.

이 구조는 선택문의 일부 사례를 하위 절차로 변환하여 개선할 수 있다는 점에 유의하십시오.

참고 항목

참조

  1. ^ a b c Dexter Kozen and Wei-Lung Dustin Tseng (2008). The Böhm–Jacopini Theorem Is False, Propositionally (PDF). Mpc 2008. Lecture Notes in Computer Science. Vol. 5133. pp. 177–192. CiteSeerX 10.1.1.218.9241. doi:10.1007/978-3-540-70594-9_11. ISBN 978-3-540-70593-2.
  2. ^ "CSE 111, Fall 2004, BOEHM-JACOPINI THEOREM". Cse.buffalo.edu. 2004-11-22. Retrieved 2013-08-24.
  3. ^ a b c d e f g h Harel, David (1980). "On Folk Theorems" (PDF). Communications of the ACM. 23 (7): 379–389. doi:10.1145/358886.358892.
  4. ^ Bohm, Corrado; Giuseppe Jacopini (May 1966). "Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules". Communications of the ACM. 9 (5): 366–371. CiteSeerX 10.1.1.119.9119. doi:10.1145/355592.365646.
  5. ^ Donald Knuth (1974). "Structured Programming with go to Statements". Computing Surveys. 6 (4): 261–301. CiteSeerX 10.1.1.103.6084. doi:10.1145/356635.356640.
  6. ^ Bruce Ian Mills (2005). Theoretical Introduction to Programming. Springer. p. 279. ISBN 978-1-84628-263-8.
  7. ^ a b Ammarguellat, Z. (1992). "A control-flow normalization algorithm and its complexity". IEEE Transactions on Software Engineering. 18 (3): 237–251. doi:10.1109/32.126773.
  8. ^ Dijkstra, Edsger (1968). "Go To Statement Considered Harmful". Communications of the ACM. 11 (3): 147–148. doi:10.1145/362929.362947. Archived from the original on 2007-07-03.
  9. ^ a b 로버츠, E. [1995] "루프 출구 및 구조화된 프로그래밍: 토론 재개", ACM SIGCSE 게시판, (27)1: 268–272.
  10. ^ E. N. Yourdon (1979). Classics in Software Engineering. Yourdon Press. pp. 49–50. ISBN 978-0-917072-14-7.
  11. ^ Ashcroft, Edward; Zohar Manna (1971). "The translation of go to programs to 'while' programs". Proceedings of IFIP Congress. 배포가 제한되어 원래의 회의 절차에서 얻기 어려운 이 논문은 1979년 유돈의 책 페이지 51-65에 다시 게재되었다.
  12. ^ David Anthony Watt; William Findlay (2004). Programming language design concepts. John Wiley & Sons. p. 228. ISBN 978-0-470-85320-7.
  13. ^ Kenneth C. Louden; Kenneth A. Lambert (2011). Programming Languages: Principles and Practices (3 ed.). Cengage Learning. pp. 422–423. ISBN 978-1-111-52941-3.
  14. ^ 코사라주, S. RAO. "구조화된 프로그램의 분석", Proc. 다섯 번째 연간 ACM 시럽. 컴퓨팅의 이론,(도 될까 1973년), 240-252;또한 Kosaraju, S.Rao(1974년)."구조화된 프로그램 분석".저널 컴퓨터 및 시스템 과학원.9:232–255. doi:10.1016(74)80043-7. 도널드 크누스에 의해 인용된(1974년)."공업화 프로그래밍 재표에로 가자".조사 결과 추가하십시오.6(4):261–301.CiteSeerX 10.1.1.103.6084. doi:10.1145/356635.356640.
  15. ^ Brender, Ronald F. (2002). "The BLISS programming language: a history" (PDF). Software: Practice and Experience. 32 (10): 955–981. doi:10.1002/spe.470.
  16. ^ 원본은 2차 박람회용이다.
  17. ^ Williams, M. H. (1983). "Flowchart Schemata and the Problem of Nomenclature". The Computer Journal. 26 (3): 270–276. doi:10.1093/comjnl/26.3.270.
  18. ^ Ramshaw, L. (1988). "Eliminating go to's while preserving program structure". Journal of the ACM. 35 (4): 893–920. doi:10.1145/48014.48021.
  19. ^ Godfrey Nolan (2004). Decompiling Java. Apress. p. 142. ISBN 978-1-4302-0739-9.
  20. ^ https://www.usenix.org/legacy/publications/library/proceedings/coots97/full_papers/proebsting2/proebsting2.pdf
  21. ^ http://www.openjit.org/publications/pro1999-06/decompiler-pro-199906.pdf

추가 읽기

아직 위에서 다루지 않은 재료: