컴퓨터 과학자로서의 삶

젊은 시절의 에드스거 다익스트라​†​

에드스거 다익스트라(Edsger Wybe Dijkstra)는 1930년 5월 11일에 네덜란드 로테르담에서 태어났다.​‡​ 그의 아버지는 고등학교 화학 선생님이었고 네덜란드 화학 학회장을 지내기도 했다. 어머니는 전업주부로 살았지만 수학 전공자여서 그가 수학적 우아함을 중요시하는 데 영향을 미쳤다고 한다.​3​

1948년에 고등학교를 졸업한 그는 레이던 대학교에 입학하였고 이론 물리학자가 되기로 마음먹었다. 1951년에 그의 아버지는 그에게 컴퓨터 프로그래밍을 배워볼 것을 권유했다. 그는 아버지의 지원을 받아 영국 케임브리지 대학에 가서 여름 특별 강좌를 들었다. 모리스 윌크스, 윌러, 길이 진행한 이 프로그래밍 강의를 통해 그는 EDSAC 컴퓨터에서 프로그래밍하는 법을 배웠다.​4​

1952년에 네덜란드로 돌아온 그는 암스테르담에 있는 수학 센터의 컴퓨팅 부서에서 파트타임 프로그래머로 고용되었다. 네덜란드 최초의 공식적인 프로그래머로 인정받고 있다.​1​ 그가 한 일은 단순한 프로그래머라고 하기에는 광범위했다. 당시에 수학 센터에서는 자체적으로 전자식 컴퓨터를 개발했는데, 그는 이 컴퓨터의 명령어 구조를 설계하는 일에 참여했으며, 이렇게 개발한 시스템에 대한 강연을 맡기도 했다.​2​ 그가 실제로 프로그래밍 작업을 시작한 것은 1955년이 되어서였고 이때 그는 베인하든Adrian von Wijngaarden 박사와의 면담을 통해 자신의 진로를 프로그래머로 결정짓게 된다.

그는 일단 학부 과정을 빨리 정리하겠다고 마음먹었고, 1956년에 물리학 학사 학위를 받은 후 암스테르담 대학교 대학원에 입학하여 본격적으로 컴퓨터 분야를 파고들었다. 그는 1959년에 ‘인터럽트’에 관한 주제로 박사학위를 받았다.


1956년에는 학부 졸업 외에도 그에게 아주 의미 있는 사건이 있었다. 수학 센터는 자체적으로 사용하던 ARRA라는 컴퓨터를 대체할 ARMAC라는 컴퓨터를 개발 완료했고 이를 공식적으로 발표하고 시연할 계획을 세웠다. 몇 년 전에 ARRA를 발표할 때는 컴퓨터의 신뢰도가 낮아서 난수 생성 정도의 시연밖에 하지 못했지만 ARMAC는 좀 욕심을 낼 만큼 신뢰성이 개선되어 있었다. 시연을 맡게 된 다익스트라는, 수학적 지식이 별로 없는 사람들도 쉽게 직관적으로 이해할 수 있는 문제를 고민했고 그러다가 ‘최단 경로 알고리듬’이라는 문제를 생각해냈다.

그래서 나는 네덜란드에 있는 두 개의 도시 사이를 연결하는 최단 경로를 찾는 프로그램을 설계했습니다. 축소된 지도 위에는 64개의 도시가 있었습니다.(6비트만 있으면 도시를 모두 구분할 수 있었죠.)… 어느 아침에 나는 약혼자와 함께 암스테르담에서 쇼핑을 하고 있었습니다. 지쳐서 좀 쉬려고 카페 테라스에 앉아서 커피 한 잔을 마시고 있었는데 그냥 그 문제를 어떻게 하면 풀 수 있을까 생각해보았고 최단 거리를 구하는 알고리듬을 만들어 보았습니다. 20분밖에 안 걸렸답니다. 외부에 논문으로 발표한 것은 3년 뒤인 1959년이었습니다.​2​

