남자 또는 남자 테스트
Man or boy test남자 또는 남자 테스트는 컴퓨터 과학자인 Donald Knuth에 의해 ALGOL 60 프로그래밍 언어의 구현을 평가하기 위한 수단으로 제안되었습니다.이 테스트의 목적은 "재귀 및 로컬 이외의 참조"를 올바르게 구현한 컴파일러와 올바르게 구현되지 않은 컴파일러를 구별하는 것이었습니다.
ALGOL60 번역기는 재귀나 로컬 이외의 레퍼런스에 적절히 대응하도록 설계되어 있어, 작은 테스트 프로그램이 도움이 될지도 모른다고 생각했습니다.그래서 나는 다음과 같은 간단한 루틴을 작성했는데, 이는 man-compiler와 boy-compiler를 구분할 수 있다.
--
크누스의 예
ALGOL 60의 경우:
시작한다. 진짜 절차. A(k, x1, x2, x3, x4, x5); 가치 k; 정수 k; 진짜 x1, x2, x3, x4, x5; 시작한다. 진짜 절차. B; 시작한다. k := k - 1; B := A := A(k, B, x1, x2, x3, x4) 끝.; 한다면 k ≤ 0 그리고나서 A := x4 + x5 또 다른 B 끝.; 진품보다 뛰어나다(A(10, 1, -1, -1, 1, 0)) 끝.; 이것에 의해, 서로 참조하는B 콜 프레임의 트리가 작성되어 A 콜 프레임이 격납되어 있습니다.각 콜 프레임에는 관련된B가 호출될 때마다 변경되는k의 카피가 있습니다.서류상으로는 해결하려고 해도 성과가 없을 수 있지만, 원본 기사에서는 Knuth가 -67이라고 추측했지만 k = 10의 경우 정답은 -67입니다.참고[citation needed] 자료에서 언급된 찰스 H. 린지의 조사 기사에는 다양한 시작 값에 대한 표가 포함되어 있습니다.최신 머신도 아래 표에 나와 있는 k 값이 클 경우 스택 공간이 빠르게 고갈됩니다(OEIS: A132343).[2]
| k | |
|---|---|
| 0 | 1 |
| 1 | 0 |
| 2 | −2 |
| 3 | 0 |
| 4 | 1 |
| 5 | 0 |
| 6 | 1 |
| 7 | −1 |
| 8 | −10 |
| 9 | −30 |
| 10 | −67 |
| 11 | −138 |
| 12 | −291 |
| 13 | −642 |
| 14 | −1446 |
| 15 | - 3250 |
| 16 | −7244 |
| 17 | −16065 |
| 18 | −35601 |
| 19 | −78985 |
| 20 | - 175416 |
| 21 | - 389695 |
| 22 | - 865609 |
| 23 | -param362 |
| 24 | - 4268854 |
| 25 | - 9479595 |
| 26 | - 21051458 |
설명.
 |
컴파일러에서 올바르게 구현하기 어려운 세 가지 Algol 기능이 이 프로그램에서 사용됩니다.
- 중첩 함수 정의:B는 A의 로컬콘텍스트에서 정의되기 때문에 B의 본문은 A에 로컬한 기호(특히 k)에 액세스 할 수 있습니다.또한 이를 수정하는 것은 x1, x2, x3, x4 및 x5도 마찬가지입니다.이것은 Algol 하위 Pascal에서는 간단하지만 다른 주요 Algol 하위 C에서는 가능하지 않습니다(함수 간에 로컬 변수에 대한 포인터를 전달하고 C의 주소 연산자를 사용하여 메커니즘을 수동으로 시뮬레이션하지 않는 경우).
- 함수 참조:재귀 콜의 B
A(k, B, x1, x2, x3, x4)는 B에 대한 콜이 아니라 B에 대한 참조이며 k가 0보다 클 때만 호출됩니다.이것은 표준 Pascal(ISO 7185)과 C에서도 간단합니다.Pascal의 일부 변형(예: 이전 버전의 Turbo Pascal)은 절차 참조를 지원하지 않지만, 참조될 수 있는 함수 집합이 미리 알려진 경우(이 프로그램에서는 B만 해당) 이 문제를 해결할 수 있습니다. - 고정/기능 이중성:A의 x1 ~x5 파라미터는 숫자 상수 또는 함수 B에 대한 참조일 수 있습니다.
x4 + x5공식 파라미터 x4와 x5가 대응하는 실제 파라미터(이름에 의한 콜)로 대체된 것처럼 표현식은 양쪽 케이스를 처리할 수 있도록 준비해야 합니다.이것은 다이내믹하게 입력된 언어보다 스태틱하게 입력된 언어에서는 문제가 될 수 있지만, 표준적인 회피책은 A에 대한 메인콜의 상수 1, 0 및 -1을 이러한 값을 반환하는 인수가 없는 함수로 재해석하는 것입니다.
그러나 이것들은 테스트의 목적이 아닙니다.그것들은 테스트의 의미를 갖기 위한 전제 조건일 뿐입니다.테스트의 목적은 B에 대한 다른 참조가 올바른 B 인스턴스(참조를 작성한 B와 동일한 A 로컬 심볼에 액세스할 수 있는 인스턴스)로 해결되는지 여부입니다.예를 들어, "보이" 컴파일러는 B가 항상 최상위 A 콜 프레임에 액세스하도록 프로그램을 컴파일할 수 있습니다.
「 」를 참조해 주세요.
레퍼런스
- ^ Donald Knuth (July 1964). "Man or boy?". ALGOL Bulletin. 17: 7."AB17.2.4 Donald Knuth: Man or boy?, page 7". archive.computerhistory.org. 다음 항목도 참조하십시오.
- ^ Rosetta 코드 "Man or Boy Page"의 "Performance and Memory"를 참조하십시오.
외부 링크
- 많은 프로그래밍 언어로 남자 또는 남자 테스트 예시
