컴퓨터는 정직한 기계다.

입력을 주면 정해진 명령을 수행하고, 그 결과를 출력한다. 적어도 우리가 작성한 프로그램이 의도한 대로 동작한다는 가정 하에서는 그렇다.

그런데 가끔 이런 생각이 든다.

프로그램이 실행되기도 전에 문제가 발생할지 알아낼 수는 없을까?

생각해 보면 프로그램은 결국 코드다. 어떤 명령을 수행할지 코드에 전부 쓰여 있다.

그렇다면 문제가 발생할 부분을 전부 찾아낼 수 있어야 하는 거 아닌가?

실행 중에 오류가 발생할 때까지 기다릴 필요도 없고,

Hello World 출력문 하나에 테스트를 20개쯤 만들어주는 AI 때문에 스트레스 받을 일도 없다.

만약 실현된다면 개발자의 삶이 상당히 편해질 것 같다.

그런데 이게 정말 불가능한 일일까?

일단 뇌로 시뮬레이션해보자

사실 이런 시도는 이미 존재한다.

정적 분석(Static Analysis) 이라는 분야다.

정적 분석은 프로그램을 실제로 실행하지 않고 잠재적인 문제를 찾아내는 기법이다.

예를 들어 다음 코드를 보자.

function calculate() {
  const value = null;

  return value.name;
}

calculate();

이 코드를 실행하면 null의 프로퍼티에 접근하려 했기 때문에 오류가 발생한다.

이건 굳이 실행해 보지 않아도 알 수 있다.

value에는 null이 할당되어 있고, 그 변수에서 name을 읽으려 한다는 사실이 코드에 드러나 있기 때문이다.

정적 분석 도구는 이러한 방식으로 프로그램이 실행되기 전에 잠재적인 문제를 찾아낼 수 있다.

실제로 TypeScript, ESLint와 같은 툴에서도 비슷한 방식을 사용한다.

근데 이런 우리가 이미 맨날 하는 지루하고 현학적이고 멍청한 거 말고, 아예 실행 전 모든 문제를 찾아낼 수는 없을까?

프로그램은 굉장히 자유롭다

앞의 예제는 굉장히 단순하다.

변수에 어떤 값이 들어 있는지 알 수 있고, 그 값을 어떻게 사용하는지도 코드에 명확하게 드러나 있다.

그런데 프로그램이 조금만 복잡해져도 상황이 달라진다.

function process(input) {
  while (input > 0) {
    input = input - Math.random();
  }

  return input;
}

이 함수는 항상 종료될까?

입력값이 충분히 크다면 반복문이 오래 실행될 수 있다.

그렇다면 얼마나 오래 실행될까?

입력값과 난수 생성 결과에 따라 달라진다. 특정 실행에서는 조기 퇴근할 수도 있고, 반대로 당신이 이미 회사에 없는 사람이 된 후에도 동작하고 있을 수 있다.

이번에는 조금 다른 코드를 보자.

function run(input) {
  if (input === 0) {
    return;
  }

  run(input - 1);
}

입력값이 양수라면 언젠가 종료된다.

하지만 음수라면 어떨까?

input은 계속 작아지고, 종료 조건인 input === 0에는 도달하지 못한다.

이 정도는 분석할 수 있을 것 같다.

그런데 불행하게도 실제 프로그램은 이렇게 간단하지 않다.

다른 함수의 반환값을 사용하고, 외부 데이터를 읽고, 여러 조건문을 통과하고, 복잡한 알고리즘을 수행한다. 심지어 프로그램이 다른 프로그램을 실행할 수도 있다.

코드가 복잡해질수록 실행 전에 모든 동작을 정확히 예측하는 일도 어려워진다.

정지 문제(Halting Problem)

이론적으로 특정 프로그램의 종료 여부를 판별하는 것은 가능하다. 몇 가지 조건 하에 보편적으로 종료 여부를 판별하는 프로그램도 만들 수 있다.

하지만 모든 상황에서 모든 프로그램의 정확하게 판별하는 알고리즘을 만들 수는 없다.