암스테르담 대학교에서 박사 과정을 밟는 중에도 다익스트라는 수학 센터에서 계속 일했다. 수학 센터는 ARMAC에 이어서 X1이라는 새로운 전자식 컴퓨터를 개발하고 있었다. X1 개발 과정에서 다익스트라는 하드웨어를 담당한 동료의 고충을 듣고 이를 도와주기 위해 ‘최소 신장 트리 알고리듬’을 개발했다.

나는 최소 신장 트리도 생각해 냈습니다. 내 하드웨어 친구들을 위해서 한 일이었습니다. (컴퓨터 하드웨어를 만들려면) 커다란 패널 위에서 여러 위치(부품의 다리)들을 하나의 구리선으로 연결해야 합니다. 같은 전압을 가져야 하니까요. 그런데 어떻게 하면 구리선을 최소한으로 사용할 수 있을까요?​2​

최단 경로 알고리듬과 최소 신장 트리 알고리듬은 1959년에 논문으로 함께 발표되었다. 최단 경로 알고리듬은 현재도 내비게이션 소프트웨어와 네트워크 라이팅 등에 사용되고 있으며 최소 신장 트리 알고리듬도 토목, 교통 등에 사용되고 있다.


다익스트라에게는 아주 유명한 일화가 있다. 그의 직업명과 관련된 이야기이다. 이미 앞에서 언급한 바와 같이 다익스트라는 많은 고민 끝에 물리학자의 길을 버리고 프로그래머의 길을 선택했다. 그러니 그가 얼마나 ‘프로그래머’라는 정체성을 중요시 여겼을지 짐작이 간다. 그래서 1957년에 결혼을 한 후, 혼인신고를 위한 서류를 작성할 때 직업란에 ‘프로그래머’라고 적은 것은 당연해 보인다. 그런데 문제가 생겼다. 시청에서 그의 서류를 반려한 것이다. ‘프로그래머’라는 직업이 존재하지 않는다는 이유에서였다. 결국 그는 ‘이론 물리학자’라고 고쳐서 제출할 수밖에 없었다.

1957년에는 혼인신고 서류 외에도 그를 괴롭히는 일이 있었다. 다름 아닌, ‘인터럽트’였다. ‘인터럽트’란 프로세서의 정상적인 실행 흐름을 중단시키고 다른 작업을 하도록 강제하는 컴퓨터 동작 방식이다. 인터럽트가 다익스트라를 당혹스럽게 만든 이유는, 그가 항상 완벽하게 검증된 프로그램을 작성해 왔기 때문이었다.

첫 5년 동안 나는 항상 존재하지 않는 기계를 위한 프로그램을 작성했습니다. (팀원들은) 논의를 통해 명령어 구조를 설계합니다. 나는 그 명령어로 내가 제대로 일을 할 수 있을지 확인하고, 하드웨어 담당 친구들은 그 명령어 구조를 구현할 수 있을지 확인하죠. 그런 다음에 내가 공식 명세서를 작성하면 모두 이를 따르겠다는 맹세를 합니다. 그리고 뿔뿔이 흩어져서 각자 일을 진행합니다… 내가 하는 프로그래밍은 모두 종이 위에서만 이루어졌고 그래서 나는 기계에서 테스트해보지 않고 프로그래밍을 하는 일에 아주 익숙했습니다…. 테스트할 길이 없으니 항상 프로그램의 정확성을 논리적으로 검증해야만 합니다…. 하지만 1957년에 실시간 인터럽트라는 개념을 접하게 되었습니다. 실시간 인터럽트는 언제 발생할지 예측이 불가능하기 때문에 결국 재현할 수 없는 오류를 만들어내는 프로그램이 생길 수 있게 됩니다…. (처음에는 당황했지만) 나는 그 문제를 다루는 방법을 알게 되었습니다. 허점이 전혀 없는 실시간 인터럽트 처리 코드를 작성했고 이것이 내 박사 논문 주제가 되었습니다.​2​

이를 통해 알 수 있는 사실은, 그가 프로그램의 정확성을 얼마나 중요시했는가이다. ‘일단 짜보고 돌린 다음에 문제가 생기면 해결하자’라는 접근 방식은 그가 가장 싫어하는 방식이었다.


