VAP 노드 사용을 위한 Hugs의 공간 최적화 기법 성능 분석 = Analysing the Performance of the Space Optimization Techniques in Hugs to Investigate the Compatability for Using VAP Nodes

국문 초록 (Abstract)

Hugs는 지인 함수형 언어인 Haskell을 위한 인터프리터이다 Hugs는 추상 그래프 축약 기계인 G-machine을 사용한다. G-machine은 표현식을 힙메모리의 그래프에 표현하고 응용식의 루트를 나타내기 위해서 AP 노드를 사용한다.
AP 노드는 세 개의 필드로 구성된다. 하나는 AP 태그 노드를 나타내기 위해서 나머지 하나는 응용식의 함수부를 나타내고 마지막 하나는 응용부의 인수부를 나타낸다. AP 노드는 그 크기가 고정되어 있기 때문에 2개 이상의 인수를 갖는 응용식을 나타내기 위해서는 일부 공간 오버헤드를 갖는다. AP 노드 사용 시에 발생하는 오버헤드를 줄이기 위해서 Hugs에서는 세 가지 명령어 ROOT, UPDAP, RUPDAP를 제공한다.
본 논문에서는 좀 더 효율적인 메모리 사용을 위해서 VAP 노드의 사용을 제안한다. VAP 노드는 최초에 Johnsson에 의해서 제안되었고 이후 G-machine의 변종인 Spineless G-machine에서 사용되었다. 그러나 Hugs에서 VAP 노드를 채택할 경우 노드 구조의 변경으로 인해서 AP 노드 기반 G-machine에서 제공되고 있는 공간 최적화 기법들의 이점을 잃어버릴 수 있다. 그러므로 본 논문에서는 메모리와 Hugs 시스템에서 제공하는 세 가지 명령어의 효과를 분석한다 또한, 본 논문에서는 Hugs 시스템에서 제공하고 있는 명령어 중에서 VAP 노드를 사용하는 G-machine에서도 적용 가능한 최적화 기법을 제시한다.
VAP 노드를 사용하는 G-machine에서는 명령어 UPDAP를 구현하기가 매우 어렵다. 그러나 실험결과에 따르면 UPDAP가 실제 프로그램 수행에 미치는 영향은 매우 적다. 그러므로 Hugs에서 VAP 노드를 사용도록 개선해도 기존 공간 최적화 기법의 성능을 유지할 수 있을 것으로 예상된다.

다국어 초록 (Multilingual Abstract)

Hugs is an interpreter for Haskell that is a lazy functional language. Hugs is based on the G-machine, an abstract graph reduction machine. The G-machine represents an expression into a graph in the heap memory and uses an AP node to represent the root of an application.
An AP node is composed of three fields: the one field for the AP tag and the others for pointing to the functional part and the argument part of the application. Using AP nodes brings some space overheads especially for an application that has more than two arguments because the size of the AP node is fixed. Hugs offers three instructions, ROOT, UPDAP and RUPDAP, in order to reduce the space overhead due to the AP nodes.
This paper proposes the method for using VAP nodes. A VAP node was originally proposed by Johnsson and used in the Spineless G-machine, a variant of the G-machine. However, adopting the VAP nodes in Hugs may lose the benefits of the space optimization techniques based on the AP nodes. Therefore, this paper investigates the effect of the above three memory optimization instructions in Hugs. This paper also offers a portable optimization technique at the G-machine level for using VAP nodes.
In fact, the instruction UPDAP is hard to be implemented in the G-machine using VAP nodes. However, according to the experimental result, the instruction UPDAP has little effect on the program execution. Therefore, Hugs using VAP node is expected to keep the performance of the memory optimization instructions of the existing Hugs.

목차 (Table of Contents)

• 목차 = ⅲ
• Ⅰ. 서론 = 1
• Ⅱ. G-machine = 4
• 1. 개요 = 4
• 2. G-machine 입력언어 = 6
• 3. G-machine 컴파일 규칙 = 7
• 4. 상태변환 규칙 = 9
• 가. 그래프 노드 구조 = 11
• 나. 스택과 컨텍스트 = 12
• 다. 기존 G-machine에서의 그래프 축약과정 = 14
• Ⅲ. Hugs의 공간 최적화 기법 = 18
• 1. ROOT = 18
• 2. UPDAP와 RUPDAP = 20
• 가. UPDAP = 20
• 나. RUPDAP = 21
• Ⅳ. Hugs의 공간 최적화 기법 성능 분석 = 23
• Ⅴ. VAP 노드 적용 G-machine = 30
• 1. AP vs. VAP = 30
• 2. VAP 노드를 사용한 그래프 축약 = 33
• 3. VAP 노드 사용 G-machine에서의 최적화 기법 = 35
• Ⅵ. 결론 = 39
• 참고문헌 = 40
• ABSTRACT = 42