에츠허르 데이크스트라(Edsger W. Dijkstra)

에츠허르 데이크스트라는 1930년 네덜란드 로테르담에서 태어나 레이던 대학에서 이론 물리학을 공부했습니다. 1952년 암스테르담 수학 센터가 그에게 컴퓨터 프로그래머 자리를 권했습니다. 그때 네덜란드에는 컴퓨터가 손에 꼽을 만큼밖에 없었고, 프로그래밍은 직업으로 인정받지도 못했습니다. 그가 1972년 튜링상⁠(Turing Award)⁠ 수상 강연에서 회고한 바로는, 1957년 결혼할 때 혼인 서류의 직업란에 '프로그래머'라고 적었다가 그런 직업은 없다는 이유로 받아들여지지 않아 '이론 물리학자'로 고쳐 적어야 했습니다. 데이크스트라는 그 없던 직업을 수학처럼 엄밀한 학문으로 만드는 데 평생을 바쳤습니다.

나이 세 ·

그가 발을 들인 네덜란드의 컴퓨터는 거의 손으로 지은 것이었습니다. 1946년 세워진 암스테르담 수학 센터는 계전기⁠(relay)⁠와 진공관으로 ARRA, ARMAC 같은 기계를 직접 만들었고, 프로그래머는 아직 조립 중인 기계를 위해 프로그램을 짰습니다. 데이크스트라는 1951년 영국 케임브리지에서 EDSAC 컴퓨터의 프로그래밍 강좌를 들었고, 이를 계기로 수학 센터의 아드리안 판베인하르던이 그를 불렀습니다. 그는 물리학과 프로그래밍 사이에서 오래 망설였습니다. 튜링상 강연에서 회고한 바로는, 판베인하르던에게 프로그래머가 되어도 존경받는 과학자일 수 있느냐고 묻자, 컴퓨터는 사라지지 않을 것이고 당신이 프로그래밍을 존경받는 학문으로 만드는 사람이 될 수 있다는 답이 돌아왔습니다. 그는 1955년 무렵 프로그래밍을 평생의 일로 정했습니다.

1956년 그는 수학 센터의 새 컴퓨터 ARMAC을 시연하면서, 수학을 모르는 사람도 알아들을 문제로 "로테르담에서 흐로닝언까지 가장 짧은 길은?"을 골랐습니다. 훗날의 인터뷰에서 그는 약혼녀와 암스테르담에서 장을 보다 지쳐 카페 테라스에서 커피를 마시며, 종이와 연필 없이 20분쯤 만에 방법을 설계했다고 회상했습니다. 방법은 이렇습니다. 출발점에서 가까운 곳부터 하나씩 거리를 확정합니다. 아직 확정되지 않은 점 가운데 잠정 거리가 가장 짧은 점 u를 골라 확정하고, u를 거쳐 가면 더 짧아지는 이웃 v가 있으면 $d(v) \leftarrow \min(d(v),\, d(u) + w(u,v))$로 고칩니다. 길이가 음수인 변이 없다면 지금 고른 u로 가는 더 짧은 길은 있을 수 없습니다. 다른 길은 확정된 점들의 무리를 처음 벗어나 어떤 점 v에 닿는 순간 이미 v의 잠정 거리 이상, 따라서 u의 잠정 거리 이상을 걸었고, 남은 구간은 음수일 수 없기 때문입니다. 이 짧은 논증 하나로, 지금 가장 좋아 보이는 것을 고르고 되돌아보지 않는 욕심쟁이 알고리즘⁠(greedy algorithm)⁠이 정확한 최단 경로를 줍니다.

1959년 세 쪽짜리 논문 「그래프에 관한 두 문제에 대한 노트」에는 이 방법과 함께, 모든 점을 가장 짧은 전선으로 잇는 최소 신장 트리⁠(minimum spanning tree)⁠를 찾는 방법도 실렸습니다. 확정된 점들로 가는 길은 출발점을 뿌리로 하는 트리⁠(tree)⁠를 이루니, 한 번의 계산으로 모든 점까지의 답이 나옵니다. 처음의 방법은 점이 n개일 때 $n^2$에 비례하는 시간이 들었는데(점근 표기법⁠, asymptotic notation⁠), 뒤에 가장 가까운 점을 우선순위 큐⁠(priority queue)⁠에서 꺼내게 되면서 큰 도로망에서도 빨라졌습니다. 오늘날 길 안내 프로그램과 인터넷의 경로 선택이 그 후손을 씁니다.