1959년은 여러모로 그에게는 위대한 해였다. ‘컴퓨터 과학 박사’ 학위를 받았을 뿐만 아니라, 그의 유명한 ‘최단 경로 알고리듬’과 ‘최소 신장 트리 알고리듬’이 정식으로 공개되었고, 또 하나의 기념비적인 발견이 기다리고 있었다. 다름 아닌 ‘동기화’ 문제였다.

시작은 연구자들끼리의 지적 경쟁에서 출발했다. 수학 센터에서 같이 일하던 동료들에게 그는 다음과 같은 문제를 냈다.

반복적인 일을 하는 두 개의 프로그램이 있다고 하자. 그 프로그램이 반복적으로 하는 일이란, 임계구역critical section이라고 불리는 것이다. 공유 저장장소에 있는 값을 읽어오고, 그곳에 어떤 값을 쓰는 일을 하는 프로그램 조각인데 이렇게 하면 두 개의 프로그램이 서로 데이터를 주고받을 수 있다. 그렇다면 두 프로그램의 상대적인 속도는 전혀 알려지지 않았다고 했을 때, 어느 한순간에 그 임계구역을 두 프로그램이 동시에 수행하지 않도록 동기화시키는 방법을 찾아라.​2​

재미있는 수수께끼 같은 이 문제는 분산 병렬 처리의 가장 기초적인 이론이 되었다. 이날 결국 문제를 푼 사람은 데커Dekker였다. 다익스트라는 1962년에 세마포어를 위한 P, V 명령을 고안해냈다.

1959년과 관련해서 알골Algol 60 이야기도 빼놓을 수는 없겠다. 다익스트라는 알골 60 언어의 적극적 지지자로도 유명하다. 그는 알골 60 언어 설계에도 깊이 관여했는데 그 시작은 거의 우연에 가까웠다. 알골 언어는 미국과 유럽의 컴퓨터 과학 연구자들이 모여 시작되었다. 이때 유럽 측 대표단의 한 명으로 네덜란드 수학 센터의 베인하든 박사가 내정되어 있었다. 그런데 그가 자동차 사고를 크게 당했고 결국 대타로 다익스트라가 참석하게 되었다. 1958년 12월 회의에서부터 참석한 그는 적극적으로 자신의 의견을 개진했다. 특히나 ‘재귀적 호출recursive call‘이 포함되도록 노력한 이야기는 흥미롭다.

그것은 좀 몰래 포함되었습니다. 1959년 12월 말에 알골 60의 초안이 회람되고 있었습니다. 그것을 읽어보니 재귀적 호출이 명시되지만 않았을 뿐 거의 인정된 것이나 다름이 없었습니다. 그래서 코펜하겐에 있던 피터 나우어Peter Naur에게 전화했습니다. 그 전화는 내가 처음 걸어본 국제전화여서 엄청나게 흥분했었죠. 나는 그에게 재귀적 호출이 포함될 수 있도록 다음과 같은 표현을 추가해달라고 제안했습니다. ‘프로시져 식별자procedure identifier가 사용되면 항상 그 프로시져를 재활성화하는 것을 의미한다.’ 뭐 이런 비스름한 문장이었습니다. 그 문장은 몰래 살짝 들어갔습니다. 이렇게 해서 재귀적 호출이 명시적으로 포함되었습니다.​2​

재귀적 호출은 이미 리스프 언어에서 사용되고 있었고 존 매카시가 제안한 상태였지만 결정적으로 명세서에 포함된 것은 다익스트라의 기지(?) 덕분이라고 하겠다. 다익스트라는 재귀적 호출에 대한 논문​5​을 발표하기도 했는데, 여기서 ‘스택stack‘이라는 용어를 처음 사용했다. 그는 EWD-1000이라는 일련번호가 붙은 메모에서 ‘스택’이라는 용어를 만들었던 때를 다음과 같이 회상했다.​§​

