같은 것을 알아내는 방법

Ailrun (UTC-5/-4) @ailrun@hackers.pub
같은 것과 같지 않은 것
국밥 두 그릇의 가격이 얼마인가? KTX의 속력이 몇 km/h인가? 내일 기온은 몇 도인가? 일상에서 묻는 이런 질문은 항상 같음의 개념을 암시적으로 사용하고 있다. 앞의 예시를 보다 명시적으로 바꾼다면 아래와 같이 (다소 어색하게) 말할 수 있다.
- 국밥 두 그릇의 가격은 몇 원과 같은가?
- KTX의 속력은 몇 km/h와 같은가?
- 내일 기온은 몇 도와 같은가?
이런 질문들의 추상화인 이론들은 자연스럽게 언제 무엇과 무엇이 같은지에 대해서 답하는 데에 초점을 맞추게 된다. 예를 들면
의 실수 해의 갯수는 0과 같다. - 물 분자 내의 수소-산소 연결 사이의 각도는 104.5도와 같다.
- 합병 정렬의 시간 복잡도는
과 같다.
등이 있다. 이렇게 어떤 두 대상이 같은지에 대해서 이야기를 하다보면 반대로 어떤 두 대상이 같지 않은지에 대해서도 이야기하게 된다. 즉,
를 로 나눈 나머지는 을 로 나눈 나머지와 같지 않다. - 연결 리스트(Linked List)와 배열(Array)은 같지 않다.
- 함수
와 정수 는 같지 않다.
같은 것과 판정 문제(Decision Problem)
이제 컴퓨터 과학(Computer Science)과 프로그래밍(Programming)에 있어 자연스러운 의문은 "두 대상이 같은지 아닌지와 같은 답을 주는 알고리즘(Algorithm)이 있나?"일 것이다. 다시 말해서 두 대상
- 알고리즘이 참 값(
)을 준다면 와 가 같고 - 알고리즘이 거짓 값(
)을 준다면 와 가 같지 않은
알고리즘이 있는지 물어볼 수 있다. 이런 어떤 명제가 참인지 거짓인지 판정하는 알고리즘의 존재 여부에 대한 질문을 "판정 문제"("Decision Problem")라고 하며, 명제
이 질문에 대한 대답은 당연하게도 어떤 대상을 어떻게 비교하는지에 따라 달라진다. 예를 들어 우리가 32 비트(bit) 정수에 대해서만 이야기하고 있다면 "임의의 32 비트 정수
그렇다면 어떤 대상의 어떤 비교에 대해 판정 문제를 물어보아야할까? 프로그래머(Programmer)로서 명백한 대답은 두 프로그램(Program)이 실행 결과에 있어서 같은지 보는 것일 것이다. 그러나 앞서 자연수를 받아 자연수를 내놓는 함수에 대해 말했던 것과 비슷하게 두 프로그램의 실행 결과를 완벽하게 비교하는 알고리즘은 존재하지않는다. 이는 우리가 두 프로그램의 같음을 판정하고 싶다면 그 같음을 비교하는 방법에 제약을 두어야 함을 말한다. 여기서는 다음의 두 제약을 대표로 설명할 것이다.
- 문법적 비교(Syntactic Comparison)
동등성 ( Equivalence)
1. 문법적 비교(Syntactic Comparison)
이 방법은 말 그대로 두 프로그램이 문법 수준에서 같은지를 보는 것이다. 예를 들어 다음의 두 JavaScript 프로그램은 문법적으로 같은 프로그램이다.
// 1번 프로그램
let x = 5;
console.log(x);
// 2번 프로그램
let x = 5;
console.log( x );
공백문자의 사용에서 차이가 있으나, 그 외의 문법 요소는 모두 동일함에 유의하자. 반면 다음의 두 JavaScript 프로그램은 동일한 행동을 하지만 문법적으로는 다른 프로그램이다.
// 1번 프로그램
let x = 5;
console.log(x);
// 2번 프로그램
let x = 3 + 2;
console.log(x);
두 프로그램 모두 x
에 5
라는 값을 할당하고 5
를 콘솔에 출력하나, 첫번째 프로그램은 = 5;
를, 두번째 프로그램은 = 3 + 2
을 사용하여 5
를 할당하고 있기 때문에 문법적으로 다르다.
문법적 비교는 이렇게 문법만 보고서 쉽게 판정할 수 있다는 장점이 있으나, 두번째 예시처럼 쉽게 같은 행동을 함을 이해할 수 있는 프로그램에 대해서도 "같지 않음"이라는 결과를 준다는 단점을 가진다. 혹자는
3 + 2
같은 계산은 그냥 한 다음에 비교하면 안돼? 컴파일러(Compiler)도 상수 전파(Constant Propagation) 최적화라던지로3 + 2
를5
로 바꾸잖아?
라는 생각을 할 수도 있을 것이다. 이 제안을 반영한 방법이 바로
2. 동등성
바로 앞의 소절에서 단순 계산의 추가에 의해 같음이 같지 않음으로 변하는 것을 보았다. 이런 상황을 피하기 위해서는 같음을 평가할 때 프로그램의 실행을 고려하도록 만들어야 한다. 가장 대표적인, 대부분의 프로그래밍 언어(Programming Language)에 존재하는 프로그램의 실행은 함수 호출이다. 따라서 함수 호출을 고려한 같음의 비교는 f(c)
와 함수 f
의 몸체 b
안에서 인자 x
를 c
로 치환한 것을 같다고 취급해야한다. 예를 들어
let f = (x) => x + 3;
이 있다면, f(5)
와 5 + 3
혹은 8
을 같은 프로그램으로 취급해야한다. 이 비교 방법의 큰 문제는 함수가 종료하는지 알지 못한다는 것이다. 두 프로그램 a
와 b
를 비교하는데, a
가 종료하지 않는 함수 l
을 호출한다면, 이 알고리즘은 "같음"이나 "같지 않음"이라는 결과를 낼 수조차 없다. 즉, 올바른 판정법이 될 수 없다.
더 심각한 문제는 아직 값을 모르는 변수가 있는 "열린 프로그램"("Open Program")에 대해서도 이런 계산을 고려해야한다는 것이다. 다음의 JavaScript 예시를 보자.
let g = (x) => f(x) + 3;
let h = (x) => (x + 3) + 3;
g
와 h
는 같은 프로그램일까? 우리가 g
와 h
가 같은 프로그램이기를 원한다면 f(x)
와 x + 3
을 같은 프로그램으로 보아야한다. 대부분의 프로그램은 함수 안에서 쓰여지기 때문에 프로그램의 비교는 거의 항상 g
와 h
의 몸체와 같은 열린 프로그램들의 비교이다. 따라서 g
와 h
를 다른 프로그램으로 본다면 계산을 실행하여 두 프로그램을 비교하는 의미가 퇴색되고 만다. 그렇기 때문에 우리는 x
와 같이 값이 정해지지 않은 변수가 있을 때에도 f(x)
을 호출하여 비교해야만 한다. 이는 우리가 단순히 모든 함수가 종료하는지 여부를 떠나서, 함수의 몸체에 등장하는 모든 부속 프로그램(Sub-program)이 종료하는지 아닌지를 따져야만 한다는 이야기이다.
이런 강한 제약조건으로 인해
의존 형이론과 형의 같음
의존 형이론은 형(Type)에 임의의 프로그램을 포함할 수 있도록 하는 형이론(Type Theory)의 한 종류이다. 예를 들어 명시적인 길이(n
)를 포함한 벡터(Vector) 형을 Vector n Int
과 같이 쓸 수 있다. 이 형은 n
개의 Int
값을 가진 벡터를 표현하는 형이다. 이제 append
라는 두 벡터를 하나로 연결하는 함수를 만든다고 해보자. 대략 다음과 같은 형을 쓸 수 있을 것이다.
append : Vector n a -> Vector m a -> Vector (n + m) a
즉, append
는 길이 n
짜리 a
형의 벡터와 길이 m
짜리 a
형의 벡터를 합쳐서 길이 n + m
짜리 a
형의 벡터를 만드는 함수이다. 이 함수를 사용해서 길이 5
의 벡터를 길이 2
와 길이 3
짜리 벡터 x
, y
로부터 만들고 싶다고 하자.
append x y : Vector (2 + 3) a
안타깝게도 우리는 길이 2 + 3
짜리 벡터를 얻었지, 길이 5
짜리 벡터를 얻진 못했다. 여기서 앞서의 질문이 다시 돌아온다.
아니,
2 + 3
를5
로 계산하면 되잖아?"
그렇다. 이런 의존 형에 Vector (2 + 3) a
과 Vector 5 a
는 같은 형이기 때문이다. 더욱이, 의존 형의 경우 종료하지 않는 부속 프로그램이 잘못된 형을 줄 수 있기 때문에 많은 경우 종료하지 않는 부속 프로그램을 어차피 포함하지 않는다. 다시 말해, 앞서 말한 제약 조건 즉 모든 부속 프로그램이 종료해야만 한다는 제약조건은 의존 형의 경우 상대적으로 훨씬 덜 심각한 제약조건이 되는 것이다.
이런 의존 형에 있어서의
마치며
이 글에서는 같음과 같지 않음의 판정 문제에 대해 간략히 설명하고 프로그램의 같음을 판정하는 법에 대해서 단순화하여 다루어보았다. 구체적으로는 문법 기반의 비교와
두 함수가 같다라고 보는 방법에 따라 다르나, 두 함수가 항상 같은 값을 가진다면 같다고 하자. 이때 함수의 판정 문제는 정지 문제(Halting Problem)와 동일하다. 임의의 튜링 기계(Turing Machine)
가 입력 을 받았을 때 종료하면 , 아니면 이라고 하면 이 함수 와 상수 함수 가 같은 함수임을 보이는 것은 가 항상 종료한다는 것을 보이는 것과 동등하기 때문이다. ↩︎