그는 곧 언어와 운영 체제로 나아갔습니다. 1960년 동료와 함께 프로그래밍 언어 알골 60의 첫 컴파일러(사람이 쓴 프로그램을 기계어로 옮기는 프로그램) 가운데 하나를 완성하면서, 자기 자신을 부르는 프로시저를 스택⁠(stack)⁠, 곧 맨 나중에 넣은 것을 맨 먼저 꺼내는 기억 장치로 처리하는 방법을 정리했습니다(재귀⁠(recursion)⁠). 1962년 에인트호번 공과대학 교수가 된 뒤에는 여러 프로그램이 한 기계를 나눠 쓰는 병행 처리를 연구했습니다. 두 프로그램이 같은 자원을 동시에 건드리지 않게 하는 신호 장치인 세마포어⁠(semaphore)⁠, 그리고 뒤에 토니 호어가 지금의 모습으로 다듬은 '식사하는 철학자⁠(dining philosophers problem)⁠' 문제, 곧 모두가 서로를 기다리느라 아무도 움직이지 못하는 교착 상태⁠(deadlock)⁠의 문제가 이 무렵 그에게서 나왔습니다. 1965년 논문에서는 여러 프로세스 가운데 하나만 공유 자원에 들어가게 하는 상호 배제⁠(mutual exclusion)⁠ 문제를 프로세스가 몇 개이든 풀리는 꼴로 풀었고(프로세스가 둘인 경우는 동료 테오도뤼스 데커의 풀이가 먼저였습니다), 1965–68년에는 학생들과 함께 운영 체제 THE를 층층이 쌓아 설계해, 층마다 바로 아래층만 믿고 옳음을 따로 확인하는 방법을 보였습니다.

1960년대 후반 컴퓨터 업계는 '소프트웨어 위기⁠(software crisis)⁠'라는 말을 쓰기 시작했습니다. 하드웨어는 해마다 빨라지는데, 그 위에서 돌아갈 큰 프로그램들은 예정보다 몇 년씩 늦고 예산을 훌쩍 넘기고 오류투성이였습니다. IBM의 운영 체제 OS/360 개발에는 수천 명이 매달렸고, 그 경험을 정리한 프레더릭 브룩스의 『맨먼스 미신』(1975)은 늦어진 계획에 사람을 더 넣으면 더 늦어진다는 말로 유명해졌습니다. 1968년 10월 독일 가르미슈에서 열린 나토의 학회는 이 문제를 다루며 '소프트웨어 공학⁠(software engineering)⁠'이라는 이름을 내걸었고, 데이크스트라도 참석했습니다. 같은 해 12월 그는 호어 등과 함께, 국제 정보 처리 연맹의 위원회가 채택한 거대한 언어 알골 68이 너무 복잡하다는 소수⁠(prime number)⁠ 의견서에 서명했습니다.

1968년 그는 『ACM 통신』에 goto 문이 프로그램의 흐름을 따라가기 어렵게 만든다는 짧은 편지를 보냈고, 편집자인 스위스의 컴퓨터 과학자 니클라우스 비르트가 붙인 제목 「goto 문은 해롭다」로 유명해졌습니다. 그의 생각은 프로그램을 먼저 짜고 나중에 시험하는 대신, 옳다는 것을 증명하면서 짜자는 것이었습니다. 반복문마다 매번 참으로 남는 성질(불변식)을 정하고 수학적 귀납법⁠(mathematical induction)⁠처럼 그것이 지켜짐을 보이면, 반복이 끝났을 때 원하는 결과가 나온다는 것을 알 수 있습니다. 변하는 것 속에서 변하지 않는 것을 붙드는 이 방법은 수학 곳곳에 있는 생각입니다(대칭과 불변량⁠(invariant)⁠). 그는 시험은 오류가 있음을 보여 줄 수는 있어도 없음을 보여 줄 수는 없다고 거듭 말했습니다. 1972년 노르웨이의 올레요한 달, 호어와 함께 『구조적 프로그래밍』을 펴냈고, 같은 해 튜링상을 받으며 「겸손한 프로그래머」라는 강연을 했습니다.

1970년대의 그는 증명하며 짜는 것을 넘어, 증명에서 프로그램을 이끌어 내는 방법을 찾았습니다. 1975년 그는 명령문마다, 실행한 뒤에 원하는 조건이 참이 되려면 실행 전에 무엇이 참이어야 하는지를 거꾸로 계산하는 '최약 전조건⁠(weakest precondition)⁠'을 정의하고, 조건이 참인 갈래 가운데 아무것이나 골라 실행하는 보호 명령⁠(guarded command)⁠을 도입했습니다. 이 계산이 이진 탐색⁠(binary search)⁠ 같은 실제 프로그램에서 어떻게 돌아가는지, 그리고 끝남을 따지지 않는 판이 실행 결과와 어떻게 갈루아 연결⁠(Galois connection)⁠을 이루는지는 호어 논리⁠(Hoare logic)⁠에서 볼 수 있습니다. 1976년의 『프로그래밍의 규율』은 목표에서 거꾸로 추론해 프로그램을 짜는 이 방법을 정리한 책입니다. 1974년에는 어떤 엉뚱한 상태에서 출발하든 유한한 시간 안에 스스로 올바른 상태로 돌아오는 분산⁠(variance)⁠ 체계, 곧 자기 안정화⁠(self-stabilization)⁠라는 생각을 짧은 논문으로 내놓았는데, 이 논문은 거의 주목받지 못하다가 1983년 레슬리 램포트가 그의 가장 뛰어난 업적의 하나로 꼽으면서 다시 읽혔습니다.

