Icon 프로그래밍 언어의 목표 지향 식 평가 시스템을 설명하고 비판적으로 검토하며, 유사한 시스템을 현대적 동적 타입 언어인 Converge에 통합한 경험과 교훈을 정리한 논문.
이 논문을 다음과 같이 인용하십시오:Icon과 유사한 식 평가 시스템에 대한 경험, Laurence Tratt, Proc. Dynamic Languages Symposium, pages 73-80, October 2010} (BibTeX file).
Icon과 유사한 식 평가 시스템에 대한 경험
Laurence Tratt
Middlesex University, The Burroughs, Hendon, London, NW4 4BT, United Kingdom
Icon 프로그래밍 언어의 식 평가 시스템은 제한된 백트래킹을 수행할 수 있으며, 만들어졌을 당시 명령형 프로그래밍 언어들 가운데서도 독특한 존재였다. 이 논문에서는 원래의 Icon 설계를 설명하고 비판적으로 검토하며, 유사한 시스템을 현대의 동적 타입 언어에 어떻게 통합할 수 있는지를 보인다. 마지막으로 이 시스템에 대한 나의 경험을 자세히 설명하고, 여기서 얻을 수 있는 교훈에 대한 제안을 제시한다.
분류 및 주제 기술자 D.3.3 [Programming Languages]: Language Constructs and Features
핵심어 Language design, Icon, Converge
Icon [3 ]은 주로 Ralph Griswold가 설계한 프로그래밍 언어로, 범용 언어로 사용할 수 있도록 의도되었지만 특히 텍스트 처리에 매우 적합하다. Icon의 직접적인 전신은 거의 알려지지 않은 SL5인데, 설계자에 의해 막다른 길로 여겨져 곧바로 폐기되었다 [2]. 논쟁의 여지는 있지만, 진정한 전신 언어는 더 잘 알려진 SNOBOL4 [5]라고 할 수 있다. 실제로 Icon은 초기 개발 단계에서 SNOBOL5로 알려져 있었다. SNOBOL4는 텍스트 처리를 명시적으로 목표로 했으며, 현대적 용어로는 범용 계산에는 적합하지 않기 때문에 도메인 특화 언어(DSL)로 간주될 것이다. Icon은 SNOBOL4풍의 텍스트 처리 능력을 동적 타입의 범용 프로그래밍 언어에 통합한 것으로 볼 수 있다.
Icon의 식 평가 시스템은 목표 지향 평가라고 부르는 방식을 사용하며, 최근까지도 백트래킹이 가능한 유일한 명령형 프로그래밍 언어였다. Icon의 목표 지향 평가 전략은 일부 선언형 언어들에서 사용되는 백트래킹(예: Prolog)만큼 강력하거나 광범위하지는 않지만, 놀랄 만큼 복잡한 관계를 표현할 수 있다. 백트래킹을 가능하게 하기 위해, Icon의 식 평가 시스템 설계는 다른 명령형 언어들과 근본적으로 다르다. 그럼에도 불구하고 ‘평범한’ 식 평가는 대부분의 다른 언어들과 동일한 관찰 가능한 효과를 보장한다. 다만 그 효과를 달성하는 수단은 대개 같지 않다. Icon 식 평가 시스템의 기반은 여러 표준적인 가정에 도전한다.
현대의 시각에서 보면 Icon은 1970년대의 유산을 반영하는 다소 구식의 느낌을 준다. 문법적으로는 동적 타입의 Algol 변형으로 설명할 수 있고, 의미적으로는 값과 참조를 구별하는 것처럼 유사한 언어들이 오래전에 버린 여러 ‘불행한’ 특성을 지닌다. 이것은 Icon에 대한 비판으로 받아들여져서는 안 된다. Icon은 여러 면에서 시대를 앞섰다. 다만 현대 프로그래머들은 자신의 프로그래밍 언어에 대해 약간 다른 것을 기대한다는 관찰일 뿐이다. 오늘날 Icon은 공정하든 아니든 대체로 잊힌 언어가 되었다. 그러나 그 영향의 작은 요소들은 다른 언어들 속에 살아 있다. 예를 들어 Python의 generator는 Icon의 대응 개념에서 영감을 받았다. 비록 그만큼 강력하지는 않지만 말이다 [8].
내가 Converge 언어 [11]를 설계할 때, 나는 Icon에서 크게 영감을 받은 식 평가 시스템을 통합했다. 내가 아는 한, Converge는 Icon의 직접적인 복제판이 아닌 언어로서 이러한 시스템을 통합한 최초이자, 현재까지도 유일한 언어이다. 이 논문1에는 두 가지 목적이 있다. 첫째, Icon의 식 평가 시스템 설계가 다른 프로그래밍 언어에서도 추출되고, 재사용되며, 필요에 따라 변경될 수 있음을 암묵적으로 보여준다. 둘째, 원래 Converge 설계에 가해진 변경, 그로부터 배운 교훈, 그리고 이후의 미래 아이디어를 기록하는 데 목적이 있다.
이 논문의 구성은 다음과 같다. 먼저 Icon과 그 식 평가 시스템의 개요를 제시한다. 이어서 이 시스템의 여러 불행한 측면을 설명하고, 그 다음 Converge가 이러한 측면들을 어떻게 해결하려 하는지 설명한다. 이어서 성능상의 함의를 간단히 기술하고, 가능한 최적화를 제안한다. 마지막으로 내 경험에 비추어 이러한 식 평가 시스템의 장점과 단점을 제시한다.
이 절의 목적은 Icon의 두드러진 특징들에 대한 기본적인 소개를 제공하는 것이다. 이것은 전체 매뉴얼 [3]을 대체하는 것이 아니지만, 주류 프로그래밍 언어에 익숙한 독자들이 이 논문의 나머지 부분을 이해하는 데 충분한 정도로 Icon을 파악할 수 있게 해 줄 것이다.
Icon은 Algol풍의 키워드 기반 문법을 사용하는 절차적 동적 타입 언어이다. 이 언어의 나머지 부분과 비교했을 때 한 가지 문법적 특이점은 if 구문의 절이나 while 루프의 본문과 같은 식들의 묶음이 중괄호로 둘러싸인다는 점이다. Icon은 문장과 식을 구별하지 않는다. 많은 언어에서 문장은 값을 생산하지 않고 식은 값을 생산하지만, Icon에서는 모든 것이 식이다. 다만 곧 보겠지만, Icon의 식이 항상 값을 생산하는 것은 아니다.
파일의 줄 수를 세고 출력하는 완전한 Icon 프로그램 하나, 즉 Unix 명령 wc -l에 해당하는 프로그램은 다음과 같다:
이 단순한 프로그램에는 뭔가 특이한 점에 대한 작은 힌트가 하나만 있다. Icon의 read 함수는 주어진 파일의 다음 줄을 반환한다. 파일의 모든 줄을 읽고 나면, read는 while 루프의 조건을 실패시키고 실행이 write 함수로 넘어가게 만든다. 이것이 일어나는 메커니즘은 다음 하위 절에서 살펴본다.
전통적인 명령형 프로그래밍 언어에서 식은 값을 생산한다. 그러나 Icon에서는 식이 성공하거나 실패한다. 성공하는 식은 값을 생산하고, 실패하는 식은 값을 생산하지 않는다. 어떤 식이 실패하면, 그 실패는 자신을 둘러싼 식으로 전달되며, 그 식 역시 재귀적으로 실패할 수 있다. 이 개념은 Icon 식 평가 시스템의 핵심에 있다. 실패의 개념은 종종 예외와 혼동되지만, 둘은 전혀 다른 것이다. 예외는 바람직하지 않은 동작, 예를 들어 파일을 열 수 없는 상황을 나타내는 반면, 실패는 식이 더 이상 값을 생산할 수 없음을 나타낸다. 예를 들어 2.1절의 read 함수가 그렇다. 두 개념은 서로 직교하며, 한 언어 안에 둘 다 존재할 수 있다. 다만 Icon 자체에는 예외가 없다.
서로 다른 상황에서 성공할 수도 있고 실패할 수도 있는 식의 간단한 예는 x < y이다. x가 2이고 y가 3이면 식은 성공하고 값 3이 생산된다. Icon에서는 관계 연산자가 성공할 경우 오른쪽 값을 생산한다. 반대로 x와 y의 값이 뒤바뀌어 있으면, 식은 실패하고 아무 값도 생산되지 않는다. 이것이 시사하듯, Icon에는 표준적인 불리언 논리가 없다. 실제로 불리언 데이터 타입도 없고, 관습적인 불리언 연산자도 없다. 그럼에도 불구하고 ‘정상적인’ 사용에서는 표준 구성 요소들이 대부분의 주류 프로그래밍 언어와 동일한 관찰 가능한 효과를 보이므로, 다음과 같은 코드는 일반적인 기대대로 실행된다:
Icon에서는 중첩된 식이 유효하며, 실패는 재귀적으로 전파된다. 이 전파의 한계에 대해서는 2.5절에서 자세히 설명한다. 따라서 식 z := x < y는 식 x < y가 성공할 때에만 y의 값을 z에 대입한다. x < y가 실패하면 z에는 아무 대입도 이루어지지 않으며, 이전 값을 유지한다.
Icon에서 procedure는 0개 이상의 값을 생성할 수 있다. 관례적으로 항상 정확히 하나의 값을 생성하는 것들은 단순히 procedure라고 부르고, 가변적인 개수의 값을 생성할 수 있는 것들은 generator라고 부른다. suspend 키워드는 일반적인 return과 비슷하지만, 함수 호출자에게 값을 전달하는 것에 더해 generator의 호출 스택을 저장한다. 이후 generator는 재개될 수 있고, 이때 generator의 호출 스택이 다시 복구되며 실행은 suspend 호출 바로 다음부터 계속된다. 이를 통해 generator는 여러 값을 생산할 수 있다. generator의 문법적 끝에 도달하거나 return &fail이 실행되면 generator는 값 생성을 마친 것이며, 실패가 호출자에게 전달된다.
generator ito를 사용해 1부터 9까지를 출력하는 다음 완전한 프로그램을 보자:
every 구문은 전형적인 for 문과 대체로 동등하다고 볼 수 있으며, Icon에서 generator의 모든 값을 소비하는 표준적인 방법이다. 위 코드는 먼저 ito를 호출하고, ito는 값 0과 함께 자신을 suspend한다. 이 값은 x에 대입되고 every 구문의 본문이 실행된다. 본문이 실행된 후 every는 중단된 ito generator를 재개하고 루프를 반복한다. generator가 결국 실패하면, every 구문 자체도 실패한다. while과 every는 매우 다른 구문이라는 점에 주목하자. every는 자신의 식을 한 번 평가한 뒤, 그것이 generator이면 계속해서 값을 끌어내지만, while은 매 반복마다 식을 새로 평가한다.
그 밖에 주목할 만한 generator 유형이 두 가지 더 있다. generator i to j는 i부터 j까지의 모든 값을 생성한다. 이는 앞서 사용한 ito 예제와 비슷하다. 더 놀랍게도, 특수한 유형의 generator 하나가 불리언 개념의 ‘or’를 흡수한다. Icon의 alternation 연산자 ‘|’는 procedure가 아닌 generator로, 각 값을 순차적으로, 따라서 지연적으로 생성한다. 목표 지향 평가(2.4절 참조) 덕분에 if x | y와 같은 구문은 일반적인 기대대로 동작한다. 그러나 every write(1 | 2) 같은 식에서 alternation을 명시적으로 활용할 수도 있으며, 이 경우 1 다음 2를 출력한다.
앞서 말했듯, Icon의 목표 지향 평가 전략은 제한된 형태의 백트래킹을 허용한다. 이는 가장 쉽게 conjunction 연산자 ‘&’를 통해 볼 수 있다. 이 연산자는 둘 이상의 하위 식을 연결하며, 각 하위 식이 모두 성공할 때에만 성공한다. 어떤 하위 식이 실패하고, 그보다 앞선 식들 가운데 하나가 generator라면, 제어는 그 generator로 되돌아가고 generator는 재개되어 또 다른 값을 생성한다. 그 뒤 conjunction는 generator 다음 지점부터 실행을 계속한다. 2.3절 프로그램을 단순히 수정하면 0부터 9까지의 짝수를 출력할 수 있다:
이것은 다음과 같이 동작한다. 먼저 ito 함수가 호출되고, 값 0과 함께 중단된다. 이 값은 x에 대입된다. 0 %2 == 0이 성공하므로 conjunction가 성공하고 every 구문의 본문이 실행된다. 그 다음 every는 ito에서 다음 값 1을 끌어오고 이를 x에 대입한다. 그러나 1% 2 == 0은 실패하므로 conjunction는 즉시 백트래킹을 일으켜 every 구문의 본문을 실행하지 않은 채 ito에서 다음 값을 끌어온다.
Icon에는 목표 지향 평가와 관련된 다른 기능들도 있다. 백트래킹이 reversible assignment 위를 지나가면, 즉 일반적인 비가역 대입과 구별하기 위해 x <- e 문법을 사용하는 대입 위를 지나가면, 변수 x는 대입 이전의 값으로 되돌아간다. 제한 생성 e \ i는 generator가 최대 i번까지만 값 생성되도록 허용한다.
Prolog 같은 언어에서는 백트래킹이 임의의 깊이까지 일어날 수 있다. 물론 ‘cut’ 술어로 제한하지 않는 한 그렇다. 명령형 언어에서의 백트래킹은 실용적으로도 철학적으로도 그만큼 광범위할 수 없다는 점은 분명하다. 실용적으로는 백트래킹을 허용하려면 일반적으로 무한정한 양의 메모리가 필요하여 예상치 못한 성능 문제를 일으킬 것이고, 철학적으로는 기본적인 명령형 프로그래밍 구성 요소들에 대한 널리 공유된 기대를 전복하게 될 것이다. Icon의 해결책은 경계 지어진 식이라는 개념이다. 백트래킹은 경계 지어진 식 안에서만 일어날 수 있다. 이것이 의미하는 바는 Icon의 백트래킹이 본질적으로 국소적이며 작은 단위로 제한된다는 것이다. Icon의 경계 지어진 식은 일반적인 기대를 보존하도록 의도적으로 선택되었다. 예를 들어 if 구문의 조건은 경계 지어진 식이며, 줄바꿈으로 구분된 최상위 식들도 마찬가지다.
이 절에서는 내가 Icon의 식 평가 전략 설계와 관련해 마주친 여러 문제를 나열한다. 이 절의 목적이 일반적인 Icon 비판이 아니라는 점에 유의하라. Icon은 설계된 시대를 반영하며, 기본값을 가진 변수나 변수와 참조의 구별과 같은 특성은 현대 프로그래머들에게 흔히 결함으로 여겨진다. 그러나 그런 문제들은 이 논문의 핵심과 관련이 없으므로 여기서는 고려하지 않는다.
Icon에서 procedure의 기본 ‘반환값’은 실패이다. 다시 말해 각 procedure의 끝에는 암묵적인 return &fail이 있다. 이것은 마지막 동작이 더 이상 생성할 값이 없음을 알리는 ito 같은 generator에게는 매우 유용하다. 그러나 다음과 같은 겉보기에 무해한 비-generator procedure는 매우 디버깅하기 어려운 방식으로 동작하게 만든다:
이 프로그램을 실행하면 화면에는 아무것도 출력되지 않는다. f의 조건이 실패하면 procedure는 기본 반환 동작을 실행하는데, 그것은 실패하는 것이다. 따라서 write는 결코 호출되지 않는다. 이 특정 예는 쉽게 디버깅할 수 있지만, x :=f(..) 대입이 실패하는 경우와 같은 이 문제의 변형들은 큰 프로그램에서 심각한 혼란을 일으킬 수 있다.
이 문제를 여러 번 겪은 뒤, 나는 몇몇 프로그램을 간단히 분석해 보았다. 그 결과 generator는 procedure 형태 가운데서도 한참 드물다는 사실이 금방 드러났다. 대부분의 procedure는 항상 하나의 값만 반환한다. 다시 말해 Icon의 기본 동작은 소수의 procedure, 즉 generator에는 유용하지만, 대다수에는 위험하다.
일반적으로 Icon에 불리언 데이터 타입이 없다는 점은 큰 문제가 되지 않는다. 정상적인 조건식 평가는 관례와 일치하는 결과를 낸다. 비록 그 기반 평가 메커니즘은 다르지만 말이다. 실제로 다른 여러 언어들, 예를 들어 K&R C도 불리언 데이터 타입이 없으며, 보통 정수 값이 0이면 거짓으로, 그 외 값이면 참으로 평가된다는 관례에 의존한다. 1은 보통 ‘참’에 사용된다. 그러나 Icon에서는 값을 생산하는 식은 모두 성공하므로, 이 개념을 표현할 동등한 방법이 없다. 따라서 다음 코드는 화면에 taken을 출력한다:
실제로 Icon에서는 변수에 기본값이 있으므로, 심지어 대입 c := 0을 제거해도 위 프로그램의 동작은 바뀌지 않는다.
이를 우회하기 위해서는 개별 코드가 어떤 상황에서 ‘참’과 ‘거짓’ 값이 무엇인지에 대한 관례를 사용해야 한다. 보통은 각각 1과 0을 사용하지만, 이는 if x == 0 같은 문장을 자주 모호하게 만든다. 이것이 정수를 사용한 불리언 검사인지, 아니면 단순한 정수 비교인지 분명하지 않기 때문이다.
Generator는 Icon의 핵심적인 부분이며, 반복된 동작을 수행하기 위해 every 구문 안에서 generator와 일반 procedure를 짝지어 사용하는 것이 흔한 관용구이다. 예를 들어 다음 코드는 generator upto와 일반 procedure write를 사용해 문자열 s 안의 모든 숫자(0-9)의 인덱스를 출력한다:
every write(upto(’0123456789’,s))
일반적으로 코드를 보기만 해서는 write와 upto 가운데 어느 것이 generator인지, 둘 다인지, 둘 다 아닌지를 알 수 없다. 이런 점은 디버깅 중 혼란을 초래할 수 있다. 이 지식이 없으면 코드의 기대 동작을 판단할 방법이 없기 때문에, 이런 generator 관련 관용구의 사용을 꺼리게 만든다.
목표 지향 평가의 주요 특징 가운데 하나는 백트래킹을 허용한다는 점이다. 이것이 달성되는 가장 일반적인 방식은 conjunction 연산자 &로 식들을 연결하는 것이다. conjunction와 every를 결합하면 다음과 같은 간결한 식을 표현할 수 있다. 여기서 upto(c, s)는 문자열 s에서 문자 c가 나타나는 각 인덱스 위치를 생성한다:
every write(i:=upto(’a’,x)&i%2==0&i)
이 코드는 x에서 2의 배수 위치이면서 문자 a를 포함하는 모든 인덱스를 출력한다. 이 경우 4와 6이다. 이 작은 예는 비교적 읽기 쉽지만, 이런 코드가 커질수록 빠르게 읽기 어려워진다. 이를 부분적으로 해결하기 위해 Icon은 문자열 스캐닝 e1?e2 개념을 도입한다. 본질적으로 e1이 평가한 문자열이 e2 안의 코드에 대한 전역 검색 대상이 된다. upto 같은 procedure는 특정 검색 문자열이 지정되지 않으면 ‘전역’ 검색 문자열을 사용하는 프로토콜을 따른다. 위 예는 문자열 스캐닝을 사용해 다음처럼 다시 쓸 수 있다:
every write(x?{upto(’a’)&i%2==0&i})
Icon에는 필요한 프로토콜을 따르는 여러 문자열 매칭 procedure가 있다. 문자열 스캐닝은 백트래킹의 복잡성을 약간 줄일 수는 있지만, 결코 완전한 해결책은 아니다. 게다가 스캔 중인 문자열을 기록하는 &subject와 문자열 검색의 현재 인덱스를 기록하는 &pos라는 두 개의 특수한 준전역 변수와, 이 두 특수 변수를 다루는 함수 집합을 필요로 한다.
훨씬 더 근본적인 문제는, 내 경험상 이 형태의 백트래킹이 문자열 이외의 대상에 대한 복잡한 연산에는 유용할 만큼 충분히 강력하지 않다는 점이다. Icon은 conjunction 내부의 변수 대입이 백트래킹 중 취소되도록 허용하지만, 리스트 내부 대입과 같은 다른 유사한 연산은 되돌리지 않는다. 내가 Icon이 이것을 할 수 있었거나 해야 했다고 주장하는 것은 아니다. 단지 그것이 없기 때문에 많은 시나리오가 배제된다는 뜻이다. 이는 더 복잡한 백트래킹 활용도, Icon 유사 시스템에서 매우 복잡한 백트래킹 예를 보여주는 [12]를 보라, 결국 대부분의 복잡한 백트래킹을 다른 명령형 언어들처럼 수동으로 인코딩해야 함을 의미한다.
요약하면, Icon의 백트래킹은 유용할 수는 있지만 특정한 사용 사례, 주로 문자열 스캐닝과 관련된 경우에만 그렇다.
내가 Converge 언어를 설계할 때 Icon에서 크게 영감을 받은 식 평가 시스템을 통합했다. 이 논문의 목적상 Converge는 Python과 Icon의 절충으로 생각하면 된다. 전자는 전반적인 미학과 문법 측면에서, 후자는 식 평가 시스템 측면에서 그렇다. Converge의 주된 목표는 동적 타입 언어에 매크로풍 시스템을 추가하는 것이었다. 이 시스템은 문법적으로 구별되는 DSL을 구현하는 데 사용된다. Converge에서 구현된 초기 DSL 가운데 다수가 트리와 그래프 구조 위에서 복잡한 매칭을 사용했기 때문에, 충분히 유사한 목적을 가지면서 다른 명령형 언어들에서는 전례가 없던 Icon의 식 평가 시스템을 통합하는 것을 고려하는 것은 자연스러웠다2. 내가 아는 한, Converge는 이런 시스템을 통합한 유일한 비-Icon 복제 언어다. 자명해 보일 수 있지만, Converge의 존재는 Icon 식 평가 시스템의 기반 아이디어가 다른 언어들에도 적용 가능함을 명시적으로 보여준다는 점을 지적할 가치가 있다.
Converge의 대부분의 측면은, 식 평가 시스템을 제외하면, 다른 곳에 문서화되어 있다. 예를 들어 [10,13]를 보라. 따라서 여기서는 대부분을 다루지 않고, Converge의 Icon 계승과 관련된 측면에 집중한다. 역사적으로 말하면 초기 버전의 Converge는 Icon의 식 평가 시스템을 거의 그대로 물려받았다. 시간이 지나면서 여러 변화가 도입되었다. 이 절에서는 그 변화를 설명하고 그 동기를 제시한다. 이하의 모든 예제 코드는 Icon이 아니라 Converge로 작성되었다.
나는 Icon이 procedure의 기본 반환을 fail로 만든 결정에 대해 두 가지 해결책을 고려했다. 3.1절 참조. 첫째, generator와 procedure를 문법적으로 구별하여 전자는 기본적으로 실패하고 후자는 그렇지 않게 할 수 있다. 둘째, 모든 procedure가 기본적으로 실패하지 않게 만들 수 있다. 새로운 문법이 주는 부담과 generator가 흔하지 않다는 점을 고려하면, 결정은 쉬웠다. Converge 함수는 많은 다른 언어와 비슷하며, 기본 반환 동작은 null 객체를 반환하는 것이다. 이는 3.1절에서 지적한 흔한 문제를 해결하는 대신, 덜 흔한 문제를 초래한다. 끝에서 명시적으로 fail하지 않는 generator는 마지막 객체로 null을 반환한다. 명시적 fail의 부재가 실수일 때, 이는 보통 null 객체에 대해 잘못된 연산을 수행하는 결과로 나타나기 때문에 원래 문제보다 상대적으로 디버깅하기 쉽다.
3.2절에서 설명했듯, Icon에는 불리언 데이터 타입이 없다. 그 결과 많은 평범한 프로그래밍 작업이 평소보다 더 번거로워진다. Icon과 유사한 언어에 단순히 불리언 데이터 타입을 추가하면, 언제 ‘false’가 실패를 일으켜야 하는지에 대한 까다로운 질문들이 생긴다. 두 개념은 어떤 경우에는 분명히 관련되지만, 어떤 경우에는 그렇지 않다. 예를 들어 2 < 1이 if 문의 else 분기를 실행하게 해야 한다는 것은 분명하지만, x := 2 < 1 같은 문장은 어떻게 되어야 할까? x에 ‘false’ 값이 대입되어야 할까, 대부분의 언어처럼? 아니면 Icon처럼 아예 대입이 실행되지 않아야 할까? 이런 경계 사례들에서 Icon 유사 동작을 유지하면서 전형적인 불리언 데이터 타입을 통합하는 것은 어려워 보인다.
그래서 나는 조건문을 실패시키는 값을 하나만 가지면 된다는 생각에 기반한, 보다 Icon다운 해결책을 찾고자 했다. 그러면 if b나 if not b 같은 관용적인 코드를 쓸 수 있게 된다. 이에 따라 Converge 런타임에 fail 값을 도입했다. 이는 null과 유사했으며, 본질적으로 fail은 싱글턴 객체를 가리키는 키워드였다. if나 return 같은 문장이 자식 식을 평가해서 fail 값을 받으면, 부모 문장은 실패하게 했다.
대부분의 단순한 불리언 사용 사례에서는, 이렇게 뒷문으로 불리언 비슷한 데이터 타입을 도입하는 방식이 매우 잘 작동했다. 그러나 불쾌한 경계 사례들도 생겨났다. 다음 Converge 코드를 보자:
이 코드는 아무것도 출력하지 않았다. l[1]은 l.get(1)의 동의어인데, 그것이 return fail을 평가하려 했고, 그 결과 get이 실패했기 때문이다. 이것은 인위적인 예처럼 보일 수 있지만, 약간 변형된 형태가 실제 코드에서 나타났다. Converge 모듈은 자신의 정의들과 그에 연결된 값들을 열거할 수 있는데, 모든 모듈은 null 같은 렉시컬 스코프용 표준 정의를 포함한다. 그 가운데 하나의 이름이 fail이었고, 당연히 fail 객체를 가리켰다. 그 정의의 값을 알아내려 하면 위의 l.get(1)과 같은 문제가 발생했고, 디버깅에 엄청난 시간이 들었다.
이 문제는 fail 객체가 근본적으로 위험하다는 깨달음으로 이어졌다. 이를 완화하려는 시도는 위험을 없애기보다는 단지 다른 곳으로 옮길 뿐일 가능성이 컸다. 컴파일러가 강제하지는 않지만, fail을 포함하는 유일하게 안전한 관용구는 return fail이라는 관례가 생겨났고, 이는 약 2년 동안 지켜졌다. 결국 fail은 Converge에서 완전히 추방되었다. 현재 버전의 Converge에서 fail은 generator를 실패시키는 문장이다. 사용자에게 fail 객체에 대한 접근을 제거한 것은, 비록 그것이 Converge VM 내부에는 여전히 존재하지만, 사용자들이 Icon과 같은 불리언 인코딩 기법을 다시 사용하도록 만들지만, 결과적으로 개념적으로 훨씬 덜 문제가 된다.
3.3절에서 보았듯, Icon에서는 주어진 함수 f 호출이 generator인지 일반 함수인지 정적으로 판별할 수 없다. 이는 특히 Converge에서 볼 수 있는 OO 다형성과 결합될 때 코드를 읽기 어렵게 만든다. 나는 이 문제에 대해 두 가지 해결책을 고려했다. 첫째, generator 호출을 위한 새로운 문법을 도입할 수 있다. 둘째, generator 함수 이름에 대한 관례를 도입할 수 있다. 가능하면 Converge에 새로운 문법을 추가하지 않으려 했기 때문에, 나는 두 번째 방식을 택했다. 일반적으로 Converge의 generator 이름은 iter _ 접두사를 붙인다. 이 방식은 눈에 거슬리지 않으면서도, 해당 함수가 generator임을 드러낸다. 이는 코드 가독성을 놀라울 정도로 크게 향상시킨다.
Converge는 reversible assignment 같은 Icon의 고급 백트래킹 기능이 약하다는 점을 인정하고, 그것들을 아예 포함하지 않는다. 다만 3.4절에서 사용한 단순한 백트래킹은 Icon과 Converge에서 동일하게 동작한다는 점에 유의하라. 이는 실질적인 기능을 크게 잃지 않으면서 언어를 상당히 단순화한다. 예를 들어 reversible assignment는 극히 드물게 사용되며, 심지어 Icon의 핵심 라이브러리 안에서도 그렇다. 이 문제의 가능한 해결책은 Icon의 백트래킹 능력을 더 강화하여 예를 들어 Prolog에 더 가깝게 만드는 것처럼 보일 수도 있다. 그러나 나는 이것이 비현실적이라고 생각한다. 가변 상태는 데이터 공유를 방해하므로, 백트래킹을 허용하려면 엄청난 양, 그리고 일반적으로 무한정한 양의 메모리가 빠르게 소모될 것이다. 이는 메모리를 빠르게 고갈시킬 뿐 아니라, 불변 상태일 때보다 훨씬 큰 규모로 데이터를 복사하고 가비지 컬렉션해야 하므로 큰 성능 손실도 초래한다. 더 미묘하게는, 이것은 명령형 프로그래밍 언어가 주는 암묵적 보장 가운데 하나인 예측 가능한 성능을 훼손한다. 요약하면, 사용자는 그런 고급 백트래킹 기능을 거의 사용하지 않을 가능성이 크고, 그것들은 얻는 것에 비해 언어와 구현에 많은 복잡성을 추가하며, 내가 보기에는 Icon의 설계 목표에서도 벗어난다.
특히 Converge에는 문자열 스캐닝에 해당하는 기능이 없다. 이유는 두 가지다. 첫째, 현대의 정규 표현식 라이브러리는 문자열 스캐닝의 대부분의 단순한 경우를 포괄하고, 형식적인 파싱 도구, 즉 문맥 자유 문법을 이용한 파싱은 대부분의 복잡한 경우를 포괄한다. 둘째, 문자열 스캐닝은 전역 또는 준전역 변수와 그것들에 대한 특권적 접근에 관한 문제를 일으킨다. 전역 변수를 사용해야 할 이유가 가끔은 있지만, 그것을 흔한 것으로 만드는 것은 아무리 좋게 보아도 위험하다.
Icon과 Converge는 둘 다 스택 기반 가상 머신(VM)으로 구현된다. 두 시스템 모두에서 컴파일러는 소스 코드를 바이트코드로 변환하고, 그 바이트코드는 VM에 의해 실행된다. 각 VM의 많은 부분은 비교적 표준적이지만, Icon의 식 평가 시스템은 특이한 접근을 요구한다. Converge는 이 점에서 Icon의 VM을 매우 밀접하게 따른다. 따라서 이 절의 대부분은 Converge의 구현을 기준으로 설명한다. Converge 쪽이 더 작고 실험하기에 용이하기 때문이다. 그러나 일반 원리는 Icon에도 쉽게 적용 가능하다.
Icon 유사 VM이 표준 VM 원리에서 벗어나야 하는 주된 이유는 실패 때문이다. 이는 여러 함의를 가지며, 특히 실패를 올바르게 처리하기 위해 스택 연산에 크게 의존하게 만든다. 예를 들어 Converge에서 다음 코드 조각은:
다음과 같이 번역된다:
ADD _FAILURE _FRAME rest//아래에서 실패가 발생하면,
Converge의 스택은 소수의 항목 유형만 가진다. 주로 continuation frame, 이 논문의 목적상 ‘함수 호출 프레임’으로 생각하면 된다, failure frame, 식 평가 중 실패가 발생했을 때 무엇을 해야 하는지 기록한다, generator frame, 중단된 generator의 상태를 기록한다, 그리고 객체 참조들이다. 어느 시점에서든 스택은 현재 continuation frame, failure frame, generator frame에 대한 포인터를 기록해야 한다. 후자의 두 포인터는 항상 continuation frame보다 스택에서 뒤쪽에 있어야 한다. ADD _FAILURE _FRAME opcode는 현재 failure 및 generator frame 포인터와 ‘실패 시 이동할’ 지점을 기록하는 failure frame을 스택에 푸시하고, 스택의 failure frame 포인터를 새 failure frame으로 갱신하며 generator frame 포인터를 해제한다. REMOVE _FAILURE _FRAME은 스택에서 failure frame을 팝하고 이전 failure frame 및 generator frame 포인터를 복원한다. ADD _FAILURE _FRAME opcode 이후, 하지만 REMOVE _FAILURE _FRAME opcode 이전에 실패가 발생하면, failure frame은 즉시 스택에서 팝되고 이전 generator 및 failure frame 포인터가 복원되며, 실행은 rest 위치로 점프한다.
다른 구성 요소들, 특히 Icon의 every 구문 번역은 유사한 스택 연산을 대량으로 사용한다. 간결함을 위해, 이 논문에서는 각 언어 구성 요소의 번역을 자세히 다루지 않는다. 자세한 설명은 [4]를 보라.
ADD _FAILURE _FRAME과 REMOVE _FAILURE _FRAME opcode는 기존의 Icon 및 Icon 유사 구현들이 공유하지만 다른 언어들은 공유하지 않는 비효율성에 대한 중요한 통찰을 제공한다. 모든 논리적 코드 줄이 경계 지어진 식이고, 논리적 줄 안에도 추가적인 경계 지어진 식이 있을 수 있기 때문에, 실행되는 ADD _FAILURE _FRAME 및 REMOVE _FAILURE _FRAME 연산의 수는 많다. 전형적인 Converge 프로그램 실행에서 이들은 실행된 opcode의 약 25-30%를 차지한다. 비교적 실행 비용이 낮은 opcode이기는 하지만, 스택을 건드리는 모든 실행은 비용을 수반하며, 그 빈도가 워낙 높기 때문에 실행 시간의 적지 않은 부분이 여기에 쓰인다. Icon풍 평가 시스템에 특화된 스택 연산들이 Converge VM 전체 실행 시간에서 차지하는 누적 비율을 정확히 구하기는 어렵다. 일부는 다른 코드와 얽혀 있기 때문이다. 그러나 거친 추정으로도 최소 10%의 전체 실행 시간을 차지한다. Converge VM에서 이런 스택 연산은 몇 안 되는 비교적 잘 최적화된 코드 조각 가운데 하나라는 점에 주목하라. VM의 나머지 부분도 비슷하게 최적화된다면, 이들은 실행 시간의 훨씬 더 큰 비중을 차지할 것이다. 따라서 이런 opcode의 실행 횟수나 실행 시간을 줄일 수 있다면 성능에 눈에 띄는 영향을 줄 가능성이 크다 [7,9]. 따라서 Icon풍 VM이 스택 연산 수를 어떻게 줄일 수 있는지 고려할 가치가 있다.
failure frame 연산만을 고려하면, 간단한 사고 실험으로 몇몇 스택 기반 연산을 정적으로 제거할 수 있음을 알 수 있다. 예를 들어 식 x := 2는 결코 실패할 수 없다. 정수 생성은 원시 연산이기 때문이다. 따라서 이 식을 failure frame 연산으로 둘러쌀 필요가 없다. 그러나 Icon과 Converge 같은 언어의 매우 동적인 성격은 정적으로 수행할 수 있는 분석을 제한하며, 이 측면에서 얻을 수 있는 이득은 작을 가능성이 크다.
다행히 실제 실행 데이터는 Icon풍 VM이 이전에 생각했던 것만큼 본질적으로 스택 기반은 아니라는 점을 보여준다. failure frame이 스택에 푸시되는 이유는 그것들이 임의의 깊이까지 중첩될 수 있고, 최대 깊이를 정적으로 계산할 수 없기 때문이다. Converge VM의 관련 부분에 단순한 로깅 문장을 삽입하면, 실제 실행에서 그런 프레임이 얼마나 깊게 중첩되는지 볼 수 있다. 다음 수치는 convergec.cv 파일 위에서 Converge 컴파일러를 실행한 결과이다. 이 파일은 컴파일러의 일부이기도 하다. continuation frame의 약 44%는 어느 시점에서도 최대 1개의 중첩 failure frame만 가진다. 60%는 최대 2개의 failure frame을, 80%는 최대 3개의 failure frame을 가진다. 중첩 failure frame의 최대 수는 17인데, 이는 실행 중 단 한 번만 발생한다. 그 다음으로 높은 수는 13인데, 이것 역시 단 한 번만 발생한다. 최대 중첩 failure frame 수는 비정상적으로 높지만, 그 점을 제외하면 이 데이터는 일반적인 실행을 잘 대표한다. 이는 임의 깊이의 중첩 failure frame을 처리할 필요가 실제로는 비교적 드물다는 것을 보여준다. 실제로 전체 시간의 80%에서는 전역 실행 상태 안에 failure frame용 ‘슬롯’ 3개를 정적으로 예약하는 것이 실용적일 것이다. 새 함수가 호출되면, 이 슬롯들을 프로그램 카운터 같은 다른 데이터와 함께 스택에 푸시할 수 있다. 드물게 3개의 슬롯으로 충분하지 않은 경우에는 전통적인 스택 기반 프레임 방식으로 되돌아갈 수 있다. 이렇게 하면 비용이 큰 스택 연산을 크게 줄일 수 있다. 동일한 기법을 generator frame에도 적용할 수 있는데, 이들은 보통 훨씬 덜 깊게 중첩된다. 같은 실행 데이터는 continuation frame의 거의 99%가 최대 하나의 중첩 generator frame만 가진다는 것을 보여준다.
이 절에서는 나와 다른 사람들이 Converge의 Icon 유사 식 평가 시스템을 사용해 온 방식으로부터 얻은 경험을 정리한다. 그 성격상 이 절은 전혀 과학적이지 않다. 그러나 독자들에게 흥미로운 통찰을 제공할 수 있기를 바란다.
Icon에서 온 두 가지 기능은 Converge에서 특히 많이 사용된다. 가장 분명한 것은, Icon의 generator 개념이 가벼운 반복 메커니즘을 제공하면서 동시에 단순한 지연 평가 수단으로도 기능한다는 점이다.
두 번째 후보는 덜 분명하다. 그것은 if 구문에서의 실패 개념이다. 자주 사용되는 라이브러리들은 ‘이 함수가 성공하면 값을 이 변수에 대입하고 그 다음 xyz를 수행하라’는 관용구를 사용함으로써 향상된다. Converge는 이 관용구를 자주 활용하도록 발전해 왔으며, 이는 Converge의 dictionary, 다른 많은 언어에서는 hash table 또는 hash map이라 부른다, 에서 잘 드러난다. 대부분의 언어와 마찬가지로 dictionary 같은 컨테이너 항목은 특정 키와 연관된 값을 반환하는 get 함수를 가진다. 키가 존재하지 않으면 get은 예외를 발생시킨다.
호출자는 종종 키가 존재하는지 확인하고, 존재한다면 값을 얻고자 하며, 존재하지 않는다면 아무 동작도 하지 않기를 원한다. 이 문제에는 두 가지 주요 해결책이 있다. 첫째, 키를 찾지 못하면 get이 null을 반환하게 하는 것이다. 그러나 이렇게 하면 어떤 키가 null에 매핑된 경우와 아예 존재하지 않는 경우를 구별할 수 없다. 둘째, 키의 존재 여부를 검사하는 contains 함수를 두고, 존재한다면 get을 호출하는 것이다. 대부분의 언어에서 이 관용구는 대략 다음과 같이 표현된다:
a에 대한 이중 조회는 보기 흉할 뿐 아니라, 유지보수 사고를 기다리는 코드이며, 빡빡한 루프에서는 상당한 오버헤드가 될 수 있다. Python과 아마 다른 언어들에서도, Converge로 표현하면 다음과 같은 관용구를 흔히 볼 수 있다:
catch Exceptions::Key_Exception:
이 관용구는 키를 찾지 못했을 때 예외를 잡는 것이 두 번 조회하는 것보다 거의 항상 빠르다는 사실을 이용한다. 내 생각에 이 관용구는 원래 의도를 흐린다. 기대되는 ‘재난 복구’가 아니라 성능상의 이유로, 그리고 꽤 보기 불편한 방식으로, 예외를 사용하기 때문이다.
Converge에서는 contains와 get의 기능을 하나의 함수로 통합할 수 있다. 이 함수는 키를 찾으면 성공하고, 찾지 못하면 실패한다. Converge에서 find 함수는 다음과 같이 사용할 수 있다:
Converge에는 get도 있고 find도 있지만, contains는 없다는 점에 주목하라. contains는 find가 성공할 때 그 반환값을 무시하는 것과 동등하기 때문이다. get과 find라는 이름은, 무언가를 get하러 가면 가져오는 것이 기대되지만, 무언가를 find하려 할 때는 찾지 못할 수도 있다는 발상에서 붙여졌다. get / find 관용구는 Converge 라이브러리 전반에서 반복적으로 사용되며, 그 빈도와 일관성은 실질적인 성공으로 입증되었다.
Converge의 Icon풍 식 평가 시스템의 가장 큰 단점은, generator와 if 구문에서의 실패를 제외하면, 그것이 크게 사용되지 않았다는 점이다. 이는 언어에 추가 개념이 있고, 컴파일러가 더 복잡하며, VM이 더 느린데도, 사용자들이 그런 비용을 정당화하는 기능들을 좀처럼 사용하지 않는다는 뜻이다. 여기에는 몇 가지 가능한 이유가 있다. 아마 사용자들, 나 자신을 포함해서, 이 ‘전통적인’ 방식으로 생각하는 경향이 있어 새 기능을 잊어버리는 것일 수도 있다. 또 문제들이 자연스럽게 그런 식 평가 시스템에 가장 적합한 방식으로 분해되지 않는 것일 수도 있다. 그러나 나는 주된 이유를 Icon에서 유추할 수 있다고 생각한다. 문자열 스캐닝은 Icon 식 평가 시스템의 정교한 사용이 이루어지는 주요 영역이지만, 현대의 정규 표현식 라이브러리는 문자열 스캐닝의 대부분의 단순한 경우를 포괄하고, 형식적 파싱 도구는 가장 복잡한 경우를 포괄한다. 요컨대, 목표 지향 평가는 Icon의 전성기만큼 현대 언어에서 유용하지 않다.
이 논문에서는 Icon 프로그래밍 언어의 독특한 식 평가 시스템을 설명했다. 이어서 이 시스템의 몇 가지 사소한 결함을 자세히 설명하고, Converge 프로그래밍 언어가 유사한 식 평가 시스템을 포함하면서 일부 결함은 수정하고 일부는 안타깝게도 유지하고 있음을 보였다. 마지막으로 이러한 식 평가 시스템의 장점과 단점이 무엇인지에 대해 내 경험에 비추어 개괄했다.
언어 설계와 관련해 세 가지 마지막 질문이 남는다.
첫째, 현대의 동적 타입 OO 언어에서 Icon풍 식 평가 시스템을 실험해 볼 가치가 있었는가? 내 대답은 쉽게 ‘그렇다’이다. Ralph Griswold와의 인터뷰와 그의 글들, 예를 들어 [1,2]를 보면, Icon의 목표 중 하나는 기존 언어 설계의 몇 가지 상투적인 요소를 합친 또 하나의 따분한 언어가 되는 것이 아니라 새로운 것을 시도하는 것이었음이 분명하다. Icon은 그 점에서 완전히 성공했으며, 탐구할 가치가 있는 진정으로 흥미로운 언어이다.
둘째, 내가 또 다른 범용 프로그래밍 언어를 설계한다면, Icon풍 식 평가 시스템을 포함하는 실험을 반복할 것인가? 여기서 내 대답은 좀 더 미묘하다. 나는 확실히 generator는 포함할 것이다. 또한 if 구문에서 실패를 허용하는 방법을 포함하려고 매우 노력할 것이다. 그러나 목표 지향 평가와 관련된 기능의 대부분을 포함해, Icon의 나머지 기능 대부분은 포함하지 않을 것이다. 그로 인해 생기는 복잡성과 비효율은 일반 사용자에게 그만한 가치가 없기 때문이다.
셋째, 마지막으로, Icon의 식 평가 시스템이 들어갈 자리를 나는 전망하는가? Icon의 목표 지향 평가는 문자열 스캐닝에서 빛을 발한다. 그러나 Icon의 문자열 스캐닝이 여전히 많은 용도를 가지는지는 내게 분명하지 않다. 정규 표현식이 대부분의 단순한 사용을 포괄하고, 형식적 파싱 기법이 가장 복잡한 사용을 포괄하기 때문이다. 따라서 현대의 범용 언어가 Icon의 식 평가 시스템으로부터 큰 이익을 얻을지도 마찬가지로 불분명하다. 그러나 향후 유망한 연구 주제로는, 도메인 특화 언어, 도메인 특화 임베디드 언어 [6]를 포함한다, 가 유사한 기능을 어떻게 통합할 수 있는지 탐구하는 일이 있을 수 있다. 나는 그런 시스템이 Icon에 존재하는 것보다 더 강력한 백트래킹 기능을 필요로 하리라고 생각하지만, 그것이 궁극적인 설계를 위한 좋은 토대를 제공할 수도 있다.
이 논문에서 논의한 시스템을 직접 실험해 보고 싶은 이들을 위해, 오픈 소스이면서 이식 가능한 Icon (http://www.cs.arizona.edu/icon/)과 Converge (http://convergepl.org/) 버전이 자유롭게 제공된다.
[1]D. S.Cargo. Ralph and Madge Griswold와의 인터뷰, 1990년 7월.
[2]R. E. Griswold and M. T. Griswold. Icon 프로그래밍 언어의 역사. pages 599–624, 1996.
[3]R. E. Griswold and M. T. Griswold. The Icon Programming Language. Peer-to-Peer Communications, third edition, 1996.
[4]R. E. Griswold and M. T. Griswold. The Implementation of the Icon Programming Language. Peer-to-Peer Communications, third edition, 1996.
[5]R. E. Griswold, J. F. Poage, and I. P. Polonsky. The SNOBOL4 Programming Language. Prentice-Hall, second edition, 1971.
[6]P. Hudak. 도메인 특화 임베디드 언어 만들기. ACM Computing Surveys, 28(4), 1996년 12월.
[7]R. Ierusalimschy, L. H. de Figueiredo, and W. Celes.The implementation of Lua 5.0. Journal of Universal Computer Science, 11(7):1159–1176, 2005.
[8]N. Schemenauer, T. Peters, and M. L. Hetland. Simple generators. Python PEP 255, 2001년 6월.http://www.python.org/dev/peps/pep-0255/Accessed Sep 15 2008.
[9]Y. Shi, K. Casey, M. A. Ertl, and D. Gregg. Virtual machine showdown: Stack versus registers. Transactions on Architecture and Code Optimization, 4(4):1–36, 2008.
[10]L. Tratt. 동적 타입 OO 언어에서의 컴파일 시점 메타프로그래밍. In Proc. Dynamic Languages Symposium, pages 49–64, 2005년 10월.
[11]L. Tratt. The Converge programming language. Technical Report TR-05-01, Department of Computer Science, King’s College London, 2005.
[12]L. Tratt. MT에서의 모델 변환. Science of Computer Programming, 68(3):169–186, 2007년 10월.
[13]L. Tratt. 컴파일 시점 메타프로그래밍을 통한 도메인 특화 언어 구현. TOPLAS, 30(6):1–40,2008.
