같은 프로그램을 다른 컴퓨터에서 실행해도 뜻은 같을까요?

사회자 기호가 다르면 값도 달라지나요?

답변 도서관 장부에 “3”, 다른 장부에 “11₂”, 또 다른 장부에 “1+2”라고 적어 봅시다. 표기법을 정하고 해석하면 세 표현은 같은 정수 3을 가리킵니다. 하지만 문자열 길이는 각각 다릅니다. 숫자를 관찰하는 일과 인쇄된 글자 수를 관찰하는 일은 다른 질문입니다. 프로그램도 먼저 무엇을 뜻으로 볼지 정해야 합니다. 여기서는 실행 시간이나 메모리 주소가 아니라 정수 입력과 종료 결과를 비교합니다. 기계가 다르다는 이유만으로 결과 의미가 달라지는 것도 아니고, 화면 결과 하나가 같다는 이유만으로 모든 입력에서 같아지는 것도 아닙니다.

사회자 문장을 조립하듯 뜻도 조립해 볼까요?

답변 I(x)=x+1, D(x)=2x를 두겠습니다. “증가한 뒤 두 배”라는 문장 I;D의 뜻은 D(I(x))=2x+2입니다. “두 배 한 뒤 증가”인 D;I는 I(D(x))=2x+1입니다. 두 문장은 같은 부품을 쓰지만 결합 순서가 다릅니다. x=4를 넣으면 첫 문장은 10, 둘째 문장은 9입니다. 합성성은 부품을 아무렇게나 섞어도 된다는 뜻이 아닙니다. 구문이 지정한 구조에 맞춰 이미 정한 부품의 뜻을 조립한다는 조건입니다. 실험 1에서 두 명령의 중간 값까지 읽으면 이 차이를 확인할 수 있습니다.

사회자 한 칸을 고치면 다른 칸도 바뀌나요?

답변 상태를 (x,y)=(2,9)라고 적고 x:=x+1을 실행합시다. 이 명령의 규칙은 x만 바꾸므로 결과는 (3,9)입니다. y를 보존한다는 조건도 의미의 일부입니다. x만 적힌 출력 화면에 3이 보였다고 해서 y가 보존됐다는 사실까지 확인한 것은 아닙니다. 전체 상태를 비교하려면 y도 읽어야 합니다. 이 글의 화면 실험은 정수 x 한 개만 다룹니다. 두 변수 예는 상태의 범위를 설명하기 위한 별도 손계산입니다. 실제 대출 권수에 음수가 없더라도 실험에서는 함수 비교를 위해 음의 정수도 허용합니다.

사회자 이름의 뜻을 바꾸는 것과 저장된 값을 바꾸는 것은 어떻게 다른가요?

답변 첫 패널에서는 ρ(bump)=I로 두고 bump를 실행합니다. I(x)=x+1이므로 x=3이 4가 됩니다. 같은 이름을 ρ′(bump)=D로 다시 연결하면 같은 입력 3에서 6을 얻습니다. 이것은 이름이 가리키는 명령의 뜻을 바꾼 경우입니다. 둘째 패널은 다른 교육용 모형입니다. 이름 x가 위치 L7을 가리키고 저장소의 L7 값이 3이라면, L7의 값을 4로 고쳐도 이름이 가리키는 위치는 그대로입니다. 두 패널은 서로 다른 대응 관계를 보여 줍니다. 원전의 명령 환경을 곧바로 메모리 주소표라고 부르면 안 되는 이유입니다.

사회자 다른 칸을 바꾸는 명령이면 순서를 바꿔도 괜찮나요?

답변 서로 다른 칸에 쓴다는 사실만으로는 부족합니다. (x,y)=(1,2)에서 x:=y 뒤에 y:=x를 실행하면 먼저 (2,2)가 되고 끝까지 (2,2)입니다. 순서를 바꾸면 첫 명령 y:=x 뒤에 (1,1)이 되고 마지막도 (1,1)입니다. 두 명령은 상대가 바꾼 칸을 읽기 때문에 결과가 달라집니다. 반면 x:=x+1과 y:=y+1은 서로의 칸을 읽지 않으므로 이 정수 모형에서 순서를 바꿔도 (2,3)입니다. 부작용·오류·공유 위치가 없는 지금의 조건을 벗어나면 다시 따져야 합니다.