1973년부터 버로스 사의 연구원으로 지내던 그는 1984년 텍사스 대학 오스틴으로 옮겨 1999년까지 가르쳤습니다. 생각을 만년필로 쓴 원고에 적어 번호를 매기고 복사해 동료들에게 돌렸는데, 머리글자를 딴 이 'EWD' 원고가 천 편이 넘습니다. 2002년 분산 컴퓨팅 학회(PODC)는 자기 안정화 논문에 영향력 있는 논문상을 주었고, 그해 8월 그가 네덜란드 뉘넌에서 세상을 떠난 뒤 이 상은 데이크스트라상으로 이름이 바뀌었습니다.

그의 날카로운 말은 적도 많이 만들었습니다. 그는 특정 프로그래밍 언어가 학생들의 생각을 망친다고 서슴없이 썼고, 1988년 글 「컴퓨팅 과학을 정말로 가르치는 일의 잔인함에 대하여」에서는 프로그래밍을 공학의 비유가 아니라 형식 수학으로 가르쳐야 한다고 주장했습니다. 『컴퓨터 프로그래밍의 예술』의 저자 도널드 크누스는 1974년 논문 「goto 문을 쓰는 구조적 프로그래밍」에서 goto를 무조건 없애기보다 잘 쓰는 법을 논하며 논쟁을 누그러뜨렸습니다. 그래도 큰 흐름은 그의 편이었습니다. 오늘날 대부분의 언어에서 goto는 사라지거나 구석으로 밀려났고, 반복문과 조건문과 함수⁠(function)⁠로 이루어진 구조적 프로그래밍은 누구나 처음 배우는 방식이 되었습니다.

이어지는 곳. 점과 선으로 길을 다루는 생각은 오일러의 쾨니히스베르크 다리 문제(오일러 경로⁠, Euler path⁠)에서 시작했고, 굽은 면 위에서 가장 짧은 길은 측지선⁠(geodesic)⁠입니다. 음수 길이의 변이 있으면 이 방법은 틀리고, 그때는 (한 바퀴 돌면 길이가 줄어드는 순환만 없다면) 표를 채워 나가는 동적 계획법⁠(dynamic programming)⁠이 필요합니다. 최단 경로는 빠르게 풀리지만 모든 도시를 한 번씩 도는 가장 짧은 길은 P 대 NP 문제⁠(P versus NP problem)⁠의 한가운데에 있고, 눈앞의 최선이 언제 전체의 최선이 되는지는 가장 좋은 것 고르기에서 다룹니다. 프로그램이 옳다는 것을 증명하는 논리는 호어의 공리적 방법과 나란히 발전했고, 어떤 절차든 알고리즘으로 적는다는 생각의 바탕에는 튜링의 기계가 있습니다.

관계.

• 함께 연구 토니 호어 — 호어는 데이크스트라가 낸 식사하는 철학자 문제를 지금의 모습으로 다듬었고, 두 사람은 1968년 알골 68 반대 소수 의견서에 함께 서명한 뒤 1972년 달과 함께 『구조적 프로그래밍』을 펴냈습니다.

연표.

• 1951년 케임브리지에서 EDSAC 컴퓨터의 프로그래밍 강좌를 듣다
• 1952년 암스테르담 수학 센터에서 프로그래머로 일하기 시작하다
• 1956년 카페 테라스에서 20분 만에 최단 경로 알고리즘을 설계하다
• 1957년 혼인 서류의 직업란에 '프로그래머'라고 적었다가 받아들여지지 않다
• 1959년 「그래프에 관한 두 문제에 대한 노트」를 발표하고 박사 학위를 받다
• 1960년 알골 60의 첫 컴파일러⁠(compiler)⁠ 가운데 하나를 완성하다
• 1962년 에인트호번 공과대학 교수가 되다
• 1965년 상호 배제 문제를 풀고 식사하는 철학자 문제를 내다
• 1968년 「goto 문은 해롭다」와 운영 체제 THE의 논문을 발표하다
• 1972년 『구조적 프로그래밍』을 펴내고 튜링상을 받다
• 1973년 버로스 사의 연구원이 되다
• 1974년 자기 안정화 논문을 발표하다
• 1976년 『프로그래밍의 규율』을 펴내다
• 1984년 텍사스 대학 오스틴으로 옮기다
• 1999년 텍사스 대학에서 은퇴하다