이걸 지루하고 현학적인 말로 정지 문제(Halting Problem) 라 부른다.

간단히 말하면 다음과 같은 문제다.

임의의 프로그램과 입력값이 주어졌을 때, 그 프로그램이 종료될지 아니면 영원히 실행될지 항상 정확하게 판별할 수 있는 알고리즘이 존재할까?

정지 여부를 판별하는 가상의 프로그램을 만들어 보자

def halts(program, input):
  # program이 input을 받아 실행했을 때
  # 종료하면 True
  # 종료하지 않으면 False
  ...

이 함수는 어떤 프로그램을 전달 받아도 그 프로그램의 종료 여부를 정확하게 판별한다고 가정한다.

프로그램이 종료하면 True, 영원히 실행된다면 False를 반환한다.

일단은 완벽해보인다. 기술적 부채는 원래 내 담당이 아니니까.

그렇다면 이 판별기를 이용해서 다음과 같은 프로그램을 만들어 보자.

def paradox(program):
  if halts(program, program):
    while True:
      pass
  
  return

이 프로그램은 전달받은 프로그램이 자기 자신을 입력으로 받았을 때 어떻게 동작하는지 확인한다.

  • 종료한다고 판단하면 무한 루프에 빠진다.
  • 종료하지 않는다고 판단하면 바로 종료한다.

이제 이 프로그램에 자기 자신을 입력으로 전달해 보자.

paradox(paradox)

halts(paradox, paradox)가 True라고 판단하면 paradox는 무한 루프에 빠진다.

반대로 False라고 판단하면 paradox는 바로 종료한다.

판별기가 판단 내리는 것과 반대로 동작하는 모순이 발생한다.

즉, 우리가 가정한 완벽한 종료 판별기는 존재할 수 없다.

이것이 정지 문제의 핵심적인 내용이다.

그렇다면 정적 분석은 정말 불가능한 걸까?

여기서 짚고 넘어가야 할 부분이 있는데,

정지 문제가 의미하는 바는 모든 프로그램의 종료 여부를 완벽히 판별하는 알고리즘은 존재할 수 없다는 것이지, 정적 분석 자체가 불가능하다는 뜻은 아니다.

실제로 현대에 정적 분석 도구는 엄청나게 많이 쓰이고 있다.

다만 완벽한 분석은 존재할 수 없기에, 현대의 도구들은 분석 범위와 정확도를 어느 정도 타협했다.

아래 방식대로 동작하는 분석 도구가 있다고 가정해보자.

  1. 프로그램이 종료할 것이라고 확실하게 판단할 수 있으면 종료한다고 알려준다.
  2. 종료하지 않을 것이라고 확실하게 판단할 수 있으면 종료하지 않는다고 알려준다.
  3. 판단할 수 없으면 알 수 없다고 알려준다.

이런 방식이라면 항상 정답을 내놓지는 못하더라도, 확실한 경우에는 정확한 결과를 제공할 수 있다.

이런 접근은 타입 시스템, 정적 분석기, 형식 검증(Formal Verification) 등 여러 재미 없는 분야에서 중요한 역할을 한다.

컴퓨터가 너무 똑똑해서 생기는 문제

컴퓨터가 처리할 수 있는 프로그램은 굉장히 자유롭다.

프로그램은 다른 프로그램을 실행할 수 있고, 자기 자신의 동작을 입력으로 활용할 수도 있으며, 입력에 따라 전혀 다른 실행 경로를 선택할 수도 있다.

그렇기 때문에 오히려 그 프로그램이 어떻게 동작할지 완벽하게 예측하는 프로그램은 만들 수 없는 것이다.

더 알아보기

수학적인 증명까지 들어가면 더 재미있는 내용이 많지만, 일단 여기서는 정지 문제의 핵심 아이디어까지만 다뤘다.

혹시 자기 자신을 입력으로 사용하는 프로그램이 왜 중요한지, 정지 문제에 대해 더 자세히 이해하고 싶다면 별도의 글로 파헤쳐 보는 것도 괜찮을 거 같다.