내가 내용을 기억하는 가장 오래된 EWD 메모는 6번이다. 그때 나는 가족과 함께 패터스불드Paterswolde에 있는 “가족용 호텔”에서 휴일을 보내고 있었다. 재귀적 호출을 구현할 방법을 막 발견한 참이었고 뭔가 좋은 이름을 붙여보려고 열심히 궁리했던 것이 지금도 생생히 기억이 난다. 나는 명사도 되고 동사도 될 수 있는 단어를 찾고 있었다.
그 당시에 나는 네덜란드어를 사용하고 있었는데 “stapel”이라는 명사와 “stapelen”이라는 동사가 떠올랐다. 영어로는 “a stack”과 “to stack”으로 각각 번역되었다. (이 용어는 운이 좋았다. 몇 년 후에 나는 <재귀적 프로그래밍​5​>이라는 논문에서 이 단어를 사용했고, 컴퓨팅 관련 공동체에서 공식 용어로 자리 잡았다.)​6​


1962년에 다익스트라는 에인트호번 기술 대학교의 수학과 교수로 채용되었다. 그는 X8 컴퓨터 개발에 관여했고 THE라는 이름의 운영체제를 직접 개발했다. THE 운영체제는 프로세스 동기화를 본격적으로 구현했고 다른 운영체제에 큰 영향을 주었다. 그는 데커의 알고리듬을 더욱 확장했다. THE 운영체제는 1966년에 설계가 완료되었고 교착상태deadlock를 방지해주는 은행원 알고리듬Banker’s Algorithm이 발표되었다.

프로세스 동기화와 관련해서 식사하는 철학자들Dining Philosophers 문제가 유명하다. 1965년에 시험 문제로 그가 생각해냈다는 이 문제는 컴퓨터 과학 전공자라면 한 번쯤은 접하게 되는 동기화 문제이다.​7​ ‘식사하는 철학자들’이라는 멋진 이름을 붙여준 이는 토니 호어Tony Hoare​¶​이다.

1967년에 다익스트라는 미국에서 열린 운영체제 관련 학술대회에 참석했다가 쉬는 시간에 다른 참석자들과 이야기하는 과정에서 GO TO 문의 문제점을 지적했다. 그는 GO TO 문이 프로그램을 복잡하게 만들기 때문에 사용하지 말아야 한다고 주장했다. 그의 말을 들은 동료들은 그에게 이를 논문으로 발표하라고 권유했고 그는 미국 컴퓨터 학회ACM에 투고했다. ACM 학회지의 편집자였던 니클라우스 비르트Niklaus Wirth​#​는 이를 빨리 공개하는 것이 좋다고 판단하여 정식 논문이 아닌 서간문 형식으로 실으면서 제목을 살짝 고쳤다. 다익스트라가 보낸 원고의 원래 제목은 <GO TO 문에 대한 반대A Case Against the GO TO Statement>였지만 바뀐 후의 제목은 <해롭다고 봐야 할 GO TO 문​8​>이었다. 이 바뀐 제목은 하나의 유행이 되어서 후에 ‘해롭다고 봐야 할 XXX’ 시리즈가 양산되기도 했다.

다익스트라가 GO TO 문의 사용에 반대한 이유는 프로그램의 우아함elegance을 떨어뜨리기 때문이었다. 그에게 우아함이란, 없어도 되는 사치품이 아니라, 성공과 실패를 가르는 요소였다.​9​ 프로그램의 우아함에 대한 그의 생각은 구조적 프로그래밍structured programming이라는 패러다임으로 발전했다. 1969년에 그는 <구조적 프로그래밍에 대한 소고​10​>라는 메모를 발표했다.

1970년대에 들어서서 다익스트라는 프로그램의 정확성에 관심을 기울였다. 비결정적 프로그램Nondeterminacy, 술어 변환 의미론Predicate transformer semantics 등의 이론적 성과를 발표했다. 유럽을 중심으로 활동해왔던 그는 1973년에 버로우즈 사의 연구 펠로우로 선정되면서 미국에서의 활동을 늘렸고 1984년에는 텍사스 대학교 오스틴 분교의 컴퓨터 과학과에서 석좌 교수로 임명되어 2000년까지 재직했다.

암과 투병하던 그는 2002년에 네덜란드로 돌아온 후 8월 6일에 누너Nuenen에서 세상을 떠났다.

1 2 3 4 5 6