연속(continuation)과 연속 전달 스타일(CPS)이 1960~1970년대에 여러 연구자들에 의해 어떻게 독립적으로 발견·재발견되었는지, 그 배경과 맥락을 간략히 정리한다.
LISP A N D S Y M B O L I C C O M P U T A T I O N : An International Journal, 6, 233-248, 1993 © 1993 Kluwer Academic Publishers - Manufactured in The Netherlands
JOHN C. REYNOLDS
School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213-3890 (John.Reynolds@cs.cmu.edu)
키워드: 의미론, 연속(Continuation), 연속 전달 스타일(Continuation-Passing Style)
초록. 우리는 A. van Wijngaarden, A. W. Mazurkiewicz, F. L. Morris, C. P. Wadsworth, J. H. Morris, M. J. Fischer, S. K. Abdali에 의해 연속(continuation)과 관련 개념들이 어떻게 발견되었는지에 대한 간단한 개요를 제시한다. 연속의 초기 역사에서 기본 개념은 놀라울 정도로 여러 번 독립적으로 발견되었다. 이는 컴퓨터 과학자들 사이의 의사소통이 서툴렀기 때문이라기보다는, 연속이 유용하게 쓰이는 “환경(setting)”이 매우 다양했기 때문이다. 연속은 (연속 전달 스타일로의) 프로그램 변환 기법, 한 언어를 다른 언어로 작성된 인터프리터로 정의하는 정의적(definitional) 인터프리터의 한 스타일, 그리고 (Scott와 Strachey의 의미에서의) 표시적(denotational) 의미론의 한 스타일을 떠받친다. 이들 각각의 환경에서, “프로그램의 나머지 부분의 의미”를 함수나 프로시저로 표현함으로써, 연속은 값에 의한 호출(call by value)과 goto 문을 포함한 다양한 언어 구성 요소를 우아하게 기술해 준다.
1960년대 초, Algol 60 [32, 33]의 등장은 프로그래밍 언어의 구현과 형식적 정의에 관한 연구 열풍을 불러일으켰다. 이러한 연구의 여러 측면은 연속의 발견에 결정적 전조(precursor)가 되었다.
Algol 60에서 블록 밖으로, 심지어 프로시저 본문 밖으로도 점프할 수 있는 능력은 구현자들로 하여금 레이블의 표현이 환경(environment)에 대한 참조를 포함해야 함을 깨닫게 했다. Peter Naur에 따르면:
… 제어의 이동(transfer of control)을 지정하기 위해서는 일반적으로 목적지의 정적 서술 …과 그 환경, 즉 스택 참조라는 동적 서술을 둘 다 제공해야 한다. 이 집합 …은 함께 우리가 프로그램 지점(program point)이라 부르는 것을 정의한다. [31]
돌이켜보면 프로그램 지점은 연속의 표현이었다.
더 미묘한 깨달음은 반환 주소(return address)를 프로시저 매개변수와 동등한 지위로 다룰 수 있다는 점이었다. E. W. Dijkstra는 선견지명적인 표현으로 다음과 같이 말했다:
우리는 메인 프로그램이 서브루틴을 호출할 때 서브루틴에 제시되는 모든 정보를 “매개변수(parameters)”라 부른다; 그러므로 함수 인수(function arguments)가 있다면 그것들도 매개변수이다. “링크(link)”라는 용어로 묶이는 데이터 또한 매개변수로 간주된다; 링크는 서브루틴이 완료된 후 메인 프로그램의 계속(continuation)에 필요한 모든 데이터를 포함한다. [9]
실제로 Naur와 Jørn Jensen이 설계한 GIER Algol 컴파일러 [31]에서는 반환 주소와 레이블 매개변수(둘 다 프로그램 지점으로 간주됨)가 본질적으로 같은 방식으로 처리되었다.
연속의 또 다른 전조는 Peter Landin의 SECD 기계 [14]였다. 이는 비형식적 람다 계산과 구문적으로 유사하지만 값에 의한 호출 순서로 평가되는 적용적(applicative) 표현 언어를 위한 상태 전이 인터프리터였다. SECD라는 약어가 말해 주듯, 인터프리터의 상태는 네 구성 요소로 이루어졌다: 스택(stack), 환경(environment), 제어(control), 덤프(dump). 덤프는 제어가 소진된 이후 수행될 남은 계산을 인코딩했는데, 돌이켜보면 이것 또한 연속의 표현이었다.
Algol 60을 적용적 표현으로 번역하기 위해, Landin은 나중에 이 표현들과 인터프리터를 대입(assignment) 연산과 제어 연산자 J로 확장하여 goto와 레이블의 번역을 표현했다 [15, 16]. 확장된 SECD 기계에서 J를 적용한 결과는 덤프를 포함한 값이었다. 즉 현대 용어로 J 연산자는 연속을 값 속에 “임베딩”하는 수단을 제공했으며, Reynolds의 escape [36], 그리고 Scheme의 catch [44], call/cc [8] 같은 연산의 선조였다.
연속의 사용에 대한 가장 이른 기술은 1964년 9월(오스트리아 바덴 베이 빈에서 열린 IFIP 작업 회의 “형식 언어 기술 언어”)에서 Adriaan van Wijngaarden(암스테르담 Mathematisch Centrum 소장)이 한 것으로 보인다. 이 발표의 서면본과 이후 토론의 기록이 회의록 [45]에 실려 있다.
Van Wijngaarden의 목표는 Algol 60을 더 제한된 부분언어로 번역하는 전처리기(preprocessor)를 공식화하는 것이었다. 전처리의 마지막 단계는 (오늘날 우리가 부르는 바대로) 적절(proper) 프로시저를 연속 전달 스타일(CPS) [41]로 변환하는 것이었고, 그에 따라 레이블과 goto 문을 제거했다. (전처리의 앞 단계에서는 함수 프로시저를 적절 프로시저로 치환했다.) 변환은 다음과 같이 기술된다:
각 프로시저 선언에 추가 형식 매개변수—지정된 레이블(specified label)—를 하나 제공하고, 본문 끝에 그 형식 매개변수로 향하는 goto 문을 삽입하라. 이에 대응하여, 프로시저 문 다음의 문장을(이미 레이블이 붙어 있지 않다면) 레이블 붙이고, 그 레이블을 대응하는 추가 실제 매개변수로 제공하라. [45]
다음으로, 레이블과 goto 문을 삽입하여 각 블록을
begin L1:S1; … ; Ln:Sn end
형태의 동등한 블록으로 변환했는데, 이때 각 문 Si를 통과하는 모든 실행 경로는 goto 문으로 끝난다.
실제로, 그의 다소 불투명한 산문을 내가 오해하지 않았다면, van Wijngaarden의 이 변환 설명에는 오류가 있다. 위 블록이 더 큰 블록의 문장일 때, 내부 블록 안에서 내부 블록 뒤의 문장으로 점프하는 경우를 삽입할 방도가 없다. 그러나 이 결함은(예컨대 J. H. Morris [28]의 작업처럼) van Wijngaarden 변환을 적용하기 전에 그러한 내부 블록을 대응하는 매개변수 없는 프로시저 호출로 대체함으로써 쉽게 고칠 수 있다.
마지막으로 van Wijngaarden [45]에 따르면:
이제 각 블록 끝에 그 블록의 첫 문장으로 향하는 레이블 없는 goto 문을 삽입해도 전혀 해가 없다. 왜냐하면 이 문장은 결코 실행되지 않을 것이기 때문이다. 지금까지 우리는 레이블과 goto 문의 수만 늘렸다. 하지만 이제 다음 조작을 수행할 수 있다:
- 각 레이블 앞에 procedure를 써라.
- 그 뒤의 콜론을 세미콜론으로 바꿔라.
- 각 goto를 지워라.
이어진 토론에서의 다음 교환은, 연속 전달 스타일로의 변환이 레이블과 goto 제거 이상의 것임을 van Wijngaarden가 분명히 이해하고 있었음을 보여 준다:
MCILROY: … goto를 제거하는 데 너무 멀리 간 것 같습니다. 왜냐하면 이것은 값의 시간적 존재(temporal existence)를 실제로 바꾸기 때문입니다. 모든 goto를 프로시저 호출로 바꾸면 계산의 전체 이력을 유지해야 한다는 뜻입니다. 이런 제한이 걱정됩니다.
VAN WIJNGAARDEN: 당신이 그렇게 말할 때 특정한 프로시저 호출 구현을 염두에 두고 있는 것 같습니다. 하지만 그 구현이 어려운 이유는 goto 문을 처리해야 하기 때문입니다. 그런데 내가 고안한 이 트릭을 쓰면, 실제 프로그램 실행은 문장들의 집합과 동등해집니다. 어떤 프로시저도 반환하지 않습니다. 끝나기 전에 항상 다른 것을 호출하기 때문입니다. 그리고 모든 프로시저의 모든 end는 프로그램 끝에 있을 것입니다: 백만, 이백만 개의 end. 어떤 프로시저가 끝에 도달하면 그것이 곧 전부의 끝입니다; 그러므로 멈출 수 있습니다. 즉 반환을 가능케 하느라 신경 쓰지 않는 방식으로 프로시저 구현을 만들 수 있습니다. 프로시저 구현의 모든 어려움은 거기에 있습니다. 그래서 이것이 매우 단순합니다; 다른 말로 부르는 것만 빼면 goto와 정확히 같습니다. [45]
돌이켜보면, van Wijngaarden의 발표가 연속과 CPS를 컴퓨터 과학의 표준 개념으로 만들지 못했다는 점이 놀랍게 느껴질 수 있다. 토론 참가자에는 Dijkstra, Hoare, McCarthy, McIlroy, Strachey가 있었고, 그 외에도 Böhm, Elgot, Landin, Nivat 등이 참석했다. 그러나 이 아이디어는 자리잡지 못했다.
특히 Landin은 Algol 60을 다루면서 van Wijngaarden의 변환을 언급했지만 [15], 1970년 F. L. Morris의 콜로퀴움(4절)을 들었을 때 이 작업을 전혀 언급하지 않았다. 또한 Christopher Strachey는 이 작업을 Wadsworth의 연속과 연결하지 못했으며, Wadsworth에 대한 자신의 기술 [42, 43]에서도 van Wijngaarden를 인용하지 않았다(5절).
발표 이후 토론은 van Wijngaarden와 다른 연구자들 사이의 깊은 철학적 차이를 드러낸다. 특히 추상 구문(abstract syntax)에 대한 그의 혐오, 그리고 적절 프로시저가 함수보다 더 기초적이라는 믿음이 그러했다. 하지만 의사소통의 더 큰 장벽은 CPS 변환의 동기 부여 실패였을 것이다. M. D. McIlroy에 따르면:
나는 그 강연을 잘 기억한다. 통찰력 있는 환원주의(reductionism)의 기막힌 시연이었다 … van Wijngaarden의 논증은 또렷하고 잊히지 않게 빛났다 … [하지만] 아이디어는, 그것의 모든 파급효과가 드러나지 않더라도 이해될 수 있다—심지어 발명가 자신에게도. van Wijngaarden는 연속 전달의 실용적 예도, 이미 알려진 고립된 결과 하나를 증명하는 트릭 말고는 어떤 이론적 응용도 제시하지 않았기 때문에, 연속 그 자체의 가치가 전달되지 못했다. [22]
게다가 van Wijngaarden의 발견은 실제로 연속 자체라기보다는 CPS 변환이었다. 그는 연속의 개념을 어디에서도 정의하거나 강조하지 않는다. 이는 다른 환경에서 나타난 연속들과의 연결을 알아보기 어렵게 만들었을 것이다. 또한 van Wijngaarden 자신이 이후에 연속을 다시 사용한 적이 없었던 것으로 보인다.
한편 McIlroy [22]가 기억하는 강연의 또 다른 일화는 다음과 같다:
그 강연은 실제로 컴퓨팅에 하나의 직접적이고 중요한 결과를 남겼다. goto가 불필요하다는 발상에 자극받아, Dijkstra는 그날 저녁 goto 없는 현실적인 프로그램 예들을 구성하기 시작했고, 다음 날 커피 브레이크 때 냅킨에 그것들을 휘갈겨 썼다. 그 과정에서 그는 “quit” 문(CPL과 C의 break)을 가정했다 … 그 커피 브레이크 잡담은 컴퓨팅 역사상 가장 유명한 편지 [10]로 익어 갔다. 그러니 van Wijngaarden가 goto가 불필요하다고 말했을 때 … Dijkstra는 그 점을 더 확장해 goto가 불편하다고 말했다. 후자의 교훈이 남았다.
1969년 12월, Antoni W. Mazurkiewicz(당시 바르샤바의 Instytut Maszyn Matematycznych)는 “Proving Algorithms by Tail Functions”라는 작업 문서를 IFIP 작업 그룹 2.2 회원들(여기에는 Strachey도 포함됨)에게 배포했다. 출판용 버전은 1970년 4월 Information and Control에 제출되었고, 11월 수정된 뒤 1971년 4월에 출판되었다 [18].
이 논문에서 Mazurkiewicz는 오토마톤과 유사한 알고리즘 개념을 다뤘다. 이는 레이블 집합 E, 종료 레이블 부분집합 T ⊂ E, 상태 집합 R, 그리고 (E − T) × R에서 E × R로의 부분 전이 함수 τ로 이루어졌다. 그는 그러한 알고리즘의 의미론을 “꼬리 함수(tail function)”라 부르며, 다음을 만족하는 E × R에서 R로의 최소 부분 함수 θ로 제안했다:
[ \theta(e,x)=\begin{cases} \theta(\tau(e,x)) & \text{if } e \notin T\ x & \text{if } e\in T \end{cases} ]
커링하면 꼬리 함수는 레이블을 명령 연속(command continuation)으로 매핑하는 환경이 되며, 이는 레이블과 goto 명령이 있는 명령형 언어의 연속 의미론과 같다.
그러나 Mazurkiewicz의 알고리즘 개념은 계층적 구조가 전혀 없는 매우 제한된 프로그래밍 언어이므로, 그의 작업은 연속의 일반적 성격을 많이 드러내지 않는다. 예컨대 의미가 연속을 받는 함수가 되어야 하는 구문 구성 요소가 없다. 또한 알고리즘을
while e ∉ T do (e, x) := τ(e, x)
(변수 e와 x가 레이블과 상태를 가리킨다고 하자)로 본다면, 꼬리 함수는 단지 이 명령의 직접 의미론일 뿐이다. 따라서 이것이 연속의 “발견”인지 전조인지 말하기 어렵다.
분명한 것은 이것이 Wadsworth의 이후 작업을 고무했다는 점이다(5절). 1972년 Mazurkiewicz는 꼬리 함수 기법에 관한 두 편의 추가 논문 [19, 20]을 발표했다.
1970년 11월, F. Lockwood Morris(당시 스탠퍼드 대학 대학원생으로, 박사 논문을 진행하며 에식스 대학에서 강의 중)는 런던의 Queen Mary College에서 “The Next 700 Formal Language Descriptions”라는 콜로퀴움을 했다. (이는 Peter Landin의 “The Next 700 Programming Languages” [17]을 빗댄 제목이며, Landin이 Morris를 초청했다.) 이 강연에서 Morris는 값에 의한 호출의 함수형 언어에 대해 다양한 정의적 인터프리터를 제시했고, 대입과 레이블을 포함하도록 확장했다. 강연에서 배포된 노트는 본 학술지 특집호에 실려 있다 [26].
노트의 마지막 인터프리터에서는 Gedanken [35]에서 볼 수 있는 종류의 레이블과 점프를 처리하기 위해 연속을 사용한다. 구체적으로 Morris가 “덤프(dump)”라 부르는 것은 표현식 연속(expression continuation)이며, 그가 “레이블 값(label values)”이라 부르는 것은 명령 연속(command continuation)이다. 이는 SECD 기계의 덤프를 추상화한 것이다.
SECD 기계와 마찬가지로(하지만 Morris가 eval°, eval′, eval″이라 부르는 “원형(circular)” 인터프리터들과는 달리), 연속을 사용하는 이 인터프리터는 그것이 작성된 언어가 값에 의한 호출이든 이름에 의한 호출(call by name)이든 상관없이 값에 의한 호출 언어를 정의한다.
자신의 작업을 돌아보며 Morris는 다음과 같이 말한다:
내 생각에 연속으로 프로그래밍하는 데 대한 주된 영감은 Lisp 1.5 Programmer’s Manual [21]에 기술된 세 함수 prop, sassoc, search였다 … 나는 McCarthy나 다른 누군가가 프로그래밍 예제에서 같은 종류의 일을 한 것을 본 기억이 없지만, 일어났을 수도 있다. [25]
그는 Snobol [11]과 Cogent [34]의 실패 메커니즘에서도 어느 정도 영감을 얻었다고 믿는다. 연속을 발견하기 전, 그는 Snobol의 정의를 다음 아이디어로 전개하고 있었는데,
… 기억하기로는 모든 함수에 성공 시 연속과 실패 시 연속, 두 개의 연속 인자가 필요하다는 아이디어를 구체화한 것뿐이었다. 나는 하나만 있는 것보다 두 개의 연속이라는 선택이 더 알아보기 쉬웠던 것 같다. [25]
본 저자는 Morris의 강연에 참석할 수 있는 행운을 가졌다. 그것은 내가 연속을 사용하는 것을 처음 접한 경험이었고, 추상성 및 순환성 정도가 서로 다른 정의적 인터프리터의 다양한 스타일이 존재한다는 사실을 처음 배운 자리였다. 이 아이디어들은 나의 정의적 인터프리터 작업 [36]의 기원이 되었고, 그것은 결국 연속을 대중화하는 데 크게 기여했다.
이야기의 다음 부분은 1인칭으로 가장 간단히 전개할 수 있다.
1970년 12월 에든버러 대학을 방문했을 때, Rod Burstall과 Chris Wadsworth(당시 옥스퍼드 대학 대학원생)와 대화하면서 나는 Queen Mary에서의 Lockwood Morris의 콜로퀴움을 요약해 이야기했다. Morris의 아이디어의 성격을 이해하자마자 Wadsworth는 “그게 내가 하고 있던 거야”라고 외쳤다.
실제로 Wadsworth는 레이블과 goto의 동작을 기술하기 위해 연속을 사용하는 방법을 발견했고, 이 방법이 값에 의한 호출 및 평가 순서를 제한하는 다른 구성요소들을 기술하는 데도 충분함을 곧 깨달았다. 하지만 그는 정의적 인터프리터가 아니라 Dana Scott의 당시 새로운 격자 이론적 의미론 [39, 40]에서의 표시적 정의를 작업하고 있었다. 그의 말로는:
1969-70 동안 나는 Christopher Strachey의 지도 아래 [점프에 대한] 좋은 표시적 의미론(당시에는 ‘수학적 의미론’이라 불렸다)을 얻으려 노력했다. 우리는 여러 “정교한” 도식들을 고안했지만, 그 어떤 것도 만족스럽지 않았다.
또한:
그러다 A. Mazurkiewicz [18]의 논문을 접했고 … 그것이 우리에게 필요한 불꽃을 주었다. 나는 그 결과로 나온 개념/접근에 대해 “continuation(연속)”이라는 용어를 만들었다. [47]
그리고 다른 불꽃은, 그 전 수개월(1969-70)의 고투가 나를 “거꾸로 생각하기(thinking backward)”로 이끌었지만, 그것을 표시적으로 어떻게 표현할지 보지 못했던 것이었다. Mazurkiewicz의 논문을 읽고 난 뒤 어려우며 지저분하던 것을 너무도 단순하게 만들어 주는 핵심 통찰을 얻었다. 그 통찰은: “프로그램의 나머지의 의미”라는 개념을 도입하라는 것이었다. [48]
‘continuations’라는 단어에 대해 그는 다음과 같이 덧붙였다:
종종 올바른 단어를 얻는 것이 촉매가 되는데, 내게도 그랬다. 단어를 만들어 내자 모든 것이 맞물렸고 나머지(의미 영역, 의미 방정식 등)는 며칠 만에 따라왔다. 그 단어가 있으니 쓰고, 토론하고, 전파하기가 쉽고 자연스러웠다(몇 번이나 더 짧은 단어였으면 좋겠다고 생각하긴 했지만!). [48]
Wadsworth는 연속에 관한 작업의 출판을 미루고, 람다 계산의 표시적 모델과 그래프 환원에 관한 박사 논문 주제 [46]를 추구했다.
(일반적인 지연 사유들 외에도) Strachey는 유망한 아이디어는 출판하기 전에 한동안 함께 살아 보며 시험해 보는 것이 종종 좋다고 느꼈다—요즘(또는 그때?) 지배적인 관행은 아니지만! 그는, 아이디어의 발명자는 세상에 잠정적 가치일 수 있는 결과로 귀찮게 하기 전에, 그것을 점검하고 어느 정도 다듬을 시간을 스스로에게 허락해야 한다고 생각했던 것 같다. [48]
마침내 Strachey는 1973년 5월 프랑스 IRIA(현재 INRIA)에서 세미나로 이 아이디어를 설명했고, 서면본은 IRIA [42]로 출판되었으며, 수정·소폭 확장판이 옥스퍼드 Programming Research Group 보고서 [43]로 나왔다.
구체적으로 이 보고서들은 레이블과 점프가 있는 명령형 언어(표현식 안에 중첩된 블록 밖으로 점프하는 경우 포함)에 대한 연속 스타일의 표시적 정의를 제공했다. 텍스트는 대부분 Strachey가 썼지만, 근본적인 “연속의 방법(method of continuations)”은 Wadsworth의 것이었다. (예시 언어에 프로시저가 포함되어 있지는 않았지만, Wadsworth는 함수 프로시저의 처리를 이해하고 있었던 것으로 보인다.)
1971년 상반기, James H. Morris, Jr.(당시 UC 버클리, 그리고 F. L. Morris의 먼 사촌)는 Algol 유사 언어(구체적으로 Algol 60의 상당한 부분집합) 프로그램에 대한 CPS 변환을 기술한 논문 [28]을 Communications of the ACM에 제출했다.
그 변환은 van Wijngaarden의 것과 유사했으나, 더 자세히 기술되었고, 중첩 블록에 대한 오류를 피했으며, 함수 프로시저와 적절 프로시저를 같은 틀에서 다뤘다(함수 프로시저를 предвар 단계에서 적절 프로시저로 바꾸지 않았다). Morris는 또한 레이블과 goto 제거 외에도, 변환이 배열, 프로시저, 레이블 등과 같이 복잡한 결과를 반환하는 프로시저의 등장도 제거할 수 있음을 지적했다(그런 프로시저를 허용하는 더 풍부한 언어에 적용한다는 가정 하에서).
심사자는 이 논문의 기본 아이디어가 van Wijngaarden에 의해 이미 선행되었음을 알아차렸고, 그 결과 논문은 거절되었다. 대신 Morris는 짧은 편지 [29]를 출판했는데, 프로그램 변환을 자세히 설명하지는 않았지만, 그것이 복잡한 값을 반환하는 프로시저를 제거하는 데 쓸 수 있음을 보였다. (그 편지는 또한 변환된 프로그램을 전통적인 스택 기반 방식으로 구현하면 스택을 빠르게 소진한다는 점을 언급했다.)
돌이켜보며 Morris는 다음과 같이 말한다:
내가 연속 방법을 처음 발견한 상세 과정은 도무지 기억나지 않는다. 그러나 나는 처음에 그것을 순수 람다 계산 기법으로 구상했는데, 이는 분명 Peter Landin의 J-연산자와 여러 해 함께 살아온 결과였을 것이다(그 연산자는 다른 발견자들에게도 무대를 깔아 주었을 것이다). 나는 그 아이디어를 독자들이 더 접근하기 쉽도록 Algol 60으로 힘들게 번역했다. [30]
1972년 1월, 뉴멕시코 주 라스 크루세스에서 열린 ACM “프로그램에 대한 단언(assertions) 증명” 회의에서 Michael J. Fischer(당시 MIT)는 “Lambda Calculus Schemata” [12]라는 논문을 발표했다. (최종적이고 더 완전한 버전은 본 학술지 특집호 [13]에 실려 있다.) 이 논문에서 그는 값에 의한 호출 람다 계산을 조건식, 미해석 상수, 원시 함수로 확장했고, 이 함수형 언어를 CPS로 변환하는 변환을 기술했다.
Fischer의 목적은 임의의 프로그램이 (CPS 변환을 통해) 스택으로 구현 가능한 형태로 변환될 수 있음을 보이는 것이었다. 즉 프로시저 실행 중 할당된 저장 공간이 프로시저가 종료될 때 삭제될 수 있는 형태 말이다. 물론 대가로(이미 J. H. Morris [29]가 언급했듯) 스택은 프로그램 실행이 끝날 때까지 결코 팝(pop)되지 않는다.
Fischer의 논문은 연속 의미론에 관한 최초의 정리 증명으로 주목할 만하다. 즉 CPS 변환이 적절한 의미에서 의미(meaning)를 보존한다는 것이다. 이 결과는 람다 표현식이 클로저(closure)를 나타내는 설정에서 얻어졌다. (연속의 의미에 대한 표시적 의미론 설정—즉 람다 표현식이 연속 함수(continuous function)를 나타내는 설정—에서의 결과들은 몇 년 뒤에야 등장했다 [23, 37, 24, 38].)
1972년 1월의 Fischer [12] 논문, 그리고 8월의 J. H. Morris [29] 및 Reynolds [36] 논문의 출현으로 연속은 1972년 말까지 널리 알려지게 되었다. 그럼에도 이후에도 적어도 한 번의 ‘재발견’이 있었다.
1973년 2월, S. Kamal Abdali(당시 위스콘신 대학 대학원생으로, 박사 논문을 진행하며 뉴욕대에서 강의 중)는 오하이오 주 콜럼버스에서 열린 제1회 Computer Science Conference에서 짧은 논문을 발표했다. 그는 Algol 60 프로그램을 비형식 람다 계산으로 번역하는 새로운 언어 정의 형태를 설명했다. 이 작업은 제1회 ACM POPL에 제출되었으나, 확장 초록이 프로시저 처리를 설명하지 않았다는 이유로 거절되었다. 그해 여름, 프로시저 처리를 포함한 작업이 예비 보고서 [1]로 출판되었다. Abdali는 이후 뉴욕 주 트로이의 Rensselaer Polytechnic Institute로 옮겼고, 1974년 위스콘신 박사 학위 논문 [2]을 마쳤다.
Abdali에 따르면, J. Barkley Rosser와 그 추종자들(그의 지도교수 George Petznick 포함)은
… Landin이 Algol 60과 람다 계산 사이의 대응을 확립하는 데서 사용했던 람다 계산에 대한 확장 [15]이, 그 대응을 이용해 프로그램의 성질을 도출하는 데 어렵게 만든다고 느꼈다. 그러므로 내 임무는 프로그래밍 구성 요소들을 “순수(pure)” 람다 계산으로 번역하는 것이었다. 예컨대 대입은 메모리, 주소, fetch 및 store 연산의 개념을 피하고 치환(substitution)으로 모델링되어야 했다. [5]
Algol 60의 명령형 측면을 다루기 위해 Abdali는 CPS 변환과 매우 유사한 번역을 고안했다. 그는 연속(그가 “program remainder”, 즉 “프로그램의 나머지”라고 부른 것)의 아이디어가
… J. H. Morris의 학위 논문 [27], 특히 38-39쪽의 개요가 실제로 작동하도록 만들려는 시도에서 영감을 받았다. 그 뒤 연속은 블록 구조뿐 아니라 점프와 레이블을 다루는 길을 열었다. 연속의 힘과 중요성은 이름에 의한 호출(call-by-name)의 어려움을 극복하면서 확인되었다; 그 구성 요소는 호출하는/호출되는 문맥을 나타내기 위해 즉시 연속(immediate continuations)과 원격 연속(remote continuations)을 사용해 해명되었다. [5]
Abdali가 자신의 “program remainders”를 앞선 연속의 발견들(F. L. Morris와 Wadsworth)과 처음 연결한 것은, 박사 논문에서 파생된 출판 논문들 [3, 4]에서였다. 그는 이후 Franz Winkler [6], David S. Wise [7]와의 공동 작업에서 Algol 유사 언어 모델링에 자신의 접근을 사용했다.
요약하면, 본 저자의 지식이 미치는 한 연속 또는 매우 가까운 관련 개념은 1964년 van Wijngaarden에 의해 처음 발견되었고, 1970~1971년 동안 지리적·지적 환경의 매우 다양한 곳에서 반복적으로 재발견되었으며, 그 이후에도 때때로 재발견되었다.
가장 큰 수수께끼는 van Wijngaarden의 초기 작업이 왜 널리 이해되지 못했는가 하는 점이다. 여러 추측은 가능하지만, 특히 Strachey(1975년 5월 18일)와 van Wijngaarden(1987년 2월 7일)의 사망 이후로는 확실히 알기 어려울 것이다.
그럼에도 연속의 초기 역사는, 독창적 아이디어가 완전한 일반성 속에서 태어나는 경우가 드물며, 그 전달이 언제나 단순하거나 곧장 이루어지는 일이 아님을 날카롭게 상기시켜 준다.
이 논문을 크게 개선해 준 의견과 회고를 제공한 Kamal Abdali, Jaco de Bakker, Olivier Danvy, Edsger Dijkstra, Matthias Felleisen, Andrzej Filinski, Michael Fischer, Dan Friedman, Peter Landin, Antoni Mazurkiewicz, John McCarthy, Douglas McIlroy, Lockwood Morris, James Morris, Peter Naur, Dana Scott, Tom Steel, Guy Steele, Carolyn Talcott, Mads Tofte, Chris Wadsworth에게 감사한다.