사회자 조건이 거짓일 때도 두 분기를 모두 실행하나요?

답변 “x<3이면 x에 1을 더하고, 아니면 그대로 둔다”고 정합시다. x=2에서는 조건이 참이므로 3, x=4에서는 거짓이므로 4입니다. 고르지 않은 분기는 실행하지 않습니다. 이 예의 조건은 x를 읽기만 합니다. 만약 조건 검사 자체가 방문 횟수를 늘린다면 조건 평가 뒤의 상태를 선택한 분기에 전달해야 합니다. 같은 참·거짓 값이 나왔다고 상태까지 같다고 할 수 없습니다. 여기서는 그런 부작용 조건을 구현하지 않았으므로 실제 언어의 조건 평가 전체를 실험 결과로 보증하지 않습니다.

사회자 반복 전체를 한 번 더 펼치면 무엇이 보이나요?

답변 W를 while x<3 do x:=x+1의 뜻이라고 합시다. 입력 x가 3 이상이면 W(x)=x입니다. 입력 x가 3보다 작으면 한 번 증가한 x+1에서 나머지 반복을 수행하므로 W(x)=W(x+1)입니다. x=1을 넣으면 W(1)=W(2)=W(3)=3이 됩니다. 이 식은 원하는 관계를 쓰지만, 모든 재귀식에서 그것만으로 유일한 답을 정하는 것은 아닙니다. 항상 참인 조건에 skip을 반복하면 식은 W(x)=W(x)가 되어 아무 결과나 허용하는 듯 보입니다. 그래서 종료 정보를 근거 없이 더하지 않는 최소 해를 고르는 기준이 필요합니다.

사회자 w₀부터 직접 표를 채워 볼까요?

답변 w₀는 모든 입력에서 ⊥입니다. w₁은 조건이 이미 거짓인 입력만 반환합니다. 그래서 w₁(3)=3이지만 w₁(2)는 w₀(3)=⊥입니다. 다음 w₂(2)=w₁(3)=3, w₃(1)=w₂(2)=3, w₄(0)=w₃(1)=3이 됩니다. 입력 0에서는 본문을 세 번 실행하지만 결과를 알게 되는 근사 번호는 4입니다. 종료 조건을 확인하는 한 층이 필요하기 때문입니다. 반대로 입력 4는 본문을 한 번도 실행하지 않지만 w₀(4)는 여전히 ⊥이고 w₁(4)=4입니다. 근사 번호를 실행 횟수라고 읽지 마세요.

사회자 팩토리얼도 밑에서부터 계산할 수 있나요?

답변 자연수 입력에 대해 f₀(k)=⊥, fₙ₊₁(0)=1, fₙ₊₁(k)=k·fₙ(k−1)(k>0)로 정합시다. ⊥에 수를 곱한 결과는 ⊥로 둡니다. f₁은 0의 결과 1만 알고, f₂는 1의 결과 1까지, f₃는 2의 결과 2까지, f₄는 3의 결과 6까지 압니다. 이 계산에서 음수 입력은 정의하지 않았습니다. 팩토리얼 표는 반복 근사와 같은 발상을 보여 주는 별도 예이며 화면의 while 실험에 숨겨진 기능은 아닙니다. 유한 표 몇 칸이 모든 재귀 함수의 수렴을 증명하지도 않습니다.

사회자 답이 같아도 느린 프로그램이 있을 수 있나요?

답변 P를 x:=x+2, Q를 x:=x+1; x:=x+1로 둡시다. 무한 정수 모형에서 모든 입력에 대해 둘 다 x+2를 냅니다. 단순히 명령문 한 개를 비용 1로 세면 P는 비용 1, Q는 비용 2입니다. 이 비용은 편집부가 정한 문장 수이며 실제 CPU 시간의 측정값이 아닙니다. 컴파일러가 두 프로그램을 같은 기계 명령으로 바꿀 수도 있습니다. 따라서 결과 의미가 같다는 증명과 어느 쪽이 빠른지의 측정은 다른 검증입니다. 같은 결과를 낸다는 이유만으로 더 싸거나 안전하다고 결론내리지 않습니다.

사회자 작은 호출 하나를 처음부터 끝까지 읽어 주세요.

답변 부작용 없는 값 전달 예로 f(a)=a+1, 호출 f(2+2)를 고릅시다. 먼저 인수 2+2를 계산해 4를 얻고, 매개변수 a에 값 4를 연결한 환경에서 몸체 a+1을 계산해 5를 얻습니다. 밖에 같은 이름 a=100이 있어도 이 예에서는 함수 안의 매개변수 a가 4를 가리킵니다. 반환 뒤 바깥 a는 100으로 남습니다. 이는 이름의 범위를 설명하려고 고른 단순한 규칙입니다. 실제 언어의 참조 전달·이름 전달·부작용·클로저 전체가 이 예 하나로 결정되지 않으며, PRG-6의 프로시저 공간 전체를 재현한 것도 아닙니다.

사회자 정수 뜻과 실제 기계의 실행을 어떻게 비교하나요?

답변 뜻을 I(n)=n+1로 정해도 컴퓨터가 무한한 정수를 한 번에 저장할 수 있다는 결론은 나오지 않습니다. 예를 들어 0부터 255까지만 담는 8비트 부호 없는 저장소를 택하고 넘치면 0으로 돌아간다고 정합시다. 입력 4에서는 수학식과 기계 모두 5를 냅니다. 입력 255에서는 수학식이 256을 내지만 이 기계 규칙은 0을 냅니다. 그러므로 입력 범위를 0..254로 제한하거나, 더 큰 정수 표현을 쓰거나, 넘침을 뜻에 포함해야 합니다. 어떤 선택을 했는지 없이 구현이 올바르다고 말할 수 없습니다. 그림은 비교해야 할 관계를 보여 주며 두 구현의 일치를 증명한 그림은 아닙니다.

사회자 화면에 x만 보여 주면 무엇을 놓치나요?

답변 P가 (x,y)를 (1,0)으로, Q가 (1,9)로 만드는 두 프로그램이라고 합시다. 화면에 x만 보여 주면 둘 다 1이므로 구별되지 않습니다. x와 y를 함께 관찰하면 곧바로 구별됩니다. 처음부터 최종 상태 전체가 같다고 정의했다면 P와 Q는 동치가 아닙니다. 제한된 화면에서 같아 보인다는 사실은 더 약한 명제입니다. 실험 2는 x만 가진 정수 상태와 다섯 입력이라는 두 가지 제한을 모두 사용합니다. 화면에서 “같다”고 읽을 때는 바로 옆에 적힌 그 범위를 함께 읽어야 합니다.

사회자 다섯 입력을 모두 통과해도 반례가 남을 수 있나요?

답변 P(x)=x, Q(x)=x가 3이면 4를 반환하고 그 밖에는 x를 반환한다고 정합시다. 시험 입력 −2,−1,0,1,2에서는 두 프로그램의 결과가 모두 같습니다. 그러나 입력 3에서는 P(3)=3, Q(3)=4입니다. 표의 모든 칸을 확인했다는 사실은 표 밖의 입력을 확인했다는 뜻이 아닙니다. 실험 2가 다섯 입력의 성공을 전체 정수 동치 증명이라고 부르지 않는 이유입니다. 반례 하나는 전칭 주장을 깨뜨릴 수 있지만, 성공한 사례를 많이 모았다는 것만으로 무한한 전칭 주장이 완성되지는 않습니다.

사회자 마지막으로 무엇을 실제로 확인한 셈인가요?

답변 정수 명령의 순서, 다섯 입력에서의 결과 비교, while 근사의 처음 다섯 층을 실제 계산했습니다. 각 결과는 명령의 규칙과 초기값에서 다시 계산할 수 있습니다. 별도 손계산에서는 환경의 종류, 교차 읽기, 팩토리얼 근사, 비용과 관찰 범위를 구별했습니다. 이 글을 읽고 확인할 질문은 “같다”라는 말 뒤에 어떤 입력·상태·종료·관찰 조건이 붙어 있는가입니다. 이 조건을 빠뜨린 채 실제 은행·시험·대출 시스템의 정확성을 보증해서는 안 됩니다. 작은 모형의 검산과 운영 시스템 검증은 각각 필요한 증거가 다릅